Vägplanering
Automatgenerering av vägpunktsgrafer & navigationsnät
Waypoint graphNavigation meshNavmeshPathfindingAutomatic generationA*VägpunktsgrafNavigationsnätVägplaneringAutomatgenereringA*
I nästan alla moderna datorspel så återfinns datorstyrda karaktärer, vilka behöver kunna navigera i spelvärlden. Dessa karaktärer kan vara olika typer av fiender i ett förstapersonskjutarspel, eller motståndare och medhjälpare i ett sportspel (exempelvis fotboll- eller rallyspel) med mera. Det finns många tekniker för att realisera vägplanering och det kan vara stora skillnader, både prestandamässiga och funktionella, mellan dem. Detta arbete jämför två olika sökrymdsrepresentationer för vägplanering, nämligen vägpunktsgrafer och navigationsnät, där sökrymderna automatgenererats. Jämförelsen görs med ett experiment och avser såväl prestanda (tids- och minneskostnad) som funktionalitet (optimal väg och antal svängar). Experimentmiljön stödjer godtyckliga vägar och ger detaljerad statistik för en noggrann jämförelse av vägplaneringsteknikerna. Arbetet visar på att navigationsnätet presterar bäst vad gäller funktionalitet. Vad gäller prestanda så presterar navigationsnätet generellt sett bäst, men vägpunktsgrafen kan ge bättre prestanda om nodavståndet hålls relativt högt. Det finns också många möjligheter att vidareutveckla arbetet, exempelvis förfina vägarna och kombinera vägplaneringsteknikerna med robotik.