Ok, I''m currently involved in a game project for academic credit. The group I''m working with is requesting that I code a realtime A* path finding algorithim. I''ve come to the conclution that A* is simply too slow for this purpose, and was wondering if anyone out there has suggestions and/or counter arguments. The ai in question has to drive a vehicle over a dynamic terain system. The AI controls said vehicle through action flags.

Do you have to drive the vehicle over the best possible path or just make it through? A* will only really work well in a more stable system where the map is known. If you are being presented with a dynamic terain, it is more of a reactive thing than a planned thing. A simpler A* looking just ahead of you combined with perhaps a steering algorithm may work.

Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"

It would be possible to help you find a suitable solution to your problem if we had more details of the problem specifics. Can you give a better description of what you want the AI to be able to do? What factors will influence the decisions made by the AI? Do you want the AI to be ''human-like'', in that it can make incorrect decisions? Will the AI have to deal with uncertain knowledge regarding the environment (car/terrain)?

These are the sorts of questions you need to ask yourself and answer before you can choose an appropriate AI tool (or tools) for your game. If you can answer some/any/all of these questions, we can certainly help you find an appropriate solution to your problem.

Cheers,

Timkin

How slow is too slow. A customized A* implementation, with some knoweldege of how the data is arranged as well as a hierachial representation scheme of the data, can find paths through complex terrain over large scale reasaonly fast. Here is a paper :

http://www.d.kth.se/~f93-maj/pathfinder/

Good Luck.

-ddn

In response to a request for more info, I would like the aI to behave as follows. The AI should avoid drastice differnces in terrain, such as a ravine or cliff while patroling between two predetermined points. In terms of pathfinding, the AI can make a grand total of 4 actions, accelerate, brake, turn left, and turn right. The system must manage between 2-25 "bots" total, updating a certain number of them each frame. As for what I"m currently using, and how slow is too slow, I'm currently using a local space test, and to give you and idea, the test program's frame rate dropped for 120fps running 10 bots without A* to 9fps runnig 1 bot with A*.

[edited by - Slegato on September 11, 2003 1:27:35 PM]

[edited by - Slegato on September 11, 2003 3:04:28 PM]

This article seemed cool at the time:

http://www.gamedev.net/reference/articles/article1988.asp

Since A* is the defacto pathing algorihtim for most games, I''m surprised there is such a large hit for your application. I know from my tests and observing most RTS, can find paths on data sets of around 1000-500 nodes in 1-2ms. Essentially realtime for hundred of units. Ofcoruse they have their own built in scheduler and queue up the path request so the game doesnt spend too much CPU on AI.

Perhaps your data sets are order of magnnitudes larger, which could explain the performance drop. As a previous poster has suggest, combing a reactive AI and A*, would proably be your best bet. You will need to write a scheduler for the AIs, so each one gets some time to find their paths, and perhaps you could precompute a path solution using this approach :

http://www.gamedev.net/reference/articles/article1939.asp

Well Good Luck!

-ddn

Ok, Most of the problems have been resolved, mainly because of some redesignes of what''s happening, and the suggestions from all the posters has been a great help. Thank you all.