Share
En * gridbaserad sökväg fungerar bra för spel där tecknen kan röra sig fritt längs både x- och y-axlarna. Problemet med att applicera detta på plattformar är att rörelsen på y-axeln är starkt begränsad på grund av simulerade gravitationskrafter.
I denna handledning ger jag en bred översikt över hur man modifierar en standard A * -algoritm för att arbeta för plattformspersoner genom att simulera dessa gravitationsbegränsningar. (I nästa del går jag igenom faktiskt kodning av algoritmen.) Den anpassade algoritmen kan användas för att skapa ett AI-tecken som följer spelaren eller för att visa spelaren en väg till sitt mål, till exempel.
Jag antar här att du redan är bekant med A * pathfinding, men om du behöver en introduktion är Patrick Lesters A * Pathfinding for Beginners utmärkt.
Du kan spela Unity-demo eller WebGL-versionen (64 MB) för att se slutresultatet i åtgärd. Använda sig av WASD för att flytta karaktären, vänster klick på en plats för att hitta en väg som du kan följa för att komma dit, och Högerklicka en cell för att växla marken vid den tiden.
I slutet av denna serie har vi också lagt till envägsplattformar, utökat koden för att hantera olika storlekar av tecken och kodade en bot som automatiskt kan följa vägen! Kolla in Unity demo här (eller 100MB + WebGL versionen).
Innan vi kan anpassa pathfinding-algoritmen måste vi tydligt definiera vilka former vägarna själva kan ta.
Låt oss säga att vår karaktär tar upp en cell, och kan hoppa tre celler hög.
Vi tillåter inte att vår karaktär flyttas diagonalt genom celler, eftersom vi inte vill att den ska gå igenom solid terräng. (Det vill säga att vi inte tillåter det att röra sig genom hörnet av en cell, bara genom den övre, nedre, vänstra eller högra sidan.) För att flytta till en diagonalt intilliggande cell måste tecknet flytta en cell upp eller ner , och en cell till vänster eller höger.
Eftersom karaktärens höjdhöjd är tre celler, så ska den inte kunna flytta när den hoppar, efter att den har flyttat upp tre gånger upp några fler celler, men det borde fortfarande kunna flytta till sida.
Baserat på dessa regler är här ett exempel på den väg som karaktären skulle ta under dess maximala distanshopp:
Naturligtvis kan karaktären hoppa rakt upp, eller med en kombination av vänster och höger rörelser, men det här exemplet visar vilken typ av approximation vi behöver ta om när vi beräknar banan med hjälp av gallret.
Var och en av cellerna i banan måste behålla data om höjdhöjden, så att vår algoritm kan upptäcka att spelaren kan hoppa inte högre och måste börja falla ned.
Låt oss börja med att tilldela varje cells hoppvärde genom att öka den med en, varje cell, så länge hoppet fortsätter. Naturligtvis, när karaktären är på marken, bör hoppvärdet vara 0.
Här är den här regeln som tillämpas på samma högsta distanshoppväg från tidigare:
Den cell som innehåller en 6 markerar den högsta punkten i sökvägen. Det här är meningsfullt, eftersom det är dubbelt så mycket som karaktärens maximala hopphöjd, och karaktären växlar till att flytta en cell upp och en cell till sidan, i det här exemplet.
Observera att om tecknet hoppar rakt upp och vi fortsätter att öka hoppvärdet med en varje cell, fungerar det inte längre, för i så fall skulle den högsta cellen ha ett hoppvärde av 3.
Låt oss ändra vår regel för att öka hoppvärdet till nästa jämnt nummer när tecknet rör sig uppåt. Då, om hoppvärdet är jämnt, kan tecknet flytta antingen till vänster, höger eller nedåt (eller uppåt, om de inte har nått ett hoppvärde av 6 ändå), och om hoppvärdet är udda, flyttar tecknet bara uppåt eller nedåt (beroende på huruvida de har nått toppen av hoppet än).
Så här ser det ut som ett hoppa rakt upp:
Och här är ett mer komplicerat fall:
Här är hur hoppa värdena beräknas:
Som du kan se, med denna typ av nummerering vet vi exakt när karaktären når sin maximala höjdhöjd: det är cellen med hoppvärdet lika med dubbelt högsta teckenhopphöjd. Om hoppvärdet är mindre än detta kan tecknet fortfarande röra sig uppåt; annars måste vi ignorera noden direkt ovanför.
Nu när vi är medvetna om vilken typ av rörelser karaktären kan göra på nätet, låt oss överväga följande inställningar:
Den gröna cellen i position (3, 1) är karaktären; den blå cellen i position (2, 5) är målet. Låt oss rita en rutt som A * -algoritmen kan välja först för att försöka nå målet @
Det gula numret i det högra högra hörnet av en cell är cellens hoppvärde. Som du kan se, med ett rakt uppåt hopp kan karaktären hoppa tre kakel upp, men inte längre. Det här är inte bra.
Vi kan hitta mer lycka till med en annan rutt, så låt oss spola tillbaka vår sökning och börja igen från nod (3, 2).
Som du kan se hoppade på kvarteret till höger om karaktären fick det hoppa tillräckligt högt för att nå målet! Det finns dock ett stort problem här ...
I all sannolikhet är den första vägen som algoritmen tar är den första vi undersökte. Efter att ha tagit det kommer algoritmen inte att bli väldigt långt, och kommer att hamna tillbaka vid noden (3, 2). Det kan sedan söka igenom noder (4, 2), (4, 3), (3, 3) (igen), (3,4) (igen), (3, 5), och slutligen målcellen, (2, 5).
I en grundläggande version av A * -algoritmen, om en nod har besökts en gång redan, behöver vi inte behandla det någonsin igen. I den här versionen gör vi dock. Detta beror på att noderna inte skiljer sig uteslutande av x- och y-koordinater, men också av hoppvärden.
I vårt första försök att hitta en sökväg, hoppar värdet vid nod (3, 3) var 4; i vårt andra försök var det 3. Eftersom i det andra försöket hoppvärdet vid den cellen var mindre, menade det att vi potentiellt kunde bli högre därifrån än vi kunde under det första försöket.
Detta betyder i grunden att noden (3, 3) med ett hoppvärde på 4 är en olika nod än noden vid (3, 3) med ett hoppvärde på 3. Nätet behöver i huvudsak bli tredimensionellt vid vissa koordinater för att tillgodose dessa skillnader, som så:
Vi kan inte bara ändra nodens hoppvärde på (3, 3) från 4 till 3, eftersom vissa vägar använder samma nod flera gånger; om vi gjorde det skulle vi i grund och botten åsidosätta den tidigare noden och det skulle givetvis korrumpera slutresultatet.
Vi skulle ha samma problem om den första vägen skulle ha nått målet trots de högre hoppvärdena om vi hade överträtt ett av noderna med en mer lovande, så hade vi inget sätt att återställa den ursprungliga vägen.
Kom ihåg att det är algoritm som använder ett nätbaserat tillvägagångssätt I teorin behöver ditt spel och dess nivåer inte.
Det är viktigt för karaktären att ha åtminstone lika mycket rörelsefrihet som algoritmen förväntar sig - och helst lite mer än det.
Med karaktärsrörelsen matchar exakt är algoritmens begränsningar inte ett livskraftigt tillvägagångssätt, på grund av nätets diskreta natur och nätets cellstorlek. Det är möjligt att koda fysiken på ett sådant sätt att algoritmen kommer alltid hitta en väg om det finns en, men det kräver att du bygger fysiken för det ändamålet.
Tillvägagångssättet jag tar i denna handledning är att passa algoritmen till spelets fysik, inte tvärtom.
De största problemen uppstår i kantfall när algoritmens förväntade frihetsfrihet inte överensstämmer med den sanna spelets karaktärs rörelsefrihet.
Låt oss säga att AI möjliggör hoppar sex celler långt, men spelets fysik tillåter en sju-cell hopp. Om det finns en väg som kräver att det längre hoppet når målet på den snabbaste tiden, kommer boten att ignorera den banan och välja den mer konservativa, tänkande att det längre hoppet är omöjligt.
Om det finns en väg som kräver längre hoppa och det finns inget annat sätt att nå målet, då kommer sökaren att dra slutsatsen att målet är oåtkomligt.
Om omvänt talar algoritmen om att det är möjligt att hoppa sju celler bort, men spelets fysik tillåter endast en sexcellshopp, då kan bot antingen följa fel väg och falla till en plats från vilken den inte kan få ut, eller försök hitta en sökväg igen och få samma felaktiga resultat, vilket orsakar en slinga.
(Av dessa två problem är det att föredra att låta spelets fysik möjliggöra mer rörelsefrihet än vad algoritmen förväntar sig.)
Det första sättet att säkerställa att algoritmen alltid är korrekt är att ha nivåer som spelare inte kan ändra. I det här fallet behöver du bara se till att oavsett terräng du designar eller genererar fungerar bra med AI.
Den andra lösningen på dessa problem är att finjustera algoritmen, fysiken eller båda, för att se till att de matchar. Som jag nämnde tidigare betyder det inte att de behöver matcha exakt; till exempel om algoritmen tycker att tecknet kan hoppa fem celler uppåt är det bra att ställa in det riktiga maximala hoppet på 5,5 celler höga. (Till skillnad från algoritmen kan spelets fysik använda fraktionsvärden.)
Beroende på spel kan det också vara sant att AI-botten inte hittar en befintlig väg är inte en stor sak. det kommer helt enkelt ge upp och gå tillbaka till sin post, eller bara sitta och vänta på spelaren.
Vid denna tidpunkt borde du ha en anständig begreppsmässig förståelse för hur A * pathfinding kan anpassas till en plattformsperson. I min nästa handledning kommer vi att göra denna konkreta genom att faktiskt anpassa en befintlig A * sökningsalgoritm för att implementera detta i ett spel!
Accentsconagua