Pathfinding

För annan användning, se Pathfinder (disambiguation) .
Motsvarande vägar mellan A och B i en 2D-miljö

Pathfinding eller pathing är ritningen, med en datorapplikation, av den kortaste vägen mellan två punkter. Det är en mer praktisk variant på att lösa labyrinter . Detta forskningsområde är starkt baserat på Dijkstras algoritm för att hitta den kortaste vägen på en viktad graf .

Pathfinding är nära relaterat till problemet med kortaste vägen inom grafteorin , som undersöker hur man identifierar den väg som bäst uppfyller vissa kriterier (kortast, billigast, snabbast, etc) mellan två punkter i ett stort nätverk.

Algoritmer

I grunden söker en sökvägsmetod en graf genom att börja vid en vertex och utforska intilliggande noder tills destinationsnoden nås, i allmänhet med avsikten att hitta den billigaste rutten. Även om grafsökningsmetoder som en bredd-först-sökning skulle hitta en rutt om de ges tillräckligt med tid, skulle andra metoder, som "utforskar" grafen, tendera att nå destinationen tidigare. En analogi skulle vara en person som går över ett rum; snarare än att undersöka alla möjliga vägar i förväg, skulle personen i allmänhet gå i riktning mot destinationen och bara avvika från vägen för att undvika ett hinder och göra avvikelser så små som möjligt.

Två primära problem med vägsökning är (1) att hitta en väg mellan två noder i en graf ; och (2) problemet med den kortaste vägen - att hitta den optimala kortaste vägen . Grundläggande algoritmer som bredd-först och djup-först sökning tar itu med det första problemet genom att uttömma alla möjligheter; med början från den givna noden, itererar de över alla potentiella vägar tills de når destinationsnoden. Dessa algoritmer körs i eller linjär tid, där V är antalet hörn och E är antalet kanter mellan hörn .

Det mer komplicerade problemet är att hitta den optimala vägen. Den uttömmande metoden i detta fall är känd som Bellman–Ford-algoritmen , som ger en tidskomplexitet av eller kvadratisk tid. Det är dock inte nödvändigt att undersöka alla möjliga vägar för att hitta den optimala. Algoritmer som A* och Dijkstras algoritm eliminerar strategiskt vägar, antingen genom heuristik eller genom dynamisk programmering . Genom att eliminera omöjliga vägar kan dessa algoritmer uppnå tidskomplexiteter så låga som .

Ovanstående algoritmer är bland de bästa allmänna algoritmerna som fungerar på en graf utan förbearbetning. Men i praktiska resedirigeringssystem kan ännu bättre tidskomplexitet uppnås med algoritmer som kan förbearbeta grafen för att uppnå bättre prestanda. En sådan algoritm är kontraktionshierarkier .

Dijkstras algoritm

Ett vanligt exempel på en grafbaserad vägsökningsalgoritm är Dijkstras algoritm . Denna algoritm börjar med en startnod och en "öppen uppsättning" av kandidatnoder. Vid varje steg undersöks noden i det öppna setet med det lägsta avståndet från start. Noden är märkt "stängd", och alla noder intill den läggs till den öppna uppsättningen om de inte redan har undersökts. Denna process upprepas tills en sökväg till destinationen har hittats. Eftersom de lägsta avståndsnoderna undersöks först, första gången destinationen hittas, kommer vägen till den att vara den kortaste vägen.

Dijkstras algoritm misslyckas om det finns en negativ kantvikt . I den hypotetiska situationen där noderna A, B och C bildar en sammankopplad oriktad graf med kanterna AB = 3, AC = 4 och BC = −2, kostar den optimala vägen från A till C 1, och den optimala vägen från A till B kostar 2. Dijkstras algoritm med start från A kommer först att undersöka B, eftersom det är närmast. Den kommer att tilldela en kostnad på 3 till den och markera den som stängd, vilket innebär att kostnaden aldrig kommer att omvärderas. Därför kan Dijkstras inte utvärdera negativa kantvikter. Men eftersom det för många praktiska ändamål aldrig kommer att finnas en negativ kantväv, är Dijkstras algoritm till stor del lämplig för sökvägssyftet.

A*-algoritm

