Pathfinding in procedurally generated mazes

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 case the path exists. The whole system is integrated in a simple user interface with which the algorithms may be tested and their results can be displayed (number of nodes in the path, pathfinding duration). In addition, there is also a graphic display for easier monitoring of the path that the player will move along. The results shown can indicate which algorithm would be more appropriate to use in certain situations