Categories

# Procedural Generation in GMS #7: To Perturb A Room (Dungeon Generation)

In this entry, we learn about perturbing rooms to generate a dungeon layout!

#### THE ENTIRE SERIES

More to come…

Note: None of the code for any of these proc-gen tutorials is highly optimised. My goal was to get the concepts across as simply as possible, rather than to make them run as fast as possible. Use the following as a springboard for further learning and experimentation, rather than as the best solution possible.

Also, if you are a complete beginner, it’s probably best to start at the first entry and work your way through, as further into the series we get, the more knowledge from previous entries is assumed.

I’ve been banging my head against autotiling for the past few days, which has meant that I haven’t been focusing on getting this entry done. 4-direction bitwise tiling is easy-peasy but I don’t like the way it ignores a specific section of tiles as it leads into a corridor, on the other hand, setting up 8-direction bitwise tiling just pisses me off. Having to map the binary onto the actual tile positions, rather than having the binary be the tile positions is too error prone for my ape brain to get right.

In any case, I finally decided to leave that problem for Future RefresherTowel and actually do the entry on room perturbation.

Let’s start at the start, then head in the vague direction of the middle and hopefully we’ll eventually get to somewhere in the realm of the end.

Room perturbation (I have no idea if that’s the “official” name, but that’s the one I use) is a generation method which involves creating a bunch of randomly sized rooms and then “perturbing” their positions until they are all a minimum distance from each other. You can see how it works in extreme slow motion via the gif at the top of the page.

The perturbation process involves a cool concept known as avoidance behaviour, which we will get into later. This method of generation is pretty random. BSP and other generation techniques like that generally lead to an “ordered chaos”, whereas room perturbation does not give the slightest shit about where the rooms end up. This means there’s less of the grid structure visible in the outcome, which is a good or a bad thing depending on your aesthetic.

Contents

BECOMING TOMMY WISEAU

ON THE METHODS OF ART VANDELAY

AVOIDANCE AS A COPING MECHANISM

THE NEXT STEP

## BECOMING TOMMY WISEAU

Since we have only very briefly touched on constructors so far, and creating a “room” in this room perturbation function requires the use of a constructor, I thought that’s where we would start. Create a new script and call it something to do with room perturbation (or not, I’m not the boss of you).

Let’s have a look at the code.

```///@func CreateRoom(x,y,width,height,no);
///@param x
///@param y
///@param width
///@param height
///@param no
function CreateRoom(_x,_y,_width,_height,_no) constructor {
width = _width;
height = _height;
x = _x;
y = _y;
rm_number = _no;
x2 = x+width;
y2 = y+height;
center_x_offset = 3+irandom(width-6);
center_y_offset = 3+irandom(height-6);
center_x = x+center_x_offset;
center_y = y+center_y_offset;

///@func Update();
static Update = function() {
x = round(clamp(x,1,other.map_width-width-1));
y = round(clamp(y,1,other.map_height-height-1));
x2 = round(x+width);
y2 = round(y+height);
center_x = x+center_x_offset;
center_y = y+center_y_offset
}
}
```

We have a function and as you can see after the function name `CreateRoom()` we have the special keyword `constructor`. If we go all the way back to #2: Learning the Basics, we’ll remember that a constructor is a “factory” for producing structs. This is super useful for when we want to create a bunch of “things” that all have the same basic parameters, which our dungeon rooms are perfect for. We know they’ll all need a width, height, position, etc, so we create a little constructor factory for pumping them out.

Most of it should be relatively self-explanatory if you’ve been following the previous entries. We have a bunch of variables that we’ll use for drawing and doing programmatic tests on the rooms. The only ones that may be slightly confusing to beginners are these.

```	center_x_offset = 3+irandom(width-6);
center_y_offset = 3+irandom(height-6);
center_x = x+center_x_offset;
center_y = y+center_y_offset;
```

All we are doing here is calculating a point that is within a certain range of each little “room”. We could literally just use the exact center of each room (in which case we would use `center_x = x+width div 2` and the corresponding for `center_y`), but I think it’s a bit more interesting to randomise the center point within the room. Depending on how we proceed with the next entry, where we build a fully connected dungeon, these values will be used as the starting point from which we connect the rooms to each other.

We also have an `Update()` method, which is simply called whenever we move the room and it “fixes” some of the values. For one, it makes sure the dungeon “rooms” never leave the border of the actual GMS room. Secondly, if we move the `x` and `y` of the room, then `x2`, `y2` and the center point will not be aligned correctly, so this is a simple way of adjusting them easily.

It’s all pretty simple but deceptively powerful. I’ve seen too many beginner coders trying to hard-code a bunch of sequential variables, rather than taking advantage of arrays and (now with 2.3) constructors, with the classic case being weapons the player might have. I see this all the time:

```weapon1 = true;
weapon2 = false;
weapon3 = false;
weapon1_dmg = 10;
weapon2_dmg = 5;
weapon3_dmg = 15;
weapon1_spd = 15;
// Etc, etc
```

This leads to a huge amount of problems. You can’t easily “cycle” through weapons, each weapon stat is completely disconnected from the weapon itself, adding or changing weapons is difficult and confusing. It’s a shitshow. Using a constructor and an array like we are going to be doing with our rooms is way more efficient and easily accessible/changeable. That being said, let’s get back to our room perturbation.

