6 added 114 characters in body edited Jun 21 '11 at 1:16 Tashu 19122 silver badges99 bronze badges 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 OP O O O O T O O O O O T OP 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 OP O O O O O O O O T T O OP O O O O O O O O O O O O O O O O O O  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. O O O O O O O O T O O O O O O O O O O T O O O O O T O 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 O O O O O O O O O T T O O O O O O O O O O O O O O O O O O O O  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  5 added 380 characters in body edited Jun 21 '11 at 1:09 Tashu 19122 silver badges99 bronze badges 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. O O O O O O O O T O O O O O O O O O O T O O O O O T O 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 O O O O O O O O O T T O O O O O O O O O O O O O O O O O O O O  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. O O O O O O O O T O O O O O O O O O O T O O O O O T O 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 O O O O O O O O O T T O O O O O O O O O O O O O O O O O O O O  4 added 486 characters in body edited Jun 21 '11 at 0:49 Tashu 19122 silver badges99 bronze badges private List 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 openList = new ArrayList(); List closedList = new ArrayList(); List bestList = new ArrayList(); 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 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; } public double getPassThrough(Cell goal) { if (start) { return 0.0; } return getLocalCost(goal) + getParentCost(); } enter public codedouble heregetLocalCost(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; }  private List 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 openList = new ArrayList(); List closedList = new ArrayList(); List bestList = new ArrayList(); 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 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; } public double getPassThrough(Cell goal) { if (start) { return 0.0; } return getLocalCost(goal) + getParentCost(); } enter code here  private List 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 openList = new ArrayList(); List closedList = new ArrayList(); List bestList = new ArrayList(); 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 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; } 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; }  3 added 191 characters in body edited Jun 20 '11 at 21:03 Tashu 19122 silver badges99 bronze badges 2 deleted 5 characters in body; edited title edited Jun 20 '11 at 15:40 Josh 95.4k1717 gold badges215215 silver badges334334 bronze badges 1 asked Jun 19 '11 at 23:46 Tashu 19122 silver badges99 bronze badges