# Infinite loop during A* algorithm

The A* algorithm is used by enemies to have a path to the goal. It's working but when sometimes I placed a tower in a grid (randomly) it produces a stack overflow error. The A* algorithm would iterate the enemy and find its path and pass the list to the enemy's path.

I added debug logs and the list that I'm getting it looks like it would arrive from start cell to goal cell.

Here's the log -

``````06-19 19:26:41.982: DEBUG/findEnemyPath, enemy X:Y(4281): X2.8256836:Y3.5
06-19 19:26:41.990: DEBUG/findEnemyPath, grid X:Y(4281): X3:Y2
06-19 19:26:41.990: DEBUG/START CELL ID:(4281): 38
06-19 19:26:41.990: DEBUG/GOAL CELL ID:(4281): 47
06-19 19:26:41.990: DEBUG/Best : 38(4281):  passThrough:0.0
06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 38
06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 38
06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 38
06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 38
06-19 19:26:41.990: DEBUG/Best : 39(4281):  passThrough:8.875
06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 39
06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 39
06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 39
06-19 19:26:41.990: DEBUG/Best : 40(4281):  passThrough:7.9375
06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 40
06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 40
06-19 19:26:41.990: DEBUG/Best : 52(4281):  passThrough:8.9375
06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 52
06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 52
06-19 19:26:41.990: DEBUG/Best : 53(4281):  passThrough:7.96875
06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 53
06-19 19:26:41.990: DEBUG/Best : 28(4281):  passThrough:8.9375
06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 28
06-19 19:26:41.990: DEBUG/Best : 65(4281):  passThrough:8.984375
06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 65
06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 65
06-19 19:26:41.990: DEBUG/Best : 66(4281):  passThrough:7.9921875
06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 66
06-19 19:26:42.000: DEBUG/Best : 78(4281):  passThrough:8.99609375
06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 78
06-19 19:26:42.000: DEBUG/Best : 79(4281):  passThrough:7.998046875
06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 79
06-19 19:26:42.000: DEBUG/Best : 80(4281):  passThrough:6.9990234375
06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 80
06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 80
06-19 19:26:42.000: DEBUG/Best : 81(4281):  passThrough:5.99951171875
06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 81
06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 81
06-19 19:26:42.000: DEBUG/Best : 82(4281):  passThrough:4.999755859375
06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 82
06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 82
06-19 19:26:42.000: DEBUG/Best : 83(4281):  passThrough:3.9998779296875
06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 83
06-19 19:26:42.000: DEBUG/Best : 71(4281):  passThrough:2.99993896484375
06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 71
06-19 19:26:42.000: DEBUG/Best : 59(4281):  passThrough:1.99951171875
06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 59
06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 59
06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 59
06-19 19:26:42.000: DEBUG/Best : 47(4281):  passThrough:0.99951171875
``````

Then, the goal cell would be iterating its parent till start cell to break off the loop.

``````private void populateBestList(Cell cell, List<Cell> bestList) {

if (cell.parent.start == false) {
Log.d("ID:", ""+cell.id);
Log.d("ParentID:", ""+cell.parent.id);
populateBestList(cell.parent, bestList);
}
return;
}
``````

The log with error above would show like this -

``````06-19 19:26:42.010: DEBUG/ID:(4281): 47
06-19 19:26:42.010: DEBUG/ParentID:(4281): 59
06-19 19:26:42.010: DEBUG/ID:(4281): 59
06-19 19:26:42.010: DEBUG/ParentID:(4281): 71
06-19 19:26:42.010: DEBUG/ID:(4281): 71
06-19 19:26:42.010: DEBUG/ParentID:(4281): 59
06-19 19:26:42.010: DEBUG/ID:(4281): 59
06-19 19:26:42.010: DEBUG/ParentID:(4281): 71
06-19 19:26:42.010: DEBUG/ID:(4281): 71
``````

71 and 59 would switch over and goes on.

I thought the grid is the issue due to the fact that enemies are using the single grid so I make the parent, start, and goal clear before starting the A* algorithm for an enemy.

``````for(int i = 0; i < GRID_HEIGHT; i++) {
for(int j = 0; j < GRID_WIDTH; j++) {
grid[i][j].parent = null;
grid[i][j].start = false;
grid[i][j].goal = false;
}
}
``````