## ON THE METHODS OF ART VANDELAY

We’ve had a look at our room constructor function, now let’s see what’s happening in the main function.

```///@func GenerateDungeon(width,height,min_rm_size,max_rm_size);
///@param width
///@param height
///@param min_rm_size
///@param max_rm_size
function GenerateDungeon(_map,_width,_height,_min_rm_size,_max_rm_size,_room_coverage) {

room_list = [];
room_no = 0;

static map_width = _width;
static map_height = _height;
static map_area = map_width*map_height;
static min_rm_size = _min_rm_size;
static max_rm_size = _max_rm_size;
static coverage = _room_coverage;
coverage = clamp(coverage,0,1);

///@func	UpdateMap(map)
///@desc	Updates the values stored in the map to correspond with the placed rooms
///@param	{array}	map	The 2D array used for the map
static UpdateMap = function(map) {

for (var i=0;i<room_no;i++) {
var _rm = room_list[i];
with (_rm) {

for (var xx=0;xx<width;xx++) {
for (var yy=0;yy<height;yy++) {
other.map[x+xx][y+yy] = ROOM;
}
}

}
}

}

///@func	GenerateTotalRooms(map,map_width,map_height,map_area,coverage,min_rm_size,max_rm_size)
///@desc	Attempts to generate enough rooms to fill the coverage percent provided for the map
///@param	{array}	map			The 2D array used for the map
///@param	{int}	map_width	The width of the map
///@param	{int}	map_height	The height of the map
///@param	{int}	map_area	The area of the map
///@param	{float}	coverage	The percent of the map that should be covered by rooms
///@param	{int}	min_rm_size	The minimum size of each room
///@param	{int}	max_rm_size	The maximum size of each room
static GenerateTotalRooms = function(map,map_width,map_height,map_area,coverage,min_rm_size,max_rm_size,move_rooms,update_map) {
var successful = false;
do {

var coverage_complete = false;
while (!coverage_complete) {

var _w = irandom_range(min_rm_size,max_rm_size);
var _h = irandom_range(min_rm_size,max_rm_size);
var _x = map_width div 2+irandom_range(-2,2)-(_w div 2);
var _y = map_height div 2+irandom_range(-2,2)-(_h div 2);

array_push(room_list,new CreateRoom(_x,_y,_w,_h,array_length(room_list)));

var total_room_area = 0;
var cancel_pos = -1;
room_no = array_length(room_list);
for (var i=0;i<room_no;i++) {
var _rm = room_list[i];

total_room_area += ((_rm.width+4)*(_rm.height+4));
if (total_room_area > map_area*coverage) {
cancel_pos = i-1;
break;
}
}

if (cancel_pos != -1) {
delete room_list[cancel_pos];
array_delete(room_list,cancel_pos,array_length(room_list)-cancel_pos);
coverage_complete = true;
room_no = array_length(room_list);
}

}

if (move_rooms()) {
successful = true;
}
else {
for (var i=0;i<room_no;i++) {
delete room_list[i];
}
room_list = [];
}
}
until (successful);

update_map(map);

}

///@func	MoveRooms()
///@desc	Uses steering behaviour to try to push all the rooms away from each other
static MoveRooms = function() {
var move_attempts = 0;
var total_attempts = 0;
do {

var pushed = false;

for (var i=0;i<room_no;i++) {

var _this_pushed = false;
var _rm = room_list[i];
var _steer_x = 0;
var _steer_y = 0;
var _pushes = 0;

for (var k=0;k<room_no;k++) {
if (i != k) {
var _rm2 = room_list[k];
if (rectangle_in_rectangle(_rm.x-2,_rm.y-2,_rm.x2+2,_rm.y2+2,_rm2.x,_rm2.y,_rm2.x2,_rm2.y2) > 0) {
_steer_x += (_rm.center_x-_rm2.center_x);
_steer_y += (_rm.center_y-_rm2.center_y);
_this_pushed = true;
pushed = true;
_pushes++;
}
}
}

if (_this_pushed) {
_steer_x /= _pushes;
_steer_y /= _pushes;
if (_steer_x == 0) {
_steer_x++;
}
if (_steer_y == 0) {
_steer_y++;
}
_rm.x += sign(_steer_x);
_rm.y += sign(_steer_y);
_rm.Update();
}

}

move_attempts++;
if (move_attempts > 200) {
for (var i=0;i<room_no;i++) {
var _rm = room_list[i];
_rm.x = round(map_width/2)+irandom_range(-3,3)-round(_rm.width/2);
_rm.y = round(map_height/2)+irandom_range(-3,3)-round(_rm.height/2);
}
move_attempts = 0;
total_attempts++;
}

if (total_attempts > 100) {
return false;
}

}
until (pushed == false);

return true;

}

GenerateTotalRooms(_map,map_width,map_height,map_area,coverage,min_rm_size,max_rm_size,MoveRooms,UpdateMap);
}
```

Wow, she’s a biggun. Let’s break it down a little. Firstly, we create a few instance variables and `static` variables.

```room_list = []; // These two are instance variables created
room_no = 0; // In whatever instance calls the GenerateDungeon() function

static map_width = _width;
static map_height = _height;
static map_area = map_width*map_height;
static min_rm_size = _min_rm_size;
static max_rm_size = _max_rm_size;
static coverage = _room_coverage;
coverage = clamp(coverage,0,1);
```

