20.500.12556/RUL-181017 Hevristični algoritmi za iskanje poti v štirismernih grafih Heuristic pathfinding algorithms on 4-way connected graphs 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. In this thesis we implemented and compared four pathfinding algorithms on 4-way connected grid graphs: A*, ALT, HPA*, and JPS4. The algorithms were tested on eight maps consisting of 512 × 512 nodes — six from the game Baldur’s Gate 2, a maze, and a randomly generated map with 10% obstacle density. For each algorithm, we measured preprocessing time, pathfinding time, number of expanded nodes, and path length. JPS4 proved to be the best algorithm on most metrics. It achieved an average speedup factor of 23.38 over A* and expanded 79.54% fewer nodes while maintaining optimal path length. Since it requires no preprocessing, it is suitable for both static and dynamic graphs. HPA* with 8 ×8 regions achieved a speedup factor of 15.22 and a low break-even point, but found paths that are on average 1.52% longer. ALT with 8 landmarks yielded a speedup factor of 1.85 and performed best on maze-like maps, but could be slower than A* on open maps with sparse obstacles. For most practical applications, JPS4 is the best choice. HPA* becomes competitive when the number of queries on a static graph is large, while ALT is recommended for pathfinding in maze-like environments. Iskanje poti analiza JPS A* HPA* ALT Pathfinding benchmark JPS A* HPA* ALT true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2026-03-23 08:19:59 2026-03-23 08:20:06 2026-04-17 10:41:07 0000-00-00 00:00:00 2026 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 38101 275574019 Cernilec_Domen_-_Hevristicni_algoritmi_za_iskanje_poti_v_stirismernih_grafih.pdf Cernilec_Domen_-_Hevristicni_algoritmi_za_iskanje_poti_v_stirismernih_grafih.pdf 1 38E12A43CBEC89B489638B0F02BE9677 617c2bedff04b0603a173713b2a33ffd856c48d1a769ccf6d33c444273f801b5 9b70b961-2688-11f1-b0ab-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=231072 Fakulteta za računalništvo in informatiko 0 0 0