Hello! I am currently implementing the A* Pathfinding algorithm and I have encountered an issue. I have implemented the pathfinding algorithm and it does work as expected when I hard code the values for starting and ending positions. However, when I am trying to change these values during run time, Unity crashes. I have simplified the code and I removed the movement of the agent, so that the path is searched only when pressing the space key.
void Update()
{
if (Input.GetKeyDown("space"))
{
//Get the Astar component
Astar search = GetComponent<Astar>();
//Get the grid component
GridScript grid = gridObject.GetComponent<GridScript>();
//Assign start and end values at random positions in grid
search.Search(grid.GetNodePosition(Random.Range(1, 50),
Random.Range(1, 50)),
grid.GetNodePosition(Random.Range(1, 50),
Random.Range(1, 50))
);
search = null;
grid = null;
}
When I do this, the algorithm works only for the first three or four key presses (=it finds 3/4 paths) before it crashes. I believe that the problem is on memory allocation, but I am not sure if this causes the problem. I would appreciate any suggestions regarding this matter!
Thank you in advance!
Here is the code:
Astar.cs:
public class Astar : MonoBehaviour {
public GameObject gridObject;
private GridScript grid;
public bool drawCubes = false;
public List<NodeGrid> path = new List<NodeGrid>();
List<NodeGrid> openList, closedList;
void Awake ()
{
grid = gridObject.GetComponent<GridScript>();
}
public float Heuristic(NodeGrid start, NodeGrid end)
{
return (int)Mathf.Sqrt((start._position.x - end._position.x) * (int)(start._position.x - end._position.x) + (int)(start._position.z - end._position.z) * (int)(start._position.z - end._position.z));
//return Mathf.Abs(start._position.x - end._position.x) + Mathf.Abs(start._position.z - end._position.z);
}
public NodeGrid GetLowestF(List<NodeGrid> list)
{
NodeGrid minNode = new NodeGrid();
minNode=list[0];
for (int i=1; i<list.Count;i++)
{
if (list<em>._F <= minNode._F && list*._tag != "wall")*</em>
{
//Debug.Log("Comparing: " + list*.F +" with: " + minNode.F );
_minNode = list;*
}
}_
return minNode;
}
public bool SearchInList(NodeGrid searchNode, List list)
{
foreach (NodeGrid node in list)
{
if(searchNode._id==node._id) return true;
}
return false;
}
public void PrintPath(NodeGrid node)
{
GameObject cube = GameObject.CreatePrimitive(PrimitiveType.Cube);
cube.renderer.material.color = Color.cyan;
cube.transform.localScale=new Vector3(0.4f, 0.4f, 0.4f);
cube.transform.position = node._position;
}
public void Search(NodeGrid start, NodeGrid end)
{
openList = new List();
closedList = new List();
start._G = 0f;
start._F = start._G + Heuristic(start, end);
openList.Add(start);
while (openList != null)
{
NodeGrid currentNode = new NodeGrid();
* currentNode = GetLowestF(openList);*
if (drawCubes)
{
GameObject neighbourCube = GameObject.CreatePrimitive(PrimitiveType.Cube);
neighbourCube.renderer.material.color = Color.black;
neighbourCube.transform.position = currentNode._position;
}
//Check if the current node has the same position as the end node
if (currentNode._position == end._position)
{
Debug.Log(“Path Found!”);
break;
}
openList.Remove(currentNode);
closedList.Add(currentNode);
for (int i = 0; i < 8; i++)
{
currentNode.neighbour = new NodeGrid();
}
if (currentNode._position.x < GridScript.GRID_X - 1 && currentNode._position.z < GridScript.GRID_Z - 1 && currentNode._position.x > 1 && currentNode._position.z > 1)
{
currentNode.neighbour[0] = grid.GetNodePosition((int)currentNode._position.x + 1, (int)currentNode._position.z - 1);
currentNode.neighbour[0]._neigbourPosition = “upLeft”;
currentNode.neighbour[1] = grid.GetNodePosition((int)currentNode._position.x + 1, (int)currentNode._position.z);
currentNode.neighbour[1]._neigbourPosition = “up”;
currentNode.neighbour[2] = grid.GetNodePosition((int)currentNode._position.x + 1, (int)currentNode._position.z + 1);
currentNode.neighbour[2]._neigbourPosition = “upRight”;
currentNode.neighbour[3] = grid.GetNodePosition((int)currentNode._position.x, (int)currentNode._position.z + 1);
currentNode.neighbour[3]._neigbourPosition = “right”;
currentNode.neighbour[4] = grid.GetNodePosition((int)currentNode._position.x - 1, (int)currentNode._position.z + 1);
currentNode.neighbour[4]._neigbourPosition = “downRight”;
currentNode.neighbour[5] = grid.GetNodePosition((int)currentNode._position.x - 1, (int)currentNode._position.z);
currentNode.neighbour[5]._neigbourPosition = “down”;
currentNode.neighbour[6] = grid.GetNodePosition((int)currentNode._position.x - 1, (int)currentNode._position.z - 1);
currentNode.neighbour[6]._neigbourPosition = “downLeft”;
currentNode.neighbour[7] = grid.GetNodePosition((int)currentNode._position.x, (int)currentNode._position.z - 1);
currentNode.neighbour[7]._neigbourPosition = “left”;
}
float tentativeScore;
foreach (NodeGrid neighbour in currentNode.neighbour)
{
if (SearchInList(neighbour, closedList) == true) continue;
if (neighbour._neigbourPosition == “left” || neighbour._neigbourPosition == “right” ||
neighbour._neigbourPosition == “up” || neighbour._neigbourPosition == “down”) tentativeScore = currentNode._G + Heuristic(currentNode, neighbour);
else tentativeScore = currentNode.G + Heuristic(currentNode, neighbour)*1.41f;
if (SearchInList(neighbour, openList) == false || tentativeScore<neighbour._G)
{
neighbour._parent = currentNode;
neighbour._G = tentativeScore;
neighbour._F = neighbour._G + Heuristic(neighbour, end);
if (SearchInList(neighbour, openList) == false && neighbour._tag!=“wall” )
{
openList.Add(neighbour);_
}
}
}
}
while (end._parent != null)
{
// Debug.Log(endNode._position);
PrintPath(end);
path.Add(end);
end = end._parent;
}
* }*
NodeGrid:
public class NodeGrid
{
public Vector3 _position;
public string _neigbourPosition;
public int _id;
public NodeGrid _parent;
public float _F, _G, _H;
public string _tag;
//Neighour has 8 successors
//neigbour[0] = up left
//neigbour[1] = left
//neigbour[2] = down left
//neigbour[3] = down
//neigbour[4] = down right
//neigbour[5] = right
//neigbour[6] = up right
//neigbour[7] = up
public NodeGrid[] neighbour = new NodeGrid[8];
}
GridScrips.cs:
public const int GRID_X = 100, GRID_Z = 100;
public class Grid
{
public NodeGrid[,] _grid = new NodeGrid[GRID_X, GRID_Z];
public Grid()
{
Vector3 pos;
int tempID = 0;
for (int z = 0; z < GRID_Z; z++)
for (int x = 0; x < GRID_X; x++)
{
_grid[x, z] = new NodeGrid();
pos = new Vector3(x, 1f, z);
_grid[x, z]._position = pos;
_grid[x, z]._id = tempID;
_grid[x, z]._G = 0f;
tempID++;
}
}
public void Tag(int x1, int z1)
{
_grid[x1, z1]._tag = “wall”;
}
public NodeGrid Node(int x1, int z1)
{
return _grid[x1, z1];
}
}
public NodeGrid GetNodePosition(int x, int z)
{
return grid.Node(x, z);
}
public void SetTag(int x, int z)
{
grid.Tag(x, z);
}
Grid grid;
void Awake()
{
grid = new Grid();
}