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

---

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!

Advertisement