Trying to build an A*, instead I'm crashing my computer.

Questions & Answers
1

So, I’m trying to build an A* pathfinding thing for a three-dimensional tactical RPG. As I did not (and kind of still don’t, really) know how to build one, I looked for examples. The only examples I could find were designed for a 2d map, often generating the map via a partner script.

I didn’t like that, so I found one that seemed the most complete, and began attempting to make it work - after some trial and error, I ended up basically translating it into terms I’d ‘get.’ I’ll end up updating it as I go, but I need it to work in order to…well, go.

It’s currently…I think it’s currently very close to working, except for this minor (not really) issue where it either outputs nothing or causes my computer to lock up due to a memory leak. Looking at the script, I really can’t figure out why it does the latter (which I cause by resolving the former in the only way I see to do so). The issue itself comes up as

OutOfMemoryException: Out of memory
System.Array.Resize[GameObject] (UnityEngine.GameObject[]& array, Int32 length, Int32 newSize) (at /Users/builduser/buildslave/mono-runtime-and-classlibs/build/mcs/class/corlib/System/Array.cs:1928)
System.Array.Resize[GameObject] (UnityEngine.GameObject[]& array, Int32 newSize) (at /Users/builduser/buildslave/mono-runtime-and-classlibs/build/mcs/class/corlib/System/Array.cs:1912)
System.Collections.Generic.List`1[UnityEngine.GameObject].set_Capacity (Int32 value) (at /Users/builduser/buildslave/mono-runtime-and-classlibs/build/mcs/class/corlib/System.Collections.Generic/List.cs:622)
System.Collections.Generic.List`1[UnityEngine.GameObject].GrowIfNeeded (Int32 newCount) (at /Users/builduser/buildslave/mono-runtime-and-classlibs/build/mcs/class/corlib/System.Collections.Generic/List.cs:100)
System.Collections.Generic.List`1[UnityEngine.GameObject].Add (UnityEngine.GameObject item) (at /Users/builduser/buildslave/mono-runtime-and-classlibs/build/mcs/class/corlib/System.Collections.Generic/List.cs:91)
IxAStar.FindPath (UnityEngine.GameObject startTile, UnityEngine.GameObject endTile) (at Assets/IxAStar.cs:83)
IxBoard.FindPath (UnityEngine.GameObject startTile, UnityEngine.GameObject endTile) (at Assets/IxBoard.cs:166)
IxBoard.Update () (at Assets/IxBoard.cs:49)

In the debug log; IxBoard.Update is the bit that calls the function.

The actual script itself is:

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

public class IxAStar {

	List<GameObject> open;
	List<GameObject> closed;
	List<GameObject> neighbors;
	List<GameObject> path;

	public int curCost;

	public IxAStar () 
	{

		open = new List<GameObject>();
		closed = new List<GameObject>();
		neighbors = new List<GameObject>();
		path = new List<GameObject>();
	}
	


	public void FindPath(GameObject startTile, GameObject endTile)
	{
		bool Search = true;
		bool isPath = true;
		GameObject start = startTile;
		GameObject end = endTile;
	open.add (start);

		while ((Search == true) && (isPath == true)) 
		{


			GameObject curTile = BestFromOpen();

			if (curTile == null) 
			{

				isPath = false;
				break;
			}
			closed.Add (curTile);

			Debug.Log (curTile);
			if (curTile == end)
				Search = false;
			else 
			{

				GetNeighborList(curTile);
				foreach (GameObject neighbor in neighbors) 
				{
					if (CheckClosed(neighbor) != null)
						continue;
					GameObject InOpen = CheckOpen(neighbor);
					if (InOpen == null) 
					{

						open.Add (neighbor);
					}
					else 
					{
						if (neighbor.gameObject.GetComponent<IxTile>().moveCostToHere < InOpen.GetComponent<IxTile>().moveCostToHere) 
						{
							InOpen.GetComponent<IxTile>().moveCostToHere = neighbor.gameObject.GetComponent<IxTile>().moveCostToHere;
							InOpen.GetComponent<IxTile>().moveCostTotal = InOpen.GetComponent<IxTile>().moveCostToHere + InOpen.GetComponent<IxTile>().estimateToEnd;
							InOpen.GetComponent<IxTile>().prevTile = curTile;
							curTile.GetComponent<IxTile>().nextTile = InOpen;
						}
					}
				}
			}
		}

//Problem actually seems to originate here, in this last bit of code, somehow.
if (isPath)
		{
			GameObject findEnd = CheckClosed(end);
			while (findEnd != null) 
			{
				path.Add (findEnd);
				findEnd = findEnd.GetComponent<IxTile>().prevTile;
			}
		}
	}

	void GetNeighborList(GameObject tarTile)
	{
		neighbors.Clear ();
		List<GameObject> tarNeighbors = tarTile.GetComponent<IxTile>().tileNeighbors;
		for (int i = 0; i < tarNeighbors.Count; i++) 
		{
			GameObject neiTile = tarNeighbors *;*

  •  	neiTile.GetComponent<IxTile>().prevTile = tarTile;*

  •  	neiTile.GetComponent<IxTile>().moveCostToHere = curCost + neiTile.GetComponent<IxTile>().moveCostThisTile;*

  •  	neiTile.GetComponent<IxTile>().moveCostTotal = neiTile.GetComponent<IxTile>().moveCostToHere + neiTile.GetComponent<IxTile>().estimateToEnd;*

  •  }*

  •  tarTile.GetComponent<IxTile> ().tileNeighbors.ForEach (neighbors.Add);*

  • }*

  • GameObject BestFromOpen()*

  • {*

  •  float minCostToHere = float.MaxValue;*

  •  GameObject best = null;*

  •  for (int bestCheck = 0; bestCheck < open.Count; bestCheck ++)* 

  •  {*

  •  	GameObject tarTile = open [bestCheck];*

  •  	Debug.Log (bestCheck);*

  •  	if (tarTile.GetComponent<IxTile> ().moveCostToHere < minCostToHere)* 

  •  	{*

  •  		minCostToHere = tarTile.GetComponent<IxTile> ().moveCostToHere;*

  •  		best = tarTile;*

  •  	}*

  •  }*

  •  if (best != null)*

  •  	open.Remove(best);*

  •  return best;*

  • }*

  • GameObject CheckOpen (GameObject curTile)*

  • {*

  •  if (open.Contains (curTile))* 

  •  {*

  •  	return curTile;*

  •  }*

  •  return null;*

  • }*

  • GameObject CheckClosed (GameObject curTile)*

  • {*

  •  if (closed.Contains (curTile))* 

  •  {*

  •  	return curTile;*

  •  }*

  •  return null;*

  • }*

  • public List PointsFromPath()*

  • {*

  •  List<float> points = new List<float>();*

  •  foreach (GameObject tarTile in path)* 

  •  {*

  •  	points.Add (tarTile.transform.position.x);*

  •  	points.Add (tarTile.transform.position.y);*

  •  	points.Add (tarTile.transform.position.z);*

  •  }*

  •  return points;*

  • }*

  • public List TilesFromPath()*

  • {*

  •  List<GameObject> pathTiles = new List<GameObject> ();*

  •  foreach (GameObject tarTile in path)* 

  •  {*

  •  	pathTiles.Add(tarTile);*

  •  	Debug.Log("Path Tile output is:");*

  •  	Debug.Log (tarTile);*

  •  }*

  •  if (pathTiles.Count != 0)* 

  •  {*

  •  	pathTiles.Reverse ();*

  •  	pathTiles.RemoveAt(0);*

  •  }*

  •  Debug.Log ("check.");*

  •  return pathTiles;*

  • }*

}

In conversations with a more knowledgeable friend, they’ve suggested that I’m accidentally causing a massive recursion, leading to a memory leak, but…if I am, I just don’t see it. Anybody got any ideas on how I can fix this?

2

The problem could potentially be in your IxTile or IxBoard class. You can also try Debug.Log(open.Count) every time you add to the open list. Make sure your open list isn’t spiraling out of control. Maybe even do the same with the closed list. Your error occurs when you try and add to a list, but there’s not enough room in memory to hold all the objects. Either one of two things is happening. Either one of your lists has way too many items in it or when you reconstruct the path, it ends up pointing to tiles that were already in the path causing you to reconstruct an infinite looping path. You can try logging the first 100 items in the path as you add to it to see if there are any repeats. This will help you narrow down where the problem is. Good luck!

3

Welp, via commenting out things I suspected of causing the problem, I was eventually able to narrow the problem down to the while (findEnd != null) line. Remembered an issue I’d had a while ago where using ‘while’ would lock Unity up.

Turned the ‘while’ to an ‘if.’

Now it works, in that Unity does not crash.

4

RedBlobGames has the best discussion about A* I’ve found anywhere. I would suggest reading through that and starting with his Breadth First Search algorithm and proceeding through everything until you get to the A* implementation. It’ll help you understand it all and make it easier to figure out where you’re going wrong in your code.

I’ll just say that you aren’t the only one who had problems with infinite recursion :slight_smile: Mine wasn’t properly dealing with the close list and I was processing nodes that had already been processed.