Lately I have been working during my free time in a rogue-like game prototype and one key aspect of such games is the procedural generation of the different gameplay elements, such as monsters, chests, vendors, traps and so on. So  I came across a relatively innocent-looking challenge and I after spending some minutes thinking about it I decided to get deeper into this topic and help other people facing the same issues. I will be analyzing how to semi randomly position the doors of my procedurally generated rooms in a way that they look original, realistic, fun and still make sense. The following methods can also be applied to a wide range of gameplay areas: looting, monsters, leveling, dynamic difficulty, luck attribute influences, random events based on game status, etc..

Here is the starting point: every room is shaped as a 2d rect and has a variable width and height. The top wall will have a variable number of doors and every tile will be one unit wide. The possible tiles for the top wall are: wall or door. Now we should decide for each tile whether it is going to be a wall or a door.

Ok, so what options do we have?

A. Premade configurations + random picking

One option would be creating per hand the different combinations and then get a random number between 0 and the number of combinations – 1. Then we get the prefab using that random index and use it for our top wall.

The main advantage of it is that it is straightforward to implement; in Unity it would barely take three lines of code to get it done. Also, you make sure that it will look well, since you’ve made them beforehand.

Between their disadvantages we could especially point out that the amount of manual work setting up the scenarios will skyrocket if the number of variables increases (number of doors, possible wall widths, etc.). Maintaining them is also tedious and it may be hard to combine this technique with continuous (non-discreet) variables that have an infinite amount of values or those which are not known in compile time.

Instantiate(ScenePrefabs[UnityEngine.Random.Range(0, ScenePrefabs.Length)]);

B. Pure random positioning

The second option is to take a random number between 0 and the number of tiles and position the door there. If you have more than one door, then repeat that procedure until all doors have been placed.

Still, you have to be careful not to overwrite doors in the same position. If you are unlucky, you may get the same random number a few times. You can easily make a workaround and throw a dice until you get a number that has not been picked yet. Another problem of this approach: if you are even unluckier, that process might take a while since you might be getting the same random numbers the whole time. It is not likely to happen, but it might, since this process is not guaranteed to end.

As I do not like to depend on luck, here is another option: you may also create an array with all possible tile numbers and then you get a random number so you choose the tile to put the door in. Afterwards, you take that tile out of the array and keep moving. That will also fix the problem of infinite randoms loop.

However, there are more issues here: you might need to adjust the process so it looks well in your game (padding between doors? no clustered areas of doors? no doors in the corners?).

const int NumberOfDoors = 3;
var tiles = new GameObject[]{WallPrefab, WallPrefab, WallPrefab, WallPrefab, WallPrefab};
for (int i = 0; i < NumberOfDoors; ++i)
{
	int tile = Random.Range(0, tiles.Length);
	if (tiles[tile] == WallPrefab)
	{
		tiles[tile] = DoorPrefab;
	}
	else
	{
		i--; // Repeat.
	}
}
for (int tile = 0; tile < tiles.Length; ++tile)
{
	Instantiate(tiles[tile]).transform.position = new Vector3(tile, 0, 0);
}

You may expect such results:

Random placement strategy

C. Random positioning based on statistics

I wasn’t totally happy with the previous solutions, especially since I didn’t have any way of influencing the process of selecting tiles for our doors. I could just throw a dice a few times and wait for a result. Now, as a game designer, you would normally like to be able to influence  the mechanics a bit.

For instance, I would prefer my doors not to spawn on the corners but rather around a certain range on the center. If we translate that word, prefer, into the mathematical language, we get to relate it to probabilities. We would like the probability of spawning a door in a corner to be much lesser than in the middle.

Now, statistics is a complex topic to start with for people having no prior experience with it, so let’s try to keep it simple. We can use an example to make clear what we want to achieve. If we are to build 100 rooms with a fixed number of tiles, we can represent in the following grid the number of doors of a specific type that will be spawned in every tile for the experiment:

As we see, we want most of the doors to spawn around the center. Following the definition of probability, in this case the probability of spawning a door just in the center will be 30%. Here is the same data in a chart:

Spawn probabilities per tile

What is so powerful about this? Well, we may change those probabilities in runtime depending on the game design. Also, after spawning a door in one place, we can set the probability of that tile (and maybe neighbor tiles, if we want to leave some space between them) to zero and rescale our model so the sum of all probabilities is 1. Let’s say we want to spawn two doors and the first one was spawned in the tile number 5; how would the new chart look like after taking that element out? We first sum the remaining probabilities and we get 0.90; that means, we have to scale every element by 1/0.90 like this:

