Heuristic pathfinding algorithms on 4-way connected graphs
Summary
No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.
Summarise with VIRAT Free to try with your Science Catalogs account.Abstract
V diplomskem delu smo implementirali in primerjali štiri algo ritme za iskanje poti na štirismerno povezanih mrežnih grafih: A*, ALT, HPA* in JPS4. Algoritme smo testirali na osmih zemljevidih velikosti 512× 512 vozlišč — šestih iz igre Baldur’s Gate 2, labirintu in naključnem zemlje vidu z desetimi odstotki ovir. Za vsak algoritem smo merili čas predprocesi ranja, čas iskanja poti, število raziskanih vozlišč in dolžino najdene poti. Algoritem JPS4 se je izkazal kot najboljši na večini metrik. Dosegel je povprečno 23,38-kratni pospešek v primerjavi z algoritmom A*, raziskal 79,54% manj vozlišč, pri tem pa ohranja optimalno dolžino poti. Ker ne potrebuje predprocesiranja, je primeren tako za statične kot dinamične grafe. Algoritem HPA* z regijami 8×8 je dosegel 15,22-kratni pospešek in nizko točko preloma, a je našel v povprečju za 1,52% daljšo pot. Algoritem ALT z 8 orientacijskimi točkami je prinesel 1,85-kratni pospešek. Odlikuje se na labirintskih strukturah, na odprtih zemljevidih pa je lahko bil celo počasnejši od A*. Za večino praktičnih aplikacij je algoritem JPS4 najboljša izbira. Algo ritem HPA* postane konkurenčen pri velikem številu poizvedb na statičnih grafih, algoritem ALT pa je priporočljiv za iskanje poti v labirintskih okoljih.
Fields of Study & Subjects
Robotic Path Planning Algorithms
Artificial Intelligence in Games
Digital Image Processing Techniques
Publication details
- Journal / source
- Repository of the University of Ljubljana (University of Ljubljana)
- Publication date
- 23 March 2026
- Language
- SL
- Document type
- Thesis