Unlimited WordPress themes, graphics, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Game Development
  2. Pathfinding
Gamedevelopment

A * Pathfinding vir 2D Grid-Based Platformers: Maak die Bot Volg die Weg

by
Difficulty:IntermediateLength:LongLanguages:
This post is part of a series called How to Adapt A* Pathfinding to a 2D Grid-Based Platformer.
A* Pathfinding for 2D Grid-Based Platformers: Different Character Sizes
A* Pathfinding for 2D Grid-Based Platformers: Ledge Grabbing

Afrikaans (Afrikaans) translation by Meyria (you can also view the original English article)

In hierdie handleiding sal ons gebruik the platformer pathfinding algorithm we've been building om 'n bot aan te sit wat die pad self kan volg; kliek net op die plek en dit sal hardloop en na dit spring. Dit is baie nuttig vir NPC!

Demo

Jou kan play the Unity demo, of the WebGL version (100MB+), om die finale uitslag in aksie te sien. Gebruik WASD om die karakter te beweeg, klik links en iewers om 'n pad te vind wat jou kan volg om daar te kom, regskliek op die sel om op daardie stadium na die grond te skuif, middelste kliek om die eenrigtingplatform te plaas, en klik en skuif die skuifbalk na verander die waarde daarvan.

Opdatering van die Enjin

Hantering van die Bot Staat

Die bot het twee state gedefinieer: die eerste is om niks te doen nie, en die tweede is vir die hantering van die beweging. In jou spel sal jou waarskynlik nog baie meer nodig hê om die bot se gedrag volgens die situasie te verander.

Die bot se opdateringslus sal verskillende dinge doen, afhangende van watter toestand tans aan mCurrentBotState toegewys is:

Die CharacterUpdate funksie hanteer al die insette en updates fisika vir die bot.

Om die staat te verander, sal ons 'n ChangeState funksie gebruik wat die nuwe waarde net aan mCurrentBotState toeken:

Beheer van die Bot

Ons sal die bot beheer deur insette te simuleer, wat ons sal toewys aan 'n verskeidenheid Booleans:

Hierdie skikking word geïndekseer deur die KeyInput enum:

As ons byvoorbeeld wil simuleer, druk die linker knoppie, ons sal dit so doen:

Die karakterlogika sal dan hierdie kunsmatige insette hanteer op dieselfde manier dat dit werklike insette hanteer.

Ons benodig ook addisionele hulpfunksies of opknappingstabelle om die aantal rame te kry wat ons nodig het om die springknoppie te druk om na 'n gegewe aantal blokke te spring:

Let daarop dat dit net konsekwent sal werk as ons speletjies met 'n vaste frekwensie opgedateer word en die aanvanklike sprongspoed van karakters dieselfde is. Ideaal gesproke sal ons hierdie waardes afsonderlik vir elke karakter bereken, afhangende van die spoed van daardie karakter, maar die bogenoemde sal in ons geval goed werk.

Voorbereiding en Verkryging van die Pad om te Volg

Beperking van die Doelplek

Voordat ons die navigator eintlik gebruik, sal dit 'n goeie idee wees om die bestemmingsdoel te dwing om op die grond te wees. Dit is omdat die speler heel waarskynlik 'n puntjie wat effens bokant die grond is, klik. In dié geval sal die botpad met 'n ongemaklike sprong in die lug beland. Deur die eindpunt te verlaag om reg op die grond te wees, kan ons dit maklik vermy.

Kom ons kyk eers na die TappedOnTile funksie. Hierdie funksie word geroep wanneer die speler enige plek in die spel klik. die parameter mapPos is die posisie van die teël waarop die speler gekliek het:

Ons moet die posisie van die geklikte teël laat sak totdat dit op die grond is:

Ten slotte, wanneer ons by 'n grondtand kom, weet ons waarheen ons die karakter wil skuif na:

Bepaling van die Beginpunt

Voordat ons eintlik die FindPath funksie noem, moet ons seker maak dat ons die korrekte aanvangsel slaag.

Eerstens, laat ons aanneem dat die aanvangskakel die onderste linker sel van 'n karakter is:

