Primjena algoritama za pronalaženje puta za navigaciju u videoigrama

master's thesis

• Title (english): Application of algorithms for path finding for navigation in video games
• Author: Matko Šilić
• Mentor: Mirko Sužnjević (mentor)
• Committee member: Mirko Sužnjević (predsjednik povjerenstva)
• Committee member: Lea Skorin-Kapov (član povjerenstva)
• Committee member: Jurica Babić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2020-07-09, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Jedan od najvećih izazova u dizajnu umjetne inteligencije u videoigrama je kretanje računalno kontroliranih entiteta. Za kontrolu takvih entiteta koriste se razni algoritmi pronalaska puta. Ovaj rad daje pregled najčešće korištenih prikaza geometrije svijeta igre i algoritama za pronalaženje puta. Detaljnije je opisan algoritam A* i njegove poboljšane varijante. Potom su elaborirane alternative klasičnom pretraživanju poput umjetnih neuronskih mreža i evolucijskih algoritama. Dodatno, razvijena je pokazna videoigra u sustavu za izradu igara Unity koja demonstrira primjenjivost ovih algoritama. Uz igru su napravljene i detaljne upute uz pomoć kojih se igra može ponovno izraditi.

Abstract (english)

One of the biggest challenges in artificial intelligence design in video games is the movement of computer-controlled entities. Various path finding algorithms are used to control such entities. This paper provides an overview of the most commonly used representations of game world geometry and path finding algorithms. The algorithm A* and its improved variants are described in more detail. Next, the alternatives to classical search such as artificial neural networks and evolutionary algorithms are elaborated. Additionally, a demonstrative video game has been developed in the Unity game engine that demonstrates the applicability of these algorithms. Along with the game, detailed instructions have been made with the help of which the game can be re-created.

• Keywords: pronalazak puta; videoigre; navigacija; umjetna inteligencija; Unity
• Keywords (english): pathfinding; video games; navigation; artificial intelligence; Unity
• Language: croatian
• URN:NBN: urn:nbn:hr:168:552857
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-13 13:55:45