ARRAY / BIT-WISE COLLISION

Array & Bit-wise collision, GMS2 TUTORIALS

Difficulty (6/10 chillies)

🌶️🌶️🌶️🌶️🌶️🌶️

Introduction

This system has ONE object for the level. All the blocks you can interact and collide with are values in an array. The amazing thing about this is you can load, save and use random generation to fill out this array. (generating a level!). Doing that is the easy part, collision is the hard part, that’s why I’m here!


the why

You may be asking “why do I need this system?” And its a good question. When building a game like Mincraft, Terraria, Spelunky and many others, there’s a problem that you will run into when loading and saving levels, as well as randomly generating levels. You only get this problem if you base your collision system on objects. Loading and saving objects is not only slow (when done in masses), but you have to build a big complex system that checks the objects positions, and converts that to a data structure just so you can save levels. If you have random generation or you want to load a level you have to do the same thing but backwards! THIS SUCKS. Its frustrating and unnecessary.

WHY don’t you cut out the middle man and just skip having objects for your terrain and collision system? WELL NOW YOU CAN.



NUMBER THEORY 

If you understand binary number theory you can skip to THE TUTORIALheader if not..
Something simple to start it off, numbers! This is the most basic theory of binary, how numbers are stored and how they are created.

00000000 = 0
00000001 = 1 
00000010 = 2
00000100 = 4

Each 0 or 1 that we have here are a ‘bit’, a piece of data. Each bit is 2 times the value of its previous bits value, what does this mean? Well, if we follow this rule of times 2 then 1000 would be the value 0100 but times 2. And we know that 0100 equal to 4, so 1000 must be equal to 8!

This is awesome if we are only using numbers that have a power of 2, but what if we want to create more interesting numbers like 69? Good news! We can combine our bytes to make any number we want, as an example. (A byte is a collection of 8 bits).

00000000 = 0
00000001 = 1
00000010 = 2
00000011 = 3
00000100 = 4
00000101 = 5

So if we wanted to create the number 69, we would do this by breaking down what numbers we can fit into our ‘byte’ that’s lower than 69.

The highest single bit number that there is in a byte is 128 (shown as 10000000). 128 does not fit into 69, so the next smallest number in our byte would be half of 128, 64 (shown as 01000000).

So our byte is looking like;

01000000 = 64 

Now we need to find the next bit value that will fit into 5, as that’s how much we need to make 69. (69 – 64 = 5). We know how to make 5 with 00000100 and 00000001, so if we add everything together;

01000000 = 64
00000100 = 4
00000001 = 1

Adding them together we get

01000101 = 69 

TRUTH TABLES

Now how can we manipulate these bits to create faster functions for our projects? With operators! We can use | (or) and the & (and). Both of these operators have a truth table.

OR

00 | 00 = 00
00 | 01 = 01
01 | 00 = 01
01 | 01 = 01

As an example using the OR operator we could toggle our bytes like this;

01001010  OR
11001101  =
11001111

AND

00 & 00 = 00
00 & 01 = 00
01 & 00 = 00
01 & 01 = 01

As an example using the AND operator we could merge our bytes like this;

01001010  AND
11001101  =
01001000

These truth tables are the rules that we use to manipulate our bytes. 

The cool thing about bytes is that it has 8 true or false bits in them. This means you can check multiple ‘flags’ (flag being a bit) at once. 


BIT shifting

Bit shifting just like its name allows us to ‘shift’ bits left and right. Why do we need to know this? Well just like the other operators they’re very useful and will be one of the most used operators in the tutorial!

As an example lets say we have a grid that’s our rooms length and width, and the cells size for this grid is 32×32 pixels. What if we want to know what cell the player is currently in? how would we do it? There’s actually two options!

Option 1

var _xpos = floor(x / 32);

With this option we have to divide the x by the cell size, the problem is that we then have to get rid of the decimal points if we want to use this value in something like an array.

Option 2

var _xpos = (x >> 5); //Bit shifting

This option is using bit shifting. It bit shifts all our bits down by 5, this means that any value that’s less then 32 is discarded giving us a whole number.

So I’ll show you how this works! Lets say the players x is 185. If the cell size is 32 pixels wide, then we want to shift the bits to the right to remove any bits under the value 32. Because 32 in binary is 00100000, we want to get rid of the 5 bits to the right of it (those bits been 16, 8, 4, 2, 1 ).

x >> 5 = 10111001 >> 5

shifting the bits over by 5

