Infinite loop during A* algorithm
- by Tashu
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) {
bestList.add(cell);
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);
openList.add(0, 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;
openList.add(start);
while(openList.size() > 0) {
Cell best = findBestPassThrough(openList, goal);
//Log.d("ID:", ""+best.id);
openList.remove(best);
closedList.add(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;
bestList.add(exit);
//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);
openList.add(0, neighbor);
}
}
}
}
Log.d("Cannot find a path", "");
return null;
}
