Heuristic pathfinding algorithms on 4-way connected graphs

Read full text Summarise with VIRAT
Authors: DOMEN ČERNILEC
Cited by: 0
References: 12

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