`room_list` is the array which we’ll be storing our constructed rooms in. `room_no` simply keeps track of how many rooms we are creating (it is essentially `array_length(room_list)`, but keeping track of it manually is just a very slight optimisation technique, probably unnecessary but whatever, I did it).

Then we have the `map_width`, the `map_height` and the collective `map_area`, all pretty self explanatory. The `min_rm_size` and `max_rm_size` are exactly what they sound like. We’ll be randomising the size of the rooms the dungeon creates, but we want to constrain that within a certain range. Those values are the range. Finally we have the `coverage`. This is a “percentage” of how much of the GMS room we want to be covered with our dungeon “rooms”. I’ve found best results by not going over 80% (0.8 in terms of what the actual value should be). Anything higher and we start to run into the map rerunning it’s generation too much because it can’t find the correct ways to position rooms. I’m also clamping it between 0 and 1 because you can’t really cover 150% of the room or anything like that without rooms overlapping, which we’re not allowing here. You can input whatever you want between 0 and 1, of course, the lower the number the more sparsely the dungeon is populated with rooms.

Let’s have a look at the first method.

```///@func	UpdateMap(map)
///@desc	Updates the values stored in the map to correspond with the placed rooms
///@param	{array}	map	The 2D array used for the map
static UpdateMap = function(map) {

for (var i=0;i<room_no;i++) {
with (room_list[i]) {

for (var xx=0;xx<width;xx++) {
for (var yy=0;yy<height;yy++) {
other.map[x+xx][y+yy] = ROOM;
}
}

}
}

}
```

This method basically updates the game map we’re using in the background. Despite the fact that it’s the first method, it’s the last thing to be run in the actual generation. By the time this code is called, we will already have created all our rooms, stored them all in `room_list` and positioned them properly (we’ll see this in the next method). It’s a simple loop running through `room_list`. Each entry in room list is a struct created by the `CreateRoom()` constructor. Since structs can be accessed in the same way as instances/objects, we can use a simple `with()` statement to access each struct as we loop through the array (we could also use dot notation if we wanted: `room_list[i].x`, etc).

Since we are using `with()`, we are entering the “scope” of the struct. This means that we can access the variables stored in the struct as without any prefixes (such as the previously mentioned dot notation). So when we run the `for()` loop from `0` to `width`, for instance, `width` refers to the `width` variable stored in the room struct created by the constructor. If we look inside `CreateRoom()`, sure enough, we see a variable named `width`. Same goes for `height`, `x` and `y`, which we are all accessing inside of the `with()` statement.

So we using `xx` and `yy` to loop from `0` to the `width` and the `height` of the constructed room, we’re adding these incremented loop values to the `x` and `y` of the room, and changing the map coordinates at these positions to a simple macro (the creation of which isn’t shown in this tutorial) called `ROOM`. We have to use `other.map` to access the map because we are inside the scope of the `with()`. If we simply tried to access `map[xx][yy]` instead of `other.map[xx][yy]`, the computer would look for a variable named `map` inside of the room struct. There isn’t one so the game would crash. By using `other`, we are telling the computer this variable belongs to the thing that is running the `with()` statement. The “other” thing, not the `with()` thing.

Ok, onto the main body of the whole generator.

```///@func	GenerateTotalRooms(map,map_width,map_height,map_area,coverage,min_rm_size,max_rm_size)
///@desc	Attempts to generate enough rooms to fill the coverage percent provided for the map
///@param	{array}		map			The 2D array used for the map
///@param	{int}		map_width	The width of the map
///@param	{int}		map_height	The height of the map
///@param	{int}		map_area	The area of the map
///@param	{float}		coverage	The percent of the map that should be covered by rooms
///@param	{int}		min_rm_size	The minimum size of each room
///@param	{int}		max_rm_size	The maximum size of each room
///@param	{method}	move_rooms	The method function we want to run when we call move_rooms()
///@param	{method}	update_map	The method function we want to run when we call update_map()
static GenerateTotalRooms = function(map,map_width,map_height,map_area,coverage,min_rm_size,max_rm_size,move_rooms,update_map) {
var successful = false;
do {

var coverage_complete = false;
while (!coverage_complete) {

var _w = irandom_range(min_rm_size,max_rm_size);
var _h = irandom_range(min_rm_size,max_rm_size);
var _x = map_width div 2+irandom_range(-2,2)-(_w div 2);
var _y = map_height div 2+irandom_range(-2,2)-(_h div 2);

array_push(room_list,new CreateRoom(_x,_y,_w,_h,array_length(room_list)));

var total_room_area = 0;
var cancel_pos = -1;
room_no = array_length(room_list);
for (var i=0;i<room_no;i++) {
var _rm = room_list[i];

total_room_area += ((_rm.width+4)*(_rm.height+4));
if (total_room_area > map_area*coverage) {
cancel_pos = i;
break;
}
}

if (cancel_pos != -1) {
delete room_list[cancel_pos];
array_delete(room_list,cancel_pos,array_length(room_list)-cancel_pos);
coverage_complete = true;
room_no = array_length(room_list);
}

}

if (move_rooms()) {
successful = true;
}
else {
for (var i=0;i<room_no;i++) {
delete room_list[i];
}
room_list = [];
}
}
until (successful);

update_map(map);

}
```

