Calculating the number of steps it takes to get from point S to F

Question

I have following Java class called TheNewMario. It reads a String path and iterates through the path from S to F. If the path is closed, we assume the runner can jump. The class returns the amount of steps it takes to get from S to F.

I have added two path files. In the first example path, it works fine, but when the path gets bigger it takes longer to execute. I am very sure that the performance of processing a bigger path should not take longer than 30-60 seconds. but in my case it takes over 30 minutes, and does not return an error. I use the BFS (breadth-first search) algorithm.

What can I do to optimize the performance of this?

public class TheNewMario {

    private static int maxX = 0;
    private static int maxY = 0;
    private BufferedReader fileRead = null;
    private static int[][] mapXY;
    private HashSet visitedLocation = new HashSet();

    public static void main(String[] args) {
        TheNewMario mario = new TheNewMario();
        mario.pathFileReader(args);
        System.out.println(mario.bfs());
    }

    private int bfs() {

        Queue<Node> queue = new Queue<Node>();

        for (int y = 0; y < maxY; y++) {
            for (int x = 0; x < maxX; x++) {
                if (mapXY[x][y] == 2) {
                    queue.enqueue(new Node(x, y, 0, 0));
                    visitedLocation.add(new Node(x, y, 0, 0));
                }
            }
        }

        int disCount = 1;

        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                Node node = queue.dequeue();
                if (mapXY[node.posX][node.posY] == 3) {
                    return disCount;
                }

                visitedLocation.add(node);

                ArrayList<Node> results = generateNeighbours(node);

                for (Node in : results) {
                    queue.enqueue(in);
                }
            }
            disCount++;
            System.out.print(".");
            System.out.print(": " + disCount);
        }
        return -1;
    }

    private class Node {
        final int posX;
        final int posY;
        final int velX;
        final int velY;

        public Node(int posX, int posY, int velX, int velY) {
            this.posX = posX;
            this.posY = posY;
            this.velX = velX;
            this.velY = velY;
        }

        @Override
        public boolean equals(Object thatobject) {
            Node that = (Node) thatobject;
            if (this.posX == that.posX && this.posY == that.posY && this.velX == that.velX && this.velY == that.velY)
                return true;
            else return false;

        }

        public int hashCode() {
            String hs = " " + posX + posY + velX + velY;
            return hs.hashCode();
        }
    }

    private ArrayList<Node> generateNeighbours(Node node) {

        ArrayList<Node> neighbours = new ArrayList<Node>();

        for (int x = -1; x < 2; x++) {
            for (int y = -1; y < 2; y++) {
                Node in = new Node(
                        node.posX + node.velX + x,
                        node.posY + node.velY + y,
                        node.velX + x,
                        node.velY + y
                );
                if (in.posX >= 0 &&
                        in.posX < maxX &&
                        in.posY >= 0 &&
                        in.posY < maxY &&
                        mapXY[in.posX][in.posY] %2 == 1  &&
                        !visitedLocation.contains(in)
                        ) {
                    neighbours.add(in);
                }
            }
        }
        return neighbours;
    }

    private void pathFileReader(String[] args) {
        File fileName = new File(args[0]);
        int lineCount = 0;
        String line;
        if (!fileName.exists()) {
            System.out.println(args[0] + " does not exist.");
            return;
        }
        if (!(fileName.isFile() && fileName.canRead())) {
            System.out.println(fileName.getName() + " cannot be read from.");
            return;
        }
        try {
            fileRead = new BufferedReader(new FileReader(fileName));
            maxY = Integer.parseInt(fileRead.readLine());
            maxX = Integer.parseInt(fileRead.readLine());

            mapXY = new int[maxX][maxY];

            while ((line = fileRead.readLine()) != null) {
                for (int x = 0; x < maxX; x++) {
                    switch (line.charAt(x)) {
                        case 32:
                            mapXY[x][lineCount] = 1;
                            break;
                        case 79:
                            mapXY[x][lineCount] = 0;
                            break;
                        case 83:
                            mapXY[x][lineCount] = 2;
                            break;
                        case 70:
                            mapXY[x][lineCount] = 3;
                            break;

                    }
                }
                lineCount++;
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

Path1.txt

40
40
OSOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
O                                      F
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

Path2.txt

80
80
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
S                                                                           OOOO
S                                                                            OOO
S                                                                             OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO     OOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO       OOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO       OOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO       OOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO    OOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO     OOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO       OOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO        OOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO         OOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO       OOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO     OOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO    OOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO    OOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO    OOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO    OOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO    OOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO     OOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO     OOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO     OOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO      OOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO       OOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO        OOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO  FFF   OOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO          OOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOO           OOOOOOOOOOOOO           OOOOOOOOOOOOO           OOO   OO
OO   OOOOOOOO                                                        OOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO              OOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO             OOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO           OOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO        OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO       OOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO  OOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO    OOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO    OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OO
OO    OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO   OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO    OO
OO                                                                            OO
OOO                                                                          OOO
OOOO                                                                        OOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

Answer 1

Initialization / Prep work

• Well one thing that immediately jumps out is your initialization. If you are really trying to squeeze out every bit of performance from your code, then this chunk that is done in the bfs method should be done when reading the file:

Queue<Node> queue = new Queue<Node>();

for (int y = 0; y < maxY; y++) {
    for (int x = 0; x < maxX; x++) {
        if (mapXY[x][y] == 2) {
            queue.enqueue(new Node(x, y, 0, 0));
            visitedLocation.add(new Node(x, y, 0, 0));
        }
    }
}

It's no wonder your code runs very slow, just taking a look at all the work you did in that bfs method is enough to conclude that the performance will not scale very well with larger graphs. I almost have half the mind to say you should refractor by starting over

Generating neighbours

• To eliminate the need for that generateNeighbours method, you should be using an adjacency list representation for your graph. This makes it so that each node already has a list of the other nodes it is connected to. It will also make it easier to extend this program to one that finds the shortest path to the finish because you can decide to represent the edges as objects and store the cost of going from one edge to the other as links joining nodes together.

---

Readability

• Use informative enums to represent key aspects of the graph. This part of your code threw me off a bit.

switch (line.charAt(x)){
    case 32:
        mapXY[x][lineCount] = 1;
        break;
    case 79:
        mapXY[x][lineCount] = 0;
        break;
    case 83:
        mapXY[x][lineCount] = 2;
        break;
    case 70:
        mapXY[x][lineCount] = 3;
        break;
}

Apart from the 32, I had to look up what the other characters meant in ascii and even this required knowing that they are in ascii in the first place.

Something like this would have been much easier to understand at first glance

switch (line.charAt(x)){
    case ' ':
        mapXY[x][lineCount] = Point.SPACE;
        break;
    case 'O':
        mapXY[x][lineCount] = Point.PATH;
        break;
    case 'S':
        mapXY[x][lineCount] = Point.START;
        break;
    case 'F':
        mapXY[x][lineCount] = Point.FINISH;
        break;
}

Memory

• Don't let that term visited set confuse you. Using a hashset is good and all, but it is a bit of overkill. Graphs and graph algorithms tend to take up a lot of space, so the best way to represent a visited set is to not use a set data structure but to use a boolean array.
• The way to make this work is to number each node with values from 1-n. Then for each visited node, you simply index into the array using the value of the node and set that index to true. This is a more direct, efficient and (dare I say) faster alternative to a hashset

Extras

• You didn't make use of the vel properties of your node class. This may or may not be intentional but every bit of efficiency helps and initializing unused variables is definitely going to hurt performance
• Close a (Buffered)reader when you are done with it or avoid that scenario by making use of a try-with-resources statement
• Do most of the initialization at the start of your program, so generating nodes and so on should be done earlier than later. This makes the code look cleaner than having initializations here and there making the overall look scattered

Answer 2

Since this is Code Review I'll comment on the code style first.

• Avoid mutable static variable at all costs. They are just global variables.
• It contains a lot of magic numbers. What is 0, 1, 2, 3 in mapXY? Yes I know it was set in pathFileReader and corresponds to S, F, 0 and space, but I am too lazy to lookup their ASCII code.
• Avoid using implementation type, as in ArrayList. Return a List instead.

And I may have missed something but where did you use Kruskal?

The slowness may due to the fact that the same node can be put in the queue multiple times, since in generateNeighbours you only check against visited nodes, but not common un-visited neighbours of different nodes. Also you did not check visitedLocation to avoid run generateNeighbours again for those nodes.

Also the answer would be incorrect since the steps increment regardless, even if Mario is on the wrong path. It is the number of node visited, not the number of steps taken.

If you still find it slow given that you ensure all node visited at most once, further optimization can be done using heuristics. Instead of stride on random paths, you may check the node that is nearest (ignoring obstacles) to the end point first. You can use a heap data structure (PriorityQueue in java) for quick access to such node. That may contribute to some cleverer guessing instead of fumbling wildly. Look up A* search for more information.