The dungeon rooms are initially placed by randomly spawning them inside a radius. This results in a lot of overlapping squares, Separating Axis Theorem is then used to detect which squares are overlapping. The squares are then moved outward from the overlapped squares until they are no longer overlapping, similarity to how a lot of physics based collision systems work. So Separating Axis Theorem is in this case quite literally used to separate the dungeon rooms.
Delaunay Triangulation
Now that the rooms have been placed they need to be connected. A great to connect a large volume of points is triangulation. Delaunay triangulation is a form of triangulation that results in the points being triangulated in such a way that no point is inside a triangle. This is ideal for dungeons as that means we wont have any crazy overlapping or strange long connections.
Urquhart Graph
Once the rooms have all been connected we don’t need every single connection so you want to construct a planer graph for a more balanced amount of connections. There are lots of different planar graphs that can be used but i chose the Urquhart graph due its simplicity and elegance. How it works is you go through all the triangles and simply remove the longest side. This results in a very pleasing and effective set of coordinates.
About
In this project I created a procedural dungeon generator by combining several different algorithms. You start by randomly placing a set amount of rectangles in a defined radius. You then separate out the rectangles so none are overlapping using Separating Axis Theorem. Once you have all the rooms placed you connect them up using Delaunnay Triangulation. This results in a nice set of triangles but we don’t need that many connections, we need to make a more dungeon like layout which i do here by using a Urquhart graph to get a very dungeon-y lay out of paths. We now have all the data we need, we just have to construct it. So we take the rooms and replace the inner areaswith floor tiles and the outer areas with wall tiles, we then can replace connection lines with corridor tiles and then finally we have a dungeon.
This system will hopefully be fleshed out further in the future with the addition of a random interior to the dungeon rooms with multiple kinds of tiles.
Video (Video Jittery Due to OBS Capturing from VR )
Details
Programming Language: C++.
Engine: Unreal 4.
Project Type: University.
Platform: PC & HTC Vive.
Technical Features
Simplex Noise
Simplex Noise is an algorithm created by Ken Perlin. Similar to Perlin noise its creates random data that is incredibly useful in procedural generation. Simplex noise has a few advantages over Perlin noise such as being faster for large amounts of data, producing less unwanted artifacts and when used in three dimensions produces better results. In this project it is used to generate the starting data set.
3D Cellular Automata
Cellular Automata (CA) has been used for many different purposes over the years, from reproducing real world patterns such as snowflakes and seashells to full games such as the Conway’s Game of Life. These examples and the majority of uses of Cellular Automata differ from this project in one key aspect: they are usually 2D. While not being used as often for 3D as it is for 2D, CA is very good at creating cave like patterns in 3D. Starting with data generated using simplex noise the algorithm is run multiple times until distinct cave formations are formed. this data can then be passed to the Marching Cubes algorithm to be transformed into a mesh
Marching Cubes
Marching Cubes is an algorithm used to convert simple data in to 3D meshes. Used initially for medical imaging it has now been used to create a plethora of other things, one of the most common being procedural meshes for games. In my honours project it was used to procedurally generate the cave mesh from an isosurface created using Cellular Automata
Chunk System
Since you don’t want to render an infinite cave at all times a chunk system was necessary so as to allow only a set amount of chunks to be created and shown at once. This was done by defining set cube size and generating multiple of these cubes side by side. Due to the seeded nature of Simplex noise persistent caves were able to be achieved despite being generated as separate individual chunks. A big benefit to this approach is also the fact that it works extremely well with multi-threading.
Multi-Threading
Multi-threading is the process of running operations in parallel using different threads. For this project multiple chunks would be generated at the same time on different threads so as to greatly increase the performance of the real time generation of the cave.
Virtual Reality
The cave was designed to be explored in virtual reality, this meant considering its generation to be well suited to teleportation as well as giving a good sense of presence. Another big consideration was to make sure both the movement around the cave as well as the cave itself didn’t produce nausea. These considerations paid of as at the 2018 Abertay Digital Grad Show many people who who played this project commented that usually VR made them fell ill or nauseous but they felt fine exploring this VR cave.
About
A defining problem upon the consumer release of virtual reality hardware was a lack of content in Virtual Reality games. One way that the content within these games could be improved is the use of Procedural Content Generation. The Aim of this honours project was to investigate whether the use of Procedural Content Generation is a viable and effective technique for improving VR games.
In order to look into the applications of procedural generation in terms of VR and test if it is a viable method for the generation of VR content, an application was created in which you can explore a procedural generated environment in VR. This environment was created through a combination of Marching Cubes, Cellular Automata and Simplex Noise to produce an interesting and immersive world. The application was then user tested to assess the effectiveness of the research project. Qualitative and quantitative data was gathered through user testing and performance testing so that the feedback and results from these tests could be used to determine how viable procedural environments are for use in VR games.
The results of this project demonstrated that while not a perfect answer to VR’s content problems procedurally generated environments where indeed very effective at encouraging exploration, discovery and immersion as well as greatly increasing replayability. However, the results also revealed that a lot of thought and work need to be put into VR performance and gameplay in order to achieve good results using procedural environments. It was fond that using the techniques and methods explored in this project Procedural Content Generation can be achieved that works very well in VR as on top of the expected result of being able to create large interesting environments, it also creates environments that encourage natural exploration and invoke a fantastic sense of wonder and discovery.
Most of the game is procedurally generated. The placement of the stations as well as the train lines are completely random so the game is different each time you play. It also randomly names the stations from a list of station names that is loaded in from a text file.
Splines
To connect up the the stations after they are generated I created a spline system to act as the tracks that the trains could follow.
About
Trains mission was my submission to the Grads in Games Competition “Search for a Star”. The game started out as a game jam game created at the 2018 Global Game Jam. make this game was a great experience and I really liked the game idea so me and the artist(Molly McCarthy) who also worked on it kept developing it after the jam. It soon became better then what the search for a star game I had been working on so I kept working on and it became my search for a star game. The game consists of a procedurally generated subway system that the player has to make their way through to a certain station. After search for a star me and the artist have continued to improve and polish it with the intention of possibly releasing it fully on Itch once its good enough.
