Share
Pathfinding is alomtegenwoordig in games. Het is dus belangrijk om de implicaties te begrijpen die aanwezig zijn bij het gebruik van algoritmen zoals A *. In deze tutorial gaan we een relatief nieuwe methode behandelen om op rasters gebaseerde werelden te zoeken: Jump Point Search, die A * kan versnellen in ordes van grootte.
Notitie: Hoewel deze tutorial geschreven is met behulp van AS3 en Flash, zou je in bijna elke game-ontwikkelomgeving dezelfde technieken en concepten moeten kunnen gebruiken.
Deze implementatie is gebaseerd op het originele artikel en artikel over JPS hier: Jump Point Search. De
Op Lua gebaseerde implementatie, Jumper, werd gebruikt voor hulp bij sommige delen van de implementatie.
Klik op de SWF om deze focus te geven en beweeg uw muis vervolgens over niet-blokkerende gedeelten van de kaart om de NPC's ernaar te laten gaan. Druk op de spatiebalk om te schakelen tussen A *, Jump Point Search en beide.
Geen flash? Bekijk in plaats daarvan de YouTube-video:
De demo-implementatie hierboven gebruikt AS3 en Flash met het Starling Framework voor GPU-versnelde rendering en de polygonal-ds-bibliotheek voor datastructuren.
Pathfinding wordt vaak gebruikt in videogames en je zult er zeker op een bepaald moment tegenaan lopen tijdens je game-ontwikkelingscarrière. Het primaire gebruik ervan is om intelligent uitziend bewegingsgedrag te geven aan kunstmatige entiteiten (NPC's), om te voorkomen dat ze (vaak) tegen dingen aanlopen.
In sommige games is de avatar van de speler ook onderwerp van pathfinding (strategiespellen, veel third-party-RPG's en adventure-games). U kunt dus aannemen dat het probleem van het vinden van paden is opgelost, maar helaas is dat niet het geval; er is geen zilveren kogel die je kunt gebruiken en er gewoon mee klaar kunt zijn.
En zelfs in grote AAA-spellen zul je nog steeds grappige dingen vinden zoals dit:
Er is misschien geen zilveren kogel, maar er is een kogel: het A * (A ster) -algoritme. In deze tutorial zien we een kort overzicht van A * en hoe je het kunt versnellen met een ander algoritme, Jump Point Search.
Ten eerste hebben we een manier nodig om onze spelwereld te representeren op een manier die een pathfinding-algoritme kan gebruiken.
Een van de belangrijkste dingen om rekening mee te houden bij het nadenken over het vinden van een pad voor je spel is wereld vertegenwoordiging. Hoe worden de gegevens van de begaanbare gebieden en obstakels georganiseerd met programmeerstructuren in het geheugen?
De eenvoudigste weergave die u kunt gebruiken, is een op rasters gebaseerde structuur, waarbij padknooppunten in een raster zijn geordend en kunnen worden weergegeven door een 2D-array. We gaan deze weergave gebruiken in deze zelfstudie. Concreet zal het een acht-weg-rasterweergave zijn: beweging toestaan in rechte en diagonale richtingen.
Uw vereisten kunnen verschillen, dus deze structuur is mogelijk niet geschikt voor u. Het goede ding is dat met sommige verwerking (meestal offline gedaan) u pathfinding-representaties naar andere formaten kunt veranderen. Alternatieven voor grid-gebaseerde benadering omvatten dingen zoals polygoon (obstakels die worden weergegeven door polygonen) of navigatiemazen (navigatiegebieden die worden vertegenwoordigd door polygonen); deze kunnen dezelfde gegevens vertegenwoordigen met minder knooppunten.
Een andere gegevens die kunnen worden opgeslagen in kaartweergave zijn kosten: hoeveel kost het om van het ene knooppunt naar het andere te reizen? Dit kan worden gebruikt voor de AI om het pad te bepalen dat bijvoorbeeld de voorkeur geeft aan wegen boven regulier terrein (waardoor de kosten van de weg minder zijn dan het terrein).
Jump Point Search is specifiek ontworpen voor kaartrepresentatie op basis van acht richtingen, dus we zullen dat gebruiken. Ook biedt het in zijn vanillevorm geen gewogen kaarten. (In het laatste deel zal ik een mogelijke manier bespreken om dit te verhelpen.)
Nu hebben we een wereldrepresentatie, laten we een snelle blik werpen op de implementatie van A *. Het is een algoritme met een gewogen grafiek en maakt gebruik van heuristieken (kleine "hints") over hoe het gebied het best kan worden doorzocht, van het startknooppunt tot het eindpuntknooppunt.
Ik raad ten zeerste aan om deze visualisatie van pathfinding-algoritmen te bekijken:
PathFinding.js - visueel. Als je er mee speelt, kun je je intuïtie over wat het algoritme aan het doen is verbeteren, plus het is leuk!
Voor verplaatsing met A * in rechthoekige rasters doen we het volgende:
1. Zoek het knooppunt dat zich het dichtst bij uw positie bevindt en declareer het startknooppunt en plaats het op de open lijst. 2. Hoewel er knooppunten in de open lijst staan: 3. Kies het knooppunt uit de open lijst met de kleinste F-score. Zet het op de gesloten lijst (je wilt het niet nog een keer bekijken). 4. Voor elke buur (aangrenzende cel) die niet in de gesloten lijst staat: 5. Stel de bovenliggende in op het huidige knooppunt. 6. Bereken G-score (afstand van startknooppunt tot deze buurman) en voeg deze toe aan de open lijst 7. Bereken F-score door heuristieken toe te voegen aan de G-waarde.gerelateerde berichten
Heuristiek maakt in wezen een gok bij de kans dat het te evalueren knooppunt naar het doel leidt. Heuristieken kunnen een groot verschil maken in de efficiëntie van pathfinding-algoritmen omdat ze de neiging hebben het aantal nodes te beperken dat moet worden bezocht. We gaan de Manhattan-afstand gebruiken voor onze doeleinden (wat betekent dat knooppunten dichter bij het doel een kleiner aantal hebben):
private function manhattanDistance (start: Node, end: Node): int return Math.abs (end.x - start.x) + Math.abs (end.y - start.y);
Dit is min of meer het. We stoppen het algoritme wanneer we het doelknooppunt vinden en volgen vervolgens de oudervariabele van het knooppunt om het pad te construeren.
Zoekalgoritmen kunnen ook voor andere dingen worden gebruikt. A * is een algoritme voor algoritmen met algemeen gewogen grafiek en kan in een dergelijke grafiek worden gebruikt. Dit kan andere gebieden in AI bestrijken, zoals het vinden van de optimale stappen om een bepaald doel te bereiken: een bom gooien of rennen om te schuilen en proberen achter een vijand te sluipen?
Bij game-ontwikkeling moeten we snel dingen doen, bij het updaten van onze games met 60 frames per seconde, elke milliseconde telt. Hoewel A * redelijk goed presteert voor sommige toepassingen, bestaat de behoefte om het sneller te maken of minder geheugen te gebruiken.
Het kiezen van de weergave is het eerste dat invloed zal hebben op de prestaties van de paden en de keuze van het padbepalingsalgoritme. De grootte van de grafiek die wordt doorzocht, zal een grote correlatie hebben met hoe uw pathfinding presteert (wat logisch is, het is gemakkelijker om uw weg in uw kamer te vinden dan in een grote stad).
Dan zou u optimalisaties op hoger niveau overwegen, die meestal het clusteren van gegevens naar kleinere regio's inhouden en die vervolgens doorzoeken terwijl u later paden verfijnt in afgelegde kleinere regio's. Als u bijvoorbeeld naar een restaurant in een naburige stad wilt gaan, bekijkt u eerst hoe u van uw stad naar die stad reist en als u eenmaal in die stad bent beperkt u uw "zoeken" naar het gebied waar het restaurant zich bevindt , de rest negerend. Dit omvat zaken als moerassen, doodlopende eliminatie en HPA *.
Op het laagste niveau moet je het zoeken doen. U koos uw gegevensrepresentatie en mogelijke abstracties en plugt ze vervolgens in een algoritme dat knooppunten uitzoekt, hier en daar op zoek gaat naar het doel. Deze algoritmen zijn meestal gebaseerd op het A * -zoekalgoritme met mogelijke wijzigingen. In eenvoudiger gevallen kunt u wegkomen met het gebruik van rechte A *, die u de eenvoud biedt. Ik heb een grid-gebaseerde implementatie in de brondownload opgegeven.
Aangezien deze zelfstudie gaat over het implementeren van Jump Point Search, wordt de padzoekgrafiek weergegeven met een raster. En het moet specifiek een achtwegs raster zijn, omdat het algoritme het direct gebruikt.
Wat Jump Jump Search echt doet, is het verwijderen van veel tussenliggende knooppunten in bepaalde soorten rastercombinaties. Het slaat een aantal hiervan over dat je zou toevoegen aan de open lijst en de gesloten lijst, evenals andere berekeningen, ten gunste van wat meer verwerking bij het kiezen van het volgende knooppunt.
Net als bij A * kiezen we uit de open scène de knoop met de laagste F-score. Maar dit is waar dingen interessant beginnen te worden. In plaats van aangrenzende knooppunten te selecteren, noemen we deze functie om het voor ons te doen:
function identifySuccessors (current: Node, start: Node, end: Node): Vector.var opvolgers: Vector. = nieuwe Vector. (); var buren: Vector. = nodeNeighbours (current); voor elk (var neighbor: Node in buren) // Richting van huidig knooppunt naar buur: var dX: int = clamp (neighbour.x - current.x, -1, 1); var dY: int = clamp (neighbour.y - current.y, -1, 1); // Probeer een knooppunt te vinden om naartoe te springen: var jumpPoint: Node = jump (current.x, current.y, dX, dY, start, end); // Indien gevonden, voeg het toe aan de lijst: if (jumpPoint) successors.push (jumpPoint); terugkeer opvolgers;
Wat dit doet is nodes elimineren die niet interessant zijn voor ons pad. Hiervoor gebruiken we de richting van ouder als de hoofdrichtlijn. Hier zijn voorbeelden van het snoeien van de knooppunten die we zullen negeren voor horizontale en verticale richtingen:
Voorbeeld van een horizontale snoeimesituatie.
In code zal dit eindigen als een reeks als verklaringen controleren voor deze situaties. Je kunt het voorbeeld hier zien, met een beschrijving van de juiste zaak uit de afbeelding:
if (directionY == 0) if (! _world.isBlocked (current.x + directionX, current.y)) if (_world.isBlocked (current.x, current.y + 1)) // maak een knooppunt met de nieuwe positie neighbours.push (Node.pooledNode (current.x + directionX, current.y + 1));
Nadat we de buurman hebben gepickt, proberen we een sprongpunt te vinden, een knooppunt dat vanaf de huidige kan worden bereikt, maar niet noodzakelijkerwijs op een enkele manier. Formeler gezegd, wat JPS doet, is het elimineren van symmetrie tussen paden - elk heeft een andere permutatie van dezelfde zetten:
Dus voor grote open ruimtes kunnen we enorme winsten behalen. Hier is hoe de sprongmethode werkt:
functie jump (cX: int, cY: int, dX: int, dY: int, start: Node, end: Node): Node // cX, cY - Huidige knooppuntpositie, dX, dY - richting // Positie van nieuwe knoop die we gaan overwegen: var nextX: int = cX + dX; var nextY: int = cY + dY; // Als het geblokkeerd is, kunnen we hier niet springen als (_world.isBlocked (nextX, nextY)) null retourneert; // Als het knooppunt het doel is, retourneert u dit als (nextX == end.x && nextY == end.y) een nieuw knooppunt retourneert (nextX, nextY); // Diagonal Case if (dX! = 0 && dY! = 0) if (/ * ... Diagonal Forced Neighbour Check ... * /) return Node.pooledNode (nextX, nextY); // Controleer in horizontale en verticale richting voor gedwongen buren // Dit is een speciaal geval voor diagonale richting als (jump (nextX, nextY, dX, 0, start, end)! = Null || jump (nextX, nextY, 0 , dY, start, end)! = null) retourneer Node.pooledNode (nextX, nextY); else // Horizontal case if (dX! = 0) if (/ * ... Horizontal Forced Neighbour Check ... * /) return Node.pooledNode (nextX, nextY); /// Vertical case else if (/ * ... Verticale geforceerde buurcontrole ... * /) return Node.pooledNode (nextX, nextY); /// Als de geforceerde buur niet is gevonden, probeer dan de volgende jump point return jump (nextX, nextY, dX, dY, start, end);
Ik heb de gedwongen buurcontroles uit de if-instructies verwijderd omdat deze vrij groot zijn. Ze bestaan in feite uit de controles die vergelijkbaar zijn met die toen we voor het eerst buren kochten voor een nieuw knooppunt (veel controles om te zien of cellen zijn geblokkeerd). Ze dienen om te detecteren wanneer we onze aannames over symmetrie mogen hebben.
Het diagonale omhulsel is speciaal en we moeten niet alleen kijken naar gedwongen buren in de diagonale richtingen, maar ook in de horizontale en verticale richting, en als een van deze faalt, moeten we een geforceerd knooppunt als springpunt plaatsen. We moeten ook een speciaal geval van het doelknooppunt overwegen, waar de sprongmethode eindigt.
Telkens wanneer we geen zoekknooppunt vinden, noemen we de sprongfunctie recursief in de opgegeven richting. In de demo heb ik deze recursieve oproep eigenlijk uitgerold omdat dit veel wordt genoemd. (In mijn testen verbeterde deze prestatie met een factor twee.)
Dit is wat JPS doet; het eindresultaat is nieuw te controleren knooppunten voor A * en we gaan verder met het algoritme. Wanneer een doelknooppunt wordt gevonden, reconstrueren we het pad en geven het terug.
JPS kan veel knooppunten overslaan tijdens het zoeken, wat mooie snelheidsverbeteringen kan opleveren (in mijn project is het ongeveer 30x meer dan A *), maar er zijn wel kosten aan verbonden.
Het werkt het beste op een uniform raster, maar kan worden gemaakt om te werken met niet-uniformen met behulp van extra aanpassingen, waarbij buren worden gemarkeerd als geforceerd wanneer er een overgang is naar een knooppunt met verschillende kosten (het beste om discrete kosten te gebruiken).
In een game waaraan ik werk, is het raster uniform, behalve op wegen, wat veel minder kost dan op een normaal terrein te lopen. (Het ziet er veel beter uit als het personage dat respecteert.) Uiteindelijk heb ik dit opgelost door een aantal waarden van wegposities vooraf te berekenen. Wanneer pathfinding wordt geïnitieerd, zoekt het algoritme mogelijke dichtstbijzijnde punten naar het pad vanaf de start- en doelknooppunten en zoekt het vervolgens een speciale grafiek op hoog niveau van wegen (die vooraf is berekend) en gebruikt het vervolgens JPS om terreingebieden te doorzoeken.
Een korte opmerking over foutopsporing. Het debuggen van dit soort algoritmen kan heel moeilijk zijn en het is vrijwel zeker dat de eerste implementatie moeilijk te vinden zal zijn. Je kunt jezelf een plezier doen en een soort van visualisatie functioneel bouwen en tekenen wat er gebeurt als het algoritme wordt uitgevoerd.
Als u een bug krijgt, moet u het domein (rastergrootte) tot het minimum terugbrengen, zodat u uw probleem kunt reproduceren en vanaf daar kunt testen. Zoals je waarschijnlijk wel kunt raden, werkte mijn eerste implementatie van JPS niet meteen!
Accentsconagua