尋路問題

Question

好吧我正在嘗試製作一個動態路徑系統，以便玩家可以從點A移動到點B而無需預定義路徑。注意這個遊戲是所有基於文本的沒有圖形。玩家可以在10個方向上移動：上，下，n，e，s，w，sw，se，nw和ne。

整個世界的地圖都在一個數據庫中，數據庫的每一行都包含一個房間或一個節點，每個房間/節點都有它能夠前進的方向。房間可能不是連續的。一個例子：

Map Number, Room Number, Direction_N, Direction_S, Direction_E, Direction_W, etc. 
    1   1   1/3   1/100  1/1381  1/101 

的Direction_N表示它進入地圖3室1，Direction_S地圖1個100室，等...

好吧，我重新設計搭配建議代碼（感謝你們的方式！）這裏是修改代碼。它似乎現在找到房間，甚至很遠的距離！但現在的問題是找到到目的地的最短路徑，我嘗試遍歷集合，但路徑不是正確的...

在下面的圖像鏈接，我有中心的紅色方塊的起點和停止指向左上角的紅色方塊。當它只有大約16個房間時，它返回visitedStartRooms = 103和visitedStopRooms = 86。 Quess我缺失的難題是我不知道如何理清這些集合中的房間以獲得真正的最短路線。

Example of map

這是新代碼

 public void findRoute(ROOM_INFO startRoom, ROOM_INFO destinationRoom) 
    { 
     Dictionary<ROOM_INFO, bool> visitedStartRooms = new Dictionary<ROOM_INFO, bool>(); 
     Dictionary<ROOM_INFO, bool> visitedStopRooms = new Dictionary<ROOM_INFO, bool>(); 

     List<string> directions = new List<string>(); 


     startQueue.Enqueue(startRoom); // Queue up the initial room 
     destinationQueue.Enqueue(destinationRoom); 

     visitedStartRooms.Add(startRoom, true);// say we have been there, done that 
     visitedStopRooms.Add(destinationRoom, true); 

     string direction = ""; 
     bool foundRoom = false; 

     while (startQueue.Count != 0 || destinationQueue.Count != 0) 
     { 

      ROOM_INFO currentStartRoom = startQueue.Dequeue(); // remove room from queue to check out. 
      ROOM_INFO currentDestinationRoom = destinationQueue.Dequeue(); 

      ROOM_INFO startNextRoom = new ROOM_INFO(); 
      ROOM_INFO stopNextRoom = new ROOM_INFO(); 

      if (currentStartRoom.Equals(destinationRoom)) 
      { 
       break; 
      } 
      else 
      { 
       // Start from destination and work to Start Point. 
       foreach (string exit in currentDestinationRoom.exitData) 
       { 

        stopNextRoom = extractMapRoom(exit); // get adjacent room 
        if (stopNextRoom.Equals(startRoom)) 
        { 
         visitedStopRooms.Add(stopNextRoom, true); 
         foundRoom = true; 
         break; 
        } 

        if (stopNextRoom.mapNumber != 0 && stopNextRoom.roomNumber != 0) 
        { 
         if (!visitedStopRooms.ContainsKey(stopNextRoom)) 
         { 
          if (visitedStartRooms.ContainsKey(stopNextRoom)) 
          { 
           foundRoom = true; 
          } 
          else 
          { 
           destinationQueue.Enqueue(stopNextRoom); 
           visitedStopRooms.Add(stopNextRoom, true); 
          } 
         } 
        } 
       } 

       if (foundRoom) 
       { 
        break; 
       } 
      } 

      // start from the start and work way to destination point 
      foreach (string exit in currentStartRoom.exitData) 
      { 

       startNextRoom = extractMapRoom(exit); // get adjacent room 
       if (startNextRoom.Equals(destinationRoom)) 
       { 
        visitedStartRooms.Add(startNextRoom, true); 
        foundRoom = true; 
        break; 
       } 
       if (startNextRoom.mapNumber != 0 && startNextRoom.roomNumber != 0) 
       { 
        if (!visitedStartRooms.ContainsKey(startNextRoom)) 
        { 
         if (visitedStopRooms.ContainsKey(startNextRoom)) 
         { 
          foundRoom = true; 
          break; 
         } 
         else 
         { 

          startQueue.Enqueue(startNextRoom); 
          visitedStartRooms.Add(startNextRoom, true); 
         } 

        } 
       } 
      } 


      if (foundRoom) 
      { 
       break; 
      } 
     } 

    } 

Answer 1

你有一個良好的開端。有幾個基本的改進將會有所幫助。首先，爲了能夠重建您的路徑，您應該創建一個新的數據結構來存儲訪問過的房間。但是，對於每個條目，您都需要存儲房間，並將路徑中的前一個房間加回到起點。一個好的數據結構就是一個字典，其中關鍵是房間標識符，並且該值是先前的房間標識符。要知道你是否訪問過一個房間，你看看它是否存在於這個數據結構中，而不是你的openList隊列中。有了這個新的結構，您可以正確地檢查您是否訪問過一個房間，並且可以通過反覆查找同一結構中的前一個房間來重建路徑，直到您找到起點。

第二個改進會提高性能相當多。不是像從前那樣只是從起點開始進行廣度優先搜索，直到碰到目的地爲止，而是像您現在這樣做，而是創建匹配的數據結構，就像您爲起始房間搜索一樣，但讓它們適用於目標房間。在你從一開始看了一個房間後，看看離目的地一個房間。重複這個步驟......離開兩個房間，然後離開目的地兩個房間..等等，直到你發現一個房間已被你的搜索從開始和你從目的地的搜索訪問。建立從這個房間回到起點的路徑，並返回到目的地，這將是您的最短路徑。

您試圖解決的問題是未加權邊緣或所有邊的權重相等的最短路徑問題。邊緣的重量是從一個房間移動到另一個房間的時間/成本。如果從一個房間移動到另一個房間的成本取決於您所談論的房間對的不同，那麼問題就更加複雜，而且我開始使用的算法以及我建議進行的修改的算法將不起作用是。下面是一些關於它的鏈接：

Shortest path (fewest nodes) for unweighted graph

http://en.wikipedia.org/wiki/Shortest_path_problem

您還可能有興趣在A *算法採用了不同的方法。它使用更爲人性化的方法將搜索集中在更可能包含最短路徑的解決方案空間子集中。 http://en.wikipedia.org/wiki/A%2a_search_algorithm 但是，由於所有房間的所有邊的重量都相同，因此A *可能會在您的情況下過度消耗。