Sign in to follow this  

A* question

This topic is 3772 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 noticed after putting in my A* in my RTS, if I move, say 10+ units in one frame, all the way across my map, there is a slight delay (half a sec or less). I know one way to overcome this is by using a queue of some sort, and having them find paths in different frames. But I got to wondering. My current map is small, only 30*30 nodes. In a game like Warcraft III, I imagine some of those large maps may be upwards of 400-600 square, and you almost never notice delays in pathfinding (I suppose partly due to hiding them in character animations). My question is, how many units per frame SHOULD you be able to move (and how many nodes), without noticing a delay of any kind? 10 units and 300 nodes? 20/300? 5/300, etc...? I know that the number of obstacles in the way present a bigger cpu hit, and not doing any kind of quadtree/hierarchial technique will also do this, but lets assume the map has nodes all of the same size. Jeff

Share this post


Link to post
Share on other sites
Usually we cap it to somewhere between 10-20 units per frame.

Use a profiling tool to find out where your app is getting bogged down & optimize from there.

The big games also use techniques like "hierarchical pathfinding" to limit pathfinding costs.

Are you trying to do dynamic avoidance or anything "crazy" like that inside your pathfinding search, rather than as a component of pathfollowing?

-me

Share this post


Link to post
Share on other sites
Depends. First, when units are moved in a group (as in Warcraft 3), there's no reason to do a pathfinding operation for each—find a path for the group, and fit the units by altering the compactness.

Second, there is no reason to compute an entire path in a single go. A simple optimization would be to use a simpler precomputed graph of a few regions (let's say a hundred), and find out what node you should move towards next by using either a lookup table or an A* on the graph. Then, plot a path along the actual map from the current position to the next node, and start following that path—you'll just have to refine the path when you'll have the computing power available, and the path will be complete a few frames later.

Third, there is no reason to compute a perfectly accurate path either. Following up on the previous "lightweight graph" example, you would determine which node you are closest to and, based on that node, the path to be taken on the detailed graph to reach the destination—only you restrict your path to the current node and its neighbours (so you don't have to compute a lot). Then, you'd recompute a short path whenever the "closest node" changes.

Lastly, there's no reason to use pathfinding from the start either. If you're really lacking computation power (too many units), you can use a simpler movement scheme for units not on the screen by simply throwing them in the direction of their destination (either in a straight line, or using a lookup table and the aforementioned lightweight graph), and only reverting to smart pathfinding when they hit an obstacle.

Share this post


Link to post
Share on other sites
Thanks for the replies so far.

Palidine:
I am currently only moving the units according the the static map (avoiding constant obstacles like trees). Adding unit to unit collision response is on the To Do List.
Where can I find a good, free, profiler (if one exists). I'm using OGL and VC++ 2005 Express.

ToohrVyK:
You have very good suggestions.
I considered moving Units as a group. Maybe I need to look into that.
Using a precomputed graph seems like a great idea. I'll search the boards and Google and see if I can find ways to implement one.
I will probably end up doing what you suggest and only pathfind after a unit hits an obstacle. I am doing it the brute force way now for testing, and optimization purposes in hope to make it as efficient as possible (naturally).

One other thing I thought about was my use of floats. I am using floats for coordinates, but after I thought about it, this seems excessive. I'm using Ortho view when selecting/moving objects, so integers will be fine, as each pixel would be 1 int...right? Could using floats be one problem, as I'm computing more complex numbers than I need to be?

Thanks again,
Jeff

Share this post


Link to post
Share on other sites
Quote:
Original post by geo2004
One other thing I thought about was my use of floats. I am using floats for coordinates, but after I thought about it, this seems excessive. I'm using Ortho view when selecting/moving objects, so integers will be fine, as each pixel would be 1 int...right? Could using floats be one problem, as I'm computing more complex numbers than I need to be?


I am 99.99% certain that the format you are using for your computations is not the cause for any observed slowdown.

Share this post


Link to post
Share on other sites
Quote:
I am 99.99% certain that the format you are using for your computations is not the cause for any observed slowdown.

Ok, thanks. I downloaded AMD Code Analyst and I'm gonna give it a whirl and see what results I get.

Jeff

[Edited by - geo2004 on August 15, 2007 2:48:15 PM]

Share this post


Link to post
Share on other sites

This topic is 3772 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