# Dijkstra implementation for maze solving that works fine and returns shortest path

I would like to make my code "prettier" and also speed up the runtime of my implementation. Nodeinfo is literally just an object that holds its "parent node"(the node it came from) and its distance. i try to traverse the graph by finding the distance of the node i want to move to then adding it to a priority queue based on the distance. Is there a better way to do this operation in particular?

int[] start = new int[2] ;
int[] exit = new int[2];
char[][] maze={ {'H','H','H','H','H','H','H','H','H','H','H','H','H','H','H','H'},
{'H','E','.','.','.','H','.','H','.','.','.','.','.','.','H','H'},
{'H','.','H','H','H','.','.','.','.','H','.','H','H','.','.','H'},
{'H','.','H','H','H','.','H','H','.','H','.','H','H','.','H','H'},
{'H','.','.','.','.','.','.','H','.','H','.','.','.','.','H','H'},
{'H','.','H','H','.','.','H','H','.','H','.','H','H','.','.','H'},
{'H','H','.','H','H','.','.','.','.','H','.','.','.','.','H','H'},
{'H','.','.','H','H','.','H','H','H','.','.','H','H','.','H','H'},
{'H','H','.','.','.','.','.','S','.','H','.','.','.','.','H','H'},
{'H','H','H','.','H','H','.','H','.','H','.','H','H','.','.','H'},
{'H','.','H','.','.','.','.','H','.','H','.','H','.','H','.','H'},
{'H','H','.','.','H','H','H','H','.','.','.','H','.','H','.','H'},
{'H','.','H','H','H','.','H','H','H','.','H','.','.','.','.','H'},
{'H','.','.','.','.','.','.','.','.','.','H','.','H','.','H','H'},
{'H','H','H','.','H','.','H','.','H','.','H','.','H','.','H','H'},
{'H','H','H','H','H','H','H','H','H','H','H','H','H','H','H','H'},};
NodeInfo[][] graph = new NodeInfo[maze.length][maze.length];
boolean[][] traversed= new boolean[maze.length][maze.length] ;
for(int r=0;r<maze.length;r++)
{
for(int c=0;c<maze[r].length;c++)
{
if(maze[r][c]=='E')
{
start[0]=r;
start[1]=c;
}
if(maze[r][c]=='S')
{
exit[0]=r;
exit[1]=c;
}
if(maze[r][c]!='H')
{
traversed[r][c]=true;
int[] tempo = {r,c} ;
graph[r][c]=new NodeInfo(tempo);
}
else
{
traversed[r][c]=false;
int[] tempo = {r,c} ;
graph[r][c]=new NodeInfo() ;
}
}
}
boolean canSolve = false;
int minDist =Integer.MAX_VALUE ;
NodeInfo starter = new NodeInfo(start) ;
starter.setDist(0);
PriorityQueue<NodeInfo> q = new PriorityQueue<NodeInfo>(10, new Comparator<NodeInfo>()
{
public int compare( NodeInfo node1, NodeInfo node2)
{
if(node1.getDist()<node2.getDist()) return -1;
if(node1.getDist()>node2.getDist()) return 1;
return 0;
}
}) ;
starter.setPred(null) ;
while(!q.isEmpty())
{
traversed[q.peek().getRay()[0]][q.peek().getRay()[1]]=false;
if(maze[q.peek().getRay()[0]][q.peek().getRay()[1]]=='S')
{
canSolve = true;
int r,c;
r=q.peek().getRay()[0];
c=q.peek().getRay()[1];

if(minDist>graph[r][c].getDist())
minDist=graph[r][c].getDist();
}
if(traversed[q.peek().getRay()[0]][q.peek().getRay()[1]+1]==true)
{
int r,c;
r=q.peek().getRay()[0];
c=q.peek().getRay()[1]+1;
graph[r][c].setDist(q.peek().getDist()+graph[r][c].getEdge());
graph[r][c].setPred(graph[q.peek().getRay()[0]][q.peek().getRay()[1]].getRay());

}
if(traversed[q.peek().getRay()[0]][q.peek().getRay()[1]-1]==true)
{
int r,c;
r=q.peek().getRay()[0];
c=q.peek().getRay()[1]-1;
graph[r][c].setDist(q.peek().getDist()+graph[r][c].getEdge());
graph[r][c].setPred(graph[q.peek().getRay()[0]][q.peek().getRay()[1]].getRay());

}
if(traversed[q.peek().getRay()[0]+1][q.peek().getRay()[1]]==true)
{
int r,c;
r=q.peek().getRay()[0]+1;
c=q.peek().getRay()[1];
graph[r][c].setDist(q.peek().getDist()+graph[r][c].getEdge());
graph[r][c].setPred(graph[q.peek().getRay()[0]][q.peek().getRay()[1]].getRay());

}
if(traversed[q.peek().getRay()[0]-1][q.peek().getRay()[1]]==true)
{
int r,c;
r=q.peek().getRay()[0]-1;
c=q.peek().getRay()[1];
graph[r][c].setDist(q.peek().getDist()+graph[r][c].getEdge());
graph[r][c].setPred(graph[q.peek().getRay()[0]][q.peek().getRay()[1]].getRay());

}
q.poll() ;
}

