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;
}