Computer Graphics Project 2018/19 spring

Procedural Maze

Meelis Perli

The main goal of this project is to generate an infinite maze using wave function collapse algorithm. To achieve this I plan to use Unity game engine. I don't plan to implement WFC algorithm myself, because there already are assets in Unity for that and I want to focus more on the graphical part in this course.

Once maze generation works and there is still time, I will make it into a small game.

The plan is to:

1. Learn about procedural generation.
2. Use wave function collapse assets in Unity to generate a 3D maze.
3. Polish the maze.
4. Add a player.
5. If there is still time for anything else: make it into a small game.

Technologies I'm using:

1. Unity
2. Audacity
3. Paint.net, if i need textures (might use WFC for texture generation too)
4. Unity WFC tool

Repository link

Build download

A great demo of the algorithm

Video of the final result

Milestone 1 (08.03)

• Learn about Unity WFC tool (1h) - done
• Get Unity WFC tool working (2h) - done
• Make some basic blocks to generate (1h) - done
• Try to generate a 3d chuck (3h) - done

Result

Currently there are 3 different types of blocks. Path, wall and diagonal wall. these can be seen in the top left corner of the image. In the area with purple borders, the tiles can be painted using the blocks and after that the model is trained. Once trained, patterns like the one on right can be generated.

Another chunk

Milestone 2 (22.03)

• Add at least 3 new elements to the maze (2h, actual: 1h and 40min)
• Bug fix: Make the generated chunk stay after pressing play (1h, was really easy (2min), finding and fixing a block rotation bug took 2.5h)
• Bug fix: fix block height (1h, actual: 1h)
• Add player character and make it possible to navigate in maze (1h, actual: 75min)
• Experiment with making infinite map (2h, actual: 2h)

Result

For this milestone 3 different tunnel pieces were created (straight, curve and intersection)

The player character was also added so these tunnels could be explored. Currently the player can move the character around with WASD keys, jump by pressing spacebar and rotate by moving the mouse while also the right mouse button is down.

Player character in the tunnels.

View from a distance.

Unfortunately I did not manage to make the map infinite yet, but I did learn about the WFC assets and managed to fix some of the bugs there. One of those was the block rotation bug, where all the blocks had the same rotation.

Milestone 3 (05.04)

• Total time (7h, actual: 6h, 25min)
• Add at least 5 new elements to the maze (2h, actual sum: 2h)
  • Bridges took 40min (2 new elements)
  • Boxes from Delta building visualisation (20min)
  • Instead of making another 2 I decided to fix previous elements (took 1h)
• Add textures (1h, actual 1h)
• Improve the player (1h, actual sum: 25min)
  • Fix player character collisions with the walls (actual 15min)
  • Improve turning (actual: 10min)
• Try generating with simpleTileMap instead of overLap WFC (1h, actual: 10min)
  • fix the block rotation bug here aswell (different cause)
• Try to make the map infinite (2h, actual 2h 50min)

Result

For this milestone, the experiments with making the map infinite were continued. Some progress was made in this field and now a grid of chunks is generated and extended once the player wanders too close to the edge. The chunk edges still need some work, but these will be worked on for the next milestone. simpleTileMap did not seem promising after getting it to work, so the extra 50 min went to trying to make the map infinite.

The player character was also improved. It wont get stuck to walls or rotate when near walls anymore.
Fixing previous blocks was not in the planned tasks, but I wanted to do it anyway (took 1h).

Bridges!

Boxes!

Textures!

Milestone 4 (12.04)

Total planned time 7h, actual 9h

• Improve the chunk edges (3h: actual 6h)
• Create more textures (2h: actual 2h)
  • Textures for walls and caves
• Create a nice base tile map for generating chunks (1h: actual 40min)
• Fix the bug where chunk is not generated (1h: actual 20min)

Result

Improving the chunk edges by collapsing the edges to match the neighbouring chunk edge during the initialization did not work. The chunk usually resulted in a configuration, that was not allowed and the chunk could not be drawn or in some cases Unity crashed. Trying to get it to work has taken a lot longer than i had anticipated and thus some compromises were made. The chunks were made larger so the player does not have to deal with the edges too often. A parameter called periodic output was turned on. This parameter was found to make edges nicer.
Fixing the bug where chunk is not generated turned out to be easy after looking at the code for around 6h. Basically if the chunk model turns out to be null, then a new model is generated.
A good sample grid is quite important to have. This will affect how the maze will look like and too small sample grid leads to invalid grid configurations more often than a big one. The current sample grid can be seen below.

This map has 4 main different areas.

• Caves
• Tight areas
• Open areas
• River (void) areas

In this milestone, the caves also got a rework. These should look nicer now.

Milestone 5 (03.05)

Total planned time 6.5h, actual: 6.67h

• Make the player spawn in a reasonable place (2h: actual: 2h, 30min)
  • The player should not be stuck after spawning (actual: 30min)
  • Should be able to move almost everywhere (actual: 2h)
• Add more elements (1.5h; actual: 1h, 10min)
  • Replace void with water (1h; actual: 40min)
  • Make roads (30min; actual: 30min)
• Work on improving the map generation for at least (3h; actual: 3h)

Result

For this milestone some more elements were first added. First of them was water. The water prefab was taken from Unity's standard assets, which was then added to the chunk. Because the grass is not usually underwater, most blocks' UV mapping was updated.

Roads were also added. There are 3 different road blocks, straight, crossroads and curves. After creating those, it also made sense to update the bridge staring/ending blocks.

Because the water reduces the performance quite a lot, the too far away chunks were made to unload. The player spawning was also made better. The player cannot spawn on the walls anymore and a flood-fill algorithm is now used to check how large area is traversable. If the area is large enough, then the player is spawned. If no such areas are found, then the starting chunk is regenerated.

Milestone 6 (17.05)

• Further improve map generation for at least (3h; 6h)
• Give the player something to do (3h; 8h)
• Fix textures (2h; 1h)

Result

This milestone was started by improving the map generation. The main idea this time was to try to implement the algorithm. This however was not successful due to time constraints and the difficulty of debugging the algorithm. The algorithm's implementation had issues and thus generated too random chunks and was not suitable. The map was still improved a bit by making the learning chunk bigger.

It is important to give the player something to do. Otherwise they just look around a bit and quit the game. The main objective in this maze game is to collect boxes. The boxes also have a particle system to make them easier to find.

Reaching these boxes should not be too easy, thus enemies were created.

The enemies do not move around. They just rotate and shoot the player character if it should be in their line of sight. The enemies are quite primitive. They can only see what is in front of them.

Some textures were also fixed in this milestone.