Change search
ReferencesLink to record
Permanent link

Direct link
HPA* Used With a Triangulation-Based Graph
Blekinge Institute of Technology, Faculty of Computing, Department of Creative Technologies.
2014 (English)Independent thesis Basic level (degree of Bachelor)Student thesisAlternative title
HPA* Med en Triangulationsbaserad Graf (Swedish)
Abstract [en]

Context: Pathfinding is an important phase when it comes to AI. The AI needs to know how to get from one point to another when there are obstacles ahead. For that reason, different pathfinding algorithms have been created. Objective: In this paper a new pathfinding algorithm, THPA*, is described, and it will also be compared to the more common algorithms, A*, and HPA* which THPA* is based on. Methods: These algorithms are then tested on an extensive array of maps with different paths and the results consisting of the execution times will be compared against each other. Results: The result of those tests conclude that THPA* performs better in terms of execution time in the average case; however it does suffer from low quality paths. Conclusions: This paper concludes that THPA* is a promising algorithm albeit in need of more refinement to make up for the negative points.

Place, publisher, year, edition, pages
2014. , 38 p.
Keyword [en]
Pathfinding, Graph Traversal, AI
National Category
Computer Science
URN: urn:nbn:se:bth-5630Local ID: diva2:833020
Available from: 2015-04-22 Created: 2014-10-31 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

fulltext(1265 kB)62 downloads
File information
File name FULLTEXT01.pdfFile size 1265 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Department of Creative Technologies
Computer Science

Search outside of DiVA

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

Direct link