0

好的,我正在尝试制作一个动态路径系统,以便玩家可以在没有预定义路径的情况下从 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 表示它去 Map 1 Room 3,Direction_S Map 1 Room 100 等等...

好的,我根据建议重新编写了代码(顺便谢谢你们!)这里是修改后的代码。它现在似乎找到了房间,甚至是很远的距离!但现在的问题是找到到目的地的最短路径,我尝试遍历集合,但路径不正确......

在下面的图片链接中,我在中心的红色正方形中有起点,在左上角的红色正方形中有停止点。这将返回visitedStartRooms = 103 和visitedStopRooms = 86,此时只有大约16 个房间。问我缺少的难题是我不知道如何整理这些集合中的房间以获得真正的最短路线。

地图示例

这是新代码

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

    }
4

1 回答 1

1

你有一个好的开始。有一些基本的改进会有所帮助。首先,为了能够重建您的路径,您应该创建一个新的数据结构来存储访问过的房间。但是对于每个条目,您要存储房间,以及返回起点的路径中的前一个房间。一个好的数据结构是一个字典,其中键是房间标识符,值是以前的房间标识符。要知道您是否访问过一个房间,您需要查看它是否存在于该数据结构中,而不是您的 openList 队列中。使用这种新结构,您可以正确检查您是否访问过一个房间,并且您可以通过重复查找同一结构中的前一个房间来重建返回路径,直到您到达起点。

The second improvement will increase the performance quite a bit. Instead of just doing a breadth-first search from the start point until you bump into the destination, as you currently do, instead create matching data structures like you have for the start room search, but have them be for the destination room. After you've looked one room away from the start, look one room away from the destination. Repeat this...two rooms away from start, then two rooms away from destination.. etc., working your way out, until you discover a room that has been visited by both your search from start and your search from destination. Build the path from this room back to the start, and back to the destination, and that will be your shortest path.

The problem you are trying to solve is the shortest path problem with unweighted edges or where the weights of all edges are equal. The weight of an edge is the time/cost to move from one room to another. If the cost to move from one room to another varies depending on which pair of rooms you're talking about, then the problem is more complicated, and the algorithm you started with and for which I've suggested modifications, will not work as it is. Here are some links about it:

Shortest path (fewest nodes) for unweighted graph

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

You may also be interested in the A* algorithm which uses a different approach. It uses a hueristic approach to concentrate the search in a subset of the solution space more likely to contain the shortest path. http://en.wikipedia.org/wiki/A%2a_search_algorithm But A* is probably overkill in your case since the weight of all edges is the same between all rooms.

于 2012-06-23T22:32:58.980 回答