My pathfinder has problems finding the shortest path.

Question

Hi, I'm having problems with a pathfinder (it's my first, so that was to be expected) : it doesn't always take the shortest way. For example, if I want to go one square down, the path will be : one square left, one down, one right.

public void getSquares(){
        actPath = new String[Map.x][Map.y];
        isDone = new boolean[Map.x][Map.y];
        squareListener = new SquareListener[Map.x][Map.y];
        getSquares2(x,y,0,new String());
    }
    public void getSquares2(int x, int y, int movesused, String path){
        boolean test1 = false;
        boolean test2 = false;
        test1 = (x < 0 || y < 0 || x > Map.x || y > Map.y);
        if(!test1){
            test2 = Map.landTile[y][x].masterID != 11;
        }
        if(movesused <= 6 && (test1 || test2)){
            addMoveSquare2(x,y, path);
            getSquares2(x+1,y,movesused+1,path+"r");
            getSquares2(x,y+1,movesused+1,path+"d");
            getSquares2(x,y-1,movesused+1,path+"u");
            getSquares2(x-1,y,movesused+1,path+"l");
        }
    }
    public void addMoveSquare2(int x, int y, String path){
        if(x >= 0 && y>=0 && x < Map.x && y < Map.y && (actPath[x][y] == null || actPath[x][y].length() > path.length())){
            if(squareListener[x][y] == null){
                actPath[x][y] = new String();
                actPath[x][y] = path;
                JLabel square = new JLabel();
                square.setBounds(x*16,y*16,16,16);
                square.setIcon(moveSquare);
                squareListener[x][y] = new SquareListener(x,y,path);
                square.addMouseListener(squareListener[x][y]);
                Map.cases.add(square);
            }
            else{
                squareListener[x][y].path = path;
            }
        }
    }

SquareListener is a simple MouseListener which print the square's location and the path to it. Map.x, Map.y are the map size. getSquares2 is called with the start point, and draw every squares that are 6 moves away, and consider every case with the value "11" as obstacle.

Can you please help me finding what I've done wrong ?

Here is a screenshot of the result : http://img808.imageshack.us/img808/96/screen.gif The red squares are the possible goal. The real one will be defined only when the player click on one square (the MouseListener being SquareListener, it's supposed to know the path to take). The houses are the cases with a value of "11", the obstacles.

Answer 1

You might be interested in this tutorial on the A* search algorithm.

Answer 2

You can take a look here at my answer with example code for A-Star, not a direct answer but the code is readable and it points you to a good book that deals (among many other things) path finding. I never did get around to commenting the code...

Not sure what you mean, in the comment for Daniel, by "Thanks for the link, however, I don't have 1 goal but a number of moves, which makes a lot of possible goals."

Answer 3

Your algorithm looks nearly correct. Nearly, because you forget to assign actPath[x][y] when a second path to the node is found, rendering your length check with actPath[x][y] incorrect. You should do:

        else{
            actPath[x][y] = path;             
            squareListener[x][y].path = path;
        }

Your algorithm also has abominable time complexity, as it will iterate all paths of length 6 (all 4^6 = 4096 of them) instead of the just the shortest ones (6*6 + 5*5 = 61)

For inspiration, I recommend looking at Dijkstra's algorithm (the precursor to A*), which manages to only visit the shortest paths and concludes in O(number of reachable nodes) when path lengths are small integers as it the case here.