Categories
alchementalist alchementalist devlog Games

Alchementalog #8: Do It Again, But This Time In 3D

In which we add some depth to the ore generation in Alchementalist.

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.

  1. It’s my game and I do what I want!
  2. 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.
  3. 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!

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