A* är en variant av Dijkstras algoritm som vanligtvis används i spel. A* tilldelar en vikt till varje öppen nod som är lika med vikten av kanten till den noden plus det ungefärliga avståndet mellan den noden och målet. Detta ungefärliga avstånd hittas av heuristiken och representerar ett minsta möjliga avstånd mellan den noden och slutet. Detta gör att den kan eliminera längre vägar när en första väg hittas. Om det finns en väg med längden x mellan start och mål, och minimiavståndet mellan en nod och mål är större än x, behöver den noden inte undersökas.

A* använder denna heuristik för att förbättra beteendet i förhållande till Dijkstras algoritm. När heuristiken utvärderas till noll är A* ekvivalent med Dijkstras algoritm. När den heuristiska uppskattningen ökar och närmar sig det verkliga avståndet, fortsätter A* att hitta optimala vägar, men går snabbare (i kraft av att undersöka färre noder). När värdet på heuristiken är exakt det verkliga avståndet undersöker A* de minsta noderna. (Det är dock i allmänhet opraktiskt att skriva en heuristisk funktion som alltid beräknar det verkliga avståndet, eftersom samma jämförelseresultat ofta kan uppnås med enklare beräkningar – till exempel med Chebyshev- avstånd över euklidiskt avstånd i tvådimensionellt rum .) värdet av heuristiken ökar, A* undersöker färre noder men garanterar inte längre en optimal väg. I många applikationer (som videospel) är detta acceptabelt och till och med önskvärt, för att hålla algoritmen igång snabbt.

Exempel på algoritm

Detta är en ganska enkel och lättförståelig sökvägsalgoritm för kakelbaserade kartor. Till att börja med har du en karta, en startkoordinat och en destinationskoordinat. Kartan kommer att se ut så här, X är väggar, S är början, O är mål och _ är öppna ytor, siffrorna längs den övre och högra kanten är kolumn- och radnumren: 

1 2 3 4 5 6 7 8 XXXXXXXXXX X _ _ _ XX _ X _ X 1 X _ X _ _ X _ _ _ X 2 XSXX _ _ _ X _ X 3 X _ X _ _ X _ _ _ X 4 X _ _ _ XX _ X _ X 5 X _ X _ _ X _ X _ X 6 X _ XX _ _ _ X _ X 7 X _ _ O _ X _ _ _ X 8 XXXXXXXXXX

Skapa först en lista med koordinater, som vi kommer att använda som en kö. Kön kommer att initieras med en koordinat, slutkoordinaten. Varje koordinat kommer också att ha en räknarvariabel bifogad (syftet med detta kommer snart att bli uppenbart). Således börjar kön som ((3,8,0)).

Gå sedan igenom varje element i kön, inklusive nya element som läggs till i slutet under algoritmens gång, och gör följande för varje element:

  1. Skapa en lista över de fyra intilliggande cellerna, med en räknarvariabel för det aktuella elementets räknarvariabel + 1 (i vårt exempel är de fyra cellerna ((2,8,1),(3,7,1),(4, 8,1),(3,9,1)))
  2. Kontrollera alla celler i varje lista för följande två villkor:
    1. Om cellen är en vägg, ta bort den från listan
    2. Om det finns ett element i huvudlistan med samma koordinat, ta bort det från celllistan
  3. Lägg till alla återstående celler i listan i slutet av huvudlistan
  4. Gå till nästa punkt i listan

Alltså, efter tur 1, är listan med element följande: ((3,8,0),(2,8,1),(4,8,1))

  • Efter 2 varv: ((3,8,0),(2,8,1),(4,8,1),(1,8,2),(4,7,2))
  • Efter 3 varv: (...(1,7,3),(4,6,3),(5,7,3))
  • Efter 4 varv: (...(1,6,4),(3,6,4),(6,7,4))
  • Efter 5 varv: (...(1,5,5),(3,5,5),(6,6,5),(6,8,5))
  • Efter 6 varv: (...(1,4,6),(2,5,6),(3,4,6),(6,5,6),(7,8,6))
  • Efter 7 varv: (...(1,3,7)) – problemet löst, avsluta det här steget av algoritmen – observera att om du har flera enheter som jagar samma mål (som i många spel – närmar sig mål till start för algoritmen är avsedd att göra detta enklare), du kan fortsätta tills hela kartan är upptagen, alla enheter har nåtts eller en inställd räknargräns har nåtts

