Astar algorithm, problem

If one or more paths exist, A* should find the shortest one. I suspect a bug in your implementation, in how the connectivity graph was defined, or in a related detail.

You could compare your code to the wikipedia entry

- Daniel

Thanks for Your answer. I will compare my implementation with others. Btw. I use this implementation:

Also, you can try setting the A* heuristic to 0...the algorithm should then be comparable to Dijkstra and if a path exists, it should find it. - -Win

In my algorithm heuristic is set to 0 -- each edge, cell or how you call it is equal.

It is my java implementation of A*. At the moment, unfortunately I can not see any error... but it must be somewhere there because in rare cases this algorithm falls in the sense that it can not find path, even if some exists.

The representation of maze is just 2D array. Even cells of array is for cells of maze. Odd cells of array is for walls or openings between cells of maze.

private static boolean computeShortestPath(int destX, int destY, boolean displayRoute) {

//ratX, ratY is beginning position of the robot //destX, destY is desired end position of the robot

int pointsTmp = points;

// copy maze int mazePathNumbers[][] = new int[N][N]; // LenMapa for (int x = 0; x < N; x++) for (int y = 0; y < N; y++) mazePathNumbers[x][y] = 0xffff;

class Pair { int x, y; Pair(int x, int y){this.x=x;this.y=y;}};

Pair positionOfNodes[] = new Pair[500]; // WezlyPoz positionOfNodes[0] = new Pair(ratX, ratY);

int lengths[] = new int[500]; lengths[0] = ((ratX - destX) * (ratX - destX) + (ratY - destY) * (ratY - destY));

mazePathNumbers[ratX][ratY] = 0;

int nodeNumber = 1;

int shortestPath = 0; Pair pos = null; do { for (int i = 0; i < nodeNumber; i++) if (lengths[i] < lengths[shortestPath]) shortestPath = i;

pos = positionOfNodes[shortestPath]; positionOfNodes[shortestPath] = positionOfNodes[nodeNumber - 1]; lengths[shortestPath] = lengths[nodeNumber - 1]; nodeNumber--;

int x, y;

// createNode(0, -2); x = 0; y = -1; if ((mazePathNumbers[pos.x + x + x][pos.y + y + y] == 0xffff) && (maze[pos.x + x][pos.y + y] == DISCOVERED_OPENING) && (maze[pos.x + x + x][pos.y + y + y] == DISCOVERED_SQUARE)) {

mazePathNumbers[pos.x + x + x][pos.y + y + y] = mazePathNumbers[pos.x][pos.y] + 1; positionOfNodes[nodeNumber] = new Pair(pos.x + x + x, pos.y

• y + y); lengths[nodeNumber] = (((pos.x+x+x)-destX)*((pos.x+x+x)-destX)+

((pos.y+y+y)-destY)*((pos.y+y+y)-destY)); nodeNumber++; }

//createNode(0, 2); x = 0; y = 1; if ((mazePathNumbers[pos.x + x + x][pos.y + y + y] == 0xffff) && (maze[pos.x + x][pos.y + y] == DISCOVERED_OPENING) && (maze[pos.x + x + x][pos.y + y + y] == DISCOVERED_SQUARE)) {

mazePathNumbers[pos.x + x + x][pos.y + y + y] = mazePathNumbers[pos.x][pos.y] + 1; positionOfNodes[nodeNumber] = new Pair(pos.x + x + x, pos.y

• y + y); lengths[nodeNumber] = (((pos.x+x+x)-destX)*((pos.x+x+x)-destX)+

((pos.y+y+y)-destY)*((pos.y+y+y)-destY)); nodeNumber++; }

//createNode(-2, 0); x = -1; y = 0; if ((mazePathNumbers[pos.x + x + x][pos.y + y + y] == 0xffff) && (maze[pos.x + x][pos.y + y] == DISCOVERED_OPENING) && (maze[pos.x + x + x][pos.y + y + y] == DISCOVERED_SQUARE)) {

mazePathNumbers[pos.x + x + x][pos.y + y + y] = mazePathNumbers[pos.x][pos.y] + 1; positionOfNodes[nodeNumber] = new Pair(pos.x + x + x, pos.y

• y + y); lengths[nodeNumber] = (((pos.x+x+x)-destX)*((pos.x+x+x)-destX)+

((pos.y+y+y)-destY)*((pos.y+y+y)-destY)); nodeNumber++; }

//createNode(2, 0); x = 1; y = 0; if ((mazePathNumbers[pos.x + x + x][pos.y + y + y] == 0xffff) && (maze[pos.x + x][pos.y + y] == DISCOVERED_OPENING) && (maze[pos.x + x + x][pos.y + y + y] == DISCOVERED_SQUARE)) {

