Pathfinding is expensive, so...

wfrost · 2005-01-30T20:53:29

Is the process of finding the path from A to B for an agent typically done in one call? If the path to be determined was riddled with obstructions, the pathfinding algorithm may require a significant amount of time. How is this issue handled in games today? I can think of two solutions: 1. The pathfinding procedure is parameterized with a timeout value that, once reached, will force the algorithm to return a partial path (producing a sort of 'iterative deepening' algorithmic behavior). This would allow the agent to immediately start moving towards it's destination and not sit there "thinking", waiting for a path to be determined. 2. Spawn a thread to find the complete path and force the agent to either sit and wait (and probably give the user an impression of a lack of intelligence) or send the agent towards its destination via a straight-line path and then adjust accordingly when the pathfinding algorithm completes. Maybe there are other solutions that I haven't thought of, but solution 1 seems to make the most sense to me. Solution 2 is probably very evil: if I sent 100 units to go to a location, 100 threads would be spawned which would be very bad. My Questions: a. Is there a scenario where solution 1 would not be sufficient? Or is there a better solution to this problem all together? b. Assuming you have a 'busy world' where possibly 100 units may be moving simultaneously, is solution 1 practical? c. How much time is too much time to spend on path finding, terms of CPU? 10%, 30%, 50%?

Artificial Intelligence Programming

Started by wfrost December 11, 2004 03:54 PM

27 comments, last by Timkin 20 years ago

napoleondynamite

188

January 27, 2005 05:42 PM

Wouldn't it work best for pathfinding to divide your map into smaller and smaller tiles? First you would pathfind on the largest level, and save that path. Then you would pathfind the next largest tile level, and save that path, etc. So if you had a map divided into 10x10 large tiles, it would first find the path to the goal large tile. Then you would find a path to the first tile to move to in a smaller grid inside the start tile, and unwind like that. It would also allow the whatever to end up in a dead end, so if you detected that, it would be faster and more realistic.

"Whatever I feel like, Gosh!"

Timkin

864

January 30, 2005 08:53 PM

Hehe...

It's not 'my' Distance Transform algorithm. In the thread referenced I do explain and provide an algorithm for the DTA, however I certainly didn't invent this algorithm.

Cheers,

Timkin

Pathfinding is expensive, so...

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Pathfinding is expensive, so...

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines