Pronalaženje puta u proceduralno generiranim labirintima

• Main Author: Kuprešak, Matej
• Other Authors: Livada, Časlav
• Format: Bachelor Thesis
• Language: Croatian
• Published: Sveučilište Josipa Jurja Strossmayera u Osijeku. Fakultet elektrotehnike, računarstva i informacijskih tehnologija Osijek. Zavod za programsko inženjerstvo. Katedra za vizualno računarstvo. 2023
• Subjects: algoritam pretraživanja po širini; Dijkstrin algoritam; Perlinov šum; proceduralna generacija; pronalazak puta; breadth-first search algorithm; Dijkstra's algorithm; Perlin noise; procedural generation; pathfinding; TEHNIČKE ZNANOSTI. Računarstvo. Umjetna inteligencija; TECHNICAL SCIENCES. Computing. Artificial Intelligence; Puta; sami
• Online Access: https://repozitorij.unios.hr/islandora/object/etfos:4094; https://urn.nsk.hr/urn:nbn:hr:200:437214; https://repozitorij.unios.hr/islandora/object/etfos:4094/datastream/PDF

U ovome radu napravljen je simulator za prikaz jednog od načina proceduralne generacije labirinta. Uz proceduralnu generaciju napravljen je i sustav za testiranje algoritama za pronalazak puta. Proceduralna generacija implementirana je na temeljima Perlinovog šuma (engl. Perlin noise), sami šum generira „boje“ terena te se iz toga nastavlja na izdizanje samog terena, ali se dodaju i konkretne boje kako bi teren bio što realniji. Kontroliranje ovih svojstava ponuđeno je unutar Unity sučelja. Za pronalaženje puta korišteni su Dijkstrin algoritam te algoritam pretraživanja po širini. Implementirani su na način da koriste podatke dobivene iz druge klase pod imenom WalkableTiles te koristeći znanje dobiveno o pozicijama po kojima se može kretati, ispisuju put od jedne točke do druge ukoliko takav put postoji. Cijeli sustav ukomponiran je u jednostavno sučelje za korištenje pomoću kojega možemo testirati algoritme te vidjeti njihove rezultate (broj točaka, vrijeme trajanja). Uz to postoji i grafički prikaz radi lakšeg praćenja puta kojeg će igrač prijeći. Rezultati prikazani mogu ukazati na to koji bi algoritam bilo prikladnije koristiti u određenim situacijama. This graduate paper shows the development of a simulator which presents the implementation of procedural generation. A system meant for testing some of the pathfinding algorithms was made, along with the procedural generation. Procedural generation is implemented on the basis of Perlin noise, where the noise itself generates the „colors“ of the terrain, and from that the system continues to raise up the terrain and gives it proper colors so that the terrain looks more realistic. The control of these properties is offered within the Unity interface. The two algorithms used for pathfinding were Dijkstra's and breadth-first search algorithm. They are implemented in a way so that they use the data obtained from another class titled WalkableTiles. By using the given information about positions they are able to find and show the path from one point to another in ...