Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
A comparison of algorithms for the purpose of path-finding in a 3D grid
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science.
2022 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Both AI and robotics are rapidly growing fields in today's society, however a digital mind is not inherently able to navigate the world around it, regardless of if that world is a virtual world or the real world. In order to solve this problem path-finding algorithms were created, these algorithms allow a digital mind to navigate a space as long as it is given enough information to properly calculate what path it should take. However there exists a multitude of different path-finding algorithms and ever more environments that the digital mind could be required to traverse, so which algorithm is the best? Today there is no clear answer, but it is possible to answer the question of: Which of these algorithms perform best in this specific environment? That is what this study aims to do, answer the question of which of following the algorithms, A*, Dijkstra and backtracking performs best in a 3D grid where not every node can be traversed. The metrics we will be using to evaluate the algorithms will be time and memory usage as well as briefly touching upon scalability. In order to gather sufficient data we performed a number of tests on three different grid sizes. The collected metrics shows that the Backtracking algorithm performs the best in 2 out of 3 metrics utilized in the study, however there are complicating factors that require discussion.

Place, publisher, year, edition, pages
2022. , p. 28
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:bth-22632OAI: oai:DiVA.org:bth-22632DiVA, id: diva2:1639201
Subject / course
DV1478 Bachelor Thesis in Computer Science
Educational program
DVGSP Game Programming
Supervisors
Examiners
Available from: 2022-02-21 Created: 2022-02-20 Last updated: 2022-02-21Bibliographically approved

Open Access in DiVA

A comparison of algorithms for the purpose of path-finding in a 3D grid(1030 kB)1825 downloads
File information
File name FULLTEXT02.pdfFile size 1030 kBChecksum SHA-512
d75a5af2044dbff363b586000d060a90ae2b536fa7c5244c86db4b09c5cae2bd0c9b884761b59272b8846b74a714f94960a1c063b7e5ff0240b1f279631b3f6a
Type fulltextMimetype application/pdf

By organisation
Department of Computer Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 1826 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

urn-nbn

Altmetric score

urn-nbn
Total: 559 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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