HPA* Used With a Triangulation-Based Graph
Independent thesis Basic level (degree of Bachelor)Student thesisAlternative title
HPA* Med en Triangulationsbaserad Graf (Swedish)
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.
Pathfinding, Graph Traversal, AI
IdentifiersURN: urn:nbn:se:bth-5630Local ID: oai:bth.se:arkivex480079ECC9913900C1257D82003DEDE3OAI: oai:DiVA.org:bth-5630DiVA: diva2:833020