path lengths, not the paths
Alex, thanks for the reply and clarification.
I'm not sure we're discussing the same problem. My statement is that when you complete your AI into a full blown game AI, the main demand for paths is about path lengths, not the paths themselves.
Full blown bots will spend much of time (and code) in considering alternatives (should I take cover, attack, get a power-up, get the flag, camp here, join up with teammate x,y,z, etc.). Nearly every evaluations of such alternatives requires 'distance' information: is there any cover available with 2s distance, can I get to the threat quickly, is there any power-up nearby, who is the nearest teammate, etc.
In evaluating the alternatives, the exact path does not matter. Only when an alternative is chosen, the exact path is retrieved.
In other words, what the AI really needs is a (very) efficient way to estimate distances between his position and (almost) arbitrary locations on the map.
An AI design that is purely based on dynamic pathfinding (such as A*) will not be very efficient at these distance evaluations. Something closer to lookup tables and caches is required.
Your design sounds very interesting, and it's the first time I've seen concepts like plasticity being used. You also address the problem of optimizing a path towards multiple goals (TSP like).
But from what you describe, I cannot tell whether it is aimed at rapid pathfinding or rapid distance lookup, or both.
Do you have any numbers for "Firstly, it can return after any amount of time" (which I assume refers to the algorithm's ability to provide early results, rather than an absolute time).
For reference, on a PIII/500MHz, I could do over 5,000,000 distance lookup/s, whereas I could do solely ~1,700 A* path searches. (The earlier posted difference between A* and path lookup was incorrect, and should be a factor 2,000, not 200).
This factor 2000 is the difference between freely estimating distances everytime and everywhere it is needed in the AI (implementation), and on the other hand introducing complex caching and a resource manager (with queues to handle excessive requests posted in one frame) for A* path lookup.
Obviously, standard path lookup tables become cumbersome once you have over 1,500 waypoints/areas/cells/...
William
|