Högskolan i Skövde

Algoritmer för vägplanering används ofta i dataspel för att navigera datorstyrda enheter. En av de vanligaste algoritmerna som används i samband med vägplanering är A* algoritmen, som kan användas för att effektivt hitta den kortaste vägen mellan två positioner i spelets nivåer. Algoritmen har dock inget stöd för att producera estetiskt tilltalande vägar, vilket kan leda till att spelets enheter rör sig som robotar genom spelnivån.

Detta arbete tar upp och analyserar algoritmer som kan användas i kombination med A* algoritmen för att göra vägarna rakare, mjukare och mer direkta. Algoritmerna implementeras i ett program där deras minnesanvändning, tidseffektivitet och väglängd beräknas när de körs genom en spelnivå med väggar och hinder.

Resultaten från slutet av rapporten visar att de estetiskt förbättrande algoritmerna kan implementeras för att göra stora förbättringar av A* algoritmens estetiska prestationer, utan större påverkningar på A* algoritmens minnesanvändning, tidseffektivitet och väglängd. Resultaten från både produkt och utvärderingen skulle kunna användas i framtida spelprojekt.