jmgq/php-a-star — pull request #1 by pathway (2014-10-12 19:58:23+00:00)
Title: Fixing parent loop

Using the example code to represent a graph. I made a graph that had separate links in both directions between each node. Simplest case had just 3 nodes, with links in both directions as shown:

startnode <==> node1 <==> goalnode

The search failed because after node1 was expanded, it followed the link back to the start node and set its parent, resulting in a parent loop.

node1 parent was set to start node
then, start node parent was set to node1

...resulting in a recursive data structure, so the solution could not ever be found (timeout).

I fixed it by adding to Algorithm.php line, 137