Я создал двухмерный лабиринт и хочу найти самый быстрый путь между узлами, окрашенными в красный и синий цвета. Я не уверен, как бы я мог осуществить поиск в глубину. Я знаю, что матрица смежности или список могут быть использованы для представления связей между узлами. Хотя я не уверен, как его построить.
для краткости : Мне нужно вернуть список с искомыми координатами плиток (при поиске узла цели), чтобы я мог изобразить поиск в лабиринте. Или как бы я построить матрицу смежности для этого? и соответствующий список вершин?
Общая глубина первого поиска
- Посетить узел (ячейку) (изменить флаг посещения на true)
- Push to Stack
- получить непосещенную вершину (peek stack), если ее нет (pop pop) - обновить представление модели лабиринта
Повторяйте 1 - 3, пока стек не опустеет
Вот текущий код для класса лабиринта.
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);
}
}
}
}
текущий код DFS ..
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
}
На следующих рисунках изображена структура лабиринта, она была сгенерирована псевдослучайно; окончательная реализация лабиринта будет уточнена.
Спасибо, я буду очень полон, если бы вы могли направить меня в правильном направлении ...