深度优先搜索 - 2D游戏地图 [英] Depth first search - 2D Game map
问题描述
我已经创建了一个二维迷宫，我想找到红色 - >蓝色节点之间的最快途径。我是一个知道如何将着手实施深度优先搜索。我知道邻接矩阵或列表可以被用来重新present节点之间的连接。虽然，我不能确定如何构建它。
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?
深度优先搜索一般结构
- 访问节点（单元）（更改访问标志设置为true）
- 压栈
- 在获得访问过的顶点（PEEK堆栈）如果没有（弹出堆栈） - 更新迷宫模型图
重复1 - 3，直到栈空
Repeat 1 - 3 until stack empty
下面是当前$ C $下的迷宫类。
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);
}
}
}
}
目前的DFS code ..
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...
推荐答案
对于二维迷宫，你可以简单地使用的广度优先搜索，而不是深度优先搜索，它会发现它在为O（n 2 ）如果您有n个* N的迷宫。
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.
但是，还有另一种选择，这是一种标记和BFS，并适用于你的迷宫（无需图）。
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):
-
将所有单元格为0，并设置块-1
Set all cells to 0, and set blocks to -1
从源位置开始将其设置为1，标记它的所有0 邻居2，并保存所有2的列表中。该商标后，所有0 2的邻居3，明确2的列表，并保存3的列表，并去 上到达目的地。在每个级别中只是不改变 源值。
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.
现在假设你是在目的地和您要查找路径，你 地方都有得分男，找邻居比分M-1，...，输出的路径。
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.
在事实上BFS正常又简单的方法是用Q，但我提供了这个为它的简单，因为它模拟Q的方式。
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.
有关创建邻接矩阵，你应该有一个名为节点和边缘，这样你就可以有一个类，如下面的边和节点（我在伪C＃写的）：
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;
}
现在你的图形就是你的Node对象的列表：
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.
这篇关于深度优先搜索 - 2D游戏地图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