Hierdie teël is dalk nie die een wat ons as die eerste nodus na die algoritme wil slaag nie, want as ons karakter op die rand van die platform staan, kan die startTile wat op hierdie manier bereken word, geen grond hê soos in die volgende situasie nie:

In hierdie geval wil ons graag die beginknoop op die teël sit wat aan die linkerkant van die karakter is, nie in die middel nie.

Kom ons begin met die skep van 'n funksie wat ons sal vertel of die karakter 'n ander posisie sal pas, en as dit waar is, is dit op die grond in daardie plek:

Laat ons eers kyk of die karakter die plek pas. As dit nie die geval is nie, kan ons onmiddelik vals terugkom:

Nou kan ons sien of enige van die teëls onder die karakter grondplate is:

Kom ons gaan terug na die MoveTo funksie, en kyk of ons die aanvanklike teël moet verander. Ons moet dit doen as die karakters op die grond is, maar die aanvanklike teël is nie:

Ons weet dat in hierdie geval die karakter op die linkerkant of die regterkant van die platform staan.

Laat ons eers die regterrand kyk. As die karakter daar pas en die teëls op die grond is, dan moet ons die teëls van een kamer na regs skuif. Indien nie, dan moet ons dit na links beweeg.

Nou moet ons al die data hê wat ons nodig het om die padzoeker te noem:

Die eerste argument is die begin teël.

Die tweede is die bestemming; ons kan dit as-is slaag.

