All Alchementalogs
Table of Contents
Previously
We just got done adding in the ore generation to the map in the last entry, which is swell and all, but I had a mighty hankering for the ore veins to make physical sense as you ventured deeper and deeper into the mine. This means that each floor of ore should extend from the floor previously and into the floor below cohesively. But how do we do that with a 2D cellular automata algorithm? The answer is to change the algorithm into 3D. This naturally comes with a few extra road blocks, but we’ll tackle them as they come.
So let’s get into it. But before we do, I just want to make it extra special clear: The 3D stuff shown here is not how Alchementalist is going to look graphically, it’s a visualisation tool helping me to see that the cellular automata is functioning correctly. Alchementalist is still going to be fully 2D.
Close Encounters of the 3D Kind
Let’s have a look at the current implementation of our 2D cellular automata algorithm:
///@func CountNeighbours(x,y,map);
///@param x The current cell's x position
///@param y The current cell's y position
///@param map The current map
function CountNeighbours(x,y,_map) { // We input the x (or column) and y (or row) of the cell we want to access, as well as the map we are using
var _count = 0; // This will keep track of how many neighbours are solid
for (var dx=-1;dx<2;dx++) {
for (var dy=-1;dy<2;dy++) { // Double for loop again, but this time a variant explained below
var xx = x+dx; // Get the x position of the neighbour cell
var yy = y+dy; // Get the y position of the neighbour cell
if (xx < 0 || yy < 0 || xx >= map_width || yy >= map_height) { // If the neighbour cell we are trying to check is out of bounds
/* We have two choices here: either act as though any neighbours outside of the
grid are SOLID or act as though they are EMPTY. The cellular automata will behave
differently depending on which we choose. I've chosen to act as though they are
SOLID */
if (inclusive_border) {
_count++; // Add to count because we decided to act as though out of bounds cells are SOLID
}
continue;
}
var _neighbour = _map[xx][yy]; // Get the value of the neighbour cell
if (_neighbour == SOLID) { // If the value of the neighbour is SOLID
_count++; // Add to the solid count
}
}
}
return _count; // Finally, return the SOLID count
}
///@func RunCellularAutomata(map_width,map_height,spawn_chance,create_limit,destroy_limit,iterations,inc_borders);
///@param {int} map_width The width of the map
///@param {int} map_height The height of the map
///@param {real} spawn_chance The chance a cell is turned SOLID
///@param {int} create_limit The neighbour count that will turn an EMPTY cell SOLID
///@param {int} destroy_limit The neighbour count that will turn a SOLID cell EMPTY
///@param {int} iterations The number of iterations we want to perform on the map
///@param {bool} inc_borders Whether the borders are inclusive or not
function RunCellularAutomata(_map_width,_map_height,_map_style,_spawn_chance,_create_limit,_destroy_limit,_iterations,_inc_borders) {
map_width = _map_width;
map_height = _map_height;
map_style = _map_style;
inclusive_border = _inc_borders == undefined ? true : _inc_borders;
check_size = _check_size == undefined ? 0 : _check_size;
spawn_chance = _spawn_chance;
///@func CreateMap();
static CreateMap = function() {
var _map = array_create(map_width); // Create a temporary variable to hold our 2D array
var i = 0;
repeat(map_width) {
var j = 0;
repeat (map_height) {
var _roll = random(100);
var val = EMPTY;
if (_roll <= spawn_chance) {
val = SOLID;
}
_map[i][j++] = val;
}
++i;
}
return _map; // Return the 2D array
}
///@func Iterations(old_map,create_limit,destroy_limit);
///@param old_map The map as it currently stands
///@param create_limit The neighbour count that will turn an EMPTY cell SOLID
///@param destroy_limit The neighbour count that will turn a SOLID cell EMPTY
static Iterations = function(_old_map,_create_limit,_destroy_limit) { // Pass in the currently existing map
var _new_map = array_create(map_width); // Create a temporary variable to hold our 2D array
var i = 0;
repeat(map_width) {
_new_map[i++] = array_create(map_height,EMPTY);
}
for (var xx=0;xx<map_width;xx++) {
for (var yy=0;yy<map_height;yy++) {
var _count = CountNeighbours(xx,yy,_old_map); // Check how many SOLID neighbours the current cell has on the old map
/* Normally we would have be setting the new map to either EMPTY or SOLID below, but since we already set each cell to EMPTY when
creating the map, we can simply run the checks that will turn the cell SOLID and ignore the EMPTY checks */
switch (map_style) {
case map_styles.CAVE:
if (_old_map[xx][yy] == SOLID) { // If the old map cell is SOLID
if (_count >= _destroy_limit) { // If the SOLID neighbour count is greater than the "underpopulation" limit
_new_map[xx][yy] = SOLID; // Set the corresponding cell on the new map to SOLID
}
}
else { // If the old map cell is EMPTY
if (_count > _create_limit) { // If the neighbour count is greater that the "birth" limit
_new_map[xx][yy] = SOLID; // Mark the corresponding cell on the new map to SOLID
}
}
break;
case map_styles.ROOM:
if (_old_map[xx][yy] == SOLID) { // If the old map cell is SOLID
if (_count < _destroy_limit) { //If the SOLID neighbour count is less than the "underpopulation" limit
_new_map[xx][yy] = SOLID; // Set the corresponding cell on the new map to EMPTY
}
}
else { // If the old map cell is EMPTY
if (_count >= _create_limit) { // If the neighbour count is greater that the "birth" limit
_new_map[xx][yy] = SOLID; // Mark the corresponding cell on the new map to SOLID
}
}
break;
}
}
}
return _new_map;
}
var _ca_map = CreateMap();
var i = 0;
repeat(_iterations) {
_ca_map = Iterations(_ca_map,_create_limit,_destroy_limit);
++i;
}
return _ca_map;
}
Ok, a bit of a chunky little boi for display on a website, but there’s three main points to go over. First, we start off with a little function called CountNeighbours() that does what it says on the tin, it counts how many of the neighbours of the supplied cell are marked as SOLID. A vital part of the cellular automata algorithm.
Then we get into the real meat of the algorithm with the function called RunCellularAutomata(). This does the bulk of the work, first creating a randomised map with the CreateMap() function and then iterating over it to make cellular automata do it’s spicy thing with the Iterations() function.
Note: Read more about creating 2D cellular automata in GMS here - Procedural Generation in GMS #3: Creating Sweet Maps with Cellular Automata
The really important point of interest here is that we are only ever dealing with width and height (and x and y), which is what makes this a 2D cellular automata. What we need to do is streeeeetch this out into the third dimension.
To do this is conceptually simple. We need to add another dimension to our map array of size depth, which we will refer to using the standard terminology of z. So let’s have a look at what that means for the above code.
Note: The below code is very much a proof of concept, which was written to run on timers to make it visually understandable what was happening, and I will be refactoring it later on in order to actually squeeze it into a proper "load" of the generator (in fact, this is true of all the code I've written for the generator so far, as I've been writing it with visualisation in mind for this devlog series, so none of it is optimised for a real "load" yet). Also, because it's just the way I did it, the z axis comes first, instead of the standard x, y, z used by most other 3D stuff.
///@func CountNeighbours3D(z,x,y,map);
///@param z The current cell's z position
///@param x The current cell's x position
///@param y The current cell's y position
///@param map The current map
function CountNeighbours3D(z,x,y,_map) {
var _count = 0; // This will keep track of how many neighbours are solid
for (var dz=-1;dz<2;dz++) {
for (var dx=-1;dx<2;dx++) {
for (var dy=-1;dy<2;dy++) { // A triple for loop this time, to account for the extra depth dimension
var zz = z+dz; // Get the z position of the neighbour cell
var xx = x+dx; // Get the x position of the neighbour cell
var yy = y+dy; // Get the y position of the neighbour cell
if ((zz < 0 || xx < 0 || yy < 0 || xx >= map_width || yy >= map_height) && zz < map_depth) { // If the neighbour cell we are trying to check is out of bounds
continue;
}
else if (zz >= map_depth) { // This makes sure the deepest layer is properly populated with ore
var roll = random(100);
if (roll < 50) {
_count++;
}
continue;
}
var _neighbour = _map[zz][xx][yy]; // Get the value of the neighbour cell
if (_neighbour == SOLID) { // If the value of the neighbour is SOLID
_count++; // Add to the solid count
}
}
}
}
return _count; // Finally, return the SOLID count
}
// Create the randomised map (adding instances as we go for the display)
cell_map = array_create(map_depth,EMPTY);
inst_map = array_create(map_depth,EMPTY);
var i = 0;
repeat (map_depth) {
cell_map[i] = array_create(map_width,EMPTY);
inst_map[i] = array_create(map_width,EMPTY);
var j = 0;
repeat (map_width) {
var k = 0;
cell_map[i][j] = array_create(map_height,EMPTY);
inst_map[i][j] = array_create(map_height,EMPTY);
repeat (map_height) {
var roll = random(100);
if (roll <= my_spawn_chance) {
val = SOLID;
cell_map[i][j][k] = val;
var inst = instance_create_depth(j*CELLSIZE,k*CELLSIZE,(i+5)*(CELLSIZE),obj_cell);
inst_map[i][j][k++] = inst;
}
}
++j;
}
++i;
}
// Do my_iterations number of cellular automata iterations on the map, this runs on a timer to visually show what is going on, rather than a true loop
if (iter < my_iterations) {
var _new_map = array_create(map_depth);
var i = 0;
repeat (map_depth) {
_new_map[i] = array_create(map_width,EMPTY);
var j = 0;
repeat (map_width) {
_new_map[i][j++] = array_create(map_height,EMPTY);
}
++i;
}
for (var zz=0;zz<map_depth;zz++) {
for (var xx=0;xx<map_width;xx++) {
for (var yy=0;yy<map_height;yy++) {
var _count = CountNeighbours3D(zz,xx,yy,cell_map); // Check how many SOLID neighbours the current cell has on the old map
if (cell_map[zz][xx][yy] == SOLID) { // If the old map cell is SOLID
if (_count < my_death_limit) { // If the SOLID neighbour count is less that the "underpopulation" limit
if (inst_map[zz][xx][yy] != EMPTY) {
instance_destroy(inst_map[zz][xx][yy]);
}
}
else { // Otherwiise if the SOLID neighbour count is greater than the "underpopulation" limit
_new_map[zz][xx][yy] = SOLID; // Set the corresponding cell on the new map to SOLID
if (inst_map[zz][xx][yy] == EMPTY) {
var inst = instance_create_depth(xx*CELLSIZE,yy*CELLSIZE,(zz+5)*(CELLSIZE),obj_cell);
inst_map[zz][xx][yy] = inst;
}
}
}
else { // If the old map cell is EMPTY
if (_count > my_birth_limit) { // If the neighbour count is greater that the "birth" limit
_new_map[zz][xx][yy] = SOLID; // Mark the corresponding cell on the new map to SOLID
if (inst_map[zz][xx][yy] == EMPTY) {
var inst = instance_create_depth(xx*CELLSIZE,yy*CELLSIZE,(zz+5)*(CELLSIZE),obj_cell);
inst_map[zz][xx][yy] = inst;
}
}
else { // Otherwise
if (inst_map[zz][xx][yy] != EMPTY) {
instance_destroy(inst_map[zz][xx][yy]);
}
}
}
}
}
}
cell_map = _new_map;
alarm[0] = 1;
iter++;
load_text = "CA Iteration "+string(iter);
}
So, ignoring the fact that the code is written for visualisation and not optimised for real generation, we can see that the CountNeighbours3D() function now checks along the z axis, as well as the x and y axes. I’ve also got a funny little thing going on here:
else if (zz >= map_depth) {
var roll = random(100);
if (roll < 50) {
_count++;
}
continue;
}
This is done because I want the deepest layer of the map to have as much ore as the layer above it (which requires it to act as though the non-existent layer deeper than it has some SOLID cells), but I also want the shallowest layer to have less ore than the other layers, which requires it to act as though the non-existent layer above it is EMPTY. If that makes sense? Basically without the above code the deepest and the shallowest layer both get gimped in ore deposits…With the incorporation of the codeblock above, only the shallowest layer gets gimped.
Then we move onto the main body of the automata, which isn’t a function yet (but will be when future me gets around to it). In it, we are creating an array three layers deep, instead of two and then we are basically running the same iteration routine as the 2D automata, but obviously including that third layer.
We’re Gonna Need A Bigger Boat
Whew, the code is out of the way. Awesome, I now have a 3D cellular automata going and it’s not throwing any errors. But how can I see if it’s doing its thing properly? Swapping between layers in 2D kind of works, but it’s not the best way to visualise a 3D structure. So I’ve got to build a little 3D world that can let me see how the automata looks in all its glorious dimensions. Fun!
I’ve never touched anything 3D before. 2D games are my jam and I’ve been very happy splashing around in the shallow end of the pool without feeling any deep aching need to pop an extra dimension in my pants. But here’s a chance to learn something new and I’m always down for that. However, I don’t want to spend ages trying to craft a perfect 3D world for this thing, I am trying to make a game after all. I just need the bare-bones to be able to properly visualise my little cellular baby.
The first thing I did was get stuck into some research. Let’s see how other people using GMS2 deal with 3D elements. As I surfed the breakers across the web, I came across this video by Matharoo: From 2D to 2.5D: GameMaker Studio 2 TUTORIAL (Using 3D Camera) | Easy Parallax. It definitely seemed promising, and it’s not introducing many elements that I’m not already at least passingly familiar with. So let’s give it a go.
Note: Matharoo is an awesome member of the GMS2 community who I've had the pleasure of interacting with on many occasions. He also (relatively) recently got hired as the Technical Writer for YoYo Games and does a lot of awesome tutorial work. If you're reading this Matharoo, hope you're liking the job!
So I watched the video. This is definitely it. It’s super quick to implement, let’s me use stuff I’m already familiar with and the outcome is exactly what I was looking for.
It took me a little while to get comfortable manipulating the camera in the 3rd dimension, but with a little hacky code, I got it working well enough that I could drift around and look at the cellular automata from anywhere I wanted. So, without further ado, here’s the final result:
Man that feels good to watch. There’s nothing like sculpting 1’s and 0’s with your bare hands.
The cellular automation takes a bit of time (GML doing heavier proc-gen is slooow, although I do need to tighten up the code), but once it’s generated, you can see each individual “layer” of blocks, with anything on the same plane corresponding to a tile on the floor of whatever level you are on in the Alchementalist mine. The colours that pop in are flood-filled “chunks” of connected ore that are being assigned a specific ore type (like what was done in the last blog entry). Red is fire, blue is water, grey-blue is wind and green is earth.
It’s immediately clear as the structure builds itself that the cellular automata is functioning correctly, at least if you’ve seen enough of the 2D algorithm running before. The ore is nicely spaced out across the entirety of the map and makes sense as “veins” running deeper into the layers. I haven’t gotten around to combining the 3D cellular auto with the normal map generation yet (as I still haven’t altered the normal map generation to create extra layers), but I see no reason why I can’t slot this structure easily into the game map.
The Why of Fry
Of course, one might argue what is the point of all this? The user won’t care if the generated ore makes sense between levels, they probably won’t even notice…
This may be true, but I have a few counterpoints.
- It’s my game and I do what I want!
- As game developers, we are creatives, especially when working solo and having to wear many, many hats. I think the best creative works come from people with strong, clear visions of what they want. Details like this are things I want in the game as they help me express my vision.
- This shit is fun. Like really really fun. Solving the problem of adding a 3rd dimension to my generation and then having to solve the problem of visualising that 3rd dimension was an exciting journey through code. Each time something clicked together just right, BOOM! A burst of dopamine. Details like this help keep me engaged and motivated.
So this has been a pretty big post but I wanted to go a little bit deeper with this one, as I thought it was both interesting and pretty. The next devlog will be returning to our regularly scheduled 2D programming. Probably something to do with lighting. Au revoir!
Oh, before you go, don’t forget to wishlist and follow Alchementalist on Steam!
RefresherTowel Games 