Share
I denna handledning kommer jag att förklara vektor fält pathfinding och dess fördelar jämfört med mer traditionella sökningsalgoritmer, såsom Dijkstra. En grundläggande förståelse för både Dijkstras algoritm och potentiella fält hjälper dig att förstå denna artikel, men är inte nödvändig.
Pathfinding är ett problem med många lösningar, och alla har sina fördelar och nackdelar. Många sökningsalgoritmer fungerar genom att beräkna en väg till målet för varje sökare, vilket innebär att sökningen kommer att ta dubbelt så lång tid att beräkna med dubbelt så många sökare. Detta är acceptabelt i många situationer, men när man arbetar med tusentals sökare är ett effektivare tillvägagångssätt möjligt.
Känd som vektor fält pathfinding, Detta tillvägagångssätt räknar vägen från målet till varje nod i grafen. För att stärka denna förklaring av vektorfältupptäckt kommer jag att förklara algoritmen med hjälp av min specifika implementering som ett exempel.
Notera: Vectorfältet sökande kan abstraheras till noder och grafer i allmänhet; bara för att jag förklarar det med min kakel och nätbaserad metod betyder inte att denna algoritm är begränsad till kakelbaserade världar!
Vektorfältet sökande består av tre steg.
Denna video visar dig de slutliga resultaten och ger dig en allmän översikt över de begrepp som presenteras i hela handledningen nedan:
Värmekartan lagrar banans avstånd från målet till varje kakel på kartan. Banavstånd skiljer sig från Euklidiskt avstånd, eftersom det är en beräkning av avståndet mellan två punkter som endast passerar genom en traverserbar terräng. En GPS, till exempel, beräknar alltid vägavstånd, med vägar som är den enda traverserade terrängen.
Nedan kan du se skillnaden mellan banavstånd och linjärt avstånd från målet (markerat i rött) till en godtycklig kakel (markerad i rosa). Icke traverserbara plattor ritas i grönt. Som du kan se är banavståndet (visas i gult) 9, medan linjärt avstånd (visas i ljusblå) är ungefär 4,12.
Siffrorna längst upp till vänster av varje kakel visar vägen avstånd till målet beräknat av värmekortgenereringsalgoritmen. Observera att det finns mer än ett möjligt banavstånd mellan två punkter; I den här artikeln är vi bara intresserade av den kortaste.
Värmekortgenereringsalgoritmen är a vågfrontalgoritm. Det börjar vid målet med ett värde av 0, och strömmar därefter utåt för att fylla hela den traversabla regionen. Det finns två steg till vågfrontalgoritmen:
Accentsconagua
0.Den tidigare plattans vägavstånd + 1.Notera: Vågfrontalgoritmen kör helt enkelt en breddets första sökning på rutnätet och lagrar hur många steg det tog för att komma till varje kakel längs vägen. Denna algoritm kallas ibland också borstfirealgoritm.
Nu när vägens avstånd från varje kakel till målet har beräknats, kan vi enkelt bestämma vilken väg som behöver vidtas för att komma närmare målet. Det är möjligt att göra detta vid körning för varje sökare varje ram, men det är ofta bättre att beräkna ett vektorfält en gång och sedan har alla sökare hänvisat till vektorfältet vid körning.
Vektorfältet lagrar helt enkelt en vektor som pekar ner gradienten av distansfunktionen (mot målet) vid varje sida. Här är en visualisering av vektorfältet, med vektorerna som pekar från mitten av plattan längs den kortaste vägen till målet (återigen visad i rött).
Detta vektorfält genereras en kakel åt gången genom att titta på värmekartan. X- och y-komponenterna i vektorn beräknas separat, såsom visas i pseudokoden nedan:
Vector.x = left_tile.distance - right_tile.distance Vector.y = up_tile.distance - down_tile.distance
Notera: Varje kakel distansvariabel lagrar banans avstånd till målet som beräknat av vågfrontalgoritmen ovan.
Om någon av plattorna refererade (vänster / höger / upp / ner) är icke-traverserbar och därmed inte har något användbart avstånd lagrat, används avståndet som är kopplat till den aktuella plattan istället för det saknade värdet. När vägenvektorn har beräknats grovt, normaliseras den för att undvika inkonsekvenser senare.
Nu när vektorfältet har beräknats är det väldigt lätt att beräkna rörelse för en sökare. Antag att vector_field (x, y) returnerar vektorn som vi beräknat tidigare vid plattan (X, y), och den önskade hastigheten är en skalär, pseudokoden för att beräkna hastigheten hos en partikel vid kakel (X, y) ser så här ut:
velocity_vector = vector_field (x, y) * önskad_hastighet
Partiklarna behöver helt enkelt börja röra sig i den riktning som indikeras av vektorn. Detta är det enklaste sättet att göra detta, men mer komplicerade rörelsessystem kan enkelt implementeras med hjälp av flödesfält.
Till exempel kan de tekniker som förklaras i Förstå styrningsbeteenden tillämpas på rörlängdsrörelse. I en sådan situation, velocity_vector Vi beräknade ovan skulle användas som önskad hastighet, och styrningsbeteenden skulle användas för att beräkna den faktiska rörelsen vid varje steg.
Vid beräkning av rörelse finns det ett problem som ibland kan uppstå, känt som lokala optima. Detta inträffar när det finns två optimala (kortaste) vägar att ta för att nå målet från en viss kakel.
Problemet kan ses på bilden nedan. Plattan (visas i rosa) omedelbart till vänster om mitten av väggen har en vägvektor vars komponenter (x och y) är lika med 0.
Lokala optima gör att sökare kan fastna; de kommer att referera till vektorfältet som kommer att misslyckas med att ange en riktning för att gå in. När detta händer, kommer sökandena att vara kvar på samma plats om inte en fix implementeras.
Det mest eleganta sättet (jag har hittat) att lösa problemet är att dela upp värmekartan och vektorfältet en gång. Varje enskild värmekarta och vektorfältplatta har nu delats i fyra mindre plattor. Problemet förblir detsamma med ett uppdelat rutnät; Det har bara blivit något minimerat.
Det verkliga tricket som löser det lokala optima-problemet är att initialt lägga till fyra målnoder istället för bara en. För att göra detta måste vi helt enkelt ändra det första steget i värmekortgenereringsalgoritmen. När vi bara tillsatte ett mål med ett avstånd på 0, lägger vi nu till de fyra plattorna som ligger närmast målet.
Det finns flera sätt att välja de fyra plattorna, men hur de väljs är i stor utsträckning irrelevant - så länge de fyra plattorna är angränsande (och traverserbara), bör denna teknik fungera.
Här är den förändrade pseudokoden för värmekortgenereringen:
0.Den tidigare plattans vägavstånd + 1.Och nu är här de slutliga resultaten, som tydligt visar att det lokala optimaproblemet har eliminerats:
Även om denna lösning är elegant är den långt ifrån idealisk. Med hjälp av det betyder att beräkning av värmekartan och vektorfältet tar fyra gånger längre på grund av det ökade antalet kakel.
Andra lösningar kräver att man gör kontroller och bestämmer sedan vilken riktning man ska gå till från fall till fall, vilket avsevärt saktar ner partikelrörelserna. I mitt fall var det bättre alternativet att dela upp kartorna.
Förhoppningsvis har denna handledning läst dig hur man genomför målbaserad pathfinding i en kakelbaserad värld. Tänk på att den här typen av pathfinding i sin tur är enkel: partiklar följer gradienten av avståndsfunktionen mot målet.
Genomförandet är mer komplext men kan brytas ner i följande tre hanterbara steg:
Jag hoppas att se folk expandera på de idéer som presenteras här. Som alltid, om du har frågor, tveka att fråga dem i kommentarerna nedan!