It’s a pretty big function, but that’s mainly because it’s really the thing doing the handling of the generation. As a general overview, we generate “rooms” until they roughly cover the percentage of the `map_area` that we want, then we run the avoidance system (`move_rooms()`). Once the avoidance system has done it’s work, we update the map (`update_map(map)`) and we are done. Pretty simple when it’s broken down. However, there’s a few new things we are doing here that we haven’t touched on before.

We supply a bunch of arguments to this function, but let’s note in particular the last two arguments. Because we are setting our `UpdateMap()` and `MoveRooms()` methods to `static`, we have to supply them as arguments to our `GenerateTotalRooms()` method in order to be able to access them within the correct scope. So that’s why they’re here. Whenever we call `update_map()` inside the `GenerateTotalRooms()` function it will be running the `UpdateMap()` method function and whenever we call `move_rooms()` inside the `GenerateTotalRooms()` function it will be running the `MoveRooms()` method function.

First of all, we set a variable called `successful` to false. This generator has a lot of inherent potential to fail, so we need some way to know when we have generated the set of rooms properly and this variable is how.

We then run a `do...until` loop. We haven’t touched on these loops before so let’s break it down. Conceptually, we have a block of code that we want to run until a certain condition is met. We can’t use a `for()` loop to do this, as `for()` has a set number of repetitions (we could do some stuff inside the for loop, like altering the incrementing variable, to keep it running until a condition is met, but it’s not intuitive and isn’t worth the hassle). We can’t use a `repeat()` for the same kind of reasons. We could use a `while()` loop though. The big difference between a `do...until` loop and a `while()` loop is when the condition is evaluated. A `while()` loop checks to see what the state of the condition is first and executes the loop after that, whereas a `do...until` executes the loop first and checks the state of the condition afterwards.

Let’s have a look at a small example and see what happens with both.

```var run_loop = false;
while (run_loop == true) {
x += 1;
}
```

If we were to run this `while()` loop, `x` would not be changed. This is because the `while()` checks to see if `run_loop` `== true` first before it runs the loop. Since `run_loop` is not true, it won’t run the loop. The only way the loop would ever run is if we set `var run_loop` `= true` at the start. So there’s only one value of the boolean `run_loop` that will make the `while()` loop run. However, if we look at the `do...until` loop with the same structure.

```var run_loop = false;
do {
x += 1;
}
until (!run_loop);
```

No matter what we set `run_loop` to at the start, `x += 1` will always be run. In this case, it will run once: first it’ll run the `do { }` part and increment `x`, then it will check the `until (!run_loop)`, see that `run_loop == false` and decide not to repeat the loop. If we set `var run_loop = true` at the start, the `do { }` part will run and `x` will be incremented, it’ll then check to see if `run_loop` `== false`, which it does not, so it will run the `do { }` again, then check `run_loop`, etc, etc (it will actually freeze the game as `run_loop` will never be true, since we aren’t doing anything to `run_loop` in the `do { }` part).

So this means if we want a code block to always run at least once, and potentially loop after that, a `do...until` loop is the right choice. If we want a code block to only run if a certain condition is met, and loop after that depending on the same condition, we would use a `while()` loop. I’ve elected to use a `do...until` loop here as a teaching moment.

Back to our code block. If I cut out a big chunk of the code, we can see here that `successful` is our condition for the `do...until` loop.

```var successful = false;
do {
// Code removed from here
}
until (successful);
```

We’re going to run the `do { }` part until `successful` gets set to true and `successful` is only going to be set to true if the entire room generation has happened successfully. This means that whenever we generate a dungeon that doesn’t meet our conditions, we can just neglect to set `successful` to true and the whole dungeon generation code will be run again, giving us an easy way to repeat the generation no matter how many times it failed.

Now let’s look into what is running inside the do.

```var coverage_complete = false;
while (!coverage_complete) {

var _w = irandom_range(min_rm_size,max_rm_size);
var _h = irandom_range(min_rm_size,max_rm_size);
var _x = map_width div 2+irandom_range(-2,2)-(_w div 2);
var _y = map_height div 2+irandom_range(-2,2)-(_h div 2);
```

We immediately jump into another loop, this time a `while()` loop. We could just as easily swap in a `do...until` here, but it doesn’t matter too much. We’re going to be running the `while()` loop until we set `coverage_complete` to true.

This loop is the loop that will actually be creating our “rooms”, so each cycle of this `while()` loop is going to be creating a separate room. This means that the first thing we want to do is randomly pick the width (`_w`) and height (`_h`) from our min and max variables we set up earlier using `irandom_range()`.

Now seems like as good a time as any to explain the different random functions. We have the classic `random(10)`. This will select a random number between 0 and 10 inclusive, including decimal points. It could be 2.35, it could be 4, it could be 9.61, etc. We then have `irandom(10)`. The i at the start of irandom stands for integer because irandom only returns whole integers. We could get 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 or 10 from the `irandom(10)` but never with any decimals.

`random_range(5,10)` and `irandom_range(5,10)` takes a range of values and does the same thing, except it generates numbers between the first and second argument, instead of between 0 and the argument. As you would expect `random_range()` allows decimals and `irandom_range()` does not. In our code, we want `irandom_range()`, because we are working in “grid space” and there aren’t any decimals in grid space (we could allow decimals, but there’s no point as eventually we would be rounding it off any way to apply it to the grid).

Then we pick the x (`_x`) and y (`_y`) positions for the room. These lines might seem a little confusing, but I’ll go over them bit by bit.

