if(currentNode==endNode) check seems broken

My pathfinding isn’t working. With some log statements I was able to find that on the very first iteration of the while loop, the equality check between the start and end node is broken. When I log each pathNode, I get different values for the grid positions. It seems that it may be doing a type check instead of checking for equal grid positions.

I tried to fix it by changing the equality check. Now I’m failing to find a path at all. Can I get somebody to check my code and see if I missed something? Thanks :slight_smile:

Start node and end node positions should be different. else you’re going nowhere.

Did you override the operators in GridPosition? Are they correct? Perhaps share that code and we can see if there’s an error. And please don’t share a screenshot of the code. See here how to format code

Thanks for the reply. I don’t think the problem is in my GridPosition code. It has worked well up until this point. Here is the grid position code:

using System;

public struct GridPosition

{

    public int x;

    public int z;

    public GridPosition(int x, int z)

    {

        this.x = x;

        this.z = z;

    }

    public override int GetHashCode()

    {

        return HashCode.Combine(x,z);

    }

    public override bool Equals(object obj)

    {

        return obj is GridPosition position &&

        x==position.x&&

        z==position.z;

    }

    public override string ToString()

    {

        return "x: "+x+", z:"+z;

    }

    public static bool operator ==(GridPosition a, GridPosition b)

    {

        return a.x == b.x && a.z==b.z;

    }

    public static bool operator !=(GridPosition a, GridPosition b)

    {

        return !(a==b);

    }

    public static GridPosition operator +(GridPosition a, GridPosition b)

    {

        return new GridPosition(a.x+b.x, a.z+b.z);

    }

    public static GridPosition operator -(GridPosition a, GridPosition b)

    {

        return new GridPosition(a.x-b.x, a.z-b.z);

    }

}

I think I missed something in either Pathfinding.cs or PathNode.cs. Here are both scripts. If you could run a diff with your version and tell me if anything is missing/incorrect, that would be super awesome.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class Pathfinding : MonoBehaviour
{
    public static Pathfinding Instance {get; private set;}
    private const int MOVE_STRAIGHT_COST = 10;
    private const int MOVE_DIAGONAL_COST = 14;
    private int width;
    private int height;
    private int cellSize;
    private GridSystem<PathNode> gridSystem;

    [SerializeField] private Transform gridDebugObjectPrefab;

    private void Awake()
    {
        if(Instance!=null)
        {
            Debug.LogError("There's more than one pahtfinding script");
            Destroy(gameObject);
            return;
        }
        Instance=this;

        gridSystem = new GridSystem<PathNode>(10,10,2f,
        (GridSystem<PathNode> g, GridPosition gridPosition)=>new PathNode(gridPosition));
        gridSystem.CreateDebugObjects(gridDebugObjectPrefab);
    }

    public List<GridPosition> FindPath(GridPosition startGridPosition,GridPosition endGridPosition)
    {
        Debug.Log("Start: "+startGridPosition+"\nEnd: "+endGridPosition);
        List<PathNode> openList = new List<PathNode>();
        List<PathNode> closedList = new List<PathNode>();

        PathNode startNode = gridSystem.GetGridObject(startGridPosition);
        PathNode endNode = gridSystem.GetGridObject(endGridPosition);
        openList.Add(startNode);

        //Initialize all the pathfinding nodes
        for(int x=0; x<gridSystem.GetWidth(); x++)
        {
            for(int z=0;z<gridSystem.GetHeight(); z++)
            {
                GridPosition gridPosition=new GridPosition(x,z);
                PathNode pathNode=gridSystem.GetGridObject(gridPosition);

                pathNode.SetGCost(int.MaxValue);
                pathNode.SetHCost(0);
                pathNode.CalculateFCost();
                pathNode.ResetCameFromPathNode();
            }
        }

        startNode.SetGCost(0);
        startNode.SetHCost(CalculateDistance(startGridPosition,endGridPosition));
        startNode.CalculateFCost();

        while(openList.Count>0)
        {
            PathNode currentNode = GetLowestFCostPathNode(openList);
            if(currentNode.GetGridPosition()==endNode.GetGridPosition())
            {
                Debug.Log("FOUND END. \nCurrent Node: "+currentNode+"\nEnd Node: "+endNode);
                return CalculatePath(endNode);
            }

            openList.Remove(currentNode);
            closedList.Add(currentNode);

            foreach(PathNode neighborNode in GetNeighborList(currentNode))
            {
                if(closedList.Contains(neighborNode))
                {
                    continue;
                }
                int tentativeGCost=currentNode.GetGCost()+CalculateDistance(currentNode.GetGridPosition(),neighborNode.GetGridPosition());
                if(tentativeGCost<neighborNode.GetGCost())
                {
                    neighborNode.SetCameFromPathNode(currentNode);
                    neighborNode.SetGCost(tentativeGCost);
                    neighborNode.SetHCost(CalculateDistance(neighborNode.GetGridPosition(),endGridPosition));
                    neighborNode.CalculateFCost();

                    if(!openList.Contains(neighborNode))
                    {
                        openList.Add(neighborNode);
                    }
                }

            }
        }
        //No path found
        Debug.Log("Path failed");
        return null;
    }

    public int CalculateDistance(GridPosition gridPositionA, GridPosition gridPositionB)
    {
        int xDistance = Mathf.Abs(gridPositionA.x-gridPositionB.x);
        int zDistance = Mathf.Abs(gridPositionA.z-gridPositionB.z);
        int remaining = Mathf.Abs(xDistance-zDistance);
        return (MOVE_DIAGONAL_COST*Mathf.Min(xDistance,zDistance))+(remaining*MOVE_STRAIGHT_COST);
    }

    private PathNode GetLowestFCostPathNode(List<PathNode> pathNodeList)
    {
        PathNode lowestFCostPathNode = pathNodeList[0];
        for(int i=0; i<pathNodeList.Count; i++)
        {
            if(pathNodeList[i].GetFCost()<lowestFCostPathNode.GetFCost())
            {
                lowestFCostPathNode=pathNodeList[i];
            }
        }
        return lowestFCostPathNode;
    }

    private PathNode GetNode(int x, int z)
    {
        return gridSystem.GetGridObject(new GridPosition(x,z));
    }

    private List<PathNode> GetNeighborList(PathNode currentNode)
    {
        List<PathNode> neighborList = new List<PathNode>();
        GridPosition gridPosition=currentNode.GetGridPosition();
        if(gridPosition.x-1>=0)
        {
            // Left
            neighborList.Add(GetNode(gridPosition.x-1,gridPosition.z+0));
            if(gridPosition.z-1>=0)
            {
                // Left Down
                neighborList.Add(GetNode(gridPosition.x-1,gridPosition.z-1));
            }
            if(gridPosition.z+1<gridSystem.GetHeight())
            {
                // Left Up
                neighborList.Add(GetNode(gridPosition.x-1,gridPosition.z+1));
            }
        }
        if(gridPosition.x+1<gridSystem.GetWidth())
        {
            // Right
            neighborList.Add(GetNode(gridPosition.x+1,gridPosition.z+0));
            if(gridPosition.z-1>=0)
            {
                // Right Down
                neighborList.Add(GetNode(gridPosition.x+1,gridPosition.z-1));
            }
            if(gridPosition.z+1<gridSystem.GetHeight())
            {
                // Right Up
                neighborList.Add(GetNode(gridPosition.x+1,gridPosition.z+1));
            }
        }
        if(gridPosition.z+1<gridSystem.GetHeight())
        {
            // Up
            neighborList.Add(GetNode(gridPosition.x+0,gridPosition.z+1));
        }
        if(gridPosition.z-1>=0)
        {
            // Down
            neighborList.Add(GetNode(gridPosition.x+0,gridPosition.z-1));
        }
        return neighborList;
    }
    private List<GridPosition> CalculatePath(PathNode endNode)
    {
        List<PathNode> pathNodeList = new List<PathNode>();
        pathNodeList.Add(endNode);
        PathNode currentNode = endNode;
        while(currentNode.GetCameFromPathNode()!=null)
        {
            pathNodeList.Add(currentNode.GetCameFromPathNode());
            currentNode = currentNode.GetCameFromPathNode();
        }

        pathNodeList.Reverse();
        List<GridPosition> gridPositionList = new List<GridPosition>();
        foreach(PathNode pathNode in pathNodeList)
        {
            gridPositionList.Add(pathNode.GetGridPosition());
        }
        return gridPositionList;
    }
}

