0

わかりました動的パスシステムを作成しようとしています。これにより、プレーヤーは事前定義されたパスなしでポイント A からポイント B に移動できます。このゲームはすべてテキストベースで、グラフィックはありません。プレーヤーは、上、下、n、e、s、w、sw、se、nw、ne の 10 方向に移動できます。

世界全体の地図はデータベースにあり、データベースの各行には部屋またはノードが含まれ、各部屋/ノードには移動可能な方向があります。部屋はシーケンシャルではないかもしれません。例:

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 などに向かうことを示します...

わかりました、私は提案でコードを作り直しました(ちなみにありがとうございます!)ここに改訂されたコードがあります。遠く離れていても、部屋を見つけるようです!しかし、問題は目的地への最短経路を見つけることです。コレクションをトラバースしようとしましたが、経路が正しく出てきません...

下の画像リンクでは、中央の赤い四角に開始点があり、左上の赤い四角に停止点があります。これは、約 16 室しかない場合に、visitedStartRooms = 103 および VisitedStopRooms = 86 を返します。私の欠けているパズルのピースは、真の最短ルートを得るためにそれらのコレクションの部屋を整理する方法がわからないということです.

地図の例

これが新しいコードです

        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 キューではなく、そのデータ構造に存在するかどうかを確認します。この新しい構造により、部屋を訪れたことがあるかどうかを適切に確認でき、元の部屋に到達するまで同じ構造で前の部屋を繰り返し検索することで、パスを再構築できます。

2 番目の改善により、パフォーマンスがかなり向上します。現在行っているように、開始点から目的地にぶつかるまで幅優先検索を行うのではなく、開始ルーム検索の場合と同様に一致するデータ構造を作成しますが、それらを目的地ルーム用にします。最初から 1 部屋離れたところを見終わったら、目的地から 1 部屋離れたところを見ます。これを繰り返します...最初から2部屋離れて、次に目的地から2部屋離れて..など、最初からの検索と目的地からの検索の両方で訪問された部屋を発見するまで、道を切り開きます。この部屋から出発点に戻り、目的地に戻る経路を作成すると、それが最短経路になります。

解決しようとしている問題は、重み付けされていないエッジまたはすべてのエッジの重みが等しい最短経路問題です。エッジの重みは、ある部屋から別の部屋に移動する時間/コストです。ある部屋から別の部屋に移動するコストが、話している部屋のペアによって異なる場合、問題はより複雑になり、最初に使用して修正を提案したアルゴリズムは機能しません。は。これに関するいくつかのリンクを次に示します。

重み付けされていないグラフの最短経路 (ノード数が最も少ない)

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

別のアプローチを使用する A* アルゴリズムにも興味があるかもしれません。ヒューリスティックなアプローチを使用して、最短パスを含む可能性が高い解空間のサブセットに検索を集中させます。http://en.wikipedia.org/wiki/A%2a_search_algorithm ただし、すべてのエッジの重みがすべての部屋で同じであるため、A* はおそらくやり過ぎです。

于 2012-06-23T22:32:58.980 に答える