if(minDist!=Integer.MAX_VALUE)
{
System.out.println(" Number Of Steps Taken : "+minDist + "\n Maze is solvable : " + canSolve) ;
int r,c;
r=exit[0];
c=exit[1];
boolean griph=true;
while(griph)
{

if(griph)
{
int rows=r;
int cols=c;
if(graph[r][c].getPred()==null)
{
griph=false;
}
if(griph==true)
{
if(maze[r][c]=='.')
{
maze[r][c]='x';
}
r=graph[rows][cols].getPred()[0];
c=graph[rows][cols].getPred()[1];
}
}

}
while(!steps.isEmpty())
{
System.out.println(Arrays.toString(steps.pollLast())+" ");
}
}
else
System.out.println("Maze is Solvable : "+canSolve) ;

for(int r= 0; r<maze.length;r++)
{
for(int c= 0; c<maze.length;c++)
{
System.out.print(maze[r][c]+" ");
if(c+1==maze.length)
System.out.println();
}
}


}

• Make your maze generator random, so you can test more cases.
• Avoid using single letter variables (r,c, and q are not good).
• Dont shorten variables either.
• If you find yourself accessing a function to get the same value multiple times, consider storing it to a separate variable for readability.

There are probably more efficient and 'prettier' ways to write your code, but I'm not an expert, so just posting out the things that stuck out to me.

I would parrot what Anton said about variables. You should be able to tell at a glance what type data is stored within a variable, and have a reasonable degree of accuracy of what the actual value is. To this end, your variable names should be descriptive but not so overly verbose that your code looks like a novel.

So instead of r and c, use row and column. Also, I would even consider abstracting the idea of a point in your maze. You are using maze[r][c] quite a lot. Why not create a variable like this: char mazePoint = maze[r][c];. Reading the name mazePoint is much easier on the eyes and brain than maze[r][c]. The idea is you want to remove as much mental computation from your code as possible. Your code should read well.

Next, you dont seem to have any methods. Break this stuff into smaller methods so your code isnt a giant wall of text.

## 1. Declare types as broadly as you can.

I'm thinking of those:

LinkedList<int[]> steps = new LinkedList();
PriorityQueue<NodeInfo> q = new PriorityQueue<NodeInfo>(10, new Comparator<NodeInfo>()


See this questions (and related) to find why.

## 2. Get formatting right

I would like to make my code "prettier"

Spacing is very important. It helps maintain fluidity in your code. There is a standard convention that makes sharing easier. All major IDEs will do that for you for zero effort. No reason not to. You save time, AND your code is prettier. Win-win.

## 3. Extract methods!

This code is one, big, meaty method. You must break it down. Again, IDEs will do that for you in three clicks, with a preview.

Each program has usually many parts:

• Initialize
• Pre-Process
• Process
• Post-Process

Each of those can be extracted into its own method. Having a limited scope, such methods would be shorter, easier to understand.

Those calls:

if(traversed[q.peek().getRay()[0]+1][q.peek().getRay()[1]]==true)
{
int r,c;
r=q.peek().getRay()[0]+1;
c=q.peek().getRay()[1];
graph[r][c].setDist(q.peek().getDist()+graph[r][c].getEdge());
graph[r][c].setPred(graph[q.peek().getRay()[0]][q.peek().getRay()[1]].getRay());
}
if(traversed[q.peek().getRay()[0]-1][q.peek().getRay()[1]]==true)
{
...


They are extremely repetitive. They can be extracted to a for, or better, to a method. Or, better, to a method calling a for on a method.

## 4. Make Objects!

Java is Object-Oriented. You're manipulating buil-in Objects like List, Queue, NodeInfo (what is it by the way?). THose are helpful to you in how they present a consistant logic. Do the same to your own code, make it useful!

You could use more Objects. (Also the top-level class is not shown. This is required for a proper Code Review). Here are Object with useful methods you could make to help you:

• Tile
• int getX()
• int getY()
• boolean isWall()
• Maze
• Tile getTile(Tile tile)
• void setWall(int i, int j)
• int getHeight()
• int getWidth()
• MazeSolver
• List findPath(Tile start, Tile end)

## 5. Separate logic from interface

You're storing logical information using a representation of it. You should split those responsibilities.

The logical information is "is there a wall?" and is best stored as a boolean (for now). Not for reasons of optimization (though it will optimize you program), but because it suits your data better, and is therefore easy to manipulate. Conversely, your data storage (as a char) imposes many limits:

• You only have so much chars available, you can't combine chars (walkable + grass or walkable + door + door_open etc.) which you could with a proper Tile Object
• You must know the convention (char -> what it is), throughout all your code. Changing it someplace will mean you'll have to change it everywhere!
• Parsing char is annoying (always a switch involved)
• No logic can be stored in a char (it is an primitive type).

I recommend using a Tile Object with (for now) just a boolean saying "is_walkable". You will be able to expand on it very easily later on.

Finally on this point, move the System.out.print()` out of your code. Either use a proper logging framework, or rely on rich result Objects to provide insight on the computation status.