Problemen met het vinden van een pad

Oké, ik probeer een dynamisch padenstelsel te maken, zodat de speler van punt A naar punt B kan gaan zonder vooraf gedefinieerde paden te hebben. Let op dit spel is allemaal op tekst gebaseerd, geen afbeeldingen. De speler kan in 10 richtingen bewegen: omhoog, omlaag, n, e, s, w, sw, se, nw en ne.

De kaart van de hele wereld bevindt zich in een database, elke rij van de database bevat een kamer of een knooppunt, elke kamer/knooppunt heeft een routebeschrijving die hij kan gebruiken. Het is mogelijk dat de kamer niet opeenvolgend is. Een voorbeeld:

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

De Direction_N geeft aan dat het naar Map 1 Room 3, Direction_S Map 1 Room 100, enz. Gaat.

Ok, ik heb de code herwerkt met suggesties (dank u trouwens!) Hier is de herziene code. Het lijkt nu de kamers te vinden, zelfs grote afstanden! Maar nu is het probleem het vinden van het kortste pad naar de bestemming, ik probeerde de collectie te doorkruisen maar het pad komt er niet goed uit ...

In de onderstaande afbeeldingslink heb ik startpunt in rood vierkant in het midden en stoppunt in het rode vierkant linksboven. Dit komt overeen met VisitStartRooms = 103 en visitedStopRooms = 86, wanneer het slechts ongeveer 16 kamers zijn. Volgens mij is mijn ontbrekende stukje van de puzzel dat ik niet zeker weet hoe ik de kamers in die verzameling moet sorteren om de echt kortste route te krijgen.

Voorbeeld van kaart

Hier is de nieuwe code

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

        List directions = new List();


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

    }
0
een probleem in uw algoritme is dat u de wachtrij gebruikt om te zien of u een kamer hebt bezocht. Maar als je een kamer hebt bezocht die uit de wacht is gehaald, zul je denken dat je die nog niet hebt bezocht, en dus zul je veel tijd besteden aan het opnieuw doorzoeken van reeds overgestoken paden. Dit is misschien de reden waarom de prestaties zo snel afnemen voor langere afstanden.
toegevoegd de auteur hatchet, de bron

1 antwoord

Je hebt een goede start. Er zijn een paar basisverbeteringen die zullen helpen. Ten eerste, om uw pad te kunnen reconstrueren, moet u een nieuwe gegevensstructuur maken om bezochte ruimten op te slaan. Maar voor elk item wilt u de kamer, plus de vorige kamer in het pad terug naar het beginpunt opslaan. Een goede gegevensstructuur hiervoor is een woordenboek waarin de sleutel de kamer-ID is en de waarde de vorige kamer-ID is. Om te weten of u een ruimte hebt bezocht, kijkt u of deze in die gegevensstructuur voorkomt, niet uw openLijst-wachtrij. Met deze nieuwe structuur kun je goed controleren of je een kamer hebt bezocht en kun je het pad terug reconstrueren door herhaaldelijk de vorige kamer in dezelfde structuur op te zoeken totdat je bij de originatie bent.

De tweede verbetering verhoogt de prestaties behoorlijk. In plaats van alleen maar een breedte-eerst te zoeken vanaf het startpunt totdat je tegen de bestemming botst, zoals je nu doet, maak je in plaats daarvan overeenkomende datastructuren zoals je hebt voor de startkamerzoekactie, maar laat je ze voor de bestemmingsruimte zijn. Nadat je één kamer vanaf het begin hebt bekeken, kijk je een kamer weg van de bestemming. Herhaal dit ... twee kamers uit de buurt, dan twee kamers weg van bestemming ... enz., Werk je weg naar buiten, totdat je een kamer ontdekt die bezocht is door zowel je zoekopdracht vanaf het begin als je zoekopdracht vanaf de bestemming. Bouw het pad van deze kamer terug naar het begin en terug naar de bestemming, en dat is je kortste pad.

Het probleem dat u probeert op te lossen, is het kortste padprobleem met ongewogen randen of waarbij de gewichten van alle randen gelijk zijn. Het gewicht van een rand is de tijd/kosten om van de ene kamer naar de andere te gaan. Als de kosten om van de ene kamer naar de andere te gaan variëren, afhankelijk van het paar kamers waar je het over hebt, dan is het probleem gecompliceerder en het algoritme waarmee je bent begonnen en waarvoor ik wijzigingen heb voorgesteld, werkt niet is. Hier zijn enkele links over:

Kortste pad (de minste knooppunten) voor ongewogen grafieken

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

Mogelijk bent u ook geïnteresseerd in het A * -algoritme dat een andere aanpak gebruikt. Het gebruikt een hueristische benadering om de zoekopdracht te concentreren in een subset van de oplossingsruimte die waarschijnlijker het kortste pad bevat. http://en.wikipedia.org/wiki/A%2a_search_algorithm Maar A * is waarschijnlijk overkill in uw geval, omdat het gewicht van alle randen hetzelfde is tussen alle kamers.

1
toegevoegd