miniatyr|Likvärdiga vägar mellan A och B i en tvådimensionell miljö. 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. 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.
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. 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.
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. För att hitta den kortaste vägen används ofta mer specialiserade metoder, särskilt Dijkstras algoritm och A*-algoritmen.
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.
Dijkstras algoritm Dijkstras algoritm är en klassisk metod för att hitta kortaste vägar i en graf med icke-negativa kantvikter. 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. Den används fortfarande brett inom nätverksrouting och annan vägberäkning.
En begränsning är att algoritmen inte är avsedd för grafer med negativa kantvikter.
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. 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. Därför är A* en av de vanligaste algoritmerna för pathfinding i spel och interaktiva tillämpningar.
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. Chris Crawford beskrev redan 1982 hur pathfinding kunde skapa praktiska problem i spelutveckling, bland annat när enheter fastnade i terrängen.
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. I spel används ofta rutnät, waypoints eller navigationsnät för att representera var en figur kan ta sig fram.
Hierarkisk pathfinding miniatyr|Kvadratträd kan användas för 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.
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.
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. På så sätt kan beräkningen bli snabbare samtidigt som vägkvaliteten fortfarande blir nära optimal.
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*
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. Området är viktigt bland annat för robotik, lagerautomation och simulering av flera enheter i spelmiljöer.
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ö.
Se även Kortaste-vägen-problemet Grafteori Navigationsnät Motion planning Fleragent-pathfinding
Referenser
Kategori:Algoritmer Kategori:Grafteori Kategori:Artificiell intelligens Kategori:Datorspelsutveckling