```var _x = map_width div 2+irandom_range(-2,2)-(_w div 2);
```

First we take the `map_width` and divide it by 2 (using `div` to leave no remainder) to get the center of the map. We then add a small amount of randomness using `irandom_range()` (notice that I’m using a negative number as the first argument, this is absolutely fine and will generate a random whole integer between -2 and 2). We add the randomness to give some initial shape to the directions the rooms will move. Then we subtract the width (`_w`) of the room divided by 2 (using `div` once again), in order to “center” the room. If we left out this part, the top left corner of the room would be in the center of the map, rather than the actual center of the room. The same is repeated for the `_y` coordinate.

Ok, let’s move on.

```array_push(room_list,new CreateRoom(_x,_y,_w,_h,array_length(room_list)));
```

Here we’re doing two things, we’re using the `CreateRoom` constructor to generate a new room struct by using the keyword `new`. This is important to remember whenever we’re working with constructors. If we want to use a normal function, we can just type it’s name, but if we want to generate a struct with a constructor function, we have to include the keyword `new` beforehand. So we create a new room struct, using the random values we generated before as the arguments to be stored in the struct, then we push the newly created struct into our `room_list` array.

This means we can easily look at each room struct by looping through the array and we can pick individual rooms by looking at the position in the array that coincides with that room struct.

Once we’ve done that, we move on to checking to see the how much of the `map_area` is covered by all of our generated room structs.

```var total_room_area = 0;
var cancel_pos = -1;
room_no = array_length(room_list);
for (var i=0;i<room_no;i++) {
var _rm = room_list[i];

total_room_area += ((_rm.width+4)*(_rm.height+4));
if (total_room_area > map_area*coverage) {
cancel_pos = i;
break;
}
}
```

Firstly, we set the `total_room_area` to 0 and we set up a variable called `cancel_pos` which will come into play if our `total_room_area` is greater than the amount of area we want covered.

We loop through the `room_list` array and check each room struct (we are temporarily storing the room structs in the `_rm` variable) we have added to it. We multiply the `width` and `height` of each individual room together to find the area of the individual room (we add 4 to the `width` and `height` just to make sure there’s a border around each room, otherwise depending on how much coverage we want, they might be sitting directly next to each other).

If our running tally of `total_room_area` ever gets greater than the `map_area` multiplied by our `coverage` percent, we know we have covered more than enough, so we set our `cancel_pos` equal to `i`, which is the position in the `room_list` array that held the room the pushed `total_room_area` over the `map_area*coverage` size. We’ll be removing that room later to make sure the area our rooms will cover is under our `coverage` percent, rather than over it. Then we break out of the `for()` loop.

Let’s have a look at the next section of code.

```if (cancel_pos != -1) {
delete room_list[cancel_pos];
array_delete(room_list,cancel_pos,array_length(room_list)-cancel_pos);
coverage_complete = true;
room_no = array_length(room_list);
}
```

This is running immediately after our `for()` loop. We first check if `cancel_pos != -1`. This is because if our `for()` loop ran all the way through without the room area reaching the amount we want, `cancel_pos` will still be set to -1, so we’ll just skip this and go back to the start of the `while()` loop and create a new room. However, if we did reach the room coverage we want, then `cancel_pos` will equal the position in the `room_list` array that corresponds to the room that pushed the `total_room_area` over the percentage coverage we wanted (and thus, because `cancel_pos` will not equal -1 anymore, the if conditional will run). To make sure that we don’t go over our coverage, we’re going to delete this room. So firstly we use the `delete` keyword and set it to the room struct stored in the `room_list` position pointed at by `cancel_pos`. `delete` is special keyword that tells the GMS garbage collector that this struct should be destroyed. Technically, we don’t have to do this, as the garbage collector will eventually notice that this struct has no external references pointing to it and it will destroy it automatically, but it’s good practice to do it manually to make sure.

Then we are deleting all the entries in `room_list` from the `cancel_pos` position to the end of the array. This makes sure that our `room_list` only contains the rooms whose combined size leads up to, but not over, the coverage area we want. Technically, `cancel_pos` should never be pointing to any place except the end of the array because we are checking every time we add a room, and thus the room that pushes the room area over the coverage should always be the last room added, but again it’s good practice to make sure with these sorts of things.

To briefly summarise what is happening. Each time a new room gets generated, we run through all the existing rooms using the `for()` loop adding up the total area they all cover. If our running tally of room area doesn’t exceed the area we want covered by the end of the `for()` loop, everything is good and we’ll end up back at the start of the `while()` loop and generate a new room again, repeating the process. Once enough rooms have been created that our running tally of room area is greater than the coverage we want, we immediately break out of the `for()` loop and get rid of the room that pushed it over.

Now we’re heading into the end of the generation. Let’s go over the last section.

```	if (move_rooms()) {
successful = true;
}
else {
for (var i=0;i<room_no;i++) {
delete room_list[i];
}
room_list = [];
}
}
until (successful);

update_map(map);
```

We call our avoidance behaviour method (`move_rooms()`) which will attempt to push all the rooms away from each other. If this ends up happening successfully, we return true from the `move_rooms()` method which means the if conditional will run and `successful` will be set to true, and our `do...until` loop will come to and end. However, if the avoidance behaviour can’t successfully move all the rooms away from each other, the else will be triggered. Here, we just loop through our `room_list` array and delete all the room structs we created and reset the array to a size of 0. Note that we are not setting `successful` to true if this happens, which means our `do...until` loop will go back to the start again and we’ll generate a whole new batch of rooms and run through the whole thing again, repeating this until we do successful generate and move all the rooms away from each other.

