Pathfinding
Pathfinding, ibland kallat vägsökning, är inom datavetenskap processen att beräkna en väg mellan två punkter i en graf eller annan representation av ett rum eller nätverk.[1][2] Begreppet är nära besläktat med kortaste-vägen-problemet inom grafteori, där målet är att hitta den kortaste, billigaste eller snabbaste vägen mellan två noder i ett nätverk.[1]
Algoritmer
Pathfinding bygger vanligen på att ett program söker igenom en graf från en startnod och undersöker angränsande noder tills målnoden nås.[2] En grundläggande skillnad går mellan algoritmer som enbart hittar någon väg och algoritmer som försöker hitta den optimala vägen.[1]
Bland enklare sökmetoder finns bredden-först-sökning och djupet-först-sökning, som systematiskt går igenom möjliga vägar i grafen.[3] För att hitta den kortaste vägen används ofta mer specialiserade metoder, särskilt Dijkstras algoritm och A*-algoritmen.[2][1]
Praktiska system för ruttplanering och spel använder ofta förbehandling eller hierarkiska representationer för att minska sökytan och därmed förbättra prestandan.[4]
Dijkstras algoritm
Dijkstras algoritm är en klassisk metod för att hitta kortaste vägar i en graf med icke-negativa kantvikter.[2] Algoritmen arbetar genom att successivt välja den ännu inte slutbehandlade nod som har lägst känd kostnad från startpunkten och uppdatera kostnaderna till dess grannar.[1] Den används fortfarande brett inom nätverksrouting och annan vägberäkning.[1]
En begränsning är att algoritmen inte är avsedd för grafer med negativa kantvikter.[2]
A*-algoritmen
A* är en vidareutveckling av Dijkstras algoritm där sökningen vägleder sig med en heuristik, alltså en uppskattning av hur långt det återstår till målet.[5] När heuristiken är väl vald kan A* undersöka betydligt färre noder än Dijkstras algoritm och ändå hitta en optimal väg.[5] Därför är A* en av de vanligaste algoritmerna för pathfinding i spel och interaktiva tillämpningar.[5]
I datorspel
Pathfinding har länge varit viktigt i datorspel, särskilt för icke-spelbara figurer som måste kunna röra sig genom spelvärlden på ett trovärdigt sätt.[6] Chris Crawford beskrev redan 1982 hur pathfinding kunde skapa praktiska problem i spelutveckling, bland annat när enheter fastnade i terrängen.[6]
I moderna spel används pathfinding bland annat för truppförflyttning i strategispel, fienders rörelser i actionspel och navigering i öppna 3D-miljöer.[7] I spel används ofta rutnät, waypoints eller navigationsnät för att representera var en figur kan ta sig fram.[7]
Hierarkisk pathfinding
För stora kartor eller komplexa miljöer kan vanlig vägberäkning bli för långsam. Då används ofta hierarkisk pathfinding, där kartan delas upp i större regioner eller kluster som först används för grov planering, varefter den exakta vägen beräknas lokalt inom varje område.[8][7]
Denna metod minskar sökområdet kraftigt och används därför ofta i spelutveckling och simuleringar där många agenter ska navigera samtidigt.[8][7]
Exempel
Om en mycket stor karta först delas in i ett mindre antal kluster kan algoritmen först hitta en väg mellan klustren och därefter beräkna den detaljerade vägen inom varje delområde.[8] På så sätt kan beräkningen bli snabbare samtidigt som vägkvaliteten fortfarande blir nära optimal.[8]
Algoritmer som används för pathfinding
Vanliga algoritmer och metodfamiljer är:
- Dijkstras algoritm
- A*
- D*
- Any-angle path planning
- hierarkiska metoder som HPA* och HNA*[8][7]
Fleragent-pathfinding
Fleragent-pathfinding (engelska: multi-agent pathfinding, MAPF) handlar om att hitta vägar för flera agenter samtidigt utan att de kolliderar med varandra, samtidigt som någon kostnadsfunktion optimeras, till exempel den totala vägkostnaden.[3] Området är viktigt bland annat för robotik, lagerautomation och simulering av flera enheter i spelmiljöer.[3]
Många metoder för fleragent-pathfinding bygger vidare på A* eller relaterade sökalgoritmer, men problemet blir betydligt svårare när flera aktörer ska samordnas i samma miljö.[3]
Se även
- Kortaste-vägen-problemet
- Grafteori
- Navigationsnät
- Motion planning
- Fleragent-pathfinding
Referenser
- 1 2 3 4 5 6 ”Shortest-path problem” (på engelska). Encyclopædia Britannica. https://www.britannica.com/technology/shortest-path-problem. Läst 18 april 2026.
- 1 2 3 4 5 E. W. Dijkstra (1959). ”A note on two problems in connexion with graphs” (på engelska). Numerische Mathematik 1 (1): sid. 269–271. doi:. Läst 18 april 2026.
- 1 2 3 4 Wolfgang Hönig; Jiaoyang Li; Sven Koenig (2020). ”Overview of Multi-Agent Path Finding” (på engelska). Model AI Assignments. https://idm-lab.org/project-p/material/overview.pdf. Läst 18 april 2026.
- ↑ Daniel Delling; Peter Sanders; Dominik Schultes; Dorothea Wagner (2009). ”Engineering route planning algorithms” (på engelska). Algorithmics of Large and Complex Networks. Springer. sid. 117–139. doi:. Läst 18 april 2026
- 1 2 3 Amit Patel. ”Introduction to the A* Algorithm” (på engelska). Red Blob Games. https://www.redblobgames.com/pathfinding/a-star/introduction.html. Läst 18 april 2026.
- 1 2 Chris Crawford (1 december 1982). ”Design Techniques and Ideas for Computer Games” (på engelska). BYTE. sid. 96. https://archive.org/details/byte-magazine-1982-12/page/n97/mode/2up. Läst 18 april 2026.
- 1 2 3 4 5 Nuria Pelechano; Carlos Fuentes (2016). ”Hierarchical path-finding for Navigation Meshes (HNA*)” (på engelska). Computers & Graphics 59: sid. 68–78. doi:. https://upcommons.upc.edu/server/api/core/bitstreams/e3842908-9c57-448e-9e5a-993818231cb0/content. Läst 18 april 2026.
- 1 2 3 4 5 Adi Botea; Martin Müller; Jonathan Schaeffer (2004). ”Near Optimal Hierarchical Path-Finding” (på engelska). Journal of Game Development 1 (1): sid. 7–28. Läst 18 april 2026.
| ||||||||||||||