- Home /
"Too Many Heap Sections" Building A*Pathfinding
You guys have always been pretty good to me so I come back asking for help. I am working on a simple A* path finding tech demo. I have had no previous knowledge on how to do this, so I thought it would be a great learning experience. It was awesome and with the guidance of this tutorial http://www.youtube.com/watch?v=fXh2tO0s1-g I was able to get it pretty much working.
I had to make certain adjustments from the tutorial due to the fact that it was written in another engine. But after some work around and problem solving I wanted to expand it, so I tried implementing searching diagonal tiles as well as horizontal and vertical. However once I do this I get a fatal "too many heap sections".
Now I am not a veteran programmer but I understand most things, and form I gather I have a memory leak somewhere. But I cannot pinpoint where.
I attached the main part of program, my "PathFinder" script, for reference. I have other parts written but I did not want to just paste hundreds of lines.
public List<Vector2> GetAdjacentTiles(Vector2 currentTile)
{
List<Vector2> adjacentTiles = new List<Vector2>();
//Vector2 adjacentTile;
Tile temp = AStarTest.grid[(int)currentTile.x,(int)currentTile.y];
///Adjacent Variables
Vector2 adjacentTileUp = new Vector2(currentTile.x, currentTile.y + 1);
Vector2 adjacentTileDown = new Vector2(currentTile.x, currentTile.y - 1);
Vector2 adjacentTileLeft = new Vector2(currentTile.x - 1, currentTile.y);
Vector2 adjacentTileRight = new Vector2(currentTile.x + 1, currentTile.y);
Vector2 adjacentTileLeftUp = new Vector2(currentTile.x - 1, currentTile.y + 1);
Vector2 adjacentTileLeftDown = new Vector2(currentTile.x - 1, currentTile.y - 1);
Vector2 adjacentTileRightUp = new Vector2(currentTile.x + 1, currentTile.y + 1);
Vector2 adjacentTileRightDown = new Vector2(currentTile.x + 1, currentTile.y - 1);
switch(temp.sideNum)
{
case 0:
//Tile above
if(AStarTest.grid[(int)adjacentTileUp.x,(int)adjacentTileUp.y].walkable)
{
adjacentTiles.Add(adjacentTileUp);
}
//Tile right
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileRight);
}
//diagnol right up
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileRightUp);
}
break;
case 1:
//Tile above
if(AStarTest.grid[(int)adjacentTileUp.x,(int)adjacentTileUp.y].walkable)
{
adjacentTiles.Add(adjacentTileUp);
}
//Tile right
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileRight);
}
//Tile below
if(AStarTest.grid[(int)adjacentTileDown.x,(int)adjacentTileDown.y].walkable)
{
adjacentTiles.Add(adjacentTileDown);
}
//diagnol right up
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileRightUp);
}
//diagnol right down
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileRightDown);
}
break;
case 2:
//Tile below
if(AStarTest.grid[(int)adjacentTileDown.x,(int)adjacentTileDown.y].walkable)
{
adjacentTiles.Add(adjacentTileDown);
}
//Tile right
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileRight);
}
//diagnol right down
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileRightDown);
}
break;
case 3:
//Tile below
if(AStarTest.grid[(int)adjacentTileDown.x,(int)adjacentTileDown.y].walkable)
{
adjacentTiles.Add(adjacentTileDown);
}
//Tile right
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileRight);
}
//Tile left
if(AStarTest.grid[(int)adjacentTileLeft.x,(int)adjacentTileLeft.y].walkable)
{
adjacentTiles.Add(adjacentTileLeft);
}
//diagnol right down
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileRightDown);
}
//diagnol left down
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileLeftDown);
}
break;
case 4:
//Tile below
if(AStarTest.grid[(int)adjacentTileDown.x,(int)adjacentTileDown.y].walkable)
{
adjacentTiles.Add(adjacentTileDown);
}
//Tile left
if(AStarTest.grid[(int)adjacentTileLeft.x,(int)adjacentTileLeft.y].walkable)
{
adjacentTiles.Add(adjacentTileLeft);
}
//diagnol left down
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileLeftDown);
}
break;
case 5:
//Tile above
if(AStarTest.grid[(int)adjacentTileUp.x,(int)adjacentTileUp.y].walkable)
{
adjacentTiles.Add(adjacentTileUp);
}
//Tile below
if(AStarTest.grid[(int)adjacentTileDown.x,(int)adjacentTileDown.y].walkable)
{
adjacentTiles.Add(adjacentTileDown);
}
//Tile left
Vector2 adjacentTile15 = new Vector2(currentTile.x - 1, currentTile.y);
if(AStarTest.grid[(int)adjacentTile15.x,(int)adjacentTile15.y].walkable)
{
adjacentTiles.Add(adjacentTile15);
}
//diagnol left down
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileLeftDown);
}
//diagnol left up
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileLeftUp);
}
break;
case 6:
//Tile above
if(AStarTest.grid[(int)adjacentTileUp.x,(int)adjacentTileUp.y].walkable)
{
adjacentTiles.Add(adjacentTileUp);
}
//Tile left
if(AStarTest.grid[(int)adjacentTileLeft.x,(int)adjacentTileLeft.y].walkable)
{
adjacentTiles.Add(adjacentTileLeft);
}
//diagnol left up
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileLeftUp);
}
break;
case 7:
//Tile above
if(AStarTest.grid[(int)adjacentTileUp.x,(int)adjacentTileUp.y].walkable)
{
adjacentTiles.Add(adjacentTileUp);
}
//Tile right
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileRight);
}
//Tile left
if(AStarTest.grid[(int)adjacentTileLeft.x,(int)adjacentTileLeft.y].walkable)
{
adjacentTiles.Add(adjacentTileLeft);
}
//diagnol left up
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileLeftUp);
}
//diagnol right up
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileRightUp);
}
break;
case 8:
//Tile above
if(AStarTest.grid[(int)adjacentTileUp.x,(int)adjacentTileUp.y].walkable)
{
adjacentTiles.Add(adjacentTileUp);
}
//Tile below
if(AStarTest.grid[(int)adjacentTileDown.x,(int)adjacentTileDown.y].walkable)
{
adjacentTiles.Add(adjacentTileDown);
}
//Tile left
if(AStarTest.grid[(int)adjacentTileLeft.x,(int)adjacentTileLeft.y].walkable)
{
adjacentTiles.Add(adjacentTileLeft);
}
//Tile right
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileRight);
}
//diagnol left up
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileLeftUp);
}
//diagnol right up
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileRightUp);
}
//diagnol left down
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileLeftDown);
}
//diagnol right down
if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable)
{
adjacentTiles.Add(adjacentTileRightDown);
}
break;
}
What line causes the crash? Where is the rest of the method code? Have you tried stepping through it with a debugger?
It began breaking when I added the
//diagnol right down if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileRight.y].walkable) { adjacentTiles.Add(adjacentTileRightDown); }
parts for diagonal left/right. The rest of the code is very long, I attached the project here.
I am really lost on this, if you have the time to look at it I would be beyond grateful.
I gave it a glance over and I see a few errors. $$anonymous$$ost of your diagonal code is incorrect as in the comment above. it should be:
//diagnol right down if(AStarTest.grid[(int)adjacentTileRight.x,(int)adjacentTileDown.y].walkable) // <-- note DOWN, not right
{ adjacentTiles.Add(adjacentTileRightDown); }
Also, i see the cases you are using for edge of the board. A cleaner way to do this is to throw in nested for loops, and test if the case is off the grid, if so just skip it. it will be much more readable and easier to debug.
Can't believe I missed that part in my if statement. Thank you! I guess this is beneficial to have other eyes look at your work!
Also, the second part you said about a nested loop, I am not quite sure what you mean. For some clarification each "tile" on my grid calculates their own "sideNum" on themselves by checking if their ID to see if they are a corner piece, a side (top,bottom,left,or right) then finally if not in the ceneter of the grid.
fresh eyes always helps. Nix the nested statement, i was just envisioning another way to do it that don't use a sidenum. By loop i mean, you just check all adjacent squares, if the square is off the grid, ignore it. Actually a good way to impl aStar is recursive.. There's a good article..somehwere..that i can't remember where atm.. I implemented an astar recently based on another guys code that does it recursively, i modified it to take in diagonals as well. I'll post it or send a copy if you're interested..
Answer by SinisterRainbow · Jun 29, 2013 at 03:23 AM
OK, here's the code for my AStar implementation. A few notes, this is recursive and may be cryptic to some, but is based largely on the blog post above if you have questions. This is a very clean way to do it, so I decided to use it rather than impl my own.
I haven't tweaked it yet, just wanted something that works then move on. I later plan to store the entire grid, since i always use it to get the optimal path from one point, and there can be many points checked using the same starting node. Tho on on pc it's not necessary, dunno about ios/android, probably ok.
I haven't looked at this in awhile, but i remember my original intention was to make it flexible enough for 4 major kinds of grid searches - triangle grid, square grid with corners and ignoring corners, and a hex grid. (for future games). It has a couple small data structures I use for nodes, and a quick priorityqueue impl in the same file.
Example usage: I have the calling code in a coroutine. Basically, I have an army on a square grid of various terrain types (each with it's own move cost). I Use Manhattan distance based on this cost. the my_i and my_j are grid positions. the m_iMoveCost is the cost of moving through that terrain square (forest may have a cost of 3, where dirt may be 1).. Example calling code:
public IEnumerator MoveArmy() {
...
...
BoardNode startNode = new BoardNode( sugp.my_i, sugp.my_j, sugp.m_iMoveCost );
float moveStep = 25.0f;
Vector3 startPos = sugp.GetGameObject().transform.position +(SUUniversal.m_fArmyHeight* sugp.GetGameObject().transform.TransformDirection(Vector3.forward ));
AStarPath<BoardNode> aPath = null;
sugpl.SU_G.ActivateMouseText(true);
sugpl.SU_G.TextBoxPosition(DIRECTION.D_LOWERMIDDLE);
while ( Input.GetMouseButton( 0 ) ) {
try {
float scaleStep = Time.deltaTime * 19.0f;
Vector3 mousePos = Input.mousePosition;
mousePos.z = 2.0f;
Vector3 tempP = Camera.main.ViewportToWorldPoint( Input.mousePosition );
Vector3 awayFromCam = Camera.main.ScreenToWorldPoint( mousePos );
if ( CheckTileEnter( true ) ) { //m_moPieceX >= 0)
GameObject go = GameObject.Find( "gamePiece_" + m_moPieceX + "_" + m_moPieceY );
if ( go != null && m_goArmy != null ) {
Vector3 newPos = go.transform.position + (SUUniversal.m_fArmyHeight * go.transform.TransformDirection( Vector3.forward ));
m_goArmy.transform.position = Vector3.MoveTowards( m_goArmy.transform.position, newPos, moveStep * Time.deltaTime );
m_goArmy.transform.rotation = go.transform.rotation;
BoardNode endNode = new BoardNode( m_moPieceX, m_moPieceY, m_moValue );
//Debug.Log("Startnode: " + startNode.x + "," + startNode.y + " -- and endNOde is; " + m_moPieceX + "," + m_moPieceY);
aPath = (AStarPath<BoardNode>) AStarPath<BoardNode>.FindPath < BoardNode >( startNode, endNode, 8, BoardNode.EstimateDistance,
BoardNode.GetCost, sugpl.SU_GB.GetNodeNeighbor );
... //more stuff
}//end while
Debug.Log("Total move cost: " + APath.TotalCost());
...
} //end IEnumerator
I just put it here to see how to call it and how I use my boardnodes (found in the next file along with the AStar alg and PriorityQueue). You can just copy this and throw it in a file with any file name, it doesn't use Monobehaviour. You can implement your own node class for your grid or use the boardnode inside. The AStar can take any node, and any distance function you wish. If you have questions, i'll comment back. Note: The smallVec2i type is just a Vector2 that is strictly int.
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
// SUAstar - A* Pathfinding
// **** Based on Eric Lippert C# code ****
//---------------------------------------------------------------//---------------------------------------------------------------
public interface IHasNeighbors<N> {
IEnumerable<N> Neighbors { get; }
}
public interface GenericNode {
bool IsNull { get; }
}
//---------------------------------------------------------------//---------------------------------------------------------------
/* unused :
* public enum NEIGHBOR_NODE_TYPE {
POINT_3 = 3, //equilateral triangle
POINT_4 = 4, //square grid ignore corners
POINT_6 = 6, //hex grid
POINT_8 = 8, // square grid using corners
}*/
//---------------------------------------------------------------//---------------------------------------------------------------
//[System.Runtime.InteropServices.StructLayout(System.Runtime.InteropServices.LayoutKind.Sequential, Pack=2)]
public class BoardNode {
//public smallVec2i svTile;
public int x { get; private set; }
public int y { get; private set; }
public int iNodeCost { get; private set; }
public bool bReachable { get; private set; }
//public smallVec2i[] svNeighbors { get; private set; } //Left, Right, Up, Down, UpperLeft, UpperRight, LowerLeft, LowerRight;
const int iMaxCost = 9999999;
public BoardNode( int inX = -1, int inY = -1, int cost = iMaxCost ) { //, smallVec2i[] inEdges) {
x = inX;
y = inY;
iNodeCost = cost;
if ( iNodeCost == iMaxCost || x < 0 || y < 0 ) {
bReachable = false;
} else {
bReachable = true;
}
}
public BoardNode( smallVec2i svTile, int cost = iMaxCost ) { //, smallVec2i[] inEdges) {
x = svTile.x;
y = svTile.y;
iNodeCost = cost;
if ( iNodeCost == iMaxCost || x < 0 || y < 0) {
bReachable = false;
} else {
bReachable = true;
}
}
public override bool Equals( System.Object obj) {
// If parameter is null return false.
BoardNode bnObj = obj as BoardNode;
if ( bnObj == null ) {
return false;
}
return ( (bnObj.x == x) && (bnObj.y == y) );
}
static public int EstimateDistance( BoardNode bn1, BoardNode bn2 ) { //NOTE: minimal estimate is 1 per square/straightest line. cannot have < 1 squares!
int i = (Mathf.Max( Mathf.Abs( bn1.x - bn2.x ), Mathf.Abs( bn1.y - bn2.y ) ));
//Debug.Log( "Estimate distace is: " + i + " for: " + bn1.x + "," + bn1.y + " and " + bn2.x + "," + bn2.y );
return i;
}
static public int GetCost( BoardNode ingoreNode, BoardNode getCostNode ) {
int i = getCostNode.iNodeCost;
//Debug.Log( "Getcost is: " + i );
if (getCostNode.bReachable && i != 0) {
return i;
} else {
return iMaxCost;
}
}
public bool IsNull() {
return (bReachable && x >= 0 && y >= 0);
}
}
//---------------------------------------------------------------//---------------------------------------------------------------
//---------------------------------------------------------------//---------------------------------------------------------------
class AStarPath<Node> : IEnumerable<Node> {
#region Declarations
public Node LastNode { get; private set; }
public AStarPath<Node> PreviousSteps { get; private set; }
public int TotalCost { get; private set; }
public const int iMaxCost = 9999999;
#endregion
//---------------------------------------------------------------
private AStarPath( Node lastN, AStarPath<Node> previousSteps, int totalCost ) {
LastNode = lastN;
PreviousSteps = previousSteps;
TotalCost = totalCost;
}
//---------------------------------------------------------------
public AStarPath( Node startNode ) : this( startNode, null, 0 ) { }
//---------------------------------------------------------------
public AStarPath<Node> AddStep( Node stepNode, int stepCost )
{
return new AStarPath<Node>( stepNode, this, TotalCost + stepCost );
}
//---------------------------------------------------------------
public IEnumerator<Node> GetEnumerator() {
for ( AStarPath<Node> p = this; p != null; p = p.PreviousSteps )
yield return p.LastNode;
}
//---------------------------------------------------------------
IEnumerator IEnumerable.GetEnumerator() {
return this.GetEnumerator();
}
//---------------------------------------------------------------
public int GetMaxCost() {
return iMaxCost;
}
//---------------------------------------------------------------//---------------------------------------------------------------
static public AStarPath<Node> FindPath<Node>( Node startNode,
Node destNode,
int iEdges,
System.Func<Node,Node,int> estDistFunc,
System.Func<Node, Node, int> distFunc,
System.Func<Node,int,int,Node> getNeighbor
)
{
var closed = new HashSet<Node>();
var queue = new PriorityQueue<int, AStarPath<Node> >();
queue.Enqueue( 0, new AStarPath<Node>( startNode ) );
while ( !queue.IsEmpty ) {
var path = queue.Dequeue();
if ( closed.Contains( path.LastNode ) ) {continue;}
if ( path.LastNode.Equals( destNode ) ) {return path;}
closed.Add( path.LastNode );
//foreach ( Node neighNode in path.LastNode.Neighbors ) {
for (int i=0; i <= iEdges; ++i) {
Node NeiNode = getNeighbor( path.LastNode, i, iEdges ); //should be able to do equi-tris/squares/hexs/squares with corners
if (NeiNode == null) { //default(Node)) {
//Debug.Log("Neinode was null for i: " + i + " edgtes: " + iEdges + " pathLaststp: " + path.LastNode);
//var newPath = path.AddStep( NeiNode, iMaxCost );
//queue.Enqueue( iMaxCost, newPath );
continue;
} else {
int d = distFunc( path.LastNode, NeiNode ); //Since i'm sending in a Generic 'Node' type, have to send a distance Func<>
var newPath = path.AddStep( NeiNode, d );
queue.Enqueue( newPath.TotalCost + estDistFunc( NeiNode, destNode ), newPath );
}
}
}
return null;
}
//---------------------------------------------------------------//---------------------------------------------------------------
static public void PrintPath<Node> (AStarPath<Node> apath) {
//string sNodes = "";
//foreach (Node n in apath) {
//sNodes += " " + ;
//}
Debug.Log("total path cost: " + apath.TotalCost);
}
}
//---------------------------------------------------------------//---------------------------------------------------------------
//---------------------------------------------------------------//---------------------------------------------------------------
public class Neighborly : MonoBehaviour {
public List<smallVec2i> GetNeighbors<Node>(smallVec2i sv) {
return new List<smallVec2i>();
}
IEnumerator _GetNeighbors(smallVec2i sv) {
yield return null;
}
}
//---------------------------------------------------------------//---------------------------------------------------------------
//---------------------------------------------------------------//---------------------------------------------------------------
public class PriorityQueue<P, V> {
private SortedDictionary<P, Queue<V>> list = new SortedDictionary<P, Queue<V>>();
public void Enqueue( P priority, V value ) {
Queue<V> q;
if ( !list.TryGetValue( priority, out q ) ) {
q = new Queue<V>();
list.Add( priority, q );
}
q.Enqueue( value );
}
public V Dequeue() {
// will throw if there isn’t any first element!
var pair = list.First();
var v = pair.Value.Dequeue();
if ( pair.Value.Count == 0 ) // nothing left of the top priority.
list.Remove( pair.Key );
return v;
}
public bool IsEmpty {
get { return !list.Any(); }
}
}
//---------------------------------------------------------------
FYI I recently published a high speed priority queue meant specifically for use with A*. I've found it can over double the speed of an A* implementation versus using SortedDictionary
. I am still writing up the documentation, I hope to finish it tonight. I have not tried it with Unity/$$anonymous$$ono yet, so no promises :)
@SinisterRainbow thank you for all the documentation! For some odd reason even when I changed the "getAdjacentTiles" to the proper direction is still froze up and spat out the issue again after a few $$anonymous$$utes. As of right now I have just put diagonal searching to the back burner due to the fact everything work without it.
Additionally I have a new problem. I am putting in some breaking points in the script that if it discovers there is no path possible to stop searching. However I am getting "Object reference not set to an instance of an object". So this is going to be my focus right now.
@BlueRaja This all looks really great, but I am not sure how I would totally implement it with where I am at on my project. But thank you though!
@blueRaja, $$anonymous$$d posting back when you're finished?
Hey guys, I think I finished it up. This was meant to be only a tech demo and I only gave myself 2 weeks to do it before i move onto something (Leap Camera Development!). But, I wanted to just write back and say thanks for the help. Enjoy.
https://dl.dropboxusercontent.com/u/21406099/Interactive_AStar/WebPlayer.html
Your answer
![](https://koobas.hobune.stream/wayback/20220613105026im_/https://answers.unity.com/themes/thub/images/avi.jpg)
Follow this Question
Related Questions
How to apply A* algorithm in C#? 2 Answers
Inaccurate A* Pathfinding Scan! 3 Answers
Lost in Pathfinding 1 Answer