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

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 queue = new Queue();

for (int y = 0; y 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)

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.

StackExchange Code Review Q#99151, answer score: 5