After the `do...until` loop has completed, we then run through our `update_map()` method and change all the cells covered by the rooms in our map to the macro `ROOM`. That’s pretty much it for our main `GenerateTotalRooms()` method function.

## AVOIDANCE AS A COPING MECHANISM

Now’s the time to look into the avoidance behaviour for our rooms. This is a subset of a really cool coding concept called steering behaviours. In one sense, it’s unintelligent pathfinding; in another, it’s emergent complexity.

The most common example used when describing it is the behaviour of a flock of birds. When you watch a big flock of birds swooping and diving and flying around, each bird is actually following a very simple set of rules, but the overall group seems to display a much more complex, emergent behaviour. So each bird might be following rules like:

1. Try to stay a certain distance from the nearest birds to me.
2. If I’m on the outside of the group, attempt to move towards the middle.
3. If I see a predator, flee.

But the combination of these behaviours across a group of many, many birds grouped together becomes an almost organic, living entity on it’s own (note: I have no idea what rules birds actually follow, lol).

Steering behaviours are a way of coding these sort of little rules into our game objects, and taking advantage of the complexity that arises from it. Here’s an example I whipped up. Sprite credit: “[LPC] Birds” by bluecarrot16, commissioned by castelonia. – https://opengameart.org/content/lpc-birds

That’s using a few steering behaviours combined, but we’ll just be using avoidance behaviours for our rooms. You can probably guess what will happen to the rooms. Each room will move to avoid the rooms around it, spreading them out across the map.

Let’s have a look at the full code for the avoidance behaviour of the room.

```///@func	MoveRooms()
///@desc	Uses steering behaviour to try to push all the rooms away from each other
static MoveRooms = function() {
var move_attempts = 0;
var total_attempts = 0;
do {

var pushed = false;

for (var i=0;i<room_no;i++) {

var _this_pushed = false;
var _rm = room_list[i];
var _steer_x = 0;
var _steer_y = 0;

for (var k=0;k<room_no;k++) {
if (i != k) {
var _rm2 = room_list[k];
if (rectangle_in_rectangle(_rm.x-2,_rm.y-2,_rm.x2+2,_rm.y2+2,_rm2.x,_rm2.y,_rm2.x2,_rm2.y2) > 0) {
_steer_x += (_rm.center_x-_rm2.center_x);
_steer_y += (_rm.center_y-_rm2.center_y);
_this_pushed = true;
pushed = true;
}
}
}

if (_this_pushed) {
if (_steer_x == 0) {
_steer_x++;
}
if (_steer_y == 0) {
_steer_y++;
}
_rm.x += sign(_steer_x);
_rm.y += sign(_steer_y);
_rm.Update();
}

}

move_attempts++;
if (move_attempts > 200) {
for (var i=0;i<room_no;i++) {
var _rm = room_list[i];
_rm.x = round(map_width/2)+irandom_range(-3,3)-round(_rm.width/2);
_rm.y = round(map_height/2)+irandom_range(-3,3)-round(_rm.height/2);
}
move_attempts = 0;
total_attempts++;
}

if (total_attempts > 100) {
return false;
}

}
until (pushed == false);

return true;

}
```

The first thing we do is setup some variables.

```var move_attempts = 0;
var total_attempts = 0;
```

This technique is often used in proc-gen. We want to move the rooms, but there’s the potential for the movement to get stuck in a loop (i.e. two rooms moving back and forth between the same positions and never “settling”). So each time we move the rooms, we add to a variable (`move_attempts` in this case). If we reach a max number of attempted moves, we reset the whole generator and create a new level. It’s one of the ways of guaranteeing a generated level reaches a certain criteria. We actually have two reset criteria. For `move_attempts` we are simply attempting to move the rooms. If we haven’t reached a valid arrangement after a certain amount of `move_attempts`, we increment `total_attempts`, reset the rooms back to the center of the map and retry the movement again. This is because sometimes the rooms can fit, but the arrangement they settled into randomly is sub-optimal. Resetting the positions will usually fix this. We keep doing this and if `total_attempts` reaches a critical number, we reset the whole generator and build the rooms again from scratch. Otherwise, we moved all the rooms successfully.

Moving on.

```do {

var pushed = false;

for (var i=0;i<room_no;i++) {

var _rm = room_list[i];
var _this_pushed = false;
var _steer_x = 0;
var _steer_y = 0;
```

We start up yet another `do...until` loop and we create a variable called `pushed`. Anytime any room collides with another room in the `do...until` loop, we set `pushed` to true. This is how we know if all the rooms are in valid positions. If `pushed` is still false at the end of the `do...until` loop, all the rooms have settled into good positions that we can use and we can move on from the room movement. If, instead, `pushed` is true, we know that at least two rooms were still colliding with each other, so the `do...until` loop repeats.

After we setup the `do..until` loop, we immediately start cycling through the rooms with a `for()` loop. We want to cycle through each room, compare it to every other room and see if we need to push them away from each other. We’ll do this with the good ol’ double `for()` loop. First we grab the room we want from the `room_list` array and store it in `_rm`. `_this_pushed` is set to true if `_rm` needs to be pushed away from another room. `_steer_x` and `_steer_y` are the vectors we will be pushing `_rm` in if we need to move it. Let’s look at the next chunk of code.

