Categories
personal blog procedural generation series tutorial

Procedural Generation in GMS #2: Learning the Basics

In the second entry in the series, we learn about the data structures we will be using in future procedural generation techniques.


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 ran into some personal problems recently and also had a bit of skullduggery happening with my computer which put a bit of a kibosh on the series, but I’m back in action now. In this part of the series, we’ll be going over the basic data structures we’ll be using in preparation for when we really start working with proc-gen. This entry is going to be relatively basic, but I wanted to make sure that the series was beginner friendly and that means building from the ground up.


Contents

CH-CH-CH-CHAAAAAANGES

ARRAYS ARE THE NEW BLACK

STRUCTING YOUR STUFF

THE GRID, THE LIST AND THE WARD…I MEAN MAP

THE NEXT STEP


CH-CH-CH-CHAAAAAANGES

With the (relatively) recent 2.3 update to GMS, we’ve received a number of awesome features that help us structure things better when we’re dealing with proc-gen. So let’s go over a little bit of the changes that will effect us.

Originally, in the before times, the most common data structures used when dealing with proc-gen (and a lot of other things) were lists, grids and maps. In GMS, these data structures need to be manually cleaned up, which could end up being quite a pain in the arse if you were creating many, many different structures to hold the stuff you were generating and then realised there was a memory leak. Much wailing and gnashing of teeth would follow as you sorted through a ton of code trying to find the one place where something wasn’t being deleted.

Thankfully, we live in the future now, so we have to worry about this sort of thing much less because…We can use arrays. Hoorah! Arrays are automatically garbage collected, so we’re a lot less likely to run into memory leaks when dealing with them (though there are a few specific circumstances where arrays can memory leak, though these are bugs in GMS itself and are scheduled for fixing in the future…Also, we won’t be going near the use-cases that can result in them so don’t worry).

Using a combination of arrays and structs allows us to almost completely bypass the tedious task of manual memory management and forge ahead into a dystopian future with our memories wiped by the computer itself.

That being said, we’re still going to cover all the data structures as it is useful to know how different things work, in case you run into an edge-case where one of the other data structures is the best choice. Onwards and upwards!


ARRAYS ARE THE NEW BLACK

Arrays are a very basic list structure. If you think of writing down a shopping list on a piece of paper, you can imagine the paper as the array and each item of shopping you add as an entry into the array. In other words, they’re fancy ways of storing multiple variables inside a single variable.

Let’s look at a few different ways of creating arrays:

my_array = [];

This is probably the simplest you can get. It creates an array of size 0.

my_array = array_create(size,value);

This format lets you predetermine the size of the array you want and also fill it with a value.

my_array[0] = 1;
my_array[1] = 5;

If you envision the array in your head it might look something like this:

1
5

If we wanted to read the value back, we would simply do this:

var _entry = my_array[0];

Now the temporary variable _entry would hold the value 1. You can also created 2D arrays (or 3D, or 4D, etc). A 2D array is better thought of as a grid, or a spreadsheet. You have your rows and your columns. Let’s have a look at a 2D array:

my_array[0][0] = 1;
my_array[0][1] = 5;
my_array[1][0] = 3;
my_array[1][1] = 4;

And it would look like this:

13
54

Relatively simple. Reading an entry back is as simple as this:

var _entry = my_array[0][1];

Now the temporary variable _entry holds the value 5. One thing you might note is that the above “envisioned array” looks exactly like a grid. Which, it kind of is. So that’s why we can cross ds_grids() off our list of necessary requirements to use and replace them with arrays…Wait a minute, if we look at the table before that one, it looks like a list doesn’t it? So we can also replace ds_list() with arrays. How super useful! Having said that, there may be some reasons to use the permutations of ds_list() such as the priority queue and the stack, so we’re not completely free from the old data structures, but we sure are close.

One final point to make with arrays is that you can push entries onto the end of the array without needing to know the size of the array by using the function:

array_push(my_array,150,10,20);

This will push the values 150, 10 and 20 onto the end of my_array in that order. I’ve added three values here, but you can add as many or as few values onto the end as you want simply by separating them with commas. You can also pull the last value out of the array without needing to know it’s length by using this function:

