The goal is to draw a maze after resolving it (using BFS) with the shortest path from start to exit.
OUTPUT must be like this
***************************************************
[20,19]
***************************************************
#####################
..#...........#.....#
#.#.#########.#.###.#
#...#.........#.#...#
###############.#.###
#.....#.......#.#...#
#.#######.###.#.#.#.#
#...#...#...#...#.#.#
###.###.###.###.#.#.#
#.#.#.#...#.#...#.#.#
#.#.#.#.#1#.#.###.#.#
#...#.#.#1#.#...#.#.#
#####.###1#.#####.###
#.#1111111#.#...#...#
#.#1#######.#.#.###.#
#.#1#...#...#.#.#...#
#.#1###.#.#####.#####
#.#11111111111111111#
#.##.####.#########1#
#..................11
#####################
There are many path to go to the exit [20,19] , but we must draw with the shortest path.
My code is below but it doesn't print the shortest path.
CODE
class Maze {
public static void main(String args[]) {
int W = 21;
int H = 21;
int X = 9;
int Y = 10;
String[] mazeString = {
"##########.##########",
"..#...........#.....#",
"#.#.#########.#.###.#",
"#...#.........#.#...#",
"###############.#.###",
"#.....#.......#.#...#",
"#.#######.###.#.#.#.#",
"#...#...#...#...#.#..",
"###.###.###.###.#.#.#",
"#.#.#.#...#.#...#.#.#",
"#.#.#.#.#.#.#.###.#.#",
"#...#.#.#.#.#...#.#.#",
"#####.###.#.#####.###",
"#.#.......#.#...#...#",
"#.#.#######.#.#.###.#",
"#.#.#...#...#.#.#...#",
"#.#.###.#.#####.#####",
"#.#.................#",
"#.##.####.#########.#",
"#.........#..........",
"####.######.#########"
};
Node[][] nodes = new Node[W][H];
Node start = null;
List<Node> result = new ArrayList<>();
Boolean[][] visited = new Boolean[W][H];
Boolean[][] blocked = new Boolean[W][H];
Boolean[][] exits = new Boolean[W][H];
for (int i = 0; i < H; i++) {
String R = mazeString[i];
for (int j = 0; j < W; j++) {
Node node = new Node(j, i);
blocked[j][i] = R.charAt(j) == '#';
node.blocked = R.charAt(j) == '#';
exits[j][i] = (!node.blocked) && (i == (H - 1) || j == (W - 1) || i == 0 || j == 0);
visited[j][i] = false;
node.exit = (!node.blocked) && (i == (H - 1) || j == (W - 1) || i == 0 || j == 0);
nodes[j][i] = node;
if (X == j && Y == i) {
start = nodes[j][i];
}
}
}
List<List<Node>> paths = new ArrayList<>();
findExits(start, nodes, visited, W, H, result, paths);
if (!result.isEmpty()) {
Collections.sort(result, new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
if (Integer.compare(o1.x, o2.x) == 0) {
return Integer.compare(o1.y, o2.y);
} else {
return Integer.compare(o1.x, o2.x);
}
}
});
}
for (List<Node> path : paths) {
System.out.println("***************************************************");
System.out.println("[" + path.get(0).x + "," + path.get(0).y + "]");
System.out.println("***************************************************");
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
String s = blocked[j][i] ? "#" : path.contains(new Node(j, i)) ? "1" : ".";
System.out.print(s);
}
System.out.println("");
}
}
}
public static void findExits(Node start, Node[][] nodes, Boolean[][] visited, int W, int H, List<Node> result, List<List<Node>> paths) {
int x = start.x;
int y = start.y;
visited[x][y] = true;
if (start.exit) {
result.add(start);
visited[x][y] = false;
List<Node> path = new ArrayList<Node>();
while (start.parent != null) {
path.add(start);
start = start.parent;
}
path.add(start);
paths.add(path);
}
//TOP
if ((y - 1) >= 0) {
if (!visited[x][y - 1] && (!nodes[x][y - 1].blocked)) {
nodes[x][y - 1].parent = start;
findExits(nodes[x][y - 1], nodes, visited, W, H, result, paths);
}
}
//BOT
if ((y + 1) < H) {
if (!visited[x][y + 1] && (!nodes[x][y + 1].blocked)) {
nodes[x][y + 1].parent = start;
findExits(nodes[x][y + 1], nodes, visited, W, H, result, paths);
}
}
//LEFT
if ((x - 1) >= 0) {
if (!visited[x - 1][y] && (!nodes[x - 1][y].blocked)) {
nodes[x - 1][y].parent = start;
findExits(nodes[x - 1][y], nodes, visited, W, H, result, paths);
}
}
//RIGHT
if ((x + 1) < W) {
if (!visited[x + 1][y] && (!nodes[x + 1][y].blocked)) {
nodes[x + 1][y].parent = start;
findExits(nodes[x + 1][y], nodes, visited, W, H, result, paths);
}
}
}
public static class Node {
public int x, y;
boolean blocked = false;
boolean exit = false;
Node parent = null;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final Node other = (Node) obj;
if (this.x != other.x) {
return false;
}
if (this.y != other.y) {
return false;
}
return true;
}
}
}
I want to solve a maze and print the shortest path from start to exit usign BFS. I already solve the maze but my code doesnt print the shortest path, this is my problem.
NB (Additional informations, not questions) :
Please review the following code. It lets you printout all paths found, as well as the shortest one found.
I did not change nor checked the search algorithm. I think it needs more work because I think it does not find the shortest path possible to each exit. I will look into it later.
I did not figure out yet what is the use of List<Node> result. Also I did not see you implement backtracking.
class Maze {
private static char NUMBER_SIGN = '#', DOT = '.', START = 'S';
private static char EXIT = 'E', PATH = '1';
private static Node[][] nodes;
private static Node start;
private static boolean[][] visited; //no need to use Boolean
//exit holds the same information as Node.blocked. No need to duplicate
//private static boolean[][] blocked;
//exit holds the same information as Node.exit. No need to duplicate
//private static boolean[][] exits;
private static int mazeWidth, mazeHeight, startH, startW; //use meaningful names
private static List<List<Node>> paths;
public static void main(String args[]) {
mazeWidth = 21;//use meaningful names
mazeHeight = 21;
startH = 9; startW = 10;
String[] mazeData = getMazeData() ;
makeMaze(mazeData);
drawMaze(); //draw maze as built from input data
List<Node> result = new ArrayList<>();
paths = new ArrayList<>();
findExits(start, nodes, visited, mazeWidth, mazeHeight, result, paths);
if (!result.isEmpty()) {
Collections.sort(result, new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
if (Integer.compare(o1.x, o2.x) == 0) {
return Integer.compare(o1.y, o2.y);
} else {
return Integer.compare(o1.x, o2.x);
}
}
});
}
drawAllPaths(); // see all paths found
List<Node> shortestPath = getShortestPath();
drawShortestPath(shortestPath);
}
private static void drawMaze() {
System.out.println("***************************************************");
System.out.println("Maze as defined by input");
System.out.println("***************************************************");
drawMaze(null);
}
private static void drawAllPaths() {
for (List<Node> path : paths) {
System.out.println("***************************************************");
System.out.println("Path to exit ["
+ path.get(0).x + "," + path.get(0).y + "] length:"+ path.size());
System.out.println("***************************************************");
drawMaze(path);
}
}
private static void drawShortestPath(List<Node> path) {
System.out.println("***************************************************");
System.out.println("Shortest path is to exit ["
+ path.get(0).x + "," + path.get(0).y + "] length:"+ path.size());
System.out.println("***************************************************");
drawMaze(path);
}
private static void drawMaze(List<Node> path) {
for(Node[] row : nodes ) {
for(Node node : row) {
char c = node.getGraphics();
if ((path != null) && path.contains(node)) {c = PATH;}
System.out.print(c);
}
System.out.println("");
}
}
private static void makeMaze(String[] mazeData) {
nodes = new Node[mazeHeight][mazeWidth];
visited = new boolean[mazeHeight][mazeWidth];
for (int height = 0; height < mazeHeight; height++) {
String row = mazeData[height];
for (int width = 0; width < mazeWidth; width++) {
Node node = new Node(height, width);
node.blocked = row.charAt(width) == NUMBER_SIGN;
visited[width][height] = false;
node.exit = (!node.blocked) && ((height == (mazeHeight - 1)) ||
(width == (mazeWidth - 1)) || (height == 0) || (width == 0));
nodes[height][width] = node;
}
}
start = nodes[startH][startW];//no need to set it in the loop
}
//use boolean instead of Boolean
private static void findExits(Node start, Node[][] nodes,
boolean[][] visited, int W, int H, List<Node> result, List<List<Node>> paths) {
int x = start.x;
int y = start.y;
visited[x][y] = true;
if (start.exit) {
result.add(start);
visited[x][y] = false;
List<Node> path = new ArrayList<>();
while (start.parent != null) {
path.add(start);
start = start.parent;
}
path.add(start);
paths.add(path);
}
//TOP
if ((y - 1) >= 0) {
if (!visited[x][y - 1] && (!nodes[x][y - 1].blocked)) {
nodes[x][y - 1].parent = start;
findExits(nodes[x][y - 1], nodes, visited, W, H, result, paths);
}
}
//BOT
if ((y + 1) < H) {
if (!visited[x][y + 1] && (!nodes[x][y + 1].blocked)) {
nodes[x][y + 1].parent = start;
findExits(nodes[x][y + 1], nodes, visited, W, H, result, paths);
}
}
//LEFT
if ((x - 1) >= 0) {
if (!visited[x - 1][y] && (!nodes[x - 1][y].blocked)) {
nodes[x - 1][y].parent = start;
findExits(nodes[x - 1][y], nodes, visited, W, H, result, paths);
}
}
//RIGHT
if ((x + 1) < W) {
if (!visited[x + 1][y] && (!nodes[x + 1][y].blocked)) {
nodes[x + 1][y].parent = start;
findExits(nodes[x + 1][y], nodes, visited, W, H, result, paths);
}
}
}
public static class Node {
public int x, y;
boolean blocked = false;
boolean exit = false;
Node parent = null;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final Node other = (Node) obj;
if (x != other.x) {
return false;
}
if (y != other.y) {
return false;
}
return true;
}
//it is simpler to have Node return its graphic representation
char getGraphics() {
char c = blocked ? NUMBER_SIGN : DOT;
if(equals(start)) { c=START;}
else if (exit) { c=EXIT;}
return c;
}
}
private static List<Node> getShortestPath() {
//initialize with an arbitrary path
List<Node> shortest = paths.get(0);
for (List<Node> path : paths) {
if(path.size() < shortest.size()) {
shortest = path;
}
}
return shortest;
}
private static String[] getMazeData() {
return new String[] {
"##########.##########",
"..#...........#.....#",
"#.#.#########.#.###.#",
"#...#.........#.#...#",
"###############.#.###",
"#.....#.......#.#...#",
"#.#######.###.#.#.#.#",
"#...#...#...#...#.#..",
"###.###.###.###.#.#.#",
"#.#.#.#...#.#...#.#.#",
"#.#.#.#.#.#.#.###.#.#",
"#...#.#.#.#.#...#.#.#",
"#####.###.#.#####.###",
"#.#.......#.#...#...#",
"#.#.#######.#.#.###.#",
"#.#.#...#...#.#.#...#",
"#.#.###.#.#####.#####",
"#.#.................#",
"#.##.####.#########.#",
"#.........#..........",
"####.######.#########"
};
}
}
EDIT An improved version. Please test carefully.
class Maze {
private static char NUMBER_SIGN = '#', DOT = '.', START = 'S';
private static char EXIT = 'E', PATH = '1';
private static Node[][] nodes;
private static Node startNode;
private static boolean[][] visited; //no need to use Boolean
//exit holds the same information as Node.blocked. No need to duplicate
//private static boolean[][] blocked;
//exit holds the same information as Node.exit. No need to duplicate
//private static boolean[][] exits;
private static int mazeRows, mazeCols, startRow, startCol; //use meaningful names
private static List<List<Node>> paths;
public static void main(String args[]) {
mazeCols = 21; mazeRows = 21;//use meaningful and consistent names
startRow = 9; startCol = 10; //better keep h,w or height,width all over
String[] mazeData = getMazeData() ;
makeMaze(mazeData);
drawMaze(); //draw maze as built from input data
paths = new ArrayList<>();
findExits(startNode);
drawAllPaths(); // print all paths found
List<Node> shortestPath = getShortestPath();
drawShortestPath(shortestPath);
}
private static void drawMaze() {
System.out.println("*****************************************");
System.out.println("Maze as defined by input");
System.out.println("*****************************************");
drawMaze(null);
}
private static void drawAllPaths() {
for (List<Node> path : paths) {
System.out.println("*****************************************");
System.out.println("Path to exit ["
+ path.get(0).row + "," + path.get(0).col + "] length:"+ path.size());
System.out.println("*****************************************");
drawMaze(path);
}
}
private static void drawShortestPath(List<Node> path) {
System.out.println("*****************************************");
System.out.println("Shortest path is to exit ["
+ path.get(0).row + "," + path.get(0).col + "] length:"+ path.size());
System.out.println("*****************************************");
drawMaze(path);
}
private static void drawMaze(List<Node> path) {
for(Node[] row : nodes ) {
for(Node node : row) {
char c = node.getGraphics();
//overwrite c if node is in path
if ( (c != EXIT) && ( c != START ) &&
(path != null) && path.contains(node)) {c = PATH;}
System.out.print(c);
}
System.out.println("");
}
}
private static void makeMaze(String[] mazeData) {
nodes = new Node[mazeRows][mazeCols];
visited = new boolean[mazeRows][mazeCols];
for (int rowIndex = 0; rowIndex < mazeRows; rowIndex++) {
String row = mazeData[rowIndex];
for (int colIndex = 0; colIndex < mazeCols; colIndex++) {
Node node = new Node(rowIndex, colIndex);
node.blocked = row.charAt(colIndex) == NUMBER_SIGN;
visited[rowIndex][colIndex] = false;
node.exit = (!node.blocked) && ((rowIndex == (mazeRows - 1)) ||
(colIndex == (mazeCols - 1)) || (rowIndex == 0) || (colIndex == 0));
nodes[rowIndex][colIndex] = node;
}
}
startNode = nodes[startRow][startCol];//no need to set it in the loop
}
//use boolean instead of Boolean
private static void findExits(Node node) {
int row = node.row;
int col = node.col;
if(visited[row][col]) { return; }
if (node.exit) {
List<Node> path = new ArrayList<>();
while (node.parent != null) {
path.add(node);
node = node.parent;
}
path.add(node);
paths.add(path);
return; //do not continue to check exit neighbors
}
//LEFT
if ((col - 1) >= 0) {
Node testNode = nodes[row][col - 1];
//the following if statement repeats for all directions
//better put in a method
if ((testNode.parent == null) && ! testNode.blocked) {
testNode.parent = node; //parent ! null indicates that cell is tested
findExits(testNode);
testNode.parent = null; //set back to null: test finished
}
}
//RIGHT
if ((col + 1) < mazeCols) {
Node testNode = nodes[row][col + 1];
if ((testNode.parent == null) && ! testNode.blocked) {
testNode.parent = node;
findExits(testNode);
testNode.parent = null;
}
}
//TOP
if ((row - 1) >= 0) {
Node testNode = nodes[row-1][col];
if ((testNode.parent == null) && ! testNode.blocked) {
testNode.parent = node;
findExits(testNode);
testNode.parent = null;
}
}
//BOTTOM
if ((row + 1) < mazeRows) {
Node testNode = nodes[row+1][col];
if ((testNode.parent == null) && ! testNode.blocked) {
testNode.parent = node;
findExits(testNode);
testNode.parent = null;
}
}
visited[row][col] = true; //mark as visited after all directions explored
node.parent = null;
}
public static class Node {
public int row, col;
boolean blocked = false;
boolean exit = false;
Node parent = null;
public Node(int row, int col) {
this.row = row;
this.col = col;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final Node other = (Node) obj;
if (row != other.row) {
return false;
}
if (col != other.col) {
return false;
}
return true;
}
//it is simpler to have Node return its graphic representation
char getGraphics() {
char c = blocked ? NUMBER_SIGN : DOT;
if(equals(startNode)) { c=START;}
else if (exit) { c=EXIT;}
return c;
}
@Override
public String toString() {
return "Node " + row +"-"+ col +" ("+ getGraphics() + ")";
}
}
private static List<Node> getShortestPath() {
//initialize with an arbitrary path
List<Node> shortest = paths.get(0);
for (List<Node> path : paths) {
if(path.size() < shortest.size()) {
shortest = path;
}
}
return shortest;
}
private static String[] getMazeData() {
return new String[] {
"##########.##########",
"..#...........#.....#",
"#.#.#########.#.###.#",
"#...#.........#.#...#",
"###############.#.###",
"#.....#.......#.#...#",
"#.#######.###.#.#.#.#",
"#...#...#...#...#.#..",
"###.###.###.###.#.#.#",
"#.#.#.#...#.#...#.#.#",
"#.#.#.#.#.#.#.###.#.#",
"#...#.#.#.#.#...#.#.#",
"#####.###.#.#####.###",
"#.#.......#.#...#...#",
"#.#.#######.#.#.###.#",
"#.#.#...#...#.#.#...#",
"#.#.###.#.#####.#####",
"#.#.................#",
"#.##.####.#########.#",
"#.........#..........",
"####.######.#########"
};
}
}
Feedback would be appreciated.