Fast platform collisions.

Posted on 13 October 2011

With the launch of GameMaker:HTML5, there's one brand new factor that should be at the forefront of any game you now design; speed. You see, moving from a windows executable to HTML5 carries some performance issues, and sometimes, some pretty severe ones. JavaScript isn't as quick as native code, that's obvious, and this means you will have to produce more optimal, streamlined code. This in turn means that there is some adjustment required in the way we now do some things in GameMaker. Platform games are a case in point, for while they work fine under windows, due to the way the original examples demonstrated things, they are far from optimal enough for GameMaker:HTML5. Don't worry though, anything you learn here can be carried over to Normal Windows executables, and you'll still see a speed up there as well, so it's all good.

So, why is this? Why does the current crop of platformers suffer so much in JavaScript? Well, the issue is due to the way commands such as "move_outside_solid()" work. you see, what currently happens when you write a platform game, you ask the system to give you a collision event, and then you use commands like move_outside_solid() to move outside it. The problem with commands like this is the amount of code it has to run through in order to satisfy these seemingly simple actions.

Let's take the command move_outside_solid(), how does GameMaker do this? Well... first, have a read of my collision article, because you'll need to understand how precise collisions work, and how much effort it is for the CPU to do that work. Once you've read that, you'll realise that even one precise collision can take a pretty long time, and you might even now realise that move_outside_solid() will have to do this several times in order to "move outside" the collision that just occurred.

So let's follow through what happens.... First you move the player/object as normal, and then the system throws a collision event (probably using a slow collision test in the process), telling you that your instance has just hit something. You now workout the direction you've just come from, and use move_outside_solid() to "back out" of this collision. If you were deep inside the collision (say several pixels inside the collided block), then it may take several precise collision iterations to actually move your instance back out. Add to the fact that you may also be doing this to baddies as well as the player, then you can see that this is just burning CPU time - lots of it. So, how else could you do this? How could you run around on a platform, and stop the player (and baddies) jumping into walls, or falling through the floor?

First, why don't we have a look back at some old retro systems: NES, C64, Megadrive, SNES - all of these systems are well known for platform games, and did platform collision detection in the same way; tilemaps. Now, these aren't tilemaps as GameMaker defines them, this is because GameMaker uses a somewhat warped version of tilemaps. Most of these old systems used fixed character mapped screens, that is, a screen made up of X by Y characters. (i.e. the C64 had a screen of 40x24 cells, which it uses as characters, and games use as tiles). These characters were then used as tiles, and these tiles were then defined into platforms and background, and simple collisions would occur with them.

C=64 Giana Sisters

The game above (The C64 game, "The Great Giana Sisters") shows how the game would probably tile up it's level. The larger tiles would actually be multiple tiles, chained together to make a large object. This differs greatly from GameMakers tiles, because they aren't really tiles at all, but very simple sprites. This is a problem, because we can't easily detect which tile we've hit - at least, not without extensive checking. So, how did these old - and very slow systems, collide with the background so quickly? Easy, they used a fixed grid of tiles. This meant you could easily tell which tile you hit, simply by dividing down your coordinates (usually by 8, 16,32 etc. in fact, any power of 2 number) and then using these numbers they index directly into the grid of tiles.


So, lets have a look at a simple tilemap. Above you can see a very simple tilemap where 1 is solid, 0 is empty, and 2 is a pickup. This means all we need to do is test the tiles directly under the instance (in this case, the player). So how do we do that? Well, If we're using a 16x16 tileset, and our sprite is a 16x16, then when standing directly on a tile, it's x and y coordinate will be a multiple of 16. So, when checking the tile directly below, we would simply add 16 to Y, then divide the Y coordinate by 16, and flooring it. This gives us the tile index (on Y) for the tile under our feet. If the tile is 1, then we don't fall, if it's 0, we do. 

16x16 tiles

Now that's all well and good, but what if we are falling, and what if we fall INTO a tile? How can we move out of it without commands like move_outside_solid()? This is where we use some old school tricks, and it's how these old 1Mhz systems were able to games like platformers and shooters so easily.

First; time to brush up on some binary maths. Binary is very handy, and you should be a fluent as possible with it and the tricks it allows you to do. Lets have a look at a couple of numbers.

%1     1
%10    2
%100   4
%1000  8
%10000 16

As each bit is set, it adds a power of 2 number to the total. As you can see from the above numbers, they have single bits set, and so are "pure" power of 2 numbers (1,2,4,8,16,32,64,128 etc. are all power of 2. As each number is multiplied by 2, it doubles.)

So, if we have some combinations of these bits... what does this mean?

%110     6
%1101   13
%11      3
%1001   9

Using the table above, you can see when you add the bits together, you get the resulting numbers. So, pretty straight forward so far. This is how computers store numbers, with each BYTE being able to hold 8 bits, allowing for numbers from 0 to 255. For larger numbers, the computer simply uses more bytes. 2 bytes allows 16 bits, and a number from 0 to 65535, and so on.

So... why this lesson in basic computing? Ah... well, now it gets interesting. What happens if we shift these bits around? Let's say shift them left or right by a number of bits? Well, %1 shifted left 3 would give %1000, and this gives 8. Also, if we had %1000 and shifted right 3, we'd get %1 (1). In other words, we can do simple multiplication and division by shifting the bits around. (this is again, how the computer does basic binary maths).

So... What would happen if we dropped OFF the lower bits...? Let's say we had %1011 (11), and we AND'd with %1000 (8), we would end up with...8. By removing these lower bits, we have effectively rounded DOWN to the nearest multiple of 8.


Now, that's handy.... What if our tilemap was made from 16x16s, and what if we were 4 pixels into one on Y. So the Y coordinate was 68. How could we move it back out of the tile? Well, since we know all tiles are on fixed pixel boundary's, we know that OUTSIDE the tile coordinate is 64. Using the binary tricks above, we can do a simple AND with Y coordinate (Y = Y & $fffffff0), and this will rid us of the lower bits making the value a multiple of 16, and placing it outside the collision, and back to 64; since %1001000 (68) & $fffffff0 = %1000000 (64).

So, let's look at this again. If we know we have a collision on Y (below), we can simply jump back directly into the empty space by ANDing with $fffffff0, and removing the offending bits.

This collision system is lightning fast, but to use it you must have a FIXED tilemap, not one that places tiles "anywhere". Future versions of GameMaker will remove that ability, but it will also give access to the map for use with collisions, because it's an invaluable tool. Once you collide with the map, you can collide with anything in the level. Pickups, traps, solid objects, triggers, pretty much anything you use an instance for in terms of collision, you can use tilemaps to do it faster. You do have the restriction that your object must be on a tile boundary, but for most things, this isn't an issue. After all, if you want to trigger something when the player walks over it, does it matter if it's a few pixels to the left? The same with power ups... You just get used to placing them in this manner, and then you can use the tilemap to actually collide.

GameMaker:HTML5 comes with a demo of this method, so you can now read over this and then poke around in the source till your hearts content!


Back to Top