Substantial inefficiency and potential memory leak in AStar implementation. #9
Description
When using this implementation, I noticed that the AStar closed vector was getting insanely big, and the algorithm would often drop to a crawl.
I suspect two issues in AStar::getPath(). First:
35) childNode = static_cast<AStarNode*>(children.first);
36) g = currentNode->getG() + children.second; // stance from start + distance between the two nodes
37) if( (childNode->isOpen() || childNode->isClosed()) && childNode->getG() < g) // n' is already in opend or closed with a lower cost g(n')
38) continue; // consider next successor
should actually be:
35) childNode = static_cast<AStarNode*>(children.first);
36) g = currentNode->getG() + children.second; // stance from start + distance between the two nodes
37) if( (childNode->isOpen() || childNode->isClosed()) && childNode->getG() <= g) // n' is already in opend or closed with a lower cost g(n')
38) continue; // consider next successor
Changing the < g to <= g should have no impact on the overall length of the found path, but substantially reduces re-opened nodes (especially on equi-cost square-grid or hex-grid graphs). Furthermore, if a node a is accidentally added as a child of node b twice - which is quite easy to have happen, given that Node::addChild() doesn't check - changing to <= g will automatically cull that second child link, rather than duplicating work.
Secondly, I suspect that closed nodes are being duplicated when reopened:
47) if (childNode->isClosed())
48) childNode->setClosed(false);
49) if (!childNode->isOpen())
50) pushOpen(childNode);
I'm not 100% confident, and I think it simply doesn't matter, but it seems odd that the reopened node is never being removed from closed. I suspect this is just an inefficiency in the name of efficiency, as removing items from vectors is expensive and there's no particular need to. Nevertheless, it does cause the closed vector to grow enormous it some cases.