Procedural Generation is one of the most useful and complex practices in game programming. It’s often difficult to get into because it’s quite abstract which can make it difficult to grasp. It can also be quite time consuming to experiment with and there are many different ways to get the results you want. It’s extremely useful because it can help us to generate nearly endless amounts of content on the fly. It can be used in level designing where you don’t want to generate the levels on the fly, but instead want to predetermine your levels. In this tutorial we’ll take a look at a basic procedural method to generate a 2D level’s map. Since this is the core of some basic procedural generation it can be extended and made to suit a variety of needs.
First off, let’s talk about how we’ll generate our level; what are our needs. For this example we’ll be using simple squares on a grid that have up to 4 transition points (N, E, S, W). We’ll need to ensure those points connect to other areas and build out our map. So how will we do this? Let’s step through the process.
Each of our Areas will have available transitions defined on them (North, East, South, and/or West). We’ll start off with a list of these predefined areas (or templates) so that we can choose from them to generate our level. First, we just pick one at random. Then we place that in a list of “generated areas”. Next we work our way along each of its available transition points and connect new areas to them. Connections are made both ways: one to the initial area and one to the new area. Visually the algorithm would look something like this:
We start at zero and add all of the ones, while ensuring that the connections go both ways. This is helpful to mark the transitions on as “used”. Each of the areas get added to the “generated areas” list. In the next step of our algorithm we will select an area from that list that doesn’t have all of its transitions used. We then repeat the process, but need to make sure that we look for any areas that are blocking the way (i.e. they can’t be transitioned into from an area because they don’t have a transition in that direction). Likewise, if there is an area in the way already and we can connect to it, then we should do so. We would now have a map that would be something like this:
The we simply continue in that fashion for a set number of iterations or until the areas have all their transitions covered. Here’s an animation of the algorithm in action.
As you can see, the algorithm works its way around the map connecting the transitions as it goes. Pretty nifty to watch it in action. An animation like this really helps me because I can actually watch the algorithm work. Let’s dig in further and take a look at the code.
The Code Structure
The code needed for this procedural level generation is broken down into multiple components:
- enum: This represents the place where a transition will be available on our .
- struct: This is used to map our areas to a world location in the game and allows us to work in a grid which in turn allows us to easily find existing areas to connect to or find out they’re blocking the way.
class: This is the class that will store all of the information about our areas (generated and templates).
class will have:
- A name to identify it by.
- An array of available transitions ( ).
- to tells us where on the map it should be place.
- A of with values that are a pairing of and this will store the transitions to/from this area.
class is responsible for:
- Marking a transition as used.
- Supplying a string list of the in an array (also used to generate a name for each ).
- Reporting the count of transitions that have been used.
- Reporting if a is available to create a transition on.
- Reporting if it has ANY available for placing a transition.
- And, of course, a method to supply a readable representation of the object.
- Utility classes:
- We’ll have some small extension classes (one for and one for ) that will help us out.
- We’ll have an class that will simply contain an and a corresponding custom inspector so that we can examine the on our visual representations.
: Finally we’ll have the class that contains the algorithm for generating our scene. This will inherit from
so that we can setup some
templates in the inspector and the number of iterations our algorithm should run through.
- Properties and fields:
- : number of times our algorithm will run.
- : a list that we can set in the inspector. These are our templates.
- : a list that will contain all of the areas that the algorithm generates.
- : This is a MonoBehaviour event that is called when you add the class as a component to a game object (or Reset the component). This method will just randomly fill out the array so that we don’t have to start from scratch.
- : This is our main algorithm for generating the map.
- : This will look through the list for an with matching coordinates. This will be used to find if there is already an area that we can possibly connect to or is blocking a transition.
- : This will create a new area (a copy) of a randomly selected area in the list of areaDatas that has an availableTransition in the specified direction. This is used when we’re adding areas to connect to.
- : Finally, we’ll want to see our results, so this method will create a simple representation of the map for us to see.
- Properties and fields:
All of these pieces work together to procedurally generate our map. This may feel a little overwhelming, but each class is as small as possible so that we can understand the small pieces and more easily put them together. Let’s move on to the actual code!
First up we have our Direction enum and its extension class. I think they’re pretty self explanatory, but I’d like to quickly touch on what an extension class is. An extension class is a static class with static members that act on a specific object type. In this case the only member, GetOpposite, acts upon a Direction and returns a Direction opposite to the direction acted upon. It would be used like so:
In this specific examplewould be . Extensions are just a handy way to have some quickly accessible methods that don’t need to belong to an instance of a class. Also, enums aren’t classes or structs so they can’t have methods. Extensions allow us to have methods that can act on an enum. Here’s the full code for our enum.
Next up we have ourstruct. I use this instead of a for a few reasons:
- Float comparison is imprecise and we can’t really say float a = float b with complete certainty. We can use , but that’s overhead and we don’t need float values in the algorithm.
- We don’t need fractional values. In programming it is best to just use exactly what you need. It conveys the intent you had when making the code and tells others (and your future self) there was a reason we aren’t using floats!
- A doesn’t have the methods we need and has a bunch of others we don’t need.
I could probably go on, but those are the main points. The funny thing is: I still needed a method to convert coordinates to a vector2. This was purely out of convenience so I could typeinstead of . Here’s the struct in it’s entirety:
Next up, I created two companions scripts that really don’t do anything, but help debug. The first is the Area : MonoBehaviour class. This simply contains an AreaData member so that we can view the values in the inspector.
The second script is a simple inspector script that will display the AreaData’s ToString() output in a HelpBox like so (make sure this script goes into an “Editor” folder!):
The SceneGenerator class
Finally we get to the algorithm that works out where to place our areas. I’ve liberally commented the code as usual, but let’s walk through it a bit. We have the number of or attempts to connect paths. One iteration will take a single area and make all the connections it can to that area. Two iterations will start working on an area connected to the first area, and so forth. I find with the example project on GitHub that 10 iterations is the max (i.e. I don’t get more connections). Then there is an array of AreaDatas ( ), these are the templates we’ll use when selecting areas at “random” and making our map. Then I have a List of AreaDatas ( ) that contains the AreaDatas that get generated by the algorithm.
The first method,, is a MonoBehaviour event that is called whenever a script is added in the inspector (or is reset by the context menu). In my method I simply create 4 random AreaDatas because… I’m lazy 😛 . Of course, you should fill in your own area datas in the inspector to experiment. The more areas with greater number of connections, the bigger the map will be able to grow.
Next up is the main algorithm,, this starts off by randomly selecting an AreaData from the array of templates (actually creates a new one with the same values, this is important!). Then we iterate through the algorithm for the number of indicated iterations. In the main algorithm is a sub-algorithm to find other areas to connect to the current area. In this sub-algorithm we examine each on the current area and look for an existing AreaData ( ) to connect to. If one is not found then we create an with that has a transition opposite of our current area. Then we add them both to the List and flag their corresponding transitions as used so we don’t check those transition in future iterations. Finally, we look for an area in the List that has open transitions and we repeat our algorithm to connect it to existing or new areas.
To do all of this we need a couple of companion methods.simply looks at the list of to see if there is one at the indicated coordinate. We use this to attach our current area to an existing area (if the transition between the two exists). We also have which will look through the list of template areas for one with an available transition that we need. It starts iterating through the list at a random index to provide some variation.
Last, but not least, is cuboids) at each transition point. This is really just to give us a visual representation of the layout and help us debug. It could also be captured to a texture to be displayed as a map if you like.this simply places a bunch of cubes at the coordinates of each area and places elongated cubes (or
Here’s the class in all it’s glory!
It’s a bit long, but not too bad at under 300 lines. The algorithm for generating the map is only about 100 lines. Short and sweet. However, it also has a lot of shortcomings and doesn’t create very interesting maps.
This algorithm is pretty basic, not that it is necessarily easy to pick up (algorithms often are a challenge when you’re not used to them), but it is basic in the sense that it doesn’t take many factors into account. It just blindly places areas and you may end up with very uninteresting levels. This algorithm shouldn’t ever be able to generate a level that is impassable, but you won’t get many branches or interesting shapes. The reason for this is that we may end up having areas at the edges with only one transition. That will block us in. It’s not too hard to conquer that, but I wanted to keep this post simple and aimed toward beginners. So, the first person to extend this out so that it make more interesting shapes will get a copy of my Mobile Store Screenshot Helper. If you want to see more refinement to this algorithm, let me know in the comments and I’ll work out some more complex rules in another tutorial.
You can download the entire example project from my GitHub account here: https://github.com/Naphier/Procedural2dMap/releases/tag/v1.0
If you’re interested in diving deeper into procedural level design and need some one-on-one help, give me a shout! I’m a Unity Certified Developer and I give private lessons in a variety of programming topics.
As always, thanks for reading and don’t forget to subscribe to my email list to hear about new blog posts!