Astar algorithm, problem

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.
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
Robbo wrote:

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
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload

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
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload

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
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload

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)};
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); 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); 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); 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); 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; } }
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
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.
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
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;
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload

Polytechforum.com is a website by engineers for engineers. It is not affiliated with any of manufacturers or vendors discussed here. All logos and trade names are the property of their respective owners.