```for (var k=0;k<room_no;k++) {
if (i != k) {
var _rm2 = room_list[k];
if (rectangle_in_rectangle(_rm.x-2,_rm.y-2,_rm.x2+2,_rm.y2+2,_rm2.x,_rm2.y,_rm2.x2,_rm2.y2) > 0) {
_steer_x += (_rm.center_x-_rm2.center_x);
_steer_y += (_rm.center_y-_rm2.center_y);
_this_pushed = true;
pushed = true;
}
}
}
```

Now we loop through the rooms again in our second `for()` loop, to check all the other rooms against `_rm`. Note how we’re using `k` as the incrementor instead of `i`. If we used `i` here instead, we would be messing with the `i` in the original `for()` loop, which would lead to bugs. Just something to keep in mind when looping within loops.

Now, we only want to check rooms that are not `_rm`, so we check to see if `i != k`. If `i` did equal `k`, we would be checking the same position in `room_list` as the original `for()` loop is, which is comparing `_rm` to `_rm`. `_rm` will always be colliding with `_rm`, so we need to make sure we don’t do the comparison on that cycle of the second `for()` loop. We grab the room to compare `_rm` with and store it in `_rm2`. Then we do a `rectangle_in_rectangle()` comparison using the `x`, `y`, x+width (`x2`) and y+height (`y2`) positions stored in the two room structs. We also add a little “border” radius to `_rm` (-2 and +2), just to make sure the two rooms aren’t lying directly against each other.

`rectangle_in_rectangle()` will return 1 if one of the rectangles is fully inside of the other and 2 if the rectangles are only overlapping a bit, so we want to check if it is greater than 0 because we don’t want either to be happening. Technically, we could just check if `rectangle_in_rectangle()` is true, since GMS considers all numbers equal or above 0.5 as “true” and all numbers below 0.5 as “false”, but it’s good practice to be explicit with this sort of thing, in case true booleans are implemented by the GMS team in the future or something like that.

If the `rectangle_in_rectangle()` check comes back as true, we know the two rooms are colliding. So we figure out the vector the room needs to move in and we set `_this_pushed` and `pushed` to true. Let’s go over the way we set the vector a little bit.

```_steer_x += (_rm.center_x-_rm2.center_x);
```

Let’s say the `center_x` of `_rm` is 500 and the `center_x` of `_rm2` is 300. The result of the sum will be 200 (which is really the distance between the two positions). If instead the `center_x` of `_rm` is 200 and `center_x` of `_rm2` is 600 then the sum would be -400. Wait a minute, we learnt something about positive and negative numbers in the one of the previous entries Proc Gen in GMS #4: Connecting the Dots with Bresenham’s! We can use this to determine the direction!

As we learnt in the Bresenham’s tutorial, if the number ends up being positive, we know that `_rm` is to the right of `_rm2`, if the number is negative, we know that `_rm` is to the left of `_rm2`. We can use this to figure out the direction we need to move `_rm`. Additionally, by adding to `_steer_x`, instead of just setting `_steer_x` to the value, we can average out the direction `_rm` should move if it’s colliding with multiple rooms.

For example, let’s `_rm` is colliding with two other rooms and the first room adds 100 to `_steer_x`, which means we would need to move `_rm` to the right (because 100 is positive) to avoid it, but then the second room that `_rm` is colliding with adds -200 to `_steer_`x, meaning `_rm` needs to move to the left to avoid it. The sum total of `_steer_x` ends up being -100, which flips the direction it should move.

Additionally, by making it so that there’s less of a push the closer the rooms are (because the size of the push is equivalent to the distance), we make sure the outer rooms get moved more than the rooms clumped in the center of the map, which clears out space on the edge quicker for the center rooms to move into, rather than the center rooms trying to quickly move out and running into the outer rooms and then getting pushed back into the center of the map, etc. All of this goes the same for the `_steer_y` variable, so this gives us our two movement vectors.

Let’s move on to the actual room movement.

```if (_this_pushed) {
if (_steer_x == 0) {
_steer_x++;
}
if (_steer_y == 0) {
_steer_y++;
}
_rm.x += sign(_steer_x);
_rm.y += sign(_steer_y);
_rm.Update();
}
```

Ok, so if `_this_pushed` has been set to true we want to move the room. First we have to do a check on whether `_steer_x` or `_steer_y` is 0. The reason for this is because of how `sign()` works. If the distance between the rooms is 0 (meaning they are exactly on top of each other), `_steer_x` and `_steer_y` will hold 0. If we then do `sign(_steer_x)`, the sign of 0 returns 0, which means the rooms won’t move even though they should since they are definitely colliding. Therefore we give it a little push by making `_steer_x` and/or `_steer_y` equal 1 if this is the case.

Then we simply add the sign of `_steer_x` and `_steer_y` to the rooms position, which will move `_rm` 1 pixel in the x direction it should move and 1 pixel in the y direction it should move. Then we run the `Update()` method inside of the room struct. What does `Update()` do again?

```///@func Update();
static Update = function() {
x = round(clamp(x,1,other.map_width-width-1));
y = round(clamp(y,1,other.map_height-height-1));
x2 = round(x+width);
y2 = round(y+height);
center_x = x+center_x_offset;
center_y = y+center_y_offset
}
```

