गहराई पहली खोज - 2 डी गेम मैप

Question

मैंने 2 डी भूलभुलैया बनाई है, और मैं लाल-> नीले रंग के नोड्स के बीच सबसे तेज़ पथ खोजना चाहता हूं। मैं एक अनिश्चित हूं कि मैं गहराई से पहली खोज को लागू करने के बारे में कैसे जाऊंगा। मुझे पता है कि नोड्स के बीच कनेक्शन का प्रतिनिधित्व करने के लिए एक आसन्न मैट्रिक्स या सूची का उपयोग किया जा सकता है। हालांकि, मुझे यकीन है कि इसे कैसे बनाया जाए।

संक्षिप्तता के लिए: मैं (जब लक्ष्य नोड की तलाश में) टाइल के साथ एक सूची वापस जाने के लिए की खोज निर्देशांक की जरूरत है, तो मैं उलझन पर खोज दर्शाती कर सकते हैं। या मैं इसके लिए एक आसन्न मैट्रिक्स कैसे बनाऊंगा? और संबंधित vertex सूची?

गहराई पहले खोज सामान्य संरचना

1. जाएँ नोड (सेल) (परिवर्तन को सही पर झंडा का दौरा किया)
2. पुश स्टैक करने के लिए
3. विज़िट नहीं किए गए शिखर (झांकना ढेर) प्राप्त करता है, तो कोई नहीं (पॉप ढेर) - अद्यतन भूलभुलैया मॉडल दृश्य

दोहराएँ 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); 
       } 
      } 
    } 
} 

वर्तमान डीएफएस कोड ..

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

2 डी भूलभुलैया के लिए आप बस के बजाय गहराई पहले खोज Breadth First Search उपयोग कर सकते हैं महान पूर्ण हो जाएगा, यह मिलेगा ओ में (एन) यदि आपके पास एन * एन भूलभुलैया है।

लेकिन एक और विकल्प है, जो कि लेबलिंग और बीएफएस है और आपकी भूलभुलैया पर काम करता है (ग्राफ की कोई आवश्यकता नहीं है)।

नंबरिंग एल्गोरिथ्म

चौड़ाई पहले खोज को समझने के लिए एक दिलचस्प तरीकों में से एक यह (भूलभुलैया के लिए) इस तरह से करना है: करने के लिए

1. 0 करने के लिए सभी कोशिकाओं सेट करें, और सेट ब्लॉक - 1

2. अपनी स्रोत स्थिति से शुरू करें इसे 1 पर सेट करें, इसके सभी 0 पड़ोसियों को 2 पर चिह्नित करें, और सभी 2 की सूची में सहेजें। उसके बाद 0 2 से 3 के पड़ोसी, 2 की स्पष्ट सूची और 3 की सूची सहेजें और गंतव्य तक पहुंचने के लिए पर जाएं। प्रत्येक स्तर में बस स्रोत मान को न बदलें।

3. अब मान लें कि आप गंतव्य में हैं और आप पथ खोजना चाहते हैं, तो आपके गंतव्य में स्कोर एम है, स्कोर एम -1 के साथ पड़ोसी ढूंढें .... और पथ आउटपुट करें।

वास्तव में BFS के सामान्य और सरल तरीका क्यू उपयोग कर रहा है, लेकिन मैं इस बात के लिए यह सादगी की पेशकश की और क्योंकि यह क्यू ढंग simulates।

निकटता मैट्रिक्स

का उपयोग निकटता मैट्रिक्स बनाने के लिए, आप नोड और किनारों नामित किया जाना चाहिए था, ताकि आप किनारों और नोड्स के लिए नीचे की तरह एक कक्षाएं हो सकता है (मैं इसे में छद्म सी # में लिखा था):

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>(); 
} 

और अपने भूलभुलैया मॉडलिंग के लिए आप नोड के रूप में कोशिकाओं का चयन करना चाहिए, और पड़ोसी कोशिकाओं के बीच बढ़त आकर्षित। मैं आपको अपने ग्राफ में नोड जोड़ने के लिए छोड़ दूंगा।