I have a question. Me and some friends are making a FPS. We are using WorldCraft as level editor and our own-written 3d-engine in D3D. Hmm.. here''s the problem. I''m supposed to write the AI code, and I have some problems with the PathFinding stuff. Not that It is that hard to write, but I just wonder what technique that is most common to use in FPS games. Is it common to use a designed Navigation mesh or is the best thing to do it with a A* search on a square-system? Please, help me. I don''t really know. The game are supposed to be quite flat.. Thx // Petter N, Class 69

I think this was already said today, so be sure to read the other threads. But search algorithms such as A* are not limited to squares or anything like that. It just happens that these algorithms optimise well when applied to grid-based maps, and that such maps were probably used in the first applications of A* to games. It is equally at home with any graph structure, such as a navigation mesh as you call it. If you research what the A* algorithm really is, you will see this for yourself.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files ]

I know what A* really is!!

That''s not the question. I just want to know what the best way to do the search on. (squares, triangles, etc.) And how they do in common, commersial games..

Then try asking clearer questions! You implied that you thought A* only worked on squares. In professional games I''ve never seen them divide something into squares that wasn''t already in squares for some reason. I don''t see the point. The nodes in your search could be the middle of each walkable polygon, or perhaps the midpoint of the edges between 2 walkable polygons. I''ve seen both ways described here.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files ]

Well, thanks then

If your 3D Engine uses portals, you could use each portal as a node in your search tree (you could also use that for a quick&easy line of sight thing, i.e. the bot can only see adjacent portals).

Then it''s a simple case of using a heuristic search (such as A*), and you''re away...

Well. Im quite sure you will already know what I am about to say, but regardless - heres what I would do:

Have preset nodes / connections within the map which mark major or preferred paths. For most navigation, try get the bot to work its way close to a preferred path.

Then have the map pre-calculated into sectors and portals - make use of these for the more localised tactical movements, and possibly ''intelligent'' movements such as ambushes.

The preferred path is more so for ease of debugging and use. The bot tries to stay close to it, but uses the more complex information only for localised movements.

--

If you have special doors, or areas of the map which could have connections opening and closing, these can be specified as exception cases as part of our preset nodes and connections. Hopefully this way, the exception cases (like a door that only opens every 20 seconds) should not find their way into buggering around your movement code which uses the more complex scene information such as portals / sectors.

If you would like to get into more serious tactical AI, you should buy a copy of AI Game Programming Wisdom (www.aiwisdom.com). It has some really well-written articles related to team based movements - that will give your FPS bots a lot more realism.



regards,

GeniX

www.cryo-genix.net

Just remembered..
.
Click me for a masters thesis on the Quake 3 AI. It''s a pretty good paper, and should help you quite abit )especiall with teh Area Awarenss System, which is used for tactical decision, such as cover etc)

Thanks for your help.

I already own a copy of AI Game Programming Wisdom.. thx anyway..

Thanks for your help.

I already own a copy of AI Game Programming Wisdom.. thx anyway..