Primjena algoritama traženja puta u grafu pri razvoju jednostavne 3D videoigre

undergraduate thesis

• Title (english): Application of pathfinding algorithms in a simple 3D videogame development
• Author: Marko Grozaj
• Mentor: Maja Matijašević (mentor)
• Committee member: Maja Matijašević (predsjednik povjerenstva)
• Committee member: Lea Skorin-Kapov (član povjerenstva)
• Committee member: Mirko Sužnjević (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2020-07-06, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Videoigre mogu biti vrlo koristan alat za istraživanje nepoznatog i oponašanja fizikalnog svijeta, ali također izvrstan način za vizualizaciju algoritama. Igra naziva Mystery razvijena u okviru ovog završnog rada, tako u sebi ima ugrađen algoritam za traženje puta u grafu, primijenjen na računalno generiranim likovima koji slijede igrača u virtualnom trodimenzionalnom svijetu. Na temelju analize tri algoritma za traženje puta u grafu (BFS, najbolji prvi, A*), koja uključuje vrijeme izvršavanja i broj izvršenih operacija na pet različitih mapa, za primjenu u igri odabran je algoritam A*. Opisan je postupak izrade trodimenzionalnih modela u alatu Blender te postupak dizajna i izrade igre.

Abstract (english)

Virtual games can be very useful tool for exploring the unknown and modeling the real physical world, but also a great way of visualizing the inner workings of algorithms. The game, named Mystery, includes a pathfinding applied to computer generated characters following the player inside the virtual world. Based on an analysis of the three pathfinding algorithms, including BFS, first best and A*, and their runtime and number of operations, A* has been selected to be applied in the game implementation. The process of creating three-dimensional models in Blender tool is described, as well as the overall process of the game design and implementation.

• Keywords: Unity; Blender; videoigra; traženje puta; A*; BFS; pohlepni prvi
• Keywords (english): Unity; Blender; videogame; pathfinding; A*; BFS; first best
• Language: croatian
• URN:NBN: urn:nbn:hr:168:005096
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2025-02-25 17:03:05