That didn't work. I thought it might be something related to this code, but not sure if I'm on right track -

``````neighbor.parent = best;
openList.remove(neighbor);
closedList.remove(neighbor);
``````

Here's the code of the A* algorithm -

``````private List<Cell> findEnemyPath(Enemy enemy) {

for(int i = 0; i < GRID_HEIGHT; i++) {
for(int j = 0; j < GRID_WIDTH; j++) {
grid[i][j].parent = null;
grid[i][j].start = false;
grid[i][j].goal = false;
}
}

List<Cell> openList = new ArrayList<Cell>();
List<Cell> closedList = new ArrayList<Cell>();
List<Cell> bestList = new ArrayList<Cell>();

int width = (int)Math.floor(enemy.position.x);
int height = (int)Math.floor(enemy.position.y);

width = (width < 0) ? 0 : width;
height = (height < 0) ? 0 : height;

Log.d("findEnemyPath, enemy X:Y", "X"+enemy.position.x+":"+"Y"+enemy.position.y);
Log.d("findEnemyPath, grid X:Y", "X"+height+":"+"Y"+width);
Cell start = grid[height][width];
Cell goal = grid[ENEMY_GOAL_HEIGHT][ENEMY_GOAL_WIDTH];

if(start.id != goal.id) {

Log.d("START CELL ID: ", ""+start.id);
Log.d("GOAL CELL ID: ", ""+goal.id);
//Log.d("findEnemyPath, grid X:Y", "X"+start.position.x+":"+"Y"+start.position.y);
start.start = true;
goal.goal = true;

while(openList.size() > 0) {
Cell best = findBestPassThrough(openList, goal);
//Log.d("ID:", ""+best.id);
openList.remove(best);
if (best.goal) {
System.out.println("Found Goal");
System.out.println(bestList.size());
populateBestList(goal, bestList);
/*
for(Cell cell : bestList) {
Log.d("ID:", ""+cell.id);
Log.d("ParentID:", ""+cell.parent.id);
}
*/
Collections.reverse(bestList);
Cell exit = new Cell(13.5f, 3.5f, 1, 1);
exit.isExit = true;
//Log.d("PathList", "Enemy ID : " + enemy.id);
return bestList;
}
else {
List<Cell> neighbors = getNeighbors(best);
for (Cell neighbor : neighbors) {
if(neighbor.isTower) {
continue;
}
if (openList.contains(neighbor)) {
Cell tmpCell = new Cell(neighbor.position.x, neighbor.position.y, 1, 1);
tmpCell.parent = best;
if (tmpCell.getPassThrough(goal) >= neighbor.getPassThrough(goal)) {
continue;
}
}
if (closedList.contains(neighbor)) {
Cell tmpCell = new Cell(neighbor.position.x, neighbor.position.y, 1, 1);
tmpCell.parent = best;
if (tmpCell.getPassThrough(goal) >= neighbor.getPassThrough(goal)) {
continue;
}
}
Log.d("Neighbor's Parent: ", ""+best.id);
neighbor.parent = best;
openList.remove(neighbor);
closedList.remove(neighbor);
}
}
}
}
Log.d("Cannot find a path", "");
return null;
}

public double getPassThrough(Cell goal) {

if (start) {
return 0.0;
}

return getLocalCost(goal) + getParentCost();
}

public double getLocalCost(Cell goal) {
if (start) {
return 0.0;
}

localCost = 1.0 * (Math.abs(this.position.x - goal.position.x) + Math.abs(this.position.y - goal.position.y));
return localCost;
}

public double getParentCost() {

if (start) {
return 0.0;
}

if (parentCost == 0.0) {
parentCost = 1.0 + .5 * (parent.getParentCost() - 1.0);
}

return parentCost;
}
``````

When the error occurs - O is empty, X is a tower. S is start, goal is G. The enemy would be created before the Start cell and proceed its path to goal. The infinite parent would happen - P. it looks like it'll happen in two places. one s to left and other s bottom.

