寻路问题

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 *可能会在您的情况下过度消耗。