00000101

So now we are left with the value 5, that’s how ‘simple’ it is! we can also bit shift to the left with <<, it works the same as shifting to the right but it would be like multiplication instead of dividing.

Later in the tutorial I’ll show you how we use these operators to check what tile we can or can’t collide with. It’s important you wrap your head around the basics of the number theory and the operators as it will make the rest of the tutorial easier. If you want, pick a number below 255 and see if you can convert it to its byte value, then bit shift it down by a number between 1 and 7!

Also if you want to learn more Game Maker has documentation on how to use these functions as well! Here it is!


THE TUTORIAL

The Level

Finally were at the part when we get to build something!
The first thing we are going to do is create two objects, one being the player and the other being the object that holds the level array.

First were going to start with the level object we want to set our
– Cell size
– Array size
– Array that holds the level
– Bit-shift amount
– Enum for our cell types
– Names for the cell types
– Create a floor so the player doesn’t fall through
In the create event of the level object.

#macro BITSHIFT 5
#macro CELLSIZE 1 << BITSHIFT
world = ds_grid_create(room_width >> BITSHIFT, room_height >> BITSHIFT);
ds_grid_clear(world, cell.air);		
enum cell {
	air,
	wall,
	water
}

cellName[cell.air]	= "Air";
cellName[cell.wall]	= "Wall";
cellName[cell.water]	= "Water";
lineAlpha = 1;