mazePathNumbers[pos.x + x + x][pos.y + y + y] = mazePathNumbers[pos.x][pos.y] + 1; positionOfNodes[nodeNumber] = new Pair(pos.x + x + x, pos.y

• y + y); lengths[nodeNumber] = (((pos.x+x+x)-destX)*((pos.x+x+x)-destX)+

((pos.y+y+y)-destY)*((pos.y+y+y)-destY)); nodeNumber++; }

} while (((pos.x != destX) || (pos.y != destY)) && (nodeNumber !=

String directionString = ""; int step = 0; Pair path[] = new Pair[500]; int pathIndex = 0;

if (nodeNumber != 0) { pos = new Pair(destX, destY); int shortestStep = 0xffff; Pair shortestPos = null; int x = 0, y = 0; boolean isFirstStep = true; while ((pos.x != ratX) || (pos.y != ratY)) { step++;

shortestStep = 0xffff;

//Sprawdz (0,-1); {up} x = 0; y = -1; if ((mazePathNumbers[pos.x + x + x][pos.y + y + y] < shortestStep) && (maze[pos.x+x][pos.y+y] == DISCOVERED_OPENING)){ shortestStep = mazePathNumbers[pos.x+x+x][pos.y+y+y]; shortestPos = new Pair(pos.x+x+x,pos.y+y+y); }

//Sprawdz (1,0); {right} x = 1; y = 0; if ((mazePathNumbers[pos.x + x + x][pos.y + y + y] < shortestStep) && (maze[pos.x+x][pos.y+y] == DISCOVERED_OPENING)){ shortestStep = mazePathNumbers[pos.x+x+x][pos.y+y+y]; shortestPos = new Pair(pos.x+x+x,pos.y+y+y); }

//Sprawdz (0,1); {down} x = 0; y = 1; if ((mazePathNumbers[pos.x + x + x][pos.y + y + y] < shortestStep) && (maze[pos.x+x][pos.y+y] == DISCOVERED_OPENING)){ shortestStep = mazePathNumbers[pos.x+x+x][pos.y+y+y]; shortestPos = new Pair(pos.x+x+x,pos.y+y+y); }

//Sprawdz (-1,0); {left} x = -1; y = 0; if ((mazePathNumbers[pos.x + x + x][pos.y + y + y] < shortestStep) && (maze[pos.x+x][pos.y+y] == DISCOVERED_OPENING)){ shortestStep = mazePathNumbers[pos.x+x+x][pos.y+y+y]; shortestPos = new Pair(pos.x+x+x,pos.y+y+y); }

pos = shortestPos;

path[pathIndex++] = new Pair(shortestPos.x, shortestPos.y); }

myRatX = ratX; myRatY = ratY; myRatDirection = ratDirection;

for (int i = pathIndex - 2; i >= 0; i--) directionString = directionString.concat(addMoveCommand(path[i].x, path[i].y));

directionString = directionString.concat(addMoveCommand(destX, destY)); pointsTmp -= directionString.length();

howManyStepsFromHereToDestination = directionString.length(); } else {

//!!! System.err.println("No path!"); return false; } }

In this example, robot (^) wants to go to place marked by "@". (please copy maze shown below to notepad to have equal wide fonts) . - is cell , - is opening between cells # - wall x - destination position ^ - actual position of robot

# # # # # # # # # . # ###,# # # # # # #^,.# # #,##### # # # # #.,.,.#x # #,###,#,# # # # .,.#.,.,.# ###,#,##### # # # .,.#.,.,.# # ###,###,### # # ,.#.#.#.#.# #####,#,#,#,### # #.,.,.#.,.,.,.# #,#,#######,### # .#.#.,.,.,.#.# ###,#,###,#,#,# # #.,.#.#.,.#.,.# ############### #

# # # # # # # # #

for this maze, my implementation of A* generates such digits:

# # # # # # # # # # 2 # # ### # # # # # # #^ 1# # # # ##### # # # # #1 # # # # ### # # # # # # # # ### # ##### # # # # # # # ### ### ### # # # # # # # # ##### # # # ### # # # # # # # ####### ### # # # # # # ### # ### # # # # # # # # # # ############### #

# # # # # # # # # #

As you can see, it try to go up and generates only two 1 and one 2. Digits even do not connect to destination.

I think, I found the problem:

do { for (int i = 0; i < nodeNumber; i++) if (lengths[i] < lengths[shortestPath]) shortestPath = i;

should be:

do { shortestPath = 0; for (int i = 0; i < nodeNumber; i++) if (lengths[i] < lengths[shortestPath]) shortestPath = i;