Sign in to follow this  
Shlaklava

A* Optimize

Recommended Posts

Palidine    1315
Use a profiler (like VTune) and find out why it's slow. Then fix it.

Profilers basically timestamp the inclusive/exclusive cost of your whole function tree. You use them to identify the bottlenecks.

When optimizing:

1) can you call the A* search less times? Create a manager to allow only 1-5 NPCs to pathfind per frame, etc

2) Find a better algorithm to get around hotspots identified by the profiler
3) reprofile
4) goto 1 until there's nothing left to do

5) hand optimize the bottleneck functions: assembly, code analysis, reduce cache misses, etc
6) re-profile
7) goto 4 until you're "done"

-me

Share this post


Link to post
Share on other sites
Ralph Trickey    230
Write out the nodes it's checking in order, and take a look at them, and make sure that your algorithm is closing on the solution quickly, instead of slowly.

I'd also take a look at things like search depth first. Keep track of what the maximum search depth is, and how long it takes to run A*.

What language are you using?


Share this post


Link to post
Share on other sites
Shlaklava    145
I am using C++.

It seems that the application (the sample one) that simulates a 50x50 map with 5 NPCs is taking most of the cpu processing time from my whole system (the computer itself).

The slowest part of the whole thing was the memory allocation/deallocation for the open list and (rarely) closed list if I need room.

Share this post


Link to post
Share on other sites
Vorpy    869
Are you measuring its speed in any way other than seeing that it is using all of the system's free processing time? Any infinite loop would do that.

Share this post


Link to post
Share on other sites
strtok    191
It sounds like your map is a grid, and if so, you can remove the allocation time by pre-allocating the open/closed lists. In my implementation, I actually have a grid that is the same size as the map, where each cell contains all of the A* algorithm info needed for that cell (a bool for whether it is in the open list, a bool for the closed list, actual cost to node, guessed remaining cost, etc.). To start a fresh run of the algorithm, I can simply memset the entire thing to zero, with no allocations needed (except for the priority queue used to check the next open node to visit, of course). This sped things up quite a bit for me.

Share this post


Link to post
Share on other sites
starstriker1    245
http://www.gamedev.net/reference/articles/article1139.asp

I found that article to be pretty helpful when it comes to optimizing things... a lot of it is common sense, but it gives a good check list of things to look at and some things that could be easily overlooked.

Share this post


Link to post
Share on other sites
Ahnfelt    176
If you need generic allocation, use std::vector. It doubles (or similar) it's buffers every time they run full, yielding sub-linear allocation time (amortized).

Share this post


Link to post
Share on other sites
Palidine    1315
For an A* node list you should have a custom memory allocator. new/delete are expensive calls for something like this which gets called constantly. Take a high watermark of node usage and allocate enough memory one single time for that many nodes times 1.2 or 1.5. You'll probably have to research around a bit for how to make the manager give out nodes, manage unused nodes, etc. But basically it just hands out pointers to unused nodes.

With a well designed memory manager you can completely remove node allocation from the list of significant time hogs.

-me

Share this post


Link to post
Share on other sites
Shlaklava    145
Thanks for all of your help, I got it working faster then I wanted. Thanks for all of the replies.

And I changed it so I was not running every A* every game frame, which did help (forgot about that origionally).

Share this post


Link to post
Share on other sites
BrianL    530
If you have a 50x50 grid, your search space will contain at most 2500 nodes. You can preallocate this and index into the list. Constantly time lookups can be quite fast. ;)

Share this post


Link to post
Share on other sites

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