for (var i = 0; i < room_width >> BITSHIFT; ++i) {
    world[# i, (room_height >> BITSHIFT) - 1] = cell.wall
}

Because the 5th bit is 32 we can use the MACRO we made to set the cell size to 32, but also whenever we need to bit-shift we can use it as well. This means that means if you want to change the cell size all you have to do is change BITSHIFT and the system will resize everything for you!

Next were going to draw the grid in the room, this is more of a debug tool and can easily be hidden by pressing tab.

This is in the draw event of the level object

lineAlpha ^= keyboard_check_pressed(vk_tab);
draw_set_alpha(lineAlpha * 0.1);
for (var i = 0; i < room_width >> BITSHIFT; ++i) {
	draw_line(0 + (i * CELLSIZE), 0, 0 + (i * CELLSIZE), room_height);
}
for (var i = 0; i < room_height >> BITSHIFT; ++i) {
	draw_line(0, 0 + (i * CELLSIZE), room_width, 0 + (i * CELLSIZE));
}
draw_set_alpha(1);

And this is what i should look like.

Because we used the macros, our cell size and bit shifting amount is all automatic and can be changed easily in the create event!

Building a level

Next because we can make our level in the room editor, we are not going to make a whole level generator for this tutorial, so we can make a inbuilt level maker instead ! To do this we have to find what cell the mouse x and mouse y are in. We also want to clamp that value so if our mouse goes off screen the game wont crash. (If the mouse x is greater then the rooms size, then the value returned will be greater then our array length and might crash the game!) We also want to select what cell type we want to place when building the level.

You have two options when doing this, the first is to create a level editor object, or you can put it in the level object with the world array. I’m going to create a new object so its easy to remove or edit later.

I’m going to add some variables to the create event of the new level editor object.

selected = cell.wall; 

And now I’m going to add this to the begin step even in the new level editor object.

var _mx = clamp(mouse_x >> BITSHIFT, 0, room_width >> BITSHIFT); // Bit shifting the mouse's x
var _my = clamp(mouse_y >> BITSHIFT, 0, room_width >> BITSHIFT); // bit shifting the mouse's y

if (mouse_check_button_pressed(mb_left)) {
	oLevel.world[# _mx, _my] = selected;
}

Next we want to be able to scroll through our cell types to select what one we place. We can do this by clamping the selected variable to 0 and the amount of cell names. We can also make it so we scroll to change the selected cell type. (in the begin step even as well.)

selected += mouse_wheel_down() - mouse_wheel_up()
selected = clamp(selected , 0, array_length_1d(oLevel.cellName) -1);

Now we need to know what we have selected, to do this we go to the draw event of our level editor and draw the cell name at the x and y of the mouse. (draw event of level editor object.)

draw_text(mouse_x + 16, mouse_y, "Cell: " + oLevel.cellName[selected]);

Drawing the level

We also need to draw the cells hat have been made a wall, to do this we can use a switch event and draw rectangle, or if you want you can draw a sprite. This draws by looping though each cell, checking what the value is, then drawing based on the value. This is in the draw event of our level object.

for (var i = 0; i < room_width >> BITSHIFT; ++i) {
    for (var j = 0; j < room_height >> BITSHIFT; ++j) {
		switch (world[# i, j]) {
		    case cell.air:
		        // draw nothing here
		        break;
		    case cell.wall:
		        draw_rectangle(i * CELLSIZE, 
					(j * CELLSIZE), 
					((i + 1) * CELLSIZE) - 1, 
					((j + 1) * CELLSIZE) - 1, 
					(true));
		        break;
                    case cell.water:
		        draw_rectangle_colour(i * CELLSIZE, 
					(j * CELLSIZE), 
					((i + 1) * CELLSIZE) - 1, 
					((j + 1) * CELLSIZE) - 1, 
					c_blue, c_blue, c_blue, c_blue,
					(false));
		        break;
                    default:
		        // code here
		        break;
		}
	}
}

You should have something like this!


Scripts

Before we make the players movement and collision checks we need to make a script that the player object will use. The script will be called ‘check’.

///@description check(int);
///@argument block
var _check = 1;
if (argument0 != 0) {
	return(_check << clamp(argument0 - 1, 0, 99));
} else {return(argument0)}

We use this script later in the tutorial, but what it does is convert the cell ids we’ve made from there default value. In the cell enum we made the values will be given a number based on its position in the enum. So…
air = 0
wall = 1
water = 2
But if we add another value it will be equal to 3, then 4 then 5 and so on. The problem is when we go to check for collisions, if the cell has a value of 5 (00000101) that’s actually the same as checking for id’s 1 (wall) and whatever the id of 4 is.
This script will convert the number 5 (00000101) into a single bit value with the 5th bit true ( 00010000). This means we can input this value to our collision system and it will correctly check what we want to collide with.


the player

Building the player is the tricky part of the tutorial, but where going to start with something simple. To start off we are going to set all our player variables.
Do this in the create event.

playerWidth = 16;  // players hit box width
playerHeight = 28; // player hit box height

hspd = 0; // horizontal speed
vspd = 0; // vertical speed
maxSpeed = 2;
grav = 0.7;
jumpSpd = 9;
onground = true;

We also want to create a set of variables to check what we want to collide with in each direction using the check script.

colCheckLeft	= check(cell.wall);
colCheckRight	= check(cell.wall);
colCheckUp	= check(cell.wall);
colCheckDown	= check(cell.wall);

If we want to check for another cell type we can just OR ( | ). Like this

colCheckLeft = check(cell.wall) | check(cell.doorClosed);

Its the same as doing

00000001 | 0000100 = 00000101

Because we’re not using the normal place_free method for collision checking, we have to create our own hit box. Because we are checking set values in our collision check (x and y) we have to check all four corners of the hit box.

We can set and update our corner variables values each frame; and we do this by getting our x or y, then removing or adding half the hit box size. This means that x and y will always be the middle of our hit box.
We do this in the begin step eventwe do this in the begin step event so it always updates before we do any other movement code, this helps remove some update bugs we could run into.

playerX1 = x - (playerWidth / 2);
playerY1 = y - (playerHeight / 2);
playerX2 = x + (playerWidth / 2);
playerY2 = y + (playerHeight / 2);

Now we add some simple player movement, because I’m building a platformer i only need to move left and right, as well have gravity.
We do this in the step event.

hspd = (keyboard_check_direct(vk_right) - keyboard_check_direct(vk_left)) * maxSpeed;
if (keyboard_check_pressed(vk_space) && onground) {
	vspd -= jumpSpd;
	onground = false;
}
vspd += grav;

keyboard_check returns true or false, because true or false is actually a 1 or 0 we can use this to figure out what way to move.

hspd = (1 - 0) * 2; // 2 to the right.
hspd = (0 - 1) * 2; // -2 to the left

Now that we have the movement speeds set up we can move on to collision. After the collision is set up we can then update the players position, we have to do this later in the tutorial as the way we move the player is kind of interesting.

Set up for collision

This is the tricky part, i’m going to put links you can click to go back and re-read parts of the number theory.

The first thing we need to do is create some new local variables. If you remember from the number theory part of this blog we went over how bit-shifting works. We need two sets of variables;
One that’s the current players hit-box positions,

var playerCurX1 = (playerX1) >> BITSHIFT;
var playerCurY1 = (playerY1) >> BITSHIFT;
var playerCurX2 = (playerX2) >> BITSHIFT;
var playerCurY2 = (playerY2) >> BITSHIFT;

And one that’s the players hit-box position with its speed added.

var playerNewX1 = (playerX1 + ceil(hspd)) >> BITSHIFT;
var playerNewY1 = (playerY1 + ceil(vspd)) >> BITSHIFT; 
var playerNewX2 = (playerX2 + ceil(hspd)) >> BITSHIFT;
var playerNewY2 = (playerY2 + ceil(vspd)) >> BITSHIFT;

We have to round off the speed of the player so that we don’t have decimal points. We round up because if we rounded down, we might be moving but the variables wont show it. (rounded to 0.)

Both these sets of variables will return what cell the player is currently in, and what cell the layer would be in if they had moved.

check for collision

So now we need to build the collision checks the first check we are going to do is check for collisions to the left. Using these four local variables we can hold the value of the cell that we are checking.

var _o = oLevel;        // _o is now shorthand for oLevel, makes it easier to type.
var _leftcheck1		= _o.world[# playerCurX1, playerCurY1]; // top left
var _leftcheck2		= _o.world[# playerCurX1, playerCurY2]; // bot left
var _leftcheckSpd1	= _o.world[# playerNewX1, playerCurY1]; // top left with speed
var _leftcheckSpd2	= _o.world[# playerNewX1, playerCurY2]; // bot left with speed

Now using those variables we can choose how the player moves, with this code here!

if (hspd < 0 ) {
	if ((check(_leftcheckSpd1) | check(_leftcheckSpd2)) & colCheckLeft != 0) {
		hspd = 0;
		playerX1 = (playerNewX1 + 1) << BITSHIFT;
		playerX2 = playerX1 + (playerWidth);
	} else {
		if ((check(_leftcheck1) | check(_leftcheck2)) & colCheckLeft != 0) {
			hspd = 0;
			playerX1 = (playerCurX1 + 1) << BITSHIFT;
			playerX2 = playerX1 + (playerWidth);
		} else {
			playerX1 += hspd;
			playerX2 += hspd;
		}
	}
}

So whats going on here? I’ll break it down for you.

  1. Check of we are moving to the left.
  2. OR |’ our cell checks together, then ‘AND &’ with the collision check variable.
  3. If we CANT move because there’s a cell in the way we.
    • set hspd to 0.
    • move the player so they are inline with the wall they would have gone into.
    • update the players x hitbox.
  4. If we CAN move, check if we are inside a cell. If we are.
    • set hspd to 0.
    • kick the player out of the block.
    • update the players x hitbox .
  5. If we can move and the players not in a cell, we move the players collision box by the hspd.

And that’s the collision for the left side done! For the other 3 side its almost the exact same. But we have to update all the variables for checking the cells.
I’ll give you the code as it can get frustrating just copy and pasting the same code then working out what variables need to be changed.

var _rightcheck1	= _o.world[# playerCurX2, playerCurY1];
var _rightcheck2	= _o.world[# playerCurX2, playerCurY2];
var _rightcheckSpd1	= _o.world[# playerNewX2, playerCurY1];
var _rightcheckSpd2	= _o.world[# playerNewX2, playerCurY2];

if (hspd > 0 ) {
	if ((check(_rightcheckSpd1) | check(_rightcheckSpd2)) & colCheckRight != 0) {
		hspd = 0;
		playerX2 = ((playerNewX2) << BITSHIFT) - 1;
		playerX1 = playerX2 - (playerWidth);
	} else {
		if ((check(_rightcheck1) | check(_rightcheck2)) & colCheckRight != 0) {
			hspd = 0;
			playerX2 = ((playerCurX2) << BITSHIFT) - 1;
			playerX1 = playerX2 - (playerWidth);
		} else {
			playerX1 += hspd;
			playerX2 += hspd;
		}
	}	
}

var _upcheck1	= _o.world[# playerCurX1, playerCurY1]
var _upcheck2	= _o.world[# playerCurX2, playerCurY1]
var _upcheckSpd1	= _o.world[# playerCurX1, playerNewY1];
var _upcheckSpd2	= _o.world[# playerCurX2, playerNewY1];

if (vspd < 0 ) {
   if ((check(_upcheckSpd1) | check(_upcheckSpd2)) & colCheckUp = !0) {
		vspd = 0;
		playerY1 = (playerNewY1 + 1) << BITSHIFT;
		playerY2 = playerY1 + (playerHeight);
	} else {
		if ((check(_upcheck1) | check(_upcheck2)) & colCheckUp = !0) {
			vspd = 0;
			playerY1 = (playerCurY1 + 1) << BITSHIFT;
			playerY2 = playerY1 + (playerHeight);
		} else {
			playerY1 += vspd;
			playerY2 += vspd;
		}
	}
}

var _downcheck1		= _o.world[# playerCurX1, playerCurY2]
var _downcheck2		= _o.world[# playerCurX2, playerCurY2]
var _downcheckSpd1	= _o.world[# playerCurX1, playerNewY2]
var _downcheckSpd2	= _o.world[# playerCurX2, playerNewY2]

if (vspd > 0 ) {
   if ((check(_downcheckSpd1) | check(_downcheckSpd2)) & colCheckDown != 0) {
		vspd = 0;
		playerY2 = ((playerNewY1 + 1) << BITSHIFT) - 1;
		playerY1 = playerY2 - (playerHeight);
		onground = true;
	} else {
		if ((check(_downcheck1) | check(_downcheck2)) & colCheckDown = !0) {
			vspd = 0;
			playerY2 = ((playerCurY1 - 1) << BITSHIFT) - 1;
			playerY1 = playerY2 - (playerWidth);
			onground = true;
		} else {
			playerY1 += vspd;
			playerY2 += vspd;
		}
	}
}

Note that i added the on ground variable when the vertical check is happening. (checking moving down.)

Updating the players position

The final part is adding the movement updating. Because we are moving the players hit box and not the x/y or the player, we have to update the player based on its hitbox. We do this by getting the hit box variables and finding the value between. (aka the mean.)

x = mean(playerX1, playerX2);
y = mean(playerY1, playerY2);

And that’s it! The base of the system is there. You can add, tweak and do whatever you want to make the system fit your project!

drawing the player

The final step is to draw the player, for the tutorial we are going to draw a rectangle for the player. You can draw a the players sprite if you already have sprites. (Draw event of the player.)

draw_self();
draw_rectangle(playerX1, playerY1, playerX2, playerY2, true);

Self Study

This part isn’t really part of the tutorial but more of a self study you can do before you follow this tutorial. This for 90% of you might be unnecessary. But someone who’s wants to improve on game design as a whole, or wants to learn how to use the ideas behind this tutorial to improve there projects, might be interested in this part. If you do read it, PLEASE read it to the end, It’s a little informal, but the information is there.


The goal of this tutorial isn’t to give you an array / bit-wise collision system and you carbon copy that into your project. The goal is to solve a problem. That problem could be that what your making needs this system, or it could be that you need the same outcome of this system, but not the system its self. The problem I faced when I needed this project is the ability to load and save randomly generated levels; but here’s the thing. My project didn’t have lots of crazy physics, it was just a platformer with basic enemies. It was a proof of concept.

The conclusion that I came to (building this system for my project), was done through proper planning. Lots of the time developers think of a cool idea and just tunnel vision on that single idea. There unable to realise that what they’re building isn’t for the project that they want, but instead are building a project for that one tunnelled idea, that in time will fail due to lack of planning.

A really god GDC talk about poor management in projects is Up sh*t Creek: Pro Tips for Managing the Unmanageable Project. I would suggest watching this talk. You don’t have to watch the whole talk, but do watch from the 21:30 minute mark. (The link above starts at that time). Some of the biggest problems with large projects are caused by:

  • lack of understanding what the goal is .
  • lack of understanding the consequence of failure .
  • Diving head into a project without planning. Act first plan later .
  • Over committing and over scoping .
  • Building something that’s not practical .
  • Too much process .

These are the main points, and all can be solved by planing. As a solo developer it’s even easier to fall for theses traps as there’s no one to stop you.
I hope that if you have followed the tutorial you take theses skills with you, not just building an array based collision system. But the skill to ask your self “Why do I want an array based collision system”.
If you are building a system that uses the array system please, work out what your goals are, is the system necessary? Have you planned out why you need this? Have you planned out what you need to build on top of this? Is it practical to use this system or is it over kill?

If you can ask those questions to your self before your next project; If you don’t even use the array system but apply these ideas about game design and planning, you will have learnt so much more applicable game design skills then someone who just knows how to build an array based bit-wise collision system.

Thank you for reading all the way through the tutorial and the self study. This tutorial could be half its size, but I wanted to make something more then just a tutorial on a system. I wanted it to be on some aspect of game design as well and I’m hoping you’ve gained some coding and game design skills.

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