Astar algorithm, problem

[Robbo]

Hello,

I work on some program to move a robot
through a random maze. To count path
from place A to place B I use A* (Astart)
algorithm. But, sometimes (in rare cases)
A* is unnable to find path (but path do
exists -- just A* can not find it).
Is it normal that A* in some cases is
unnable to find path or there is probably
some error in my implementation of A*?

Thanks in advance for suggestions.

[D Herring]

Robbo wrote:
> sometimes (in rare cases)
> A* is unnable to find path (but path do
> exists -- just A* can not find it).
> Is it normal that A* in some cases is
> unnable to find path or there is probably
> some error in my implementation of A*?

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
http://en.wikipedia.org/wiki/A*_search_algorithm

- Daniel

[Robbo]

> 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
> http://en.wikipedia.org/wiki/A*_search_algorithm

Thanks for Your answer. I will compare my implementation
with others. Btw. I use this implementation:
http://sebastianpawlak.com/pl/Informatyka/Artykuly/Astar/index.html

Robbo

[whe...@gmail.com]

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

[Robbo]

> 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 !=
0));

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

[Robbo]

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.

[Robbo]

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;