Depth of first search in a two-dimensional array
I am trying to learn DFS by creating a program that moves my ogre through a maze (2d array). It looks like a dailyprogramming call, but I only do it with a 1x1 ogre.
My maze:
static int[][] maze = {
{2,1,0,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,0,0},
{1,0,0,0,0,1,0,1,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,1,0,0,0,0,1,0,1},
{1,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,1,1,0,0,0},
{0,0,0,0,0,1,0,0,0,3}};
Where 2 is my hero (0,0), 3 is my target (9,9), 1s is the obstacles and 0s is the passable space.
Since I'm new to this I doubt it would be necessary, but I mean the whole program for simple duplication and troubleshooting.
import java.awt.Point;
import java.util.ArrayList;
public class OgrePath {
static int[][] maze = {
{2,1,0,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,0,0},
{1,0,0,0,0,1,0,1,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,1,0,0,0,0,1,0,1},
{1,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,1,1,0,0,0},
{0,0,0,0,0,1,0,0,0,3}};
public static boolean[][] visited = new boolean[maze.length][maze[0].length];
static ArrayList<Point> neighbors = new ArrayList<Point>();
public static void main(String[] args) {
OgrePath OP = new OgrePath();
for (int i=0;i<maze.length;i++){
for (int j=0;j<maze[i].length;j++){
visited[j][i] = false;
}
}
visited[getOgre(maze).x][getOgre(maze).y] = true;
System.out.println("Ogre: " + getOgre(maze));
dfs(maze, getOgre(maze));
}
public static boolean dfs(int[][] maze, Point p){
neighbors = getNeighbors(maze,p);
if (maze[p.x][p.y] == 3){
System.out.println("FOUND IT");
return true;
}
if (neighbors.isEmpty()){
return false;
}
for (int i=0;i<neighbors.size();i++){
System.out.println("Nieghbors: " + neighbors);
System.out.println(i + "(" + p.x + "," + p.y + ")");
visited[neighbors.get(i).x][neighbors.get(i).y] = true;
dfs(maze, neighbors.get(i));
}
return false;
}
public static ArrayList<Point> getNeighbors(int[][] maze, Point p){
ArrayList<Point> neighbors = new ArrayList<Point>();
Point left = new Point();
Point right = new Point();
Point down = new Point();
Point up = new Point();
down.x = p.x - 1;
down.y = p.y;
if (valid(maze,down)) neighbors.add(down);
up.x = p.x + 1;
up.y = p.y;
if (valid(maze,up)) neighbors.add(up);
left.x = p.x;
left.y = p.y - 1;
if (valid(maze,left)) neighbors.add(left);
right.x = p.x;
right.y = p.y + 1;
if (valid(maze,right)) neighbors.add(right);
return neighbors;
}
public static boolean valid(int[][] maze, Point p){
if (inMaze(maze,p) && canGo(maze,p) && visited[p.x][p.y] == false) return true;
else return false;
}
public static boolean inMaze(int[][] maze, Point p){
if (p.x < (maze[0].length - 1) && p.x > -1 && p.y < (maze.length - 1) && p.y > -1){
return true;
} else return false;
}
public static boolean canGo(int[][] maze, Point p){
if (maze[p.x][p.y] != 1 && maze[p.x][p.y] != 4) return true;
else return false;
}
public static Point getOgre(int[][] maze){
Point ogre = new Point();
for (int i=0;i<maze.length;i++){
for (int j=0;j<maze[i].length;j++){
if (maze[i][j] == 2){
ogre.x = j;
ogre.y = i;
}
}
}
return ogre;
}
}
I want to call DFS recursively, but something about how I wrote it causes the program to stop after it has examined 1 possible line and failed.
source to share
Ok, so there are a couple of problems I see that would prevent your code from working correctly, so let's take a look at them one at a time.
First, dfs will not go through a for loop because it will return immediately. Try to change
dfs(maze, neighbors.get(i));
to
if(dfs(maze, neighbors.get(i))){
return true;
}
This fixes part of your problem when finding only one path.
The second problem has to do with your neighbors. When your dfs has fully explored the path, it should go back a step and check all neighbors. You only have one top-level neighbor variable, so when your branch ends up with zero neighbors, it thinks that all earlier nodes have zero neighbors.
Remove the static neighbors variable
static ArrayList<Point> neighbors = new ArrayList<Point>();
And put a non-statistical version in getNeighbors
ArrayList<Point> neighbors = new ArrayList<Point>();
This almost completely fixes the search, but for your maze, you still won't find an end.
The inMaze function incorrectly checks boundaries. You checked if x or y was less than length minus one. To check the border, you need to use "less".
if (p.x < maze[0].length && p.x > -1 && p.y < maze.length && p.y > -1)
source to share