Path finding algorithm became infinite loop-CodePudding

I am developing GUI for algorithm which finds path on grid GUI. Starting point is always 0,0 and is where starfish is located! For calculating destination I am using Random class which generates random x, y depending on grid bounds(of course). I opened debugger debugger results and see that my algorithm became infinite loop and is not able to find path, because at some point starfish starts moving left-right again and again, simply waste of moves. How can i solve this bug, I have hard time on solving it, can anyone help?

private Queue<Point> findPath(Rectangle[][] matrix, Point destPoint) {
    Point move = null;
    var dir = new ArrayList<Point>();
    dir.add(new Point(1, 0)); // right
    dir.add(new Point(0, 1)); // down
    dir.add(new Point(-1, 0)); // left
    dir.add(new Point(0, -1)); // up

    Point start = new Point(0, 0);
    var tmpPath = new ArrayDeque<Point>();
    var path = new ArrayDeque<Point>();
    tmpPath.add(new Point(0, 0));

    while (!tmpPath.isEmpty()) {

        for (int dc = 0; dc < dir.size(); dc  ) {
            move = new Point(start.x()   dir.get(dc).x(), start.y()   dir.get(dc).y());
            if (!move.isValid(matrix[0].length, matrix.length)) {
                continue;
            }
            if (matrix[move.y()][move.x()].getFill() != Color.MAGENTA) {
                start = move;
                tmpPath.add(move);
                path.add(tmpPath.poll());
                System.out.println(path.peek());
                if (path.getLast().equals(destPoint)) {
                    path.poll();
                    return path;
                }
                break;
            }
        }
    }
    return null;
}

Explanation: my method adds all walked path in a queue which if path is found(or when starfish will arrive at destination) will be returned! Color.MAGENTA is considered as wall, if i click on rectangle on my GUI, rectangles color will be assigned to MAGENTA.


I am stuck at solving the bug! Project Repository: https://github.com/gchapidze/maze-solver

CodePudding user response：

This is a bit of a traditional pathfinding approach. You need to keep track of all of your possible paths.

You start at point A, aka path 0. You start by "opening" the path. You go through all of the valid moves for each move you add a new path.

Now you grab the next viable path, then you "open" that path by removing it from the list, and adding a new path for each possible move.

The type of pathfinding algorithm you use determines how you find the next viable path.

In your case, your paths are just a Deque of Points, so you can keep track of your paths with a.

I would select the next path using the length. That way you'll perform a depth first search, which is basically what you're doing.

Point start = new Point(0, 0);
//var tmpPath = new ArrayDeque<Point>(); obsolete
var path = new ArrayDeque<Point>();
//tmpPath.add(new Point(0, 0)); obsolete

Deque<Deque<Point>> availablePaths = new ArrayDeque<>();

//initialize space
path.add(start);
availablePaths.add(path);

while (!availablePaths.isEmpty()) {
    //removes the last element, which will be a depth first search.
    path = availablePaths.removeLast();
    //check for success.
    if (path.getLast().equals(destPoint)) {
        //path.poll(); 
        return path;
    }
    //open the current path.
    start = path.getLast();
    for (int dc = 0; dc < dir.size(); dc  ) {
        move = new Point(start.x()   dir.get(dc).x(), start.y()   dir.get(dc).y());
        if (!move.isValid(matrix[0].length, matrix.length)) {
            continue;
        }
        if(path.contains(move){
            continue; //this prevents the path from walking on itself.
        }
        if (matrix[move.y()][move.x()].getFill() != Color.MAGENTA) {
            //start = move; obsolete.
            // tmpPath.add(move); obsolete
            var newPath = new ArrayDeque(path);
            newPath.add(move);
            //moved the check for complete to the start of the loop!
            availablePaths.add(newPath);
            //break; don't break when you find a possible path.
            //get all possible paths, and explore in the next loop.
        }
    }
}

I've updated this to have an example using your code. I've commented out the code of yours I would remove or change and added the other code.

The main difference is there are a lot of paths that it keeps track of. This prevents the paths from overlapping. Also if a path becomes a dead end, it will not ruin the algorithm. If there is a path, this should find it.