I have created a 2D maze, and I want to find the quickest path between the red->blue colored nodes. I'm an unsure how I would go about implementing a depth-first search. I know that an adjacency matrix or list could be used to represent the connections between nodes. Though, I am unsure of how to construct it.
for brevity: I need to return a list with the tiles coordinates searched (when looking for goal node), so i can depict the search on the maze. Or how would i construct an adjacency matrix for this? and the corresponding vertex list?
Depth first search general structure
Repeat 1 - 3 until stack empty
Here is the current code for the maze class.
public class Maze {
//Tile ids
public static short OBSTICLE = 0;
public static short START_LOC_VALUE = -2;
public static short GOAL_LOC_VALUE = -3;
private int rows, cols;
private int numTiles;
private int[][] map;
private int[][] adjMatrix;
private Queue theQueue;
public Maze(int rows, int cols){
this.rows = rows;
this.cols = cols;
theQueue = new Queue();
numTiles = rows*cols;
map = new int[rows][cols];
adjMatrix = new int[rows][cols];
for (int i=0; i<rows; i++) {
for (int j=0; j<cols; j++) {
map[i][j] = 1;
}
}
}
/*
* Generate Maze
* @param numObstacles - number of obstacles
*/
public void generateMaze(int numObstacles){
for (int i = 0; i < numObstacles; i++)
setTile((int)(Math.random()*rows),(int)(Math.random()*cols), Maze.OBSTICLE);
//setTile((int)(Math.random()*rows),(int)(Math.random()*cols),Maze.START_LOC_VALUE);
//setTile((int)(Math.random()*rows),(int)(Math.random()*cols),Maze.GOAL_LOC_VALUE);
createAdjMatrix();
}
public void createAdjMatrix(){
for (int i=0; i<rows; i++) {
for (int j=0; j<cols; j++) {
if (map[i][j] == 1) {
addEdge(i,j);
}
}
}
}
/*
* Set Tile
* @param x - x cord
* @param y - y cord
* @param entity - OBSTICLE,START_LOC_VALUE or GOAL_LOC_VALUE ID
*/
public void setTile(int x, int y, short entity){
this.map[x][y] = entity;
}
public void addEdge(int start, int end) {//Start and end arguments index multidimensional array
adjMatrix[start][end] = 1;
adjMatrix[end][start] = 1;
}
public void bfs(int startDest, int goalDest) // breadth-first search
{
// begin at vertex 0
vertexList[startDest].wasVisited = true; // mark it
displayVertex(startDest); // display it
theQueue.enQueue(startDest); // insert at tail
int v2;
while (!theQueue.isEmpty()) // until queue empty,
{
int v1 = theQueue.deQueue(); // remove vertex at head
// until it has no unvisited neighbors
while ((v2 = getAdjUnvisitedVertex(v1)) != -1)
{ // get one,
vertexList[v2].wasVisited = true; // mark it
displayVertex(v2); // display it
theQueue.enQueue(v2); // insert it
} // end while(unvisited neighbors)
} // end while(queue not empty)
// queue is empty, so we’re done
for (int j = 0; j < nVerts; j++) // reset flags
vertexList[j].wasVisited = false;
}// end bfs()
/*
* Drawn Maze
* @param g - Graphics object
*/
public void draw(Graphics g){
for (int y = 0; y < cols; y++)
for (int x = 0; x < rows; x++) {
int val = map[x][y];
if (val==Maze.OBSTICLE) {
g.setColor(Color.BLACK);
g.fillRect(x*20, y*20, 20, 20);
}else if(val == Maze.START_LOC_VALUE){
g.setColor(Color.RED);
g.fillRect(x*20, y*20, 20, 20);
}else if(val==Maze.GOAL_LOC_VALUE){
g.setColor(Color.BLUE);
g.fillRect(x*20, y*20, 20, 20);
}else{
g.setColor(Color.BLACK);
g.drawRect(x*20, y*20, 20, 20);
}
}
}
}
current DFS code..
public void dfs(int vertexStart) // depth-first search
{
// begin at vertexStart
vertexList[vertexStart].wasVisited = true; // mark it
displayVertex(vertexStart); // display it
theStack.push(vertexStart); // push it
while (!theStack.isEmpty()) // until stack empty,
{
// get an unvisited vertex adjacent to stack top
int v = getAdjUnvisitedVertex(theStack.peek());
if (v == -1) // if no such vertex,
theStack.pop(); // pop a new one
else // if it exists,
{
vertexList[v].wasVisited = true; // mark it
displayVertex(v); // display it
theStack.push(v); // push it
}
} // end while
}
The following pictures depicts the maze structure, it has been generated pseudo randomly; the final maze implementation will be refined.
Thanks, I will be great full if you could guide me in the right direction...
For 2D Maze you can simply use Breadth First Search instead of Depth First Search, It will find it in O(n2) if you have n*n maze.
But there is another option, which is kind of labeling and BFS and works on your maze (no need to graph).
One of an interesting ways to understand the breadth first search is do it in this way (for maze):
Set all cells to 0, and set blocks to -1
Start from your source position set it to 1, mark all of it's 0 neighbors to 2, and save all 2's in a list. after that mark all 0 neighbors of 2's to 3, clear list of 2's and save list of 3's and go on to reach the destination. in each level just do not change the source value.
Now assume you are in destination and you want to find path, your destination has score m, find neighbor with score m-1, .... and output the path.
In fact normal and simple way of BFS is using Q, but I offered this for it's simplicity and because it simulates Q manner.
For creating adjacency matrix, you should have named node and edges, so you can have a classes like below for edges and nodes (I wrote it in pseudo C#):
public class Edge
{
public Edge(Node start, Node end, decimal weight)
{
StartNode = ...,...,...
}
public Node StartNode;
public Node EndNode;
public decimal weight;
public bool IsDirected;
}
public class Node
{
public Node(int index)
{
this.Index = index;
}
public int Index;
public List<Edge> Edges = new List<Edge>();
public bool Visited = false;
}
Now your graph is list of your Node objects:
public class Graph
{
public List<Node> Nodes = new List<Node>();
}
And for modeling your Maze you should select cells as node, and draw edge between neighbor cells. I'll left it to you how to add node to your graph.