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
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
Identifiers
URN: urn:nbn:se:bth-5630Local ID: oai:bth.se:arkivex480079ECC9913900C1257D82003DEDE3OAI: oai:DiVA.org:bth-5630DiVA: diva2:833020
Uppsok
Technology
Supervisors
Available from: 2015-04-22 Created: 2014-10-31 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

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

By organisation
Department of Creative Technologies
Computer Science

Search outside of DiVA

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