Vägplanering i dataspel med hjälp av Artificial Bee Colony Algorithm

Sammanfattning: Artificial Bee Colony Algorithm är en algoritm som tidigare tillämpats på många numeriska optimeringsproblem. Algoritmen är dock inte vanligt förekommande vad gäller vägplanering i dataspel. Detta arbete undersöker ifall algoritmen presterar bättre än A' på fyra olika testmiljöer eftersom A' är en av de mest använda algoritmerna för vägplanering i dataspel och således en bra referens. De aspekter som jämförs vid mätningarna är algoritmernas tidsåtgång samt längden på de resulterande vägarna. En riktad slumpgenerering av vägar har implementerats till algoritmen som gör att den inte fungerar på djupa återvändsgränder. Algoritmen har också en roulettehjulsselektion samt egenskapen att kunna generera slumpade grannvägar till de som skapats hittills. Resultaten visar att Artificial Bee Colony Algorithm presterar betydligt sämre än A' och att algoritmen därför inte är en bättre algoritm för vägplanering i dataspel. Algoritmen har dock potential till att prestera bättre och fungera på återvändsgränder om man förbättrar dess slumpgenerering av vägar.