A* Optimize
Author
I have finished testing my A* pathfinding sample to find out one thing...it's that it is super slow. How can I optimize the method?
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
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
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?
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?
Author
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.
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.
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.
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.
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.
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.
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).
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
With a well designed memory manager you can completely remove node allocation from the list of significant time hogs.
-me
50x50 A* for 5 agents should be an insignificant cost. Are you running A* every frame for them or something?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
