By Willem den Dikken

**1. Contents**

- Introduction
- References
- algorithms
- Random walk
- Flood Fill
- Cellular Automata

- Implementation
- Result
- Sources

**3. Introduction**

For my R&D project I wanted to make a top-down RPG with different points of interest that the player can go to. Think about mountains and an ocean.

**3. Algorithms**

There are a lot of different algorithms that can be used in games to generate new content. Here I will talk about the once I used and how they work.

**3.1 Random Walk**

Random Walk makes use of a walker that takes a step in a random direction (north, east, south or west). All the posistions are saved and this way it creates a random path. The nice thing about this algorithm is that there is always a path to all positions because a walker already walked over there.

**3.2 Cellular Automata**

This algorithms works with cells that can have 2 different states, namely dead or alive. For each cell it checks whether the neighbors are dead or alive. If there are a certain amount of neigbors alive the cell changes itself to a living cell. otherwise it becomes a dead cell. This algorithm can make certain parts of the level generation appear more natural.

**3.3 Lazy Flood Fill**

Lazy Flood Fill is kinda similar to a fill bucket used in paint. It starts from 1 point and continues to color the canvas untill it is completely filled. The nice thing about Lazy Flood Fill is that at some point it just stops. This ensures that there are “islands” with different sizes.

**4. Implementation**

I started with researching different algorithms (the ones shown above). To get a feel of how they work I created a test scene to make these algorithms. After I really knew how these algorithms can work I started to create my world. Below I explain what I made and how I achieved it:**Roads**

Now I got all the algorithms figured out I wanted to work on the idea I had. After a few retries and I had a good picuture in mind. I wanted to start with the road. This road needed a direction to go to, I did this by giving a direction (north, east, south or west) and taking away the oppertunity to go the other way. Next up I wanted the road to be wider. I achieved this by making the surrounding tiles to roads. Finally I use Cellular Automata to make ik look more natural.

Below are parts of the code and result:

**Lakes**

Next up are the lakes. To create this I made use of Cellular Automata. I first filled the world with random water tiles. Next I use Cellular Automata to make lakes out of this. Finally I change all the neighbors of these tiles and change them to grass.

Below are parts of the code and result:

**Mountains**

The mountains took me a little bit of time. I had made 3 different mountains before I was happy with the final result. How I made this was by filling a part of the map with random “mountain” tiles. Next I used Lazy Flood Fill on all the “mountain” tiles to get different little islands. To make it more natural I used Cellular Automata on all the mountain tiles. Finally I wanted some rocks to spawn on the mountains so I changed a random amount of mountain tiles to rocks and used lazy flood fill on them.

Below are parts of the code and result:

**Ocean**

For the ocean I used the same technique as the lakes but only on the right side and different parameters. Next I replaced all the non-water tiles to sand.

Below are parts of the code and result:

**5. Result**

As the end result I got a path that leads towards the beach and mountains. My main objective was to have multiple points of interests for the player and I think I reached the minimum of this goal. I could have used more algorithms to make more interesting places. Now its just a few things that doesnt really connect well.

**6. Sources**

These are my sources:

1. Adonaac, A. (2015, September 3). *Procedural Dungeon Generation Algorithm*. Game Developer. https://www.gamedeveloper.com/programming/procedural-dungeon-generation-algorithm

2. Chunawala, Q., & Chunawala, Q. (2022, November 4). *Drawing Shapes with Marching Squares | Baeldung on Computer Science*. Baeldung on Computer Science. https://www.baeldung.com/cs/marching-squares

3. GeeksforGeeks. (2020, September 30). *Binary Space Partitioning*. https://www.geeksforgeeks.org/binary-space-partitioning/

4. Klayton Kowalski. (2021, February 13). *Lazy Flood Fill | Procedural Generation | Game Development Tutorial* [Video]. YouTube. https://www.youtube.com/watch?v=YS0MTrjxGbM

5. *Marching Squares, a Unity C# Tutorial*. (n.d.). https://catlikecoding.com/unity/tutorials/marching-squares/

6. Mxgmn. (n.d.). *GitHub – mxgmn/WaveFunctionCollapse: Bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics*. GitHub. https://github.com/mxgmn/WaveFunctionCollapse

7. *Procedural Dungeon Generator | Future Data Lab*. (n.d.). https://slsdo.github.io/procedural-dungeon/

8. Sebastian Lague. (2015a, February 9). *[Unity] Procedural Cave Generation (E01. Cellular Automata)*. YouTube. https://www.youtube.com/watch?v=v7yyZZjF1z4

9. Sebastian Lague. (2015b, March 1). *[Unity] Procedural Cave Generation (E02. Marching Squares)*. YouTube. https://www.youtube.com/watch?v=yOgIncKp0BE

10. *The Wavefunction Collapse Algorithm explained very clearly | Robert Heaton*. (2018, December 17). Robert Heaton. https://robertheaton.com/2018/12/17/wavefunction-collapse-algorithm/

11. Wolfram Research, Inc. (n.d.). *Hilbert Curve — from Wolfram MathWorld*. https://mathworld.wolfram.com/HilbertCurve.html