Sign in to follow this  

A star pathfinding speed

This topic is 2663 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I just finished implementing A star path finding in my XNA/C# RTS, and was curious what the speed would be in a commercial-grade path finding algo (like in SC, WC, CnC, AoE, etc)?
The only thing I'm not sure is how exactly you measure performance. At what point in the algo would you add one to the number of checked? I did it after a neighboring node is considered valid, but I'm wondering if I should count the ones that I still have to check for validity and fail? Counting only the valid tiles, my algo was checking roughly 1360 nodes in around 90 milliseconds.

I know the usual 'don't worry about it until it becomes an issue', but I'm just curious what a 'good' algo's speed is.

Share this post


Link to post
Share on other sites
I'm not sure but I think I have some info you'd like to know that makes it a moot point in most situations.

If you have your pathfinding happen all at once in a single frame, you are going to get a huge spike in that frame's frame time which is going to be really noticeable by the player and make the game not feel as responsive and nice.

Like you said, you have yours running at about 90 miliseconds. If your game is running at 30ms and you do a 90ms path find that frame, that means you drop from 30fps (~30ms) to about 8fps (~120ms) for that frame.

That's only assuming you do one path find per frame too and there will probably be times when you want to do a couple in the same frame, or really close together in frames.

The better approach is to set up your game loop such that A* is only allowed so many iterations per frame and make it so your A* algorithm can do work peicemeal so it can continue from where it left off the next frame.

What you do is make a queue of pathing requests where everything that wants a path evaluated puts a request into the queue along with the address of a callback function (and a void * user param so it can get that param back).

Then every frame, your path calculator does so many iterations of path finding and notifies code via the callbacks when the pathing is finished.

Hope this makes sense, this makes it so your pathfinding costs is spread out as thin as you want it so that performance really isn't an issue.

Of course, the fewer cycles per frame you give to path finding, the longer it takes for paths to finish so if it's too low of a number, your people may take to long to actually start walking.

Share this post


Link to post
Share on other sites
Yea I already have it set to only do a certain number of iterations per frame, but I set it to a high number just to see what kind of performance I'm getting and for testing.

Share this post


Link to post
Share on other sites
That certainly seems high, assuming your game has some concept of 'jump lanes' or something similar to set edges to your graph. Even without that seems high since you'd be able to sort/prune the pathfinding by raw distance pretty well.

Share this post


Link to post
Share on other sites
I checked my code again and was actually counting a node after I selected the lowest F cost node. I changed this to count all neighbors, regardless of whether they're passable. Counting this way I iterated through 9504 nodes in 81 milliseconds (basically 8x the number of nodes originally checked).

Right now I'm not doing any kind of pruning. I set up the map so that the only possible path from one side to the other is by zig zagging from top to bottom all the way across, and the walkable path is only 1 node wide.
Kinda like this:


_ _ _
| | | | | | |
| | | | | | |
| |_| |_| |_|


[Edited by - Zahlman on August 31, 2010 4:53:50 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by geo2004
I checked my code again and was actually counting a node after I selected the lowest F cost node. I changed this to count all neighbors, regardless of whether they're passable. Counting this way I iterated through 9504 nodes in 81 milliseconds (basically 8x the number of nodes originally checked).


This makes it in the order of 20-30k cycles per node. Theoretical lower bound making no assumptions about memory layout is ~200 cycles per. So it's on the order of 100 slower than typically viable. There is the obvious theoretical 1 cycle per, but that is hardly realistic.

Nothing much to worry about. At least that's the ballpark figures.

Share this post


Link to post
Share on other sites

This topic is 2663 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this