hi all,
well i dont know whether this is the right place to ask this question.......... but here goes,
i am working on a 3d FPS engine ..... me and my team has almost finished work on rendering and sound components...... and now i am working on the AI module ....... what i want to know is what is the method/technique used by Half life for pathfinding ......
i now that quakeIII uses the AAS, abt which there is very little info avilable and from wateva was available i have come to know that it is quite complex so it is not an option .......
i know that in UT the person making the map has to manually place the waypoints and then the engine makes paths for the bots ........ but what is the algo used(A* or sumthin like that??? ) used for generating paths ....
i hope that i have expressed myself clearly
any help will be appreciated greatly.
enygmyx.

Half-life uses manually placed waypoints. It also uses scripted behaviours to use these waypoints. I'm not actually sure if the squad tactics even needed A*... AI Game Programming Wisdom has an article by the same guy, Lars Liden, as well as two other applicable articles by Willian van der Sterren.

I also believe that they had the player drop bread crumbs for Barney the security guard to be able to follow you around.

So you probably don't need sophisticated techniques at all!

Half-Life uses several methods for movement:

1. Pathfinding using A* (only using shortest distance though) on manually placed Mapnodes (created with the Worldcraft Editor).
2. Direct Line Movement verified for non-obstruction through expensive ingame raycasts
3. If moving without Pathnodes and there's no direct line it tries to create a path around obstacles using Splines and several Raycasts/Hullchecks.

AFAIK, the Barneys use techniques 2 and 3 (when they aren't scripted to follow the premade Pathnodes. Squads don't really check for terrain properties or advantages when engaging but all monsters can pathfind to an occluded place if this behaviour is implemented.

Having worked with Unreal for several years now I think I can give you a pretty good run through of how it's navigation system works.

The basis is a simple pathnode network, generally manually placed (although there is a less than optimal path builder that will place nodes automatically). Reachability is determined between all nodes using the normal collision/physics system (place a guy at the node, try to walk him to every other node within max distance), and then used in-game when direct reachibility checks fail, using a simple breadth-depth search.

I've also experimented with using pathing volumes in Unreal with some fairly good results, similar in effect to a navigation mesh. Also I've found it helpful to allow designers to lay down routes and the precompute the searches on those routes to reduce the in-game penalty.