深度优先搜索 – 2D游戏地图

我创建了一个2D迷宫，我想找到红色 – 蓝色节点之间最快的路径。 我不确定如何实施深度优先搜索。 我知道可以使用邻接矩阵或列表来表示节点之间的连接。 虽然，我不确定如何构建它。

为简洁起见 ：我需要返回一个列表，其中搜索了瓷砖坐标（当寻找目标节点时），因此我可以在迷宫上描绘搜索。 或者我将如何为此构建一个邻接矩阵？ 和相应的顶点列表？

深度首先搜索一般结构

1. 访问节点（单元格）（将访问标志更改为true）
2. 推送到堆栈
3. 得到未访问的顶点（peek stack）如果没有（pop stack） – 更新迷宫模型视图

重复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 } 

以下图片描绘了迷宫结构，它是伪随机生成的; 最终的迷宫实施将得到完善。

谢谢，如果你能引导我朝着正确的方向前进，我将会非常满意……

Answer 1

对于2D迷宫，您可以简单地使用广度优先搜索而不是深度优先搜索，如果您有n * n迷宫，它将在O（n ² ）中找到它。

但是还有另一种选择，它是一种标签和BFS，适用于您的迷宫（无需图表）。

编号算法

理解广度优先搜索的一种有趣方法是以这种方式（对于迷宫）：

1. 将所有单元格设置为0，并将块设置为-1

2. 从源位置开始将其设置为1，将所有0个邻居标记为2，并将所有2个保存在列表中。 在那之后标记所有0个2到3的邻居，清除2的列表并保存3的列表并继续到达目的地。 在每个级别只是不要更改源值。

3. 现在假设您在目的地，并且您想要找到路径，您的目的地有得分m，找到分数为m-1的邻居，….并输出路径。

事实上，BFS的正常和简单方式是使用Q，但我提供了这个简单，因为它模拟Q方式。

使用邻接矩阵

为了创建邻接矩阵，你应该有命名节点和边，所以你可以为边和节点创建如下所示的类（我用伪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 Edges = new List(); public bool Visited = false; } 

现在您的图表是Node对象的列表：

 public class Graph { public List Nodes = new List(); } 

对于Maze的建模，您应该选择单元格作为节点，并在相邻单元格之间绘制边缘。 我会告诉你如何将节点添加到图表中。