Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Utilizing Swarm Intelligence Algorithms for Pathfinding in Games
University of Skövde, School of Informatics.
2017 (English)Independent thesis Basic level (degree of Bachelor), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

The Ant Colony Optimization and Particle Swarm Optimization are two Swarm Intelligence algorithms often utilized for optimization. Swarm Intelligence relies on agents that possess fragmented knowledge, a concept not often utilized in games. The aim of this study is to research whether there are any benefits to using these Swarm Intelligence algorithms in comparison to standard algorithms such as A* for pathfinding in a game.

Games often consist of dynamic environments with mobile agents, as such all experiments were conducted with dynamic destinations. Algorithms were measured on the length of their path and the time taken to calculate that path.

The algorithms were implemented with minor modifications to allow them to better function in a grid based environment. The Ant Colony Optimization was modified in regards to how pheromone was distributed in the dynamic environment to better allow the algorithm to path towards a mobile target. Whereas the Particle Swarm Optimization was given set start positions and velocity in order to increase initial search space and modifications to increase particle diversity.

The results obtained from the experimentation showcased that the Swarm Intelligence algorithms were capable of performing to great results in terms of calculation speed, they were however not able to obtain the same path optimality as A*. The algorithms' implementation can be improved but show potential to be useful in games.

Place, publisher, year, edition, pages
2017. , 55 p.
Keyword [en]
Swarm Intelligence, Pathfinding, Ant Colony Optimization, Particle Swarm Optimization, A*
National Category
Computer Science
Identifiers
URN: urn:nbn:se:his:diva-13636OAI: oai:DiVA.org:his-13636DiVA: diva2:1106037
Subject / course
Informationsteknologi
Educational program
Computer Game Development - Programming
Supervisors
Examiners
Available from: 2017-06-16 Created: 2017-06-06 Last updated: 2017-06-16Bibliographically approved

Open Access in DiVA

fulltext(4332 kB)10 downloads
File information
File name FULLTEXT01.pdfFile size 4332 kBChecksum SHA-512
7eb14be450738200103abdd4fddaa59fdf31f4a3675df68d0b69afd1c51532e5550fd01910d7ad8cd9a767d369ce634050c863e427346518daf0eb80cb525f7c
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Kelman, Alexander
By organisation
School of Informatics
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 10 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 11 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf