Vägplanering i dataspel med hjälp av Artificial Bee Colony Algorithm
2015 (Swedish)Independent thesis Basic level (degree of Bachelor), 20 credits / 30 HE credits
Student thesisAlternative title
Pathfinding in computer games by using Artificial Bee Colony Algorithm (English)
Abstract [sv]
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.
Place, publisher, year, edition, pages
2015. , p. 30
Keywords [sv]
Artificial Bee Colony Algorithm, A*, vägplanering, AI, spel
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:his:diva-11044OAI: oai:DiVA.org:his-11044DiVA, id: diva2:819643
Subject / course
Computer Science
Educational program
Computer Game Development - Programming
Presentation
2015-06-03, Skövde, 08:00 (Swedish)
Supervisors
Examiners
2015-09-232015-06-112018-01-11Bibliographically approved