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

Question

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

javaalgorithmsimulation

9

我已经创建了一个2D迷宫，并希望找到红色节点到蓝色节点之间的最短路径。我不确定如何实现深度优先搜索。我知道邻接矩阵或列表可以用来表示节点之间的连接，但是我不确定如何构建它。

简而言之，我需要返回一个包含搜索过的格子坐标的列表（在寻找目标节点时），以便在迷宫上描述搜索过程。或者我该如何构建这个邻接矩阵？以及相应的顶点列表？

深度优先搜索通用结构：

1. 访问节点（单元格）（将访问标志更改为true） 2. 推入栈中 3. 获取未访问的顶点（查看栈顶）。如果没有，则弹出栈-更新迷宫模型视图。 4. 重复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
    }

以下图片展示了迷宫结构，这是伪随机生成的；最终的迷宫实现将会被完善。

谢谢，如果你能指导我正确的方向，我将不胜感激...

- Robert

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Saeed Amiri · Accepted Answer

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

但是还有另一种选择，这种选择有点标记和BFS，并且适用于您的迷宫（无需图形）。

编号算法

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

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

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

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

事实上，BFS 的普通和简单方法是使用队列（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<Edge> Edges = new List<Edge>();
   public bool Visited = false;
}

现在你的图是由节点对象列表组成的：

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

为了建模迷宫，您应该选择单元格作为节点，并在相邻单元格之间绘制边缘。关于如何向图中添加节点，我会留给你自己决定。