``````O O O O O O O O T O O O
O O P O O O O T O O O O
O T P O O O T O O O O O
S T O O O O O O O O O G
O T O O T P O O O O O O
O O T T O P O O O O O O
O O O O O O O O O O O O
``````
-
Is one (or more) of the functions that you are calling within the file a recursive function? Have you stepped through it with a debugger to find out what function is causing the stack overflow? Are variables always the same value when it breaks i.e. it always throws an exception at the same point in time? – Ray Dey Jun 20 '11 at 1:57
populateBestList() is the recursive function in question. (Although why this wasn't stated explicitly, I don't know. The original poster might do well to learn about using a debugger.) – Kylotan Jun 20 '11 at 12:13
The stack overflow error is coming from bestList.add(cell); The strange thing is the A star code would generate the A point to B point and this function would have different parents. I am not sure about an exception at the same point in time, i think I saw same start id, and goal id where the error starts. I'll check on it. – Tashu Jun 20 '11 at 21:08
Is one (or more) of the functions that you are calling within the file a recursive function? Yes, only one function, it's calling itself till it gets to the start cell. Have you stepped through it with a debugger to find out what function is causing the stack overflow? Yes. I see the infinite parent. I'll be going to see how it occurs before that method. Are variables always the same value when it breaks i.e. it always throws an exception at the same point in time? Yes. It looks like it would happen when it goes around. Putting the visual aid above. – Tashu Jun 21 '11 at 1:04
I'm curious about the line `if (closedList.contains(neighbor))`. Usually in A*, once a cell has entered the closed list, it never ever comes out again. You seem to be taking nodes out of the closed list and traversing them again, which will cause problems. Also as Kylotan mentions below, your estimate is invalid because of your strange `getParentCost` formula. – Paul Z Jun 21 '11 at 21:30

Right, so it looks like you're calling populateBestList recursively forever. This would happen if your linked list of Cell.parent values is circular for some reason.

Normally, this isn't possible, because you only ever set a parent value on a node just taken off the open list, and you set it to point to a cell you already handled and put on the closed list, and so the parent links would always point backwards along the nodes you 'closed' further into the past.

However, if a closed node were to end up back in the open list, you could end up creating a parent loop, because the node you set its parent to may already point back at this one - or, it might point to a node whose parent points back to this one, and so on. And then after creating this cycle, if any of the cycle appears in the final path, you'll be unable to complete the path and will get the error you see.

You do have code which potentially resurrects nodes from the closed list, back into the open list, based on these `getPassThrough` values. So, I would suggest double checking getPassThrough - is that definitely handling distance travelled + estimated distance remaining properly? Is it possible that it is wrongly saying that you reached a cell on the closed list by a cheaper path, and thus putting it back on the open list when it shouldn't be? If getPassThrough gets the costs wrong then the parenting links will also end up wrong.

-
Right, the logging message shows that the start cell to the goal cell is already made and then iterate its parent. I don't understand when I logged the 'Neighbor's Parent:', I don't see any infinite recursive in the block of A star code. I double checked the getpassThrough, it looks it's okay. I'll add passThrough code above. – Tashu Jun 20 '11 at 21:02
You've still not shown how getPassThrough calculates the costs, because we have no idea what getLocalCost() or getParentCost() do. For this to be A* you MUST be counting the cost of the path so far AND the estimated distance yet to travel, and you need to be using this when deciding which node to take off the open list. – Kylotan Jun 20 '11 at 22:14
Sorry, I thought I pasted the code. I added the two methods above. – Tashu Jun 21 '11 at 1:02
Your getParentCost formula doesn't make sense, as it converges towards 1, with each step costing less than the one before. This means your Manhattan heuristic becomes invalid as it ends up being an overestimate rather than an underestimate. I can't completely understand why this would create the parenting loop, but it might be because this invalid heuristic is making previously-explored cells seem more attractive than they should be. – Kylotan Jun 21 '11 at 17:15
I see. I'll google around to find out more about the heuristic formula. Thanks for pointing out. I modified the code from memoization.com/2008/11/30/a-star-algorithm-in-java It seems it's not good for this situation. Thanks for help! – Tashu Jun 23 '11 at 1:55

Maybe the width and height are exchanged.

In the loops:

``````for(int i = 0; i < GRID_HEIGHT; i++) {
for(int j = 0; j < GRID_WIDTH; j++) {
``````

you use i for height, and j for width

In the cell:

``````int width = (int)Math.floor(enemy.position.x);
int height = (int)Math.floor(enemy.position.y);
``````

x is used to width.

I suspect this because usually x is related to i, and y to j and your case is backward.

-
I don't think that's the issue, the cell position is based on height, width. – Tashu Jun 20 '11 at 0:35