And here is PathNode

using System.Collections;

using System.Collections.Generic;

using UnityEngine;

public class PathNode : MonoBehaviour

{

    private GridPosition gridPosition;

    private int gCost;

    private int hCost;

    private int fCost;

    private PathNode cameFromPathNode;

    public PathNode(GridPosition gridPosition)

    {

        this.gridPosition=gridPosition;

    }

    public override string ToString()

    {

        return gridPosition.ToString();

    }

    public int GetGCost()

    {

        return gCost;

    }

    public int GetHCost()

    {

        return hCost;

    }

    public int GetFCost()

    {

        return fCost;

    }

    public void SetGCost(int gCost)

    {

        this.gCost=gCost;

    }

    public void SetHCost(int hCost)

    {

        this.hCost=hCost;

    }

    public void CalculateFCost()

    {

        this.fCost=gCost+hCost;

    }

    public void ResetCameFromPathNode()

    {

        cameFromPathNode=null;

    }

    public void SetCameFromPathNode(PathNode pathNode)

    {

        cameFromPathNode=pathNode;

    }

    public PathNode GetCameFromPathNode()

    {

        return cameFromPathNode;

    }

    public GridPosition GetGridPosition()

    {

        return gridPosition;

    }

}

Thanks!

I had to modify my own project to paste your code in to find this: Your PathNode inherits from MonoBehaviour and it shouldn’t. It should just be a pure class.

2 Likes

Thanks so much for taking the time to help me out! I still don’t really understand why Mono behavior breaks it, but at this point I am just glad that it is working.

MonoBehaviors can only exist attached to a GameObject, meaning that they have a lot of extra overhead that we simply don’t need for the pathfinding.

2 Likes

I found that the above if condition was always returning true. Even with two completely different path nodes. Why this is the case I cannot tell you. I couldn’t find anything on the managed side of the code that explained it, and I don’t have access to the C++ code.

I think Unity would’ve warned you that classes derived from MonoBehaviour should not be created using the constructor. Maybe it did. I didn’t see it because my warnings are hidden in the console.

It’s one of the yellow warnings, and it looks like this:

You are trying to create a MonoBehaviour using the ‘new’ keyword. This is not allowed. MonoBehaviours can only be added using AddComponent(). Alternatively, your script can inherit from ScriptableObject or no base class at all

2 Likes

This topic was automatically closed 24 hours after the last reply. New replies are no longer allowed.

Privacy & Terms