Change search
ReferencesLink to record
Permanent link

Direct link
Performance Evaluation of A* Algorithms
Blekinge Institute of Technology, Faculty of Computing, Department of Creative Technologies.
Blekinge Institute of Technology, Faculty of Computing, Department of Creative Technologies.
2016 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Context. There have been a lot of progress made in the field of pathfinding. One of the most used algorithms is A*, which over the years has had a lot of variations. There have been a number of papers written about the variations of A* and in what way they specifically improve A*. However, few papers have been written comparing A* with several different variations of A*.

Objectives. The objectives of this thesis is to find how Dijkstra's algorithm, IDA*, Theta* and HPA* compare against A* based on the variables computation time, number of opened nodes, path length as well as number of path nodes.

Methods. To find the answers to the question in Objectives, an experiment was set up where all the algorithms were implemented and tested over a number of maps with varying attributes.

Results. The experimental data is compiled in a table showing the result of the tested algorithms for computation time, number of opened nodes, path length and number of path nodes over a number of different maps as well as the average performance over all maps.

Conclusions. A* is shown to perform well overall, with Dijkstra's algorithm trailing shortly behind in computation time and expanded nodes. Theta* finds the best path, with overall good computation time marred by a few spikes on large, open maps. HPA* performs poorly overall when fully computed, but has by far the best computation time and node expansion when partially pre-computed. IDA* finds the same paths as A* and Dijkstra's algorithm but has a notably worse computation time than the other algorithms and should generally be avoided on octile grid maps.

Place, publisher, year, edition, pages
2016. , 46 p.
Keyword [en]
pathfinding, astar, performance evaluation
National Category
Computer Science
Identifiers
URN: urn:nbn:se:bth-12900OAI: oai:DiVA.org:bth-12900DiVA: diva2:949638
Subject / course
DV1478 Bachelor Thesis in Computer Science
Educational program
DVGSP Game Programming
Supervisors
Examiners
Available from: 2016-08-09 Created: 2016-07-21 Last updated: 2016-08-09Bibliographically approved

Open Access in DiVA

fulltext(407 kB)8 downloads
File information
File name FULLTEXT02.pdfFile size 407 kBChecksum SHA-512
489ede6310a75d5e74ffdd7b6f59f950f1968460a2da61640e3092dc560ed9cddfe9820cb764b901f877cf621b12090a48e64f75ddc5faffb9959ab870e4c3ca
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Martell, VictorSandberg, Aron
By organisation
Department of Creative Technologies
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 8 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: 21 hits
ReferencesLink to record
Permanent link

Direct link