Die derde en vierde argumente is die breedte en die hoogte wat benader moet word deur die teëlgrootte. Let daarop dat ons die plafon van die hoogte in teëls wil gebruik? -so, byvoorbeeld, as die werklike hoogte van die karakter 2,3 teëls is, wil ons die algoritme om te dink die karakter is eintlik 3 teëls hoog. (Beter as die werklike hoogte van die werklike karakter effens kleiner is as die grootte in die teël, om 'n bietjie meer ruimte vir foute uit die pad na die AI toe te laat.)

Ten slotte is die vyfde argument die maksimum springhoogte van die karakter.

Rugsteun die Noduse Lys

Nadat ons die algoritme uitgevoer het, moet ons kyk of die resultaat goed is - dit wil sê, as daar 'n pad gevind word:

As dit so is, moet ons die nodes na 'n aparte buffer kopieer, want as 'n ander voorwerp die soekresultate se FindPath funksie nou sou bel, sal die ou resultaat oorskry word. As jou die resultaat na 'n aparte lys kopieer, sal dit voorkom.

Soos jou kan sien, kopieer ons die resultaat in omgekeerde volgorde; Dit is omdat die resultaat self omgekeer word. Deur dit te doen beteken die nodusse in die mPath lys in eerste tot laaste volgorde.

Kom ons stel nou die huidige doelknooppunt neer. Omdat die eerste nodus in die lys die beginpunt is, kan ons dit eintlik oorskakel en voortgaan vanaf die tweede knoop na bo:

Nadat u die huidige doelknooppunt ingestel het, stel ons die botstaat op MoveTo, sodat 'n toepaslike status geaktiveer sal word.

Die Konteks Kry

Voordat ons die reëls vir die AI-beweging begin skryf, moet ons in staat wees om te bepaal watter situasie die karakter op enige gegewe punt is.

Ons moet weet:

  • die posisies van die vorige, huidige en volgende bestemmings
  • of die huidige doel op die grond of in die lug is
  • of die karakter die huidige bestemming op die x-as bereik het
  • of die karakter die huidige bestemming op die y-as bereik het

Let wel: die doel hier is nie noodwendig die finale doel nie; hulle is die nodusse in die lys uit die vorige afdeling.

Hierdie inligting sal akkuraat bepaal wat die been in enige situasie moet doen.

Kom ons begin deur 'n funksie te verklaar om hierdie konteks te kry:

Berekening van Wêreldposisies van Bestemmings Node

Die eerste ding wat ons in hierdie funksie moet doen, is om die wêreldposisie van die bestemmingskode te bereken.

Kom ons begin deur dit te bereken vir die vorige bestemming. Hierdie operasie hang af van hoe jou spelwêreld ingestel is; In my geval pas die kaartkoördinate nie by die wêreldkoördinate nie, so ons moet dit vertaal.

Om dit te vertaal is baie eenvoudig: ons moet net die posisie van die nodus vermeerder volgens die grootte van die teël, dan verreken die vektor bereken op grond van die kaartposisie:

Let daarop dat ons begin met mCurrentNodeId gelyk aan 1, dus ons hoef nie bekommerd te wees dat u per ongeluk probeer om toegang te verkry tot 'n nodus met 'n indeks van -1 nie.

Ons sal die posisie van die huidige bestemming op dieselfde manier bereken:

En nou vir die volgende bestemming se posisie. Hier moet ons kyk of daar enige nodes links te volg nadat ons ons huidige doel te bereik, so eerste kom ons aanvaar dat die volgende bestemming is dieselfde as die huidige een:

Nou, as daar enige nodusse oor is, bereken ons die volgende bestemming op dieselfde manier as wat ons die vorige twee gedoen het:

Kontroleer of die knoop op die grond is

Die volgende stap is om vas te stel of die bestemming op die grond is.

Onthou dat dit nie genoeg is om slegs die teël direk onder die doel te kyk nie; ons moet die gevalle oorweeg waar die karakter meer as een blok wyd is:

Kom ons begin deur aan te neem dat die bestemming se posisie nie op die grond is nie:

Nou kyk ons ​​deur die teëls onder die bestemming om te sien of daar stewige blokke daar is. As daar is, kan ons destOnGround tot waar stel:

Kontroleer of die nodus op die X-as bereik is

Voordat ons die doel kan sien, moet ons sy posisie op die pad ken. Hierdie posisie is basies die middelpunt van die linkerkantse sel van ons karakter. Aangesien ons gekenmerk word deur die karakter se grenskas plus 'n halwe sel:

Dit is die posisie wat ons moet ooreenstem met die doel nodusse.

Hoe kan ons bepaal of die karakter die doel op die x-as bereik het? Dit sal veilig wees om te aanvaar dat as die karakter reg beweeg en 'n x-posisie het wat groter of gelyk is aan dié van die bestemming, dan is die doel bereik.

Om te sien of die karakter reg beweeg, gebruik ons ​​die vorige bestemming, wat in hierdie geval links van die huidige een moes wees:

Dieselfde geld vir die teenoorgestelde kant; as die vorige bestemming regs van die doel is en die karakter se x-posisie is, kan ons seker wees dat die karakter die doel op die x-as bereik het:

Snap die karakter se posisie

Soms weens die karakter se spoed word die bestemming oorskry, wat kan daartoe lei dat dit nie op die teikenknoop land nie. Sien die volgende voorbeeld:

Om dit reg te stel, snap ons die karakter se posisie sodat dit op die doelknoop land.

Die voorwaardes vir ons om die karakter te snap is:

  • Die doel is bereik op die x-as.
  • Die afstand tussen die posisie van die bot en die huidige bestemming is groter as cBotMaxPositionError.
  • Die afstand tussen die posisie van die bot en die huidige bestemming is nie ver nie, so ons snap die karakter van ver af nie.
  • Die karakter het nie links of regs laaste beurt beweeg nie, so ons snap slegs die karakter as dit reguit val.

cBotMaxPositionError in hierdie handleiding is gelyk aan 1 pixel; Dit is hoe ver ons die karakter uit die bestemming laat terwyl ons dit steeds toelaat om na die volgende doel te gaan.

Kontroleer of die nodus op die Y-as bereik is

Kom ons uitvind wanneer ons seker kan wees dat die karakter sy teiken se Y-posisie bereik het. Eerstens, as die vorige bestemming onder die huidige een is en ons karakter spring na die hoogte van die huidige doel, dan kan ons aanvaar dat die doel bereik is.

Net so, as die huidige bestemming onder die vorige een is en die karakter die y-posisie van die huidige nodus bereik het, kan ons bereikY ook waar maak.

Ongeag of die karakter moet spring of val om die bestemmingsknoppie se y-posisie te bereik, as dit regtig naby is, moet ons stel reachedY ook waar:

As die bestemming op die grond is, maar die karakter is nie, dan kan ons aanvaar dat die huidige Y se posisie nie bereik is nie:

Dis dis al die basiese data wat ons nodig het om te weet watter beweging die AI moet doen.

Hantering van die Bot se Beweging

Die eerste ding om te doen in ons update funksie kry die konteks wat ons pas geïmplementeer het:

Kom ons kry nou die karakter se huidige posisie langs die pad. Ons bereken dit op dieselfde manier as wat ons in die GetContextfunksie gedoen het:

Aan die begin van die raam moet ons die valse insette terugstel en dit slegs toewys as daar 'n voorwaarde ontstaan. Ons sal slegs vier insette gebruik: twee vir beweging links en regs, een vir spring, en een vir die aflê van 'n eenrigting-platform.

Die eerste voorwaarde vir beweging sal dit wees: as die huidige bestemming laer is as die posisie van die karakter en die karakter op 'n eenrigtingplatform staan, druk dan die af knoppie neer, wat die karakter moet laat spring wat van die platform afwaarts spring :

Hantering van spronge

Kom ons kyk hoe ons spronge moet werk. Eerstens wil ons nie die springknoppie druk as mFramesOfJumping 0 is nie.

Die tweede voorwaarde om te kyk is dat die karakter nie op die grond is nie.

In hierdie implementering van platformfisika word die karakter toegelaat om te spring as dit net van die rand van 'n platform af trap en nie meer op die grond is nie. Dit is 'n gewilde metode om 'n illusie te versag dat die speler die sprongknoppie gedruk het, maar die karakter het nie gespring nie, wat moontlik sou voorkom as gevolg van insetlaag of die speler wat die springknoppie druk, net nadat die karakter van die platform af beweeg het.

Hierdie voorwaarde sal werk as die karakter van 'n rand af moet spring, aangesien die rame van die spring op 'n gepaste hoeveelheid geplaas sal word, sal die karakter natuurlik van die rand af loop en op daardie punt sal die sprong ook begin.

Dit sal nie werk as die spring uit die grond uitgevoer moet word nie; Om hierdie toestande te hanteer, moet ons hierdie toestande nagaan:

  • Die karakter het die x-posisie van die bestemmingsknop bereik, waar dit begin spring.
  • Die bestemmingsknoppie is nie op die grond nie; as ons moet spring, moet ons eers 'n knoop wat eers in die lug is, gaan.

Die karakter moet ook spring as dit op die grond is en die bestemming is ook op die grond. Dit sal gewoonlik gebeur as die karakter een teël en na die kant moet spring om 'n platform te bereik wat net een blok hoër is.

Nou laat ons die sprong aktiveer en die sprongraamwerk ondergronds, sodat die karakter die sprong vir die korrekte aantal rame hou:

Let daarop dat ons slegs mFramesOfJumping verminder as die karakters nie in die grond is nie. Dit is om per ongeluk die springlengte te verminder voordat jou 'n sprong begin.

Opvolg na die Volgende Bestemmings Node

Kom ons dink oor wat moet gebeur as ons die nodus bereik - dit is wanneer reachX en reachY true is.

Eerstens verhoog ons die huidige nodus ID:

Nou moet ons seker maak of hierdie ID groter is as die aantal nodusse in ons pad. Indien wel, beteken dit dat die karakter die doel bereik het:

Die volgende ding wat ons moet doen, is om die spring vir die volgende nodus te bereken. Aangesien ons dit op meer as een plek moet gebruik, laat ons 'n funksie hiervoor maak:

Ons wil net spring as die nuwe nodus hoër is as die vorige een en die karakter is op die grond:

Om uit te vind hoeveel teëls ons moet slaan, herhaal ons hulle deur die nodes vir hoër en hoër. Wanneer ons by 'n knoop kom wat op 'n laer hoogte, of 'n knoop wat daar onder is, kan ons stop, want ons weet dat niks hoër sal wees nie.

Eerstens, laat ons verklaar en stel die veranderlike in wat die waarde van die sprong sal hou:

Laat dit nou deur die nodus let, begin by die huidige nodus:

As die volgende knoop hoër is as die jumpHeight, en dit is nie op die grond nie, laat ons die nuwe springhoogte stel:

As die hoogte van die nuwe nodus laer is as voor of op die grond, dan gee ons die aantal benodigde springrame terug na die hoogte wat gevind word. (En as dit nie nodig is om te spring nie, kom ons gaan terug 0.)

Ons moet hierdie funksie op twee plekke noem.

Die eerste een is in die geval waar die karakter die nodus se x- en y-posisies bereik het:

Let daarop dat ons die springrame vir die hele sprong stel, dus wanneer ons 'n lugnootnood bereik, wil ons nie die aantal springrame wat bepaal is voordat die sprong plaasgevind het, verander nie.

Nadat ons die doel opgedateer het, moet ons alles weer verwerk, sodat die volgende bewegingsraamwerk onmiddellik bereken word. Hiervoor gebruik ons ​​'n goto opdrag:

Die tweede plek waar ons die sprong moet bereken, is die MoveTo funksie, want dit kan die geval wees dat die eerste nodus van die pad 'n springknoop is:

Hantering Beweging om die Node se X-Posisie te Bereik

Laat ons nou die beweging hanteer vir die geval waar die karakter nog nie die x-posisie van die teikenknoppie bereik het nie.

Niks ingewikkeld hier nie; As die bestemming regs is, moet ons die regte knoppie druk simuleer. As die bestemming links is, moet ons die linker knoppie druk simuleer. Ons moet slegs die karakter beweeg as die verskil in posisie meer is as die cBotMaxPositionError konstante:

Hantering Beweging om die Node se Y-posisie te Bereik

As die karakter die x-posisie teiken bereik het, maar ons bly aan die hoër een spring, kan ons steeds die karakter na links of regs skuif, afhangende van waar die volgende bestemming is. Dit sal net beteken dat die karakters nie so rigied op die gekose pad bly nie. Danksy dit sal dit baie makliker wees om die volgende doel te bereik, want in plaas daarvan om net te wag om die y-pos teiken te bereik, sal die karakter natuurlik na die volgende x nodusposisie beweeg wanneer dit gedoen word.

Ons sal slegs die karakter na die volgende bestemming skuif as daar enigsins en niks op die grond is nie. (As dit op die grond is, kan ons dit nie mis nie, want dit is 'n belangrike kontrolepunt - dit herstel die karakter se vertikale spoed en laat dit toe om weer die spring te gebruik.)

Maar voordat ons eintlik na die volgende doel beweeg, moet ons seker maak dat ons nie die pad sal breek deur dit te doen nie.

Vermy Beëindiging van Voortydige Herfs

Oorweeg die Volgende Scenario:

Hier, sodra die karakter van die rand af begin, begin dit die x-posisie van die tweede nodus en val die y-posisie te bereik. Aangesien die derde knoop regs van die karakter is, beweeg dit regs - en eindig in die tonnel op bokant wat ons wil.

Om dit reg te stel, moet ons seker maak of daar enige struikelblokke tussen die karakter en die volgende bestemming is; as daar nie is nie, dan is ons vry om die karakter daarop te beweeg; as daar is, dan moet ons wag.

Eerstens, laat ons sien watter teëls ons moet kontroleer. As die volgende doel is aan die regterkant van die huidige een, dan moet ons die teëls regs kyk; As dit links is, moet ons die teëls na links kyk. As hulle in dieselfde x posisie is, is daar geen rede om voorbewegingsbewegings te doen nie.

Soos u kan sien, hang die x-koördinaat van die nodus regs af van die breedte van die karakter.

Nou kan ons seker maak of daar 'n teël is tussen die karakters en die volgende nodusposisie op die y-as:

Die AnySolidBlockInStripe funksie kontroleer of daar vaste stowwe tussen twee gegewe punte op die kaart is. Die punte moet dieselfde x-koördinaat hê. Die x koördinate wat ons nagaan is die teëls wat ons karakters wil skuif, maar ons weet nie of ons kan, soos hierbo beskryf nie.

Dit is die implementering van die funksie.

Soos jou kan sien, is sy funksie baie eenvoudig; net iterates deur die teëls in die kolom, vanaf die onderste een.

Noudat ons weet ons kan beweeg na die volgende doel kom ons doen:

Laat Bots Toe om Nodes te Slaag

Dit is amper - maar daar is nog een saak wat opgelos moet word. Hier is 'n voorbeeld:

Soos jou kan sien, voordat die karakter die posisie van die tweede knoop bereik, stamp dit in sy kop in 'n swewende teël, terwyl ons dit na die volgende bestemming na regs beweeg. As gevolg hiervan bereik die eindkarakter nooit die posisie van die tweede nodus y nie; in plaas van reguit na die derde nodus te beweeg. Omdat die bereikY verkeerd is in hierdie geval, kan dit nie met die pad voortgaan nie.

Om sulke gevalle te vermy, sal ons net kyk of die karakter die volgende bestemming bereik voordat die huidige een bereik word.

Die eerste stap in hierdie rigting sal die vorige berekening van reachX en reachY in hul eie funksie skei:

Vervolgens vervang die berekening met 'n funksieoproep in die GetContext funksie:

Nou kan ons kyk of die volgende doel bereik is. As dit so is, kan ons net mCurrentNode byvoeg en die status onmiddellik herwerk. Dit sal die volgende doelwit wees om die huidige een te wees, en aangesien die karakter dit bereik het, sal ons kan voortgaan:

Dit is alles vir karakterbeweging!

Hanteer Weerstoestande

Dit is goed om 'n rugsteunplan te hê vir 'n situasie waar die bot nie deur die pad beweeg nie. Dit kan gebeur, as die kaart, byvoorbeeld sal verander- Deur hindernisse vir die berekende pad te voeg, kan die pad ongeldig wees. Wat ons sal doen, is om die pad te herstel as die karakter langer as 'n sekere aantal rame vassteek. Dit gebeur, soos die kaart, byvoorbeeld sal verander-

Dus, laat ons 'n veranderlike verklaar wat sal bereken hoeveel karakters dit vasgesteek het en hoeveel rame dit die meeste in die steek laat kom:

Ons moet dit herstel wanneer ons die MoveTo funksie noem:

En uiteindelik, aan die einde van BotState.MoveTo, laat ons kyk of die karakter vas is. Hier moet ons net kyk of sy huidige posisie dieselfde is as die ou een; Indien wel, dan moet ons ook mStuckFrames insamel en kyk of die karakters vasgehou is vir meer rame as cMaxStuckFrames - en as dit waar is, moet ons die MoveTo funksie met die laaste nodus van die huidige pad as 'n parameter noem. Natuurlik, as die posisie anders is, moet ons mStuckFrames terugstel na 0:

Nou moet die karakter 'n alternatiewe manier vind as dit nie die eerste een kan voltooi nie.

Gevolgtrekking

Dit is die hele handleiding! Dit was baie werk, maar ek hoop jou sal hierdie metode nuttig vind. Dit is geensins 'n perfekte oplossing vir die opsporing van platforms nie; die sprongkromme benadering vir die karakters wat algoritmes moet maak is dikwels baie moeilik en kan lei tot verkeerde gedrag. Hierdie algoritme kan nog steeds verleng word - dit is nie te moeilik om 'n rand en 'n ander soort bewegende buigsaamheid by te voeg nie - maar ons het basiese platformmeganika gedek. Dit is ook moontlik om die kode te optimaliseer om dit vinniger te maak en minder geheue te gebruik; iterasie-algoritme is glad nie perfek wanneer dit by daardie aspekte kom nie. Dit ly ook aan 'n baie slegte voorspellingskurwe wanneer dit teen 'n groot spoed val.

Hierdie algoritme kan op baie maniere gebruik word, veral om die AI-vyand of AI-vriend te verbeter. Dit kan ook gebruik word as 'n beheerskema vir aanraaktoestelle. Dit sal wesenlik werk soos in 'n tutoriaal-demo. Die speler tik waar hulle wil hê die karakter moet beweeg. Dit elimineer die uitvoeringsuitdagings wat deur baie platforms gebruik word. Die spel moet dus anders ontwerp word om beter jou karakter op die regte plek te plaas eerder as om die karakter akkuraat te beheer.

Dankie vir die lees! Maak seker dat u terugvoering gee oor hierdie metode en laat weet of jou enige regstellings gemaak het!

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.