koobas.hobune.stream
Memory allocation issue
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[i]._F <= minNode._F && list[i]._tag != "wall")
{
//Debug.Log("Comparing: " + list[i]._F +" with: " + minNode._F );
minNode = list[i];
}
}
return minNode;
}
public bool SearchInList(NodeGrid searchNode, List<NodeGrid> 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<NodeGrid>();
closedList = new List<NodeGrid>();
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[i] = 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();
}
Check your Editor.log. It will show you the stack trace of your crash. It's almost certainly somewhere in search.Search()
It makes Unity crash? It actually closes? Or does it freeze? $$anonymous$$aybe you have some problem in your code that starts and infinite loop.
If there's some memory problem with that it could also be an issue for an infinite loop creating too much stuff. Try checking the memory usage of Unity when you press the space bar.
@DiegoSLTS Unity freezes and does not respond, I have to use the task manager to get to close. It is indeed a problem of an infinite loop. I have managed to link Unity to VS and debug the code (as the debugger from monodevelop does not work) and it turns out that there is an infinite loop inside the search function. What I did was: 1. Tested the application and recorded all of the node values, including the ones that cause the crash. Then I hard coded the values that "caused" the crash and the algorithm worked perfectly. 2. Left the starting node as a static value and searched for paths from that node to a random end node. This again, works perfectly.
It looks like whenever I am changing the starting value, Unity responds in a weird way.
I'm not familiar with the A* pathfinding, but if you share your search implementation (and any code used by that function) it would be easier to help, otherwise is just guessing.
I have edited the question to include the code that I use. I did not want to do that from the beginning because, as you can see, it is a lot...
Hello guys I have a same problem when I use AStar Pathfinding project in Unity Asset Store. I think you have a mistake in editor grid size. Check it in editor again and set suitable value for it.
Hope to hearing your result.
