Substantial inefficiency and potential memory leak in AStar implementation.

[sniggyfigbat]

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.

[Sahnvour]

Again, if you're willing to put up a PR to fix these issues, don't hesitate. Just be sure that they don't break anything 🙂

[sniggyfigbat]

@Sahnvour since I'm currently finishing up my MSc thesis I can't dedicate time to it right now, but once I've hit the deadline on that I might well slap together a PR, since you're accepting them. No promises, but probably.