Infinite cycle error in A* like pathfinding

Unity Engine
1 
 public List<Node> FindPathBetween(Transform startHex, Transform targetHex)
    {
        if (!isNodeWalkable(targetHex.gameObject.GetComponent<Hexagon>()))
        {
            Debug.Log("The hex you want to move on in unwalkable for you");
            return null;
        }

        nodesToEvaluate = new List<Node>();
        evaluatedNodes = new List<Node>();

        Node myNode = startHex.gameObject.GetComponent<Node>();
        Node targetNode = targetHex.gameObject.GetComponent<Node>();

        nodesToEvaluate.Add(myNode);    

        for (int i = 0; i < nodesToEvaluate.Count; i++) //The error is that this cycle is infinite (i suppose this because when unity crushes, usually is a infinite cycle)
        {
            Node evaluatingNode = FindNodeWithLowestFCost(startHex.position, targetHex.position);

            //remove evaluating node from nodesToEvaluate and add it to evaluatedNodes
            for (int j = 0; j < nodesToEvaluate.Count; j++)
            {
                if (evaluatingNode.gameObject.name == nodesToEvaluate[i].gameObject.name)
                {
                    nodesToEvaluate.RemoveAt(i);
                    evaluatedNodes.Add(evaluatingNode);
                    break;
                }
            }

            if (evaluatingNode.gameObject.name == targetHex.gameObject.name)
            {
                //you found a path            
                List<Node> path = new List<Node>();

                path.Add(evaluatingNode);

                Node nodeOfThePath = evaluatingNode;
                while (nodeOfThePath.parent != null)
                {
                    nodeOfThePath = nodeOfThePath.parent;
                    path.Add(nodeOfThePath);
                }

                path.Reverse();
                actualPath = path;
              
                return path;
            }
            else
            {
                //foreach hexagon near this
                foreach (var hex in evaluatingNode.gameObject.GetComponent<Hexagon>().hexagonsAroundThis)
                {
                    if (hex.Value != null)
                    {
                        bool isWalkable = isNodeWalkable(hex.Value);
                        bool isEvaluated = isNodeEvaluated(hex.Value.gameObject);

                        //Debug.Log(hex.Value.gameObject.name + "isWalkable: " + isWalkable + ", isEvaluated: " + isEvaluated);
                        if (isWalkable || isEvaluated) //continue only if the node is walkable not evaluated
                        {
                            bool isToEvaluate = isNodeToEvaluate(hex.Value.gameObject);

                            float newCostToNeighbour = evaluatingNode.gCost + Vector3.Distance(evaluatingNode.transform.position, hex.Value.transform.position);

                       
                            if (!isToEvaluate || newCostToNeighbour < hex.Value.gameObject.GetComponent<Node>().gCost) //|| is shorter path
                            {
                                Node node = hex.Value.gameObject.GetComponent<Node>();

                                node.gCost = newCostToNeighbour;
                                node.parent = evaluatingNode;

                                if (!isToEvaluate)
                                {
                                    node.InitializeNode(startHex, targetHex);
                                    nodesToEvaluate.Add(node);
                                }
                            }
                        }
                    }
                }
            }
        }

        Debug.Log("path not found");
        return null;
    }
2

Looks like you have a bug in your AStar implementation. You might want to go back to wherever you are implementing this from, or perhaps try it on a trivially small graph so you can easily debug your issue.

To help gain more insight into your problem, I recommend liberally sprinkling Debug.Log() statements through your code to display information in realtime.

Doing this should help you answer these types of questions:

  • is this code even running? which parts are running? how often does it run?
  • what are the values of the variables involved? Are they initialized?

Knowing this information will help you reason about the behavior you are seeing.

How to report your problem productively in the Unity3D forums:

http://plbm.com/?p=220

3

I think you are missing an else condition at 70. I’m not at a computer right now. My A* alg seems similar, but for grid movement in 4 directions.
https://discussions.unity.com/t/774085/3

4

CAUTION: I see your line 24 and line 32 use the GameObject’s name to determine logical decisions in the AStar algorithm that are traditionally done by something guaranteed to be different on every node.

Are you guaranteeing that every GameObject’s name is unique? That’s an important contract to how AStar works.