Share
In deze tutorial zal ik het uitleggen vector veld pathfinding en de voordelen ervan ten opzichte van meer traditionele algoritmen voor het bepalen van verplaatsingen, zoals die van Dijkstra. Een basisbegrip van zowel het algoritme van Dijkstra als potentiële velden zal u helpen dit artikel te begrijpen, maar is niet vereist.
Pathfinding is een probleem met veel oplossingen, en elk heeft zijn voor- en nadelen. Veel pathfinding-algoritmen werken door voor elke pathfinder een pad naar het doel te berekenen, wat betekent dat de verplaatsing tweemaal zo lang duurt om te berekenen met twee keer zoveel padzoekers. Dit is in veel situaties aanvaardbaar, maar bij het werken met duizenden padvinders is een efficiëntere aanpak mogelijk.
Bekend als vector veld pathfinding, deze benadering berekent het pad van het doel naar elk knooppunt in de grafiek. Om deze verklaring van vectorveldpadvinden te verstevigen, zal ik het algoritme uitleggen met behulp van mijn specifieke implementatie als een voorbeeld.
Notitie: Veldefrequentie van vectorvelden kan worden geabstraheerd naar knooppunten en grafieken in het algemeen; alleen omdat ik het uitleg met behulp van mijn tegel- en rasterbenadering, wil dit nog niet zeggen dat dit algoritme beperkt is tot op tegels gebaseerde werelden!
Vectorveldverwijzing bestaat uit drie stappen.
Deze video toont u de eindresultaten en geeft u vervolgens een algemeen overzicht van de concepten die worden gepresenteerd in de volledige zelfstudie hieronder:
De heatmap slaat de padafstand van het doel op naar elke tegel op de kaart. Padafstand is verschillend van Euclidische afstand in die zin dat het een berekening is van de afstand tussen twee punten die alleen door traversabel terrein gaan. Een GPS berekent bijvoorbeeld altijd de padafstand, waarbij wegen het enige oversteekbare terrein zijn.
Hieronder ziet u het verschil tussen padafstand en lineaire afstand van het doel (rood gemarkeerd) naar een willekeurige tegel (roze gemarkeerd). Niet-verplaatsbare tegels zijn groen getekend. Zoals je kunt zien, is de padafstand (weergegeven in geel) 9, terwijl de lineaire afstand (weergegeven in lichtblauw) ongeveer is 4.12.
De nummers in de linkerbovenhoek van elke tegel geven de padafstand naar het doel weer, berekend door het algoritme voor het genereren van heatmaps. Merk op dat er meer dan één mogelijke pad-afstand tussen twee punten is; in dit artikel zijn we alleen geïnteresseerd in de kortste.
Het algoritme voor het genereren van heatmaps is een wavefront-algoritme. Het begint bij het doel met een waarde van 0, en stroomt dan naar buiten om het gehele traverseerbare gebied te vullen. Er zijn twee stappen voor het algoritme voor golffront:
Accentsconagua
0.de padafstand van de vorige tegel + 1.Notitie: Het algoritme voor het golffront draait eenvoudigweg een eerste zoekopdracht op het raster en slaat op hoeveel stappen er nodig waren om elke tegel langs de weg te bereiken. Dit algoritme wordt soms ook wel het algoritme voor het vuren.
Nu de padafstand van elke tegel naar het doel is berekend, kunnen we eenvoudig het pad bepalen dat moet worden genomen om dichter bij het doel te komen. Het is mogelijk om dit bij runtime voor elke pathfinder in elk frame te doen, maar het is vaak beter om een vectorveld eenmaal te berekenen en dan moeten alle padzoekers tijdens runtime naar het vectorveld verwijzen.
Het vectorveld slaat eenvoudig een vector op die naar beneden wijst op de gradiënt van de afstandsfunctie (naar het doel) op elke tegel. Hier is een visualisatie van het vectorveld, waarbij de vectoren vanuit het midden van de tegel langs het kortste pad naar het doel wijzen (opnieuw in rood weergegeven).
Dit vectorveld wordt één tegel per keer gegenereerd door naar de heatmap te kijken. De x- en y-componenten van de vector worden afzonderlijk berekend, zoals weergegeven in de pseudocode hieronder:
Vector.x = left_tile.distance - right_tile.distance Vector.y = up_tile.distance - down_tile.distance
Notitie: De afstandsvariabele van elke tegel slaat de padafstand op naar het doel zoals berekend door het bovenstaande golffrontalgoritme.
Als een van de tegels waarnaar wordt verwezen (links / rechts / omhoog / omlaag) niet verplaatsbaar is en dus geen bruikbare afstand heeft opgeslagen, wordt de afstand die is gekoppeld aan de huidige tegel gebruikt in plaats van de ontbrekende waarde. Nadat de padvector ruwweg is berekend, wordt deze genormaliseerd om inconsistenties later te voorkomen.
Nu het vectorveld is berekend, is het heel eenvoudig om beweging voor een pathfinder te berekenen. Ervan uitgaande dat vector_veld (x, y) de vector retourneert die we eerder bij de tegel hebben berekend (X, y), en die gewenste snelheid is een scalaire waarde, de pseudocode om de snelheid van een deeltje op de tegel te berekenen (X, y) het lijkt op dit:
velocity_vector = vector_field (x, y) * gewenste_velocity
De deeltjes moeten gewoon beginnen te bewegen in de richting aangegeven door de vector. Dit is de eenvoudigste manier om dit te doen, maar ingewikkeldere bewegingssystemen kunnen eenvoudig worden geïmplementeerd met behulp van stroomvelden.
De technieken die worden uitgelegd in Understanding Steering Behaviors kunnen bijvoorbeeld worden toegepast op de verplaatsing van de peiling. In een dergelijke situatie, de velocity_vector we hierboven berekend zouden worden gebruikt als de gewenste snelheid, en het stuurgedrag zou worden gebruikt om de werkelijke beweging bij elke tijdstap te berekenen.
Bij het berekenen van beweging is er een probleem dat soms kan optreden, bekend als lokale optima. Dit gebeurt wanneer er twee optimale (kortste) paden zijn om van een bepaalde tegel naar het doel te gaan.
Dit probleem is te zien in de onderstaande afbeelding. De tegel (roze weergegeven) direct links van het midden van de muur heeft een padvector waarvan de componenten (x en y) gelijk zijn aan 0.
Plaatselijke optima zorgen ervoor dat padzoekers vastlopen; ze verwijzen naar het vectorveld dat geen richting aangeeft om in te gaan. Wanneer dit gebeurt, blijven de padzoekers op dezelfde locatie staan tenzij een fix is geïmplementeerd.
De meest elegante manier (ik heb ontdekt) om het probleem op te lossen, is door het heatmap- en het vectorveld één keer onder te verdelen. Elke afzonderlijke heatmap en vectorveldtegel is nu opgesplitst in vier kleinere tegels. Het probleem blijft hetzelfde met een onderverdeeld raster; het is maar een beetje geminimaliseerd.
De echte truc die het probleem met de lokale optima oplost, is om in eerste instantie vier doelknooppunten toe te voegen, in plaats van slechts één. Om dit te doen, hoeven we alleen de eerste stap van het algoritme voor het genereren van heatmaps te wijzigen. Wanneer we slechts één doel met een padafstand van 0 voegden, voegen we nu de vier tegels toe die het dichtst bij het doel liggen.
Er zijn verschillende manieren om de vier tegels te kiezen, maar de manier waarop ze worden gekozen, is grotendeels irrelevant - zolang de vier tegels aan elkaar grenzen (en te doorkruisen), zou deze techniek moeten werken.
Hier is de gewijzigde pseudocode voor het genereren van de heatmap:
0.de padafstand van de vorige tegel + 1.En nu, hier zijn de eindresultaten, waaruit duidelijk blijkt dat het probleem met de lokale optima is geëlimineerd:
Hoewel deze oplossing elegant is, is deze verre van ideaal. Als u dit gebruikt, duurt het berekenen van het heatmap- en vectorveld vier keer langer vanwege het toegenomen aantal tegels.
Andere oplossingen vereisen het uitvoeren van controles en vervolgens bepalen welke richting moet worden gevolgd, wat de berekeningen van de deeltjesbeweging aanzienlijk vertraagt. In mijn geval was het onderverdelen van de kaarten de betere optie.
Hopelijk heeft deze tutorial je geleerd hoe je doelgebaseerde pathfinding implementeert in een op tegels gebaseerde wereld. Houd er rekening mee dat dit soort verplaatsing in de kern eenvoudig is: deeltjes volgen het verloop van de afstandsfunctie naar het doel.
De implementatie is complexer, maar kan worden opgesplitst in de volgende drie hanteerbare stappen:
Ik hoop dat mensen de ideeën die hier worden gepresenteerd, zullen uitdiepen. Zoals altijd, als u vragen hebt, kunt u ze stellen in de onderstaande opmerkingen!