Modified spawn probabilities per tile after removing one

Ok ok, whatever, how do I implement this? The functions we saw are called Probability Density Functions (PDF). They are pretty straight-forward if we are working with discrete variables. The trick is to convert the PDF to a Cumulative Distribution Function (CDF), which is also straight-forward with discrete variables; the probability of every item is the sum of all probabilities from the start until that item included. For the original chart we would get this one:

Cumulative distribution function

Now getting the tile where the door is to be spawned is also easy. We just get a random number between 0 and 1 and then find the first tile whose probability is larger than that number, starting from left to right. For instance, if the number we got is 0.2, then we will choose tile 2; if the number is 0.70, we select tile 4.

using UnityEngine;
using System.Collections;
using System.Linq;

public class WallSpawner : MonoBehaviour {
	public GameObject DoorPrefab;
	public GameObject WallPrefab;

	void Start () {
		SpawnWall();
	}

	void SpawnWall () {
		const int NumberOfDoors = 3;
		var tiles = new GameObject[]{WallPrefab, WallPrefab, WallPrefab, WallPrefab, WallPrefab, WallPrefab, WallPrefab};
		var densityFunction = new float[]{ 0.05f, 0.10f, 0.20f, 0.30f, 0.20f, 0.10f, 0.05f };

		for (int i = 0; i < NumberOfDoors; ++i)
		{
			var cumulativeFunction = GetCumulativeFunction(densityFunction);
			float randomValue = Random.value;
			int tile = GetTile(cumulativeFunction, randomValue);
			tiles[tile] = DoorPrefab;
			densityFunction[tile] = 0.0f;	// This tile can't be chosen anymore.
			densityFunction = NormalizeDensityFunction(densityFunction);
		}

		for (int tile = 0; tile < tiles.Length; ++tile)
		{
			Instantiate(tiles[tile]).transform.position = new Vector3(tile, 0, 0);
		}
	}

	float[] GetCumulativeFunction(float[] densityFunction)
	{
		var cumulativeFunction = new float[densityFunction.Length];
		float accumulator = 0.0f;
		for (int i = 0; i < densityFunction.Length; ++i)
		{
			cumulativeFunction[i] = densityFunction[i] + accumulator;
			accumulator = cumulativeFunction[i];
		}
		return cumulativeFunction;
	}

	int GetTile(float[] cumulativeFunction, float randomValue)
	{
		for (int i = 0; i < cumulativeFunction.Length; ++i)
 		{
 			if (cumulativeFunction[i] >= randomValue)
			{
				return i;
			}
		}
		return cumulativeFunction.Length - 1;
	}

	float[] NormalizeDensityFunction(float[] densityFunction)
	{
		float total = densityFunction.Sum();
		return densityFunction.Select(p => p / total).ToArray();
	}
}

By using simple statistics we remain flexible enough that we can adapt our gameplay eitherdynamically by certain game events (difficulty, achievements) or statically through the further updates on the game design document. And at the same time we achieve a well-looking environment that doesn’t look 100% randomly placed.

With this strategy it is more likely that you will see this kind of placement:

Statistically based placement

Now, if you want to go with continuous variables, the cumulative distribution function has to be calculated through an integral and, as far as I know, it is hard to create probability density functions that match your gameplay preferences in a way that their CDF sum 1. Normally you have to use well known PDFs; if you know other way, please message me.

We can apply this principle to many areas of our game. For every monster we kill, we could decide which items are to be looted (by modifying base probabilities through modifiers/scores depending on the monster level, area, faction, etc.), or maybe tweak the dices in a turn-based game in order to help the player if they is not doing really well in that level. Which monster to spawn could also be modeled with statistics depending on player level or characteristics (at low levels we normally want only to spawn low level monsters, but exceptions can maybe occur). Timings can also be adjusted with statistics, but there you are looking more into continuous variables (check Poisson distribution for instance).

If you want to spawn monsters in a 2d room, you can make a grid out of it with every cell having the same probability (so that all together sum 1). After spawning a NPC in a cell, you may alter that cell and also the eight neighbor cells so you reduce the probability of creating clusters of enemies. You can consider the X and Y variables as independent random variables. If you are in a 3d world, Z is usually set at the ground level.

So, do you know a better approach for such processes? If so, let me know, I’m really looking forward to improve the system!