Maze Solver in java
It is logical thinking game. Let us implement this program in java. Maze solver can be done in many ways as follows..
This maze solver uses DFS (Depth First Search)
This algorithm starts from a root node and traverses through
its child node until depth.
It marks the visited node as visited and continues to next node.
Complete all nodes using recursion.
Code:
import java.util.*;
public class MazeSolver {
// let us create
the Maze.here, 0 = path, 1 = wall
private static
int[][] maze = {
{0, 1, 0, 0,
0},
{0, 1, 0, 1,
0},
{0, 0, 0, 1,
0},
{1, 1, 0, 1,
0},
{0, 0, 0, 0,
0}
};
private static
boolean[][] m_visited;
private static int
m_rows = maze.length;
private static int
m_cols = maze[0].length;
// Let us create
the Directions: up, down, left, right
private static
int[][] directions = {
{1, 0}, {-1,
0}, {0, 1}, {1, 0}
};
public static void
main(String[] args) {
m_visited =
new boolean[m_rows][m_cols];
System.out.println("Maze Solver using DFS:");
if
(maze_dfs(0, 0)) {
System.out.println("Path found!");
} else {
System.out.println("No path exists.");
}
}
private static
boolean maze_dfs(int r, int c) {
// The
Checking of boundaries and walls
if (r < 0
|| c < 0 || r >= m_rows || c >= m_cols || maze[r][c] == 1 ||
m_visited[r][c]) {
return
false;
}
// Mark as
visited
m_visited[r][c] = true;
// Goal:
bottom-right corner
if (r ==
m_rows - 1 && c == m_cols - 1) {
System.out.println("Reached goal at (" + r + "," + c
+ ")");
return
true;
}
// Explore
neighbors
for (int[] dir
: directions) {
int newR =
r + dir[0];
int newC =
c + dir[1];
if
(maze_dfs(newR, newC)) {
System.out.println("Step: (" + r + "," + c +
")");
return
true;
}
}
return false;
// backtrack
}
}
Output:
Maze Solver using DFS:
Reached goal at (4,4)
Step: (4,3)
Step: (4,2)
Step: (3,2)
Step: (2,2)
Step: (2,1)
Step: (2,0)
Step: (1,0)
Step: (0,0)
Path found!
Hope, the code is useful to you. This maze is developed
using DFS. You can try to implement using BFS also. Keep coding.
Comments
Post a Comment