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!
