🎉 Celebrating 25 Years of GameDev.net! 🎉
Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
What data structures are good for Opened/Closed list sorting?
Years ago I helped a guy optimize his A* (good size regular grid (ie 512x512) with 4 and 8 cell adjacents)
He used a HeapQ for the open list and a symbolic map working grid for the closed list.
I vaguely recall putting him onto using pointer math directly for offset referencing of adjacents candidates (the working grid was always a power of 2 fixed size) and the HeapQ tree likewise could used pointer offsets.
One other speedup was from using the minimum data sizes required (easier when you use structures of fixed dimensions) to cram data together to fit into caches better. Smallest ints possible, bitflags etc...
Another speedup was using a boundry of Closed marked nodes around the edges of the map (so really the pathfinding was map of 2^n-2 size) but it eliminated the new open candidates edge testing logic.
For the closed list, I've seen people put an integer field on the tile itself. Each pathfinding attempt is given a number, and the tile is marked as closed when it is given that number. That way you never have a list of closed tiles, and never have to clear the tiles either, as the next pathfinding attempt uses a different number.
For the closed list, I've seen people put an integer field on the tile itself. Each pathfinding attempt is given a number, and the tile is marked as closed when it is given that number. That way you never have a list of closed tiles, and never have to clear the tiles either, as the next pathfinding attempt uses a different number.
Except when the integer wraps back to zero/one and you potentially can then hit nodes with your current attempt tag number giving a false 'closed' status.
Flags on the tile data can be done, but if you do simultaneous pathfindings on different cores, then each has to have its own working data set
For the closed list, I've seen people put an integer field on the tile itself. Each pathfinding attempt is given a number, and the tile is marked as closed when it is given that number. That way you never have a list of closed tiles, and never have to clear the tiles either, as the next pathfinding attempt uses a different number.
Except when the integer wraps back to zero/one and you potentially can then hit nodes with your current attempt tag number giving a false 'closed' status.
I've used and worried about this in the past, but even using a 32 bit number, and calculating even 1000 paths a second would still take ~50 days before you ran into this problem. and even if this is a serious problem you need to consider, once the number hits zero, you simple iterate over your map, reset all values to 0, and then increment your pathing number.
It is a sweet thing to have the optimizations. But I'll leave that till the end of my development. Just wondering if you guys could help me out with this.
TimeAStarPath* TimeAStar::findPath(TimeAStarNode* from, TimeAStarNode* to, Unit* unit, int depth)
{
TimeAStarNode* current = NULL;
bool solved = false;
open_list.clear();
closed_list.reset();
int maxOpenSize = 0; int maxCloseSize = 0; int reachedDepth = 0;
from->transition = NULL;
from->h = from->getActualTimelessCost(to);
from->g = 0;
// total score equals the initial heuristics
from->f = from->h;
from->depth = 0;
if (from != NULL && to != NULL) {
open_list.insert(from);
// find nodes in open list till it is exhausted
while (!open_list.empty()) {
current = open_list.top();
open_list.pop();
/*if (!open_list.erase(current)) {
assert(false);
}*/
closed_list.set(current->id);
// current.depth is set somewhere else
if (current->depth > reachedDepth) {
reachedDepth = current->depth;
if (reachedDepth == depth) {
solved = true;
break;
}
}
std::vector<TimeAStarTransition*> transitions = current->getTransitions();
for (std::vector::iterator it = transitions.begin(); it != transitions.end(); it++) {
TimeAStarTransition* transition = (*it);
float cost = transition->getCost(unit);
if (cost < 0)
continue;
TimeAStarNode* neighbour = transition->toNode();
if (closed_list.at(neighbour->id))
continue;
if (open_list.find(neighbour) != open_list.end())
{
if (current->g + cost < neighbour->g)
{
//if (! open_list.erase(neighbour))
// assert(false);
open_list.pop();
// sets the parent node of this neighbour to current
neighbour->transition = transition;
neighbour->g = current->g + cost;
neighbour->f = neighbour->g + neighbour->h;
neighbour->depth = current->depth + 1;
// if current node is better, change it to neighbour and push it
// into the open list, next iteration will pop this out if better into the closed list
open_list.push(neighbour);
}
} else {
// sets the parent node of this neighbour to current
neighbour->transition = transition;
neighbour->g = current->g + cost;
neighbour->h = neighbour->getActualTimelessCost(to);
neighbour->f = neighbour->g + neighbour->h;
neighbour->depth = current->depth + 1;
open_list.push(neighbour);
}
}
}If open_list is implemented as a std::set, it's okay to find that neighbour in a std::set Now I switch to a priority_queue. As Wodinoneeye mentioned, I could use pointer math, And other posters suggest there might be collisions in a long-run application. But I'd like to use a slower method first, just to make it work first, as I am not good at it 
How can I use the priority_queue to look up a specific element in the open_list for this code snippet As for the closed_list, I am using a bitset<1024>, just enough for now. Thanks Jack
(1) When you get a node to process from the open list, check if it is in the closed list, and in that case just skip it.
(2) Don't check if the neighbor is in the open list: Just blindly push it onto the open list and trust (1) to handle the situation.
That will probably just work.
Way Ive seen done (grid type map) :
If the way your Closed List works is to look up a flag corresponding to the grid map position (or some other flagged indexing scheme corresponding to the nodes) then as you pull your next 'best' candidate from the Open List (its top if its cost is sorted like on a heapQ or priorityQ) now you find and attempt to add that candidate's adjacents (8 or 4) to the Open List AFTER you do the trivial flag check each one to see if it is closed (or off the map) to ignore it -- (because the Sorted Insert into the heap/priorityQ ISNT trivial) then set the candidate as Closed (flag mark) and then you repeat.
An optimized Open List heapQ using pointer offsets to reorder the node contents of its tree can be done (I'd have to go find the code to see to what depth the fixed size HeapQ made use of -- the very worst just fell off the bottom ) but its insert was not trivial compared to the bit flagged Closed list test that was done.