It runs in the scope of the `_rm` struct and it simply updates the `x`, `y`, etc variables for that room. We’re just making sure that the room is still contained inside the bounds of the GMS room and that all the other variables are updated to the new position `_rm` has been moved to.

We’ve successfully avoidance behavioured all the rooms once, so let’s look at the next chunk of code.

```	move_attempts++;
if (move_attempts > 200) {
for (var i=0;i<room_no;i++) {
var _rm = room_list[i];
_rm.x = round(map_width/2)+irandom_range(-3,3)-round(_rm.width/2);
_rm.y = round(map_height/2)+irandom_range(-3,3)-round(_rm.height/2);
}
move_attempts = 0;
total_attempts++;
}

if (total_attempts > 100) {
return false;
}

}
until (pushed == false);

return true;
```

So we increment the `move_attempts` variable and then we check to see if it’s over the “critical value”. I’ve set it to 200 for this, but it could be higher or lower, all that means is it will totally reset the positioning of the room quicker or slower if the rooms are stuck (this could effect your load times for the generation if you set it too high). If we do need to do a reset, we just loop through all the rooms and set their position to the center of the map, exactly like we did when we were creating them. Then we reset `move_attempts` back to 0 and increment `total_attempts`.

If `total_attempts` is greater than the critical value (100 in this case), we know we’ve had to reset the rooms a bunch of times (100 to be precise), so there’s probably no way to position the rooms correctly with the current setup we have (or the positioning required is extremely precise and we probably won’t find it randomly). If this is true, we quit out of the `MoveRooms()` method by returning false. Let’s have a look at the generation script again to remember what happens in the `MoveRooms()` method returns false.

```if (move_rooms()) {
successful = true;
}
else {
for (var i=0;i<room_no;i++) {
delete room_list[i];
}
room_list = [];
}
```

Remember that we had to pass in `MoveRooms()` as an argument named `move_rooms()` to the `GenerateTotalRooms()` method, which is why the name is slightly different, but we can see that if it’s false, we end up deleting all the room structs, clearing out the room_list array and eventually going back around to the start of the loop and regenerating all the rooms again. So that’s what happens when we return false.

However, if we get to the point where we loop through all the rooms checking for collisions and there is no collision, then `pushed` remains false and the `do...until` loop is exited. So if we get to the point where the loop has ended, we can simply return true. If we look at the `GenerateTotalRooms()` code just above, we can see that if `move_rooms()` returns true, we set `successful` to true, which then means that the `GenerateTotalRooms()` loop can end (as `successful` being true is the condition that ends the `do...until` loop in `GenerateTotalRooms()`). Wow, that means all the rooms have been generated and moved successfully, so we’re pretty much done.

We’ve got one last line that runs after the `do...until` loop in `GenerateTotalRooms()` method, which is this.

```update_map(map);
```

All that method does is loop through the rooms and set the cells in `map` that the rooms cover to the `ROOM` macro.

Aaaaaand we’re done. That’s the room generator. How do we get it to work? We simply call the `GenerateDungeon()` function like this.

```GenerateDungeon(map, map_width, map_height, 3, 10, 0.7);
```

The first argument is the map array we want to be updating in `update_map()` above. The second and third arguments are clearly the width and height of the map. The fourth argument is the minimum room size we want, the fifth is the maximum room size we want and the sixth is the coverage percentage we want. Whatever instance we call this in will end up holding `room_list` and `room_no` as instance variables, so we can simply loop through the rooms in the Draw Event or wherever if we want to do something with the rooms like draw them or access them.

## THE NEXT STEP

Well, each entry seems to be getting bigger than the last, but that’s because we’ve covered the easy stuff early on. In any case, we did it, we managed to get a true random dungeon generator running. Of course, this is only one of a few which we will end up covering over the course of this series, but we’ve finally gotten to the point where we are actually generating some real stuff. Hoorah for us!

The next entry will be focused on connecting the rooms together and maybe adding a few other things to the generator. I’m undecided as to whether we will use A* to connect the rooms or whether we’ll write a maze generator algorithm to connect them (whatever ends up with the coolest result is the one I’ll go with), we’ll cross that bridge as we come to it. So stay tuned for that entry when it comes out! Peace be to you my friends.

If you’ve got any comments, criticisms or advice don’t hesitate to comment and let me know, I’m always happy to hear feedback from readers. And if you like what I’m doing, consider supporting me through either a donation at the bottom of the page or buying my game Spaceslingers!

Sign up to get notified whenever I upload a blog post, so you don’t miss any of the next installments! ## By RefresherTowel

I'm a solo indie game developer, based in Innisfail, Australia.

## 2 replies on “Procedural Generation in GMS #7: To Perturb A Room (Dungeon Generation)” Dackersays:

Hey, this has been amazingly helpful! Do you have an ETA on the next chapter? (sorry to be that guy – it’s just that I’m hooked on your tutorials!)

Like

Awesome! I’m glad the series has been helpful! I’ve been in a bit of a rut when it comes to writing new entries because I’ve been focusing on some of my personal projects recently.

That being said, I have been feeling bad for neglecting the tutorial series, hahaha (it’s literally always sitting in the back of my mind), and I hope to get out a new entry sometime soon!

Like