A* Pathfinding implementation error

Archived Forums Questions & Answers
1

Hi, all. First note: If you spend the time to read this Question, you have my respect. If you take the time to locate the error, you rock.

So, after about 20 hours of research and four failed attempts, I managed to produce the below script:

using UnityEngine;
using System.Collections;

public class SmartMove : MonoBehaviour {

    public Transform[] CalculatePath(Transform startingNode, Transform destinationNode) {
        Node startNode = startingNode.GetComponent<Node>();
        Node endNode = destinationNode.GetComponent<Node>();

        startNode.G = 0;
        startNode.H = EuclideanHeuristic(startingNode, destinationNode);
        startNode.F = startNode.H;

        Hashtable openList = new Hashtable();
        Hashtable closedList = new Hashtable();

        openList.Add("startNode", startingNode);
        string currentNodeString;
        while(1 > 0) {

            currentNodeString = ReturnLowestF(openList);
            SwitchList(currentNodeString, openList, closedList);
            Transform currentNodeObject = (Transform)closedList[currentNodeString];
            Node currentNode = currentNodeObject.GetComponent<Node>();
            Transform[] children = currentNode.children;

            foreach(Transform child in children) {
                if(child!=null) {
                    Node childNode = child.GetComponent<Node>();
                    if(childNode.isWalkable && !closedList.ContainsValue(child)) {
                        if(!openList.ContainsValue(child)) {
                            openList.Add((Random.value*Random.value + Time.deltaTime).ToString(), child);
                            childNode.G = currentNode.G+childNode.movementCost;
                            childNode.H = EuclideanHeuristic(child, destinationNode);
                            childNode.F = childNode.G + childNode.H;
                            childNode.parent = currentNodeObject;
                        }

                        if(openList.ContainsValue(child)) {
                            float tempG = currentNode.G + childNode.movementCost;
                            if(tempG < currentNode.G) {
                                childNode.parent = currentNodeObject;
                                childNode.G = currentNode.G + childNode.movementCost;
                                childNode.F = childNode.G + childNode.H;
                            }
                        }
                    }
                }
            }

            if(closedList.ContainsValue(destinationNode))
                break;

            if (openList.Count == 0)
                break;
        }

        Hashtable pathNodes = new Hashtable();

        Node currentPathNode = endNode;
        int i = 0;
        while(1>0) {
            if (currentPathNode.parent==null)
                break;

            pathNodes.Add(i, currentPathNode.GetComponent<Transform>());
            currentPathNode = currentPathNode.parent.GetComponent<Node>();

            i++;
        }

        Transform[] path = new Transform[pathNodes.Count];
        pathNodes.Values.CopyTo(path, 0);

        return path;
    }

    string ReturnLowestF(Hashtable list) {
        float lowestF = Mathf.Pow(10,100);
        string lowestKey = "ah";
        foreach(DictionaryEntry currentEntry in list) {
            Transform currentEntryObject = (Transform)list[currentEntry.Key];
            float currentF = currentEntryObject.GetComponent<Node>().F;

            if (lowestF == 0)
                lowestF = currentF;

            if (currentF < lowestF && lowestF != 0) {
                lowestF = currentF;
                lowestKey = (string)currentEntry.Key;
            }
        }
        return lowestKey;
    }

    bool CheckAgainstList(Hashtable list, Transform searchItem) {
        bool isOnList = false;
        foreach(DictionaryEntry currentEntry in list) {
            if((Transform)list[currentEntry.Key]==searchItem) {
                isOnList = true;
            }
        }
        return isOnList;
    }

    void RemoveFromList(Hashtable list, string key) {
        list.Remove(key);
    }

    void SwitchList(string key, Hashtable listToRemoveFrom, Hashtable listToAddTo) {
        listToAddTo.Add(key, listToRemoveFrom[key]);
        listToRemoveFrom.Remove(key);
    }

    float EuclideanHeuristic(Transform start, Transform end) {
        float distance = Mathf.Sqrt(Mathf.Pow((start.transform.position.x - end.transform.position.x),2)
            + Mathf.Pow((start.transform.position.z - end.transform.position.z),2));
        return distance;
    }
}

The function is called from this script:

