I’m making A* script for my 2d enemy character.
I have Node class:
public class Node
{
#region Fields
private int g; //Represent the exact cost of the oath from the starting point
private int h; //Represent the heuristic estimated cost from the goal
private int f; //f=g+h; Used for finding shortest path.
private Vector3Int position;
private Node parent;
#endregion
#region Properties
public int G { get=> g; set{ g = value; f = h + value; } }
public int H{ get => h; set { h = value; f = g + value; } }
public int F { get => f; }
public Vector3Int Position { get => position; }
public Node Parent { get => parent; set => parent = value; }
#endregion
public Node(Vector3Int _position)
{
position = _position;
}
}
and a method for searching available neighbor node in another class:
private List<Node> FindNeighbors(Node _currentNode)
{
if (_currentNode == null) Debug.LogWarning("Current Node is Null");
Vector3Int currentPos = _currentNode.Position;
Vector3Int hPos;
Vector3Int vPos;
Vector3Int newPos;
List<Node> neighborList = new List<Node>();
for (int x = -1; x <= 1; x++)
{
hPos = new Vector3Int(currentPos.x + x, currentPos.y, currentPos.z);
if (!walkableTiles.HasTile(hPos)) continue;
for (int y = -1; y <= 1; y++)
{
if (x == 0 && y == 0) continue;
vPos = new Vector3Int(currentPos.x, currentPos.y + y, currentPos.z);
if (!walkableTiles.HasTile(vPos)) continue;
newPos = new Vector3Int(currentPos.x + x, currentPos.y + y, currentPos.z);
Node neighbor;
if (!nodeList.ContainsKey(newPos))
{
neighbor = CreateNode(newPos);
neighborList.Add(neighbor);
if (_currentNode == null) Debug.Log("Current Node is Null");
neighbor.Parent = _currentNode;
}
else
{
neighbor = nodeList[newPos];
if (openList.Contains(neighbor))
{
//ReCalculate G,F and add to neighbors if numbers are lower.
int gScore = CalculateGScore(neighbor);
if ((gScore < neighbor.G)) continue;
neighbor.G = gScore;
neighbor.Parent = _currentNode;
}
}
}
}
return neighborList;
}
problem is on line 29, when i try to add _currentNode as parent, it returns null reference exeption.
I’m doing this search in a while loop and it gives error in 3rd loop right now.
Here Full Script:
public class AStarAlgorithm: MonoBehaviour
{
#region Fields
[SerializeField] private Tilemap walkableTiles;
private List<Node> openList;
private List<Node> closedList;
private Dictionary<Vector3Int, Node> nodeList;
private Stack<Node> path;
#endregion
#region Methods
public void PathfindingAlgorithm(Vector3 _startingPos, Vector3 _goalPos)
{
ClearAlgorithm();
Vector3Int startingPos = Vector3Int.FloorToInt(_startingPos);
Vector3Int goalPos = Vector3Int.FloorToInt(_goalPos);
Node startingNode = CreateNode(startingPos);
Node goalNode = CreateNode(goalPos);
Node currentNode = startingNode;
openList.Add(currentNode);
while (openList.Count > 0)
{
Debug.LogError(currentNode.Position + "\n" + openList.Count);
List<Node> nb = FindNeighbors(currentNode);
for (int i = nb.Count - 1; i >= 0; i--)
{
CalculateScores(nb[i], goalNode);
}
currentNode = SelectNextNode(currentNode);
if (currentNode.Position != goalNode.Position) continue;
GeneratePath(currentNode, startingNode);
break;
}
AStarDebugging.Instance.GenerateDebugTiles(startingNode, goalNode, nodeList, openList, closedList);
}
private Node CreateNode(Vector3Int _position)
{
if (!walkableTiles.HasTile(_position)) return null;
Node node = new Node(_position);
nodeList.Add(_position, node);
//openList.Add(node);
return node;
}
private List<Node> FindNeighbors(Node _currentNode)
{
if (_currentNode == null) Debug.LogWarning("Current Node is Null");
Vector3Int currentPos = _currentNode.Position;
Vector3Int hPos;
Vector3Int vPos;
Vector3Int newPos;
List<Node> neighborList = new List<Node>();
for (int x = -1; x <= 1; x++)
{
hPos = new Vector3Int(currentPos.x + x, currentPos.y, currentPos.z);
if (!walkableTiles.HasTile(hPos)) continue;
for (int y = -1; y <= 1; y++)
{
if (x == 0 && y == 0) continue;
vPos = new Vector3Int(currentPos.x, currentPos.y + y, currentPos.z);
if (!walkableTiles.HasTile(vPos)) continue;
newPos = new Vector3Int(currentPos.x + x, currentPos.y + y, currentPos.z);
Node neighbor;
if (!nodeList.ContainsKey(newPos))
{
neighbor = CreateNode(newPos);
neighborList.Add(neighbor);
if (_currentNode == null) Debug.Log("Current Node is Null");
neighbor.Parent = _currentNode;
}
else
{
neighbor = nodeList[newPos];
if (openList.Contains(neighbor))
{
//ReCalculate G,F and add to neighbors if numbers are lower.
int gScore = CalculateGScore(neighbor);
if ((gScore < neighbor.G)) continue;
neighbor.G = gScore;
neighbor.Parent = _currentNode;
}
}
}
}
return neighborList;
}
private void CalculateScores(Node _node, Node _goalNode)
{
int gScore = CalculateGScore(_node);
int hScore = CalculateHScore(_node, _goalNode);
if (!openList.Contains(_node))
{
_node.G = gScore;
_node.H = hScore;
openList.Add(_node);
}
}
private int CalculateHScore(Node _node, Node _goalNode)
{
var x = Mathf.Abs(_goalNode.Position.x - _node.Position.x);
var y = Mathf.Abs(_goalNode.Position.y - _node.Position.y);
return (x + y) * 10;
}
private int CalculateGScore(Node _node)
{
Node parentNode = _node.Parent;
if ((_node.Position.x - parentNode.Position.x) + (_node.Position.y - parentNode.Position.y) % 2 == 0)
{
return parentNode.G + 14;
}
else
{
return parentNode.G + 10;
}
}
private Node SelectNextNode(Node _currentNode)
{
closedList.Add(_currentNode);
openList.Remove(_currentNode);
Node selected = openList.OrderBy(node => node.F).First();
return selected;
}
private Stack<Node> GeneratePath(Node _currentNode, Node _startingNode)
{
while (_currentNode.Position != _startingNode.Position)
{
path.Push(_currentNode);
_currentNode = _currentNode.Parent;
}
return path;
}
private void ClearAlgorithm()
{
nodeList = new Dictionary<Vector3Int, Node>();
openList = new List<Node>();
closedList = new List<Node>();
path = new Stack<Node>();
}
#endregion
}