var _entry = array_pop(my_array);

Here, _entry will hold the value 20, as that was the last value to be added to my_array.


STRUCTING YOUR STUFF

Structs are a super cool addition to the GMS roster of tools. You can think of them as “lightweight” objects. When you create an object in GMS, one of the first things you usually do is open up a Create Event and start initialising some variables. Well structs let us do that (amongst other things) without having all the overhead of a true object. They can be referenced with the same dot notation you might use to access object/instance variables.

Let’s have a look at a basic struct:

my_struct = {
	a : 0,
	b : 1,
	c : 2
}

You might notice some formatting changes there that are different to what you were used to with normal objects, but it’s really very simple. First of all, the my_struct is simply the variable you are assigning the struct to. You can think of this as the object name or instance ID of normal objects. We tell GMS it is a struct by opening immediately with the curly bracket { and then we assign values to variables using the colon : instead of equals =. Finally, instead of ending lines with a semi-colon ;, lines are ended with a comma ,.

After setting up the struct we access it like this:

my_value = my_struct.a; // This would assign 0 to my_value, as 0 is the value being held in the a variable in my_struct

Let’s take a less academic approach though, as I often find the more abstract examples a bit harder to grasp when I’m reading them myself. Suppose you wanted to have a list of spells that your player could use. Of course, you could assign a bunch of variables in the player object (or better yet, use an array) but instead, we’ll use a struct.

global.my_spells = {
	has_ice : false,
	has_fire : false,
	has_wind : false,
	wind_damage : 3,
	fire_damage : 5,
	ice_damage : 4
}

Ok, so we’re (in a very basic way that probably wouldn’t be that great for production code) listing out the spells the player could have and the damage associated with that spell. Let’s say we want our sword to apply the damage from all the spells we have when we hit an enemy.

// Check if the sword is hitting an enemy
if (instance_place(_sword.x,_sword.y,obj_enemy)) {
	var dmg = 3;
	// We'll use 3 as the base damage
	// Check if the has_ice variable in the my_spells struct is true
	if (global.my_spells.has_ice) {
		// Add the ice_damage variable from my_spells to the dmg
		dmg += global.my_spells.ice_damage;
	}
	// And so on for each of the others
	if (global.my_spells.has_fire) {
		dmg += global.my_spells.fire_damage;
	}
	if (global.my_spells.has_wind) {
		dmg += global.my_spells.wind_damage;
	}
}

This checks the struct for each has_* variable and if it is true, adds the damage associated with that spell type to the temporary dmg variable. If we wanted to switch has_wind to true, we would simply do this:

global.my_spells.has_wind = true;

And there we go, an extremely basic but at least somewhat relatable example of using structs.

However, there’s one step further we need to go with structs for procedural generation and that’s called a constructor. This let’s us basically setup a little factory to create structs automatically. The format is this:

function MyStruct(_x,_y) constructor {
     x = _x;
     y = _y;
     m = 2;
 }

Now this looks a little different from the original structs we looked at above so let’s break it down. Firstly, this is going to be used like a script would’ve been in the pre-2.3 days. So we tell GMS that it’s going to be a function (the “new scripts”) and give it a name, I’ve chosen MyStruct (this can be anything). Then finally, we follow it with the word constructor, which tells GMS that this is going to be used to “construct structs”. I’ve also added in some arguments (the _x and _y). Finally, you’ll note that we’re assigning the variables using = and ; instead of : and ,which is something to keep in mind. Basics structs use : and , while constructors use = and ; So let’s call this badboy in-game:

my_constructed_struct = new MyStruct(10,20);

We’re telling GMS to create a new struct using MyStruct as a template with the keyword new and the result will be that my_constructed_struct now looks like this if we format it as a basic struct:

my_constructed_struct = {
	x : 10,
	y : 20,
	m : 2
}

You can see that it has all the variables from the constructor, with the supplied values from the function call being slotted in.

Finally, constructors can also be inherited, which looks like this:

function Enemy() constructor {
	name = "";
	hp = 10;
	mp = 5;
	sprite = spr_enemy;
	has_sword = false;
	has_bow = false;
}

function Orc() : Enemy() constructor {
	hp += irandom_range(-1,1);
	name = "Orc";
	mp = 0;
	has_sword = true;
}

We create an Enemy() parent constructor, which has a bunch of variables. Then we create an Orc() constructor, tell it to inherit it’s variables from Enemy using the colon : , and then change the variables we want to change. If we assign a new Orc() to a variable, the resulting struct will still have all the variables from the Enemy() but the ones we changed inside the Orc() constructor will be altered. This means we can have a template for all items as a parent constructor, then maybe a child constructor related to weapons, and a child constructor related to armour and so on, with all the children having the data from the parent, but altering the variables we might want to alter.

This is super useful for proc-gen. For instance, let’s say each time the player started a new game, you wanted to randomly generate some enemies in a list that the player could encounter. We would do as above, then just run a loop a bunch of times, adding a new Orc() to an array each loop and we’ll have a bunch of different orcs stored with slightly varying hp values.

Ok, let’s all take a break for some tea and crumpets and then we’ll dive into the rest of the tutorial.


THE GRID, THE LIST AND THE WARD…I MEAN MAP

For the sake of completeness, I’ll do a brief rundown on the other data structures available to use in GMS. As a sidenote, each data structure has an accessor that allows you to access it with a little less typing, I’ll be showing the accessor way to access them, rather than using the GML function, and this is because using accessors lets you chain together access to structures stored inside of structures, and is also faster to type. If you want to learn about the GML function equivalents, just have a look at the GMS manual.

Grids

You create a grid like this:

my_grid = ds_grid_create(columns,rows);

Let’s say we create a 20×20 grid and want to store a value in the cell at column 10 and row 12, we would do it like this:

my_grid[# 10,12] = 150;

The # is the accessor for a ds_grid, and you can see that we just immediately follow the accessor with the column and row we want to be accessing. Now the cell at column 10, row 12 in my_grid holds the value 150. Let’s say we want to read that value back. Here’s how:

var _cell = my_grid[# 10,12];

Now the temporary variable _cell holds the value 150. Easy stuff. Remember that we can use a 2D array to replicate the behaviour of the grid.

Lists

You create a list like this:

my_list = ds_list();

Now, there’s two ways to access a list depending on what you want to do. You can just push a value onto the end of the list by doing this:

ds_list_add(my_list,15);

This will add a new entry to my_list at the end of the list and that entry will hold the value 15. Alternatively, if you know where you want to store your value, you can use the accessor | like this:

my_list[| 10] = 150;

This will assign the value 150 to the 11th position in the list (why the 11th? Because basically everything in computers starts counting from 0, so there is a 0th position to the list, thus accessing the entry at position 10 in the list is really accessing the 11th entry).

The same goes for reading from a list:

var _entry = my_list[| 10];

The temporary variable _entry will now hold 150. As with grids, remember that we can use a 1D array to replicate the behaviour of a list.

One thing to note about lists is that there are a few different variations to pick from. Also note, while it is possible to replicate the following behaviours using 1D arrays, it will probably be faster in GML to use these native structures, rather than writing a function that emulates them in relation to an array.

You have ds_queue, ds_priority_queue and ds_stack. These all have different functionality from a list, usually related to the fact that you can’t necessarily read all the entries like you could in the list. Rather, you want your data to flow in and out of the structure in a specific order. Let’s quickly go over them. We’ll pretend that there’s a variable called value that holds some data and we’ll use that for each of them.

ds_queue is FIFO or first in first out (in the same way a queue works in the real world). Create the queue with:

my_queue = ds_queue_create();

Push a value into the queue using:

ds_queue_enqueue(my_queue,value);

Then, you read the data from the queue like this:

my_data = ds_queue_dequeue(my_queue);

ds_queue_dequeue will return the first value that was pushed into the queue and then remove that entry from the queue, so the next time it’s called, it will return the second value that was pushed into the queue and remove that entry, and so on. You can also use ds_queue_head(my_queue) and ds_queue_tail(my_queue) to read the first and last entry of the queue.

ds_stack is FILO, or first in, last out. We create a stack using:

my_stack = ds_stack_create();

Then we push a value onto the stack like this:

ds_stack_push(my_stack,value);
ds_stack_push(my_stack,value2);
ds_stack_push(my_stack,value3);

We’ve pushed three different values onto the stack, so when we use:

var _entry = ds_stack_pop(my_stack);

_entry will end up holding value3 and value3 will be removed from the stack. Then if we pop it again:

var _entry = ds_stack_pop(my_stack);

We will get value2 back and so on. We can also simply read the top of the stack without removing the entry using ds_stack_top().

Finally, we have priority queues, which are like queues, except when we add something to the queue, we also add a “priority” (which is just a number) and the queue is ordered by that priority, and we can then check either the minimum priority or the maximum priority. We create one like this:

my_priority = ds_priority_create();

We add to the priority queue like this:

ds_priority_add(my_priority,value,1);
ds_priority_add(my_priority,value2,2);

This would add two new entries, with a priority of 1 and 2 respectively. And then we can either find the min/max values like this:

var _min = ds_priority_find_min(my_priority);
var _max = ds_priority_find_max(my_priority);

In this case, _min would end up holding value, while _max would end up holding value2 (because we added value with a priority of 1 and that’s lower than the priority of 2 we gave value2). If we want to remove the values from the priority queue after reading them, we would instead do this:

var _min = ds_priority_delete_min(my_priority);

Here, _min would end up holding value, and the only entry left in the priority queue would be value2.

Priority queues are one of the more useful list style structures. For instance, if you are writing an A* pathfinding algorithm, you could use the Manhattan distance for each cell as the priority as you add the cell to the priority queue, which would mean you can easily grab the cell with the lowest Manhattan distance to your target when you needed it. You could also add all of your AI behaviours to a priority queue and adjust the priority for each behaviour according to what is happening to the AI at the time, running whatever behaviour has the max priority at the time. There’s lots of different applications (in fact, all of these structures can be quite useful in particular situations).

Maps

Finally, we come to maps. Since we haven’t touched on maps at all yet, I want to point out that maps and structs are roughly equivalent. There are multiple reasons to use structs over maps nowadays, but they both exhibit roughly the same behaviour.

We create a map like this:

my_map = ds_map_create();

Now maps use what is known as a “key” to indicate where to store data. As an explanation of what a key is – when we think of a list, we think of each entry like this:

  1. value
  2. value2
  3. value3

Each entry has a position and a value, and we can use the positions to pull out certain values. Maps, while not being ordered in the same way as a list, use the same concept, except that each “position” in the map is actually the “key”. Keys are usually strings, but you can use numbers for them if you want (I believe GMS converts numbers to a string under the hood though, which means that using a number as a key might be slower than using a string). We refer to a key in order to insert or pull out data from the map. Let’s look at how to do that:

my_map[? "hp"] = 100;
my_map[? "sprite"] = spr_player;
my_map[? "weapon"] = WEAPONS.PISTOL;

The accessor for the map is ? followed by the key, and here we’ve inserted three entries, under the keys "hp", "sprite" and "weapon". If we wanted to read what is under the key "hp", we would simply do this:

health = my_map[? "hp"];

The health variable would end up holding the value 100 here. When we think of structs and maps, we can think of the struct as the map itself, and each variable we store in the struct is like a key inside a map, and visa versa.


THE NEXT STEP

Well, for some reason I was expecting this to be a short little rundown of the structures, but it grew into a giant behemoth of a post. I just wanted to make sure that everyone is on the same page for the future posts, whether or not you are a complete beginner or a seasoned veteran.

Now that we’ve got that out of the way, I’m not 100% sure what the next entry will be about, but I’m kind of feeling like we might do a run-down on Bresenham’s line algorithm (which has a number of useful applications in proc-gen), or perhaps we might properly start diving into some proper proc-gen with a dungeon generated with cellular automata, or room perturbation, or any number of other things. Let me know what you folks would like to focus on below.

Read on with #3: Cellular Automata


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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s