public SmartMove smartMove;
    public Transform pathEndNode;
    public Transform pathStartNode;

    public Transform[] path;

    void Update () {
        if(Input.GetButtonDown("Fire1")) {
            Ray ray = Camera.main.ScreenPointToRay (Input.mousePosition);
            RaycastHit hit;
            if (Physics.Raycast (ray, out hit)) {
                pathStartNode = hit.collider.transform;
                path = new Transform[0];
            }
        }

        if(Input.GetButtonUp("Fire1")) {
            Ray ray = Camera.main.ScreenPointToRay (Input.mousePosition);
            RaycastHit hit;
            if (Physics.Raycast (ray, out hit)) {
                pathEndNode = hit.collider.transform;
                path = smartMove.CalculatePath(pathStartNode, pathEndNode);
            }
        }
    }

Now, when I run my program, everything works fine. The first time I calculate a path (click, drag, release) it calculates fine and I get my path. The second time, however, Unity crashes. I've spent so long on this script, I feel like I just need somebody else to scan it really quick and point out the error. It's unoptimized, messy, and uncommented, so if you don't feel like reading it that's fine. If you do, though, you'll have my eternal gratitude.

Thanks a lot, Elliot Bonneville

Just skimming through your code at a glance you don't seem to be using any state data in your search - which is good - since it only operates on the parameters passed in. So that rules out any corrupt state. Actually the only time the code is called is when you release Fire1, and presequently you've set the parameters correctly. However, I am thinking what would happen if you would hit some collider that isn't in the node list? I'll take a deeper look unless I feel too tired shortly.

 –

I have checked some of the code you posted. There is one line that bug me a bit, but maybe this is intended and I am too sleepy. childNode.F = childNode.G + childNode.H; Since you're changing the F, wouldn't ReturnLowestF return some other result if you run the code with the same input twice? Also, (Random.value * Random.value + Time.deltaTime).ToString() is a very poor key string. If Random.value happens to become 0, then the other random cancels out and you risk getting the same key twice. Just use a number you increment.

 –

It also seems your Node script declare parent which makes it hard figuring out if you're trying to access the parent of the node or the parent of the transform. Finally, you have a loop where the condition to break it is if (currentPathNode.parent == null) break; - and it only seems you set parent, never clear them out between calls. So eventually you'll end up with every node having a parent node and you'll get stuck in the loop.

 –

Oh, that makes sense. Thanks for pointing that out, I'll figure out how to handle it. Maybe going through every node on the closed list and setting their parent to null would do the trick.

 –

I would also recomment to use your Node script instead of the transform. If the Node script would cache his own position in a public Vector3 you would not need a single GetComponent. Always keep in mind that the .transform shortcut also uses GetComponent behind the scenes. I guess your children (neighbours) variable is an array of Transforms? I just looked over it but can't see something else "wrong". Since the error happens when you use it a second time i guess Statement is right. It must have something to do with the data-changes.

 –

3 Answers

3
2

Does it crash on the second click down, second drag, or second release? Can you tell if it's hung up? (while (1 > 0), that's cute. I been using boring ole while (true) )

It crashes on second release, which is when my function is called for the second time.

 –
3

Here are some assorted thoughts in comments that I wrote down while I was looking through your code.

using UnityEngine;
using System.Collections;

public class x : MonoBehaviour
{
    public Transform[] CalculatePath(Transform startingNode, Transform destinationNode)
    {
        Node startNode = startingNode.GetComponent<Node>();
        Node endNode = destinationNode.GetComponent<Node>();

        startNode.G = 0;
        startNode.H = EuclideanHeuristic(startingNode, destinationNode);
        startNode.F = startNode.H;

        // string/transform "dictionaries"
        Hashtable openList = new Hashtable();
        Hashtable closedList = new Hashtable();

        openList.Add("startNode", startingNode);

        string currentNodeString;
        while (1 > 0)
        {
            // Find the lowest f cost key and switch it from open to closed
            currentNodeString = ReturnLowestF(openList);
            SwitchList(currentNodeString, openList, closedList);

            // Get that transform & node from closed 
            Transform currentNodeObject = (Transform)closedList[currentNodeString];
            Node currentNode = currentNodeObject.GetComponent<Node>();

            // For each child of the lowest f node
            Transform[] children = currentNode.children;
            foreach (Transform child in children)
            {
                if (child != null) // seems redundant enough
                {
                    Node childNode = child.GetComponent<Node>();

                    // If we can walk on it and it's not examined before
                    if (childNode.isWalkable && !closedList.ContainsValue(child))
                    {
                        // and if it is not added to the open list
                        if (!openList.ContainsValue(child))
                        {
                            // add it to the open list and calculate costs for it with a quite random key. 

                            // NOTE: If either Random.value is 0, then it's using Time.deltaTime which is - bad.
                            //       Possible duplicate key entry!!!
                            openList.Add((Random.value * Random.value + Time.deltaTime).ToString(), child);

                            // NOTE: These values are overwritten so next time it runs, 
                            //       ReturnLowestF might return some else (state changer)!
                            childNode.G = currentNode.G + childNode.movementCost;
                            childNode.H = EuclideanHeuristic(child, destinationNode);
                            childNode.F = childNode.G + childNode.H;

                            // Then parent it to the node? 
                            childNode.parent = currentNodeObject;
                        }

                        // At this point openList will contain value child 
                        // so it is pointless to check for it!
                        if (openList.ContainsValue(child))
                        {
                            float tempG = currentNode.G + childNode.movementCost;
                            if (tempG < currentNode.G)
                            {
                                childNode.parent = currentNodeObject;
                                childNode.G = currentNode.G + childNode.movementCost;
                                childNode.F = childNode.G + childNode.H;
                            }
                        }
                    }
                }
            }

            if (closedList.ContainsValue(destinationNode))
                break;

            if (openList.Count == 0)
                break;
        }

        Hashtable pathNodes = new Hashtable();

        Node currentPathNode = endNode;
        int i = 0;
        while (1 > 0)
        {
            // If some nodes parent never is nulled, then we can never break.
            if (currentPathNode.parent == null)
                break;

            pathNodes.Add(i, currentPathNode.GetComponent<Transform>());
            currentPathNode = currentPathNode.parent.GetComponent<Node>();

            i++;
        }

        Transform[] path = new Transform[pathNodes.Count];
        pathNodes.Values.CopyTo(path, 0);

        return path;
    }

    // Seems to return the key which has the lowest F value
    string ReturnLowestF(Hashtable list)
    {
        float lowestF = Mathf.Pow(10, 100); // 10 ^ 100 = large number.
        string lowestKey = "ah";            // ??? Some default value

        foreach (DictionaryEntry currentEntry in list)
        {
            Transform currentEntryObject = (Transform)list[currentEntry.Key];
            float currentF = currentEntryObject.GetComponent<Node>().F;

            if (lowestF == 0)
                lowestF = currentF;

            if (currentF < lowestF && lowestF != 0)
            {
                lowestF = currentF;
                lowestKey = (string)currentEntry.Key;
            }
        }
        return lowestKey;
    }

    // NOT USED.
    //bool CheckAgainstList(Hashtable list, Transform searchItem)
    //{
    //    bool isOnList = false;
    //    foreach (DictionaryEntry currentEntry in list)
    //    {
    //        if ((Transform)list[currentEntry.Key] == searchItem)
    //        {
    //            isOnList = true;
    //        }
    //    }
    //    return isOnList;
    //}

    // NOT USED.
    //void RemoveFromList(Hashtable list, string key)
    //{
    //    list.Remove(key);
    //}

    // SEEMS OK
    void SwitchList(string key, Hashtable listToRemoveFrom, Hashtable listToAddTo)
    {
        listToAddTo.Add(key, listToRemoveFrom[key]);
        listToRemoveFrom.Remove(key);
    }

    // SEEMS OK
    float EuclideanHeuristic(Transform start, Transform end)
    {
        float distance = Mathf.Sqrt(Mathf.Pow((start.transform.position.x - end.transform.position.x), 2)
            + Mathf.Pow((start.transform.position.z - end.transform.position.z), 2));
        return distance;
    }
}

Most of my "answer" is comments to your question.

 –

Heh, thanks. :)

 –
4

I wrote a Windows App for demonstrating A* path-finding. You can view it here:

http://stormkiernan.wordpress.com/2010/12/01/a-pathfinding/

I hope this helps.

Nice contribution!

 –