深度優先搜索 - 2D遊戲地圖

Question

我創建了一個2D迷宮，並且我想要找到紅色 - 藍色節點之間最快的路徑。我不確定如何執行深度優先搜索。我知道可以使用鄰接矩陣或列表來表示節點之間的連接。雖然，我不確定如何構建它。

爲了簡潔：我需要返回一個列表與瓷磚座標搜索（尋找目標節點時），所以我可以描述搜索迷宮。或者我將如何構造一個鄰接矩陣？和相應的頂點列表？

深度優先搜索一般結構

1. 訪問節點（小區）（改變已訪問標記爲true）
2. 壓棧
3. 得到未訪問的頂點（PEEK堆棧），如果沒有（彈出堆棧） - 更新迷宮模型視圖

重複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

對於二維迷宮，你可以簡單地使用Breadth First Search，而不是深度優先搜索，它會找到它在O（n ）如果你有n * 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<Edge> Edges = new List<Edge>(); 
    public bool Visited = false; 
} 

現在

您的圖形就是你的Node對象的列表：

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

併爲您的造型迷宮你應該選擇細胞作爲節點，相鄰小區之間畫邊。 我會給你留下如何添加節點到你的圖表。