Share
Een * grid-gebaseerde pathfinding werkt goed voor games waarin de personages vrij kunnen bewegen langs zowel de x- als de y-as. Het probleem om dit toe te passen op platformgames is dat de beweging op de y-as sterk beperkt is vanwege gesimuleerde gravitatiekrachten.
In deze zelfstudie zal ik een algemeen overzicht geven van hoe een standaard A * -algoritme moet worden aangepast om voor platformspelers te werken door deze zwaartekrachtbeperkingen te simuleren. (In het volgende deel zal ik door het coderen van het algoritme lopen.) Het aangepaste algoritme kan worden gebruikt om een AI-teken te maken dat de speler volgt of om de speler een route naar zijn doel te laten zien, bijvoorbeeld.
Ik neem hier aan dat je al bekend bent met A * pathfinding, maar als je een inleiding nodig hebt, is Patrick Lesters A * Pathfinding voor beginners uitstekend.
U kunt de Unity-demo of de WebGL-versie (64 MB) spelen om het uiteindelijke resultaat in actie te zien. Gebruik WASD om het personage te verplaatsen, links klikken op een plek om een pad te vinden dat je kunt volgen om er te komen, en klik met de rechtermuisknop een cel om de grond op dat punt te wisselen.
Aan het einde van deze serie hebben we ook eenrichtingsplatforms toegevoegd, de code uitgebreid met verschillende lettergroottes en een bot gecodeerd die automatisch het pad kan volgen! Bekijk hier de Unity-demo (of de 100MB + WebGL-versie).
Voordat we het pathfinding-algoritme kunnen aanpassen, moeten we duidelijk definiëren welke vormen de paden zelf kunnen vormen.
Laten we zeggen dat ons personage het opneemt een cel, en kan springen drie cellen hoog.
We zullen ons personage niet diagonaal door cellen laten bewegen, omdat we niet willen dat het door vast terrein gaat. (Dat wil zeggen, we zullen niet toestaan dat het door de hoek van een cel beweegt, alleen via de boven-, onder-, linker- of rechterkant.) Om naar een diagonaal aangrenzende cel te gaan, moet het personage een cel omhoog of omlaag verplaatsen en één cel naar links of rechts.
Omdat de spronghoogte van het personage drie cellen is, mag het, wanneer het springt, nadat het drie keer omhoog is bewogen, niet in staat zijn om te bewegen omhoog meer cellen, maar het moet nog steeds naar de kant.
Op basis van deze regels is hier een voorbeeld van het pad dat het personage zou volgen tijdens zijn maximale sprong op de afstand:
Natuurlijk kan het personage recht omhoog springen, of met elke combinatie van links en rechts bewegingen, maar dit voorbeeld toont het soort benadering dat we moeten omhelzen bij het berekenen van het pad met behulp van het raster..
Elk van de cellen in het pad moet gegevens over de spronghoogte bijhouden, zodat ons algoritme kan detecteren dat de speler niet hoger kan springen en moet beginnen te vallen.
Laten we beginnen met het toewijzen van de sprongwaarde van elke cel door deze met één te verhogen, elke cel, zolang de sprong doorgaat. Natuurlijk, als het personage op de grond staat, zou de sprongwaarde moeten zijn 0.
Hier is die regel toegepast op hetzelfde maximale sprongsprongstraject van vóór:
De cel die een bevat 6 markeert het hoogste punt in het pad. Dit is logisch, want dat is twee keer de waarde van de maximale springhoogte van het personage, en het personage wisselt af met één cel omhoog en één cel naar de zijkant, in dit voorbeeld.
Houd er rekening mee dat als het teken recht omhoog springt en we de sprongwaarde met één cel per keer verhogen, dit niet langer werkt, omdat in dat geval de hoogste cel een sprongwaarde van 3.
Laten we onze regel aanpassen om de sprongwaarde te verhogen naar de volgende even getal telkens wanneer het personage omhoog beweegt. Als de sprongwaarde dan gelijk is, kan het teken naar links, naar rechts of naar beneden (of omhoog, als ze geen sprongwaarde van 6 nog), en als de sprongwaarde oneven is, beweegt het personage alleen omhoog of omlaag (afhankelijk van of ze de top van de sprong al hebben bereikt).
Dit is hoe dat eruit ziet voor een sprong recht omhoog:
En hier is een meer gecompliceerd geval:
Zo worden de sprongwaarden berekend:
Zoals u kunt zien, weten we bij dit soort nummering precies wanneer het personage zijn maximale springhoogte bereikt: het is de cel met de sprongwaarde gelijk aan tweemaal de maximale spronghoogte van het karakter. Als de sprongwaarde kleiner is dan dit, kan het karakter nog steeds omhoog bewegen; anders moeten we het knooppunt direct hierboven negeren.
Nu we ons bewust zijn van het soort bewegingen dat het personage op het raster kan maken, laten we de volgende opstelling overwegen:
De groene cel op positie (3, 1) is het personage; de blauwe cel op positie (2, 5) is het doel. Laten we een route tekenen die het A * -algoritme als eerste kan kiezen om het doel @ te bereiken
Het gele getal in de rechterbovenhoek van een cel is de sprongwaarde van de cel. Zoals je kunt zien, kan het personage met een recht omhoog springen drie tegels omhoog springen, maar niet verder. Dit is niet goed.
Misschien vinden we meer geluk met een andere route, dus laten we onze zoekopdracht terugspoelen en opnieuw beginnen vanaf het knooppunt (3, 2).
Zoals je kunt zien springt het blok op de rechterkant van het personage hoog genoeg om naar het doel te gaan! Er is echter een groot probleem hier ...
Naar alle waarschijnlijkheid zal de eerste route die het algoritme zal nemen de eerste zijn die we hebben onderzocht. Na het innemen komt het algoritme niet ver en komt het weer terug bij het knooppunt (3, 2). Het kan dan door knooppunten zoeken (4, 2), (4, 3), (3, 3) (nog een keer), (3, 4) (nog een keer), (3, 5), en tenslotte de doelcel, (2, 5).
In een standaardversie van het A * -algoritme, als een knooppunt eenmaal al is bezocht, hoeven we het nooit meer te verwerken. In deze versie doen we dat echter wel. Dit komt omdat de knooppunten niet alleen worden onderscheiden door x- en y-coördinaten, maar ook door sprongwaarden.
Bij onze eerste poging om een pad te vinden, de sprongwaarde op het knooppunt (3, 3) was 4; bij onze tweede poging was het dat wel 3. Omdat in de tweede poging de sprongwaarde in die cel kleiner was, betekende dit dat we mogelijk hoger zouden kunnen komen dan we tijdens de eerste poging zouden kunnen doen.
Dit betekent in feite dat knooppunt (3, 3) met een sprongwaarde van 4 is een ander knooppunt dan het knooppunt bij (3, 3) met een sprongwaarde van 3. Het raster moet op sommige coördinaten in wezen driedimensionaal worden om rekening te houden met deze verschillen, zoals:
We kunnen niet zomaar de sprongwaarde van het knooppunt wijzigen (3, 3) van 4 naar 3, omdat sommige paden meerdere keren hetzelfde knooppunt gebruiken; als we dat zouden doen, zouden we in feite het vorige knooppunt overschrijven en dat zou natuurlijk het eindresultaat bederven.
We zouden hetzelfde probleem hebben als het eerste pad het doel zou hebben bereikt ondanks de hogere sprongwaarden; als we een van de knooppunten hadden overschreven met een meer veelbelovende, dan zouden we geen manier hebben om het oorspronkelijke pad te herstellen.
Vergeet niet dat het de algoritme die een grid-gebaseerde benadering gebruikt; in theorie hoeft je spel en zijn niveaus dat niet te doen.
Het is belangrijk voor het karakter om te hebben tenminste zoveel bewegingsvrijheid als het algoritme verwacht - en bij voorkeur een beetje meer dan dat.
De karakterbeweging exact overeenkomen met de beperkingen van het algoritme is geen haalbare aanpak, vanwege de discrete aard van het raster en de celgrootte van het raster. Het is mogelijk om de natuurkunde op zo'n manier te coderen dat het algoritme dat zal doen altijd vind een manier als er een is, maar daarvoor moet je de natuurkunde voor dat doel bouwen.
De benadering die ik in deze zelfstudie volg, is om het algoritme aan te passen aan de fysica van de game, en niet andersom.
De grootste problemen doen zich voor in randgevallen wanneer de verwachte vrijheid van bewegingsvrijheid van het algoritme niet overeenkomt met de bewegingsvrijheid van het echte in-game personage.
Laten we zeggen dat de AI het mogelijk maakt om zes cellen lang te springen, maar de fysica van het spel laten een sprong met zeven cellen toe. Als er een pad is waarbij de langere sprong nodig is om het doel in de snelste tijd te bereiken, dan zal de bot dat pad negeren en de meer conservatieve kiezen, denkend dat de langere sprong onmogelijk is.
Als er een pad is dat een langere sprong vereist en er geen andere manier is om het doel te bereiken, concludeert de Pathfinder dat het doel onbereikbaar is.
Als, omgekeerd, het algoritme denkt dat het mogelijk is om zeven cellen weg te springen, maar de fysica van de game staat eigenlijk alleen een sprong met zes cellen toe, dan kan de bot het verkeerde pad volgen en in een plaats vallen van waar het niet kan komen uit, of probeer opnieuw een pad te vinden en ontvang hetzelfde onjuiste resultaat, waardoor een lus ontstaat.
(Van deze twee problemen is het beter om de fysica van de game meer bewegingsvrijheid te laten hebben dan het algoritme verwacht.)
De eerste manier om ervoor te zorgen dat het algoritme altijd correct is, is om niveaus te hebben die spelers niet kunnen wijzigen. In dit geval moet u er alleen voor zorgen dat het terrein dat u ontwerpt of genereert goed werkt met de padvindende AI.
De tweede oplossing voor deze problemen is het aanpassen van het algoritme, de fysica of beide, om er zeker van te zijn dat ze overeenkomen. Zoals ik eerder al zei, betekent dit niet dat ze moeten matchen precies; bijvoorbeeld, als het algoritme denkt dat het personage vijf cellen omhoog kan springen, is het goed om de echte maximale sprong in te stellen 5.5 cellen hoog. (In tegenstelling tot het algoritme kan de fysica van de game fractionele waarden gebruiken.)
Afhankelijk van de game, kan het ook waar zijn dat de AI-bot geen bestaand pad vindt, geen enorme deal; het geeft gewoon op en gaat terug naar zijn post, of zit gewoon en wacht op de speler.
Op dit punt zou je een redelijk conceptueel begrip moeten hebben van hoe A * pathfinding kan worden aangepast aan een platformer. In mijn volgende tutorial zullen we dit concreet maken, door een bestaand A * pathfinding-algoritme daadwerkelijk aan te passen om dit in een game te implementeren!
Accentsconagua