I am making a simple tile-based 2D game, which uses the A* ("A star") pathfinding algorithm. I've got all working right, but I have a performance problem with the search. Simply put, when I click an impassable tile, the algorithm apparently goes through the entire map to find a route to the impassable tile—even if I'm standing next to it.
How can I circumvent this? I guess I could reduce the pathfinding to the screen area, but maybe I am missing something obvious here?
Answer
Some ideas on avoiding searches that result in failed paths altogether:
Island ID
One of the cheapest ways to effectively finish A* searches faster is to do no searches at all. If the areas are truly impassible by all agents, flood fill each area with a unique Island ID on load (or in the pipeline). When pathfinding check if the Island ID of the origin of the path matches the Island ID of the destination. If they do not match there is no point doing the search - the two points are on distinct, unconnected islands. This only helps if there are truly impassable nodes for all agents.
Limit upper bound
I limit the upper bound of the maximum number of nodes that can be searched. This helps impassable searches from running forever, but it does mean some passable searches that are very long can be lost. This number needs to be tuned, and it doesn't really solve the problem, but it mitigates the costs associated with long searches.
If what you are finding is that it is taking too long then the following techniques are useful:
Make it Asynchronous & Limit Iterations
Let the search run in a separate thread or a bit each frame so the game doesn't stall out waiting for the search. Display animation of character scratching head or stamping feet, or whatever is appropriate while waiting for the search to end. To do this effectively, I would keep the State of the search as a separate object and allow for multiple states to exist. When a path is requested, grab a free state object and add it to the queue of active state objects. In your pathfinding update, pull the active item off the front of the queue and run A* until it either A. completes or B. some limit of iterations is run. If complete, put the state object back into the list of free state objects. If it hasn't completed, put it at the end of the 'active searches' and move onto the next one. This has the benefit of preventing long searches for agents, such as those that are impassible, from blocking shorter, passable searches for other agents.
Choose the Right Data Structures
Make sure you use the right data structures. Here's how my StateObject works. All of my nodes are pre-allocated to a finite number - say 1024 or 2048 - for performance reasons. I use a node pool that speeds up the allocation of nodes and it also allows me to store indices instead of pointers in my data structures which are u16s (or u8 if I have a 255 max nodes, which I do on some games). For my pathfinding I use a priority queue for the open list, storing pointers to Node objects. It is implemented as a binary heap, and I sort the floating point values as integers since they are always positive and my platform has slow floating point compares. I use a hashtable for my closed map to keep track of the nodes I have visited. It stores NodeIDs, not Nodes, to save on cache sizes. The hashtable is a linear probe table and has the same size as the nodepool, and is allocated only once, when the StateObject is created.
Cache What You Can
When you first visit a node and calculate the distance to the destination, cache that in the node stored in the State Object. If you revisit the node use the cached result instead of calculating it again. In my case it helps not having to do a square root on revisited nodes. You may find there are other values you can precalculate and cache.
Further areas you could investigate: use two-way pathfinding to search from either end. I have not done this but as others have noted this might help, but is not without it's caveats. The other thing on my list to try is hierarchical pathfinding, or clustering path finding. There is an interesting description in the HavokAI documentation Here describing their clustering concept, which is different than the HPA* implementations described here.
Good luck, and let us know what you find.
No comments:
Post a Comment