Mappa nu räknarna på kartan och få detta:

1 2 3 4 5 6 7 8 XXXXXXXXXX X _ _ _ XX _ X _ X 1 X _ X _ _ X _ _ _ X 2 XSXX _ _ _ X _ X 3 X 6 X 6 _ X _ _ _ X 4 X 5 6 5 XX 6 X _ X 5 X 4 X 4 3 X 5 X _ X 6 X 3 XX 2 3 4 X _ X 7 X 2 1 0 1 X 5 6 _ X 8 XXXXXXXXXX

Börja nu vid S (7) och gå till den närliggande cellen med det lägsta numret (omarkerade celler kan inte flyttas till). Den spårade vägen är (1,3,7) -> (1,4,6) -> (1,5,5) -> (1,6,4) -> (1,7,3) -> ( 1,8,2) -> (2,8,1) -> (3,8,0). I händelse av att två tal är lika låga (till exempel om S var vid (2,5)), välj en slumpmässig riktning – längderna är desamma. Algoritmen är nu klar.

I tv-spel

Chris Crawford 1982 beskrev hur han "tillbringade mycket tid" på att försöka lösa ett problem med sökvägar i Tanktics , där datortankar fastnade på land i U-formade sjöar. "Efter mycket bortkastad ansträngning upptäckte jag en bättre lösning: ta bort U-formade sjöar från kartan", sa han.

Hierarkisk väg att hitta

Quadtrees kan användas för hierarkisk sökväg

Idén beskrevs först av videospelsindustrin , som hade ett behov av planering i stora kartor med låg CPU-tid . Konceptet med att använda abstraktion och heuristik är äldre och nämndes först under namnet ABSTRIPS (Abstraction-Based STRIPS ) som användes för att effektivt söka i logikspelens tillståndsutrymmen. En liknande teknik är navigationsnät (navmesh), som används för geometrisk planering i spel och multimodal transportplanering som används vid resande försäljarproblem med mer än ett transportfordon.

En karta är uppdelad i kluster . På högnivåskiktet planeras vägen mellan klustren. Efter att planen hittats planeras en andra väg inom ett kluster på lägre nivå. Det innebär att planeringen görs i två steg som är en guidad lokal sökning i det ursprungliga utrymmet. Fördelen är att antalet noder är mindre och att algoritmen fungerar mycket bra. Nackdelen är att en hierarkisk vägplanerare är svår att implementera.

Exempel

En karta har en storlek på 3000x2000 noder. Att planera en bana på en nodbas skulle ta mycket lång tid. Även en effektiv algoritm kommer att behöva beräkna många möjliga grafer. Anledningen är att en sådan karta skulle innehålla 6 miljoner noder totalt och möjligheterna att utforska det geometriska rummet är oerhört stora. Det första steget för en hierarkisk vägplanerare är att dela upp kartan i mindre delkartor. Varje kluster har en storlek på 300x200 noder. Antalet kluster totalt är 10x10=100. I den nyskapade grafen är mängden noder liten, det är möjligt att navigera mellan de 100 klustren, men inte inom den detaljerade kartan. Om en giltig sökväg hittades i högnivågrafen är nästa steg att planera sökvägen inom varje kluster. Underkartan har 300x200 noder som enkelt kan hanteras av en vanlig A*-vägplanerare .

Algoritmer som används vid sökväg

Sökväg för flera agenter

Huvudartikel: Multi-agent pathfinding

Multi-agent pathfinding är att hitta vägarna för flera agenter från deras nuvarande platser till sina målplatser utan att kollidera med varandra, samtidigt som man optimerar en kostnadsfunktion, såsom summan av väglängderna för alla agenter. Det är en generalisering av pathfinding. Många multi-agent pathfinding-algoritmer är generaliserade från A*, eller baserade på reduktion till andra välstuderade problem såsom heltalslinjär programmering. Sådana algoritmer är dock vanligtvis ofullständiga; med andra ord, inte visat sig ge en lösning inom polynomtid. En annan kategori av algoritmer offrar optimalitet för prestanda genom att antingen använda sig av kända navigeringsmönster (som trafikflöde) eller problemutrymmets topologi.

Se även

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Pathfinding&oldid=1141996275 "