Help understanding bitwise tile collision for 16px tiles

mrdaneeyul

Member
Hey everyone! So I've made several attempts at understanding the complex world of bitwise operations so I can get tile collisions all figured out, and this time I figured I'd just ask! I've read up on the new articles in the GMS2 manual, done lots of research prior, and looked through the demos in GMS and GMS2 that exhibit tile collision.

There's a demo in GMS2 called "YoYo Dungeon Lite" that uses this tile collision method, and I'd love to give this a shot. The only thing is, I don't understand what all the collision code is doing or how to replicate it for smaller tile sizes (16px instead of 32px).

Here's the tile collision code. I'll make comments on things I understand and don't understand.

Code:
/// ProcessCollision(_inst, _collision, _dx,_dy, _left,_right, _top,_bottom)
#macro TILE_SIZE    32        // this is labeled "size of debug tilemap". I assume not needed since I don't have a debug tilemap
#macro TILE_SHIFT   5        // "1<<5 = 32" - I'm not sure what this means or where these numbers are coming from.

var _inst = argument0; //The id of the object. In this case, the player
var _dx = argument1; //The horizontal speed to add/subtract to the player's x
var _dy = argument2; //The vertical speed " " " y
var _right = argument3; //The player's bounding borders (distance from origin?)
var _left = argument4;
var _top = argument5;
var _bottom = argument6;

var COLLISION_DEBUG=false;
var DEBUG_TILE = 2;


with( _inst )
{
    // Now move and do collision checks.
    x += _dx;
    y += _dy;
    if( dir = DIR_RIGHT ){
        //Here I get that we're checking the top right and top left corners to make sure it doesn't overlap a tile, but not sure how.
        var tx = (x+_right)>>TILE_SHIFT;        // What is ">>" and how does it check the right edge?
        var ty1 = ((y+_bottom)>>TILE_SHIFT);
        var ty2 = ((y-_top)>>TILE_SHIFT);
        if( COLLISION_DEBUG ){
            tilemap_set(DebugMap, DEBUG_TILE, tx,ty1);
            tilemap_set(DebugMap, DEBUG_TILE, tx,ty2);
        }
    
        // collision data never has flips etc...
        var tile1 = tilemap_get(WallMap, tx,ty1 )& tile_index_mask; //More bitwise--what is this doing?
        var tile2 = tilemap_get(WallMap, tx,ty2 )& tile_index_mask;
    
        if(( tile1!=0 ) || (tile2!=0)) { //Pretty sure this is checking whether tiles exist at top right & top left
            x = (tx<<TILE_SHIFT)-TILE_SIZE+(TILE_SIZE-_right); //Uh...
        }
    }
 
 
    if( dir = DIR_LEFT ){
        var tx = (x-_left)>>TILE_SHIFT;        // check right edge
        var ty1 = ((y+_bottom)>>TILE_SHIFT);
        var ty2 = ((y-_top)>>TILE_SHIFT);
        if( COLLISION_DEBUG ){
            tilemap_set(DebugMap, DEBUG_TILE, tx,ty1);
            tilemap_set(DebugMap, DEBUG_TILE, tx,ty2);        
        }
    
        // collision data never has flips etc...
        var tile1 = tilemap_get(WallMap, tx,ty1 )& tile_index_mask;
        var tile2 = tilemap_get(WallMap, tx,ty2 )& tile_index_mask;
    
        if(( tile1!=0 ) || (tile2!=0)) {
            x = (x&~(TILE_SIZE-1))+_left; //This looks completely different from the right collision
        }
    }
 
    if( dir = DIR_DOWN ){
        var tx1 = (x+(_right-4))>>TILE_SHIFT;        // check right edge
        var tx2 = (x-(_left-4))>>TILE_SHIFT;        // check right edge
        var ty = ((y+_bottom)>>TILE_SHIFT);
        if( COLLISION_DEBUG ){
            tilemap_set(DebugMap, DEBUG_TILE, tx1,ty);
            tilemap_set(DebugMap, DEBUG_TILE, tx2,ty);
        }
    
        // collision data never has flips etc...
        var tile1 = tilemap_get(WallMap, tx1,ty )& tile_index_mask;
        var tile2 = tilemap_get(WallMap, tx2,ty )& tile_index_mask;
      
        if(( tile1!=0 ) || (tile2!=0)) {
            y = (ty<<TILE_SHIFT)-(_bottom+1);
        }
    }
 
    if( dir = DIR_UP ){
        var tx1 = (x+(_right-4))>>TILE_SHIFT;        // check right edge
        var tx2 = (x-(_left-4))>>TILE_SHIFT;        // check right edge
        var ty = ((y-_top)>>TILE_SHIFT);
        if( COLLISION_DEBUG ){
            tilemap_set(DebugMap, DEBUG_TILE, tx1,ty);
            tilemap_set(DebugMap, DEBUG_TILE, tx2,ty);
        }
    
        // collision data never has flips etc...
        var tile1 = tilemap_get(WallMap, tx1,ty )& tile_index_mask;
        var tile2 = tilemap_get(WallMap, tx2,ty )& tile_index_mask;
    
        if(( tile1!=0 ) || (tile2!=0)) {
            y = (ty<<TILE_SHIFT)+TILE_SIZE+_top+1;
        }
    }
}
I would be very grateful if someone could help explain what's going on in these bitwise operations, as well as where the numbers in the macros are coming from! In addition, how would I do this for 16px tiles, and how could I accommodate diagonal checks as well? Any clarity on this is appreciated.
 
A simple understanding of binary numbers is imperative to understanding these functions. If you don't know how binary works, check a resource, as there are many available. As far as operators:

>> is bitwise shift right. What it does is shift a binary number X bits right, trimming any leftover bits. In functionality, these are equivalent:
Code:
x = floor(x / power(2, y));
x = x >> y;

//An example of how it works:
14 >> 2
14 = 0b1110
0b1110 >> 2 = 0b0011 = 3

<< is bitwise shift left. It shifts a binary number X bits left. It's functionally equivalent to multiplying a number by 2^x.
It works similarly to how >> functions.

& is bitwise AND. It checks bits in two numbers and outputs where both bits are 1.
Code:
x = x & y;

//An example of how it works:
x = 42 & 32
x = 0b101010 & 0b100000
//Comparing
0b101010
0b100000
//Only the first bits are 1
0b101010 & 0b100000 = 0b100000 = 32
~ is bitwise NOT. It flips bits.
Code:
x = ~x;

//An example of how it works:
x = ~31 //This is equal to (TILE_SIZE-1), so this should help you understand the left collision better
31 = 0b11111
//FLIPPING
0b11111
0b00000
~31 = 0

The code is commented very poorly, so I'd have to take the time to parse it out. I don't have the time, unfortunately. I hope this all helped!

EDIT:
Oh yeah, if you want to adapt it for 16x16, I think all you have to do is change this:
Code:
#macro TILE_SIZE    32
#macro TILE_SHIFT   5 //1 << 5 = 32
To this
Code:
#macro TILE_SIZE    16
#macro TILE_SHIFT   4 //Because 1 << 4 = 16
 
Last edited:

mrdaneeyul

Member
Ok, that definitely helps a lot. So let me run through some of the pieces after your explanation:

This bit of their code:
Code:
#macro TILE_SIZE    32
#macro TILE_SHIFT   5        // "1<<5 = 32"
Could become this in mine:
Code:
#macro TILE_SIZE 16
#macro TILE_SHIFT 4 //1<<4 = 16
I'm not quite clear on why we're shifting from 1 to 16 here, but at least I know we're shifting bits. (EDIT: This has become clear now that I've gone through the rest of the code.)

And this would be something I leave as-is from their code:
Code:
var tx = (x+_right)>>TILE_SHIFT; //takes the right boundary of the player, shifts 4 bits to the right
var ty1 = ((y+_bottom)>>TILE_SHIFT);
var ty2 = ((y-_top)>>TILE_SHIFT);
So if the player has just moved to the coordinates x = 321 and y = 19. Since we'd add the +8px, that means we're checking for x = 329, y1 = 27, y2 = 11. In binary, x = 101000001, y1 = 011011, y2 = 01011. After we shift them 4, we get x = 000010100, y1 = 000001, and y2 = 00000. Back in decimal, that means tx = 20, ty1 = 1, and ty2 = 0. Am I doing this correctly? :p Then, in the next few lines, we have:
Code:
var tile1 = tilemap_get(WallMap, tx,ty1 )& tile_index_mask;
var tile2 = tilemap_get(WallMap, tx,ty2 )& tile_index_mask;
So this is setting tile1 = to the tile at cell x=20, y=0 (using the tile_index_mask to get the tile's index). The second line sets tile2 to the tile at cell x=20, y=1.

This... actually makes a lot of sense.

One of the killer lines for me was:
Code:
x = (tx<<TILE_SHIFT)-TILE_SIZE+(TILE_SIZE-_right);
After my education, this actually becomes fairly simple. It's in an if-statement that returns true if tile1 or tile2 is a collision tile. If so, it'll take our x cell (20), shift it 4 bits to the left, making it 320. Then, we have -16+(16-8), which is a really weird way to say -8. (Why not just say -8?). So x was originally 321 in my example, and, assuming it hit a collision tile, it has become 312. That puts us square in the 19th cell/tile. In other words: holy crap, I think I've got it!
 
Last edited:
Ok, that definitely helps a lot. So let me run through some of the pieces after your explanation:

This bit of their code:
Code:
#macro TILE_SIZE    32
#macro TILE_SHIFT   5        // "1<<5 = 32"
Could become this in mine:
Code:
#macro TILE_SIZE 16
#macro TILE_SHIFT 4 //1<<4 = 16
I'm not quite clear on why we're shifting from 1 to 16 here, but at least I know we're shifting bits.
Because the collision system now works on a 2⁴x2⁴ grid, you're always dealing with 2⁴. That is why TILE_SHIFT is changed to 4.

Code:
x = (tx<<TILE_SHIFT)-TILE_SIZE+(TILE_SIZE-_right);
Then, we have -16+(16-8), which is a really weird way to say -8. (Why not just say -8?)
This a particularly rough piece of code. It could've been made MUCH more legible by adding some spaces and parentheses. Also, you can't just say "-8" because that number depends on what both "TILE_SIZE" and "_right" are equal to. The script wouldn't be so easy to adapt otherwise.
 

mrdaneeyul

Member
Because the collision system now works on a 2⁴x2⁴ grid, you're always dealing with 2⁴. That is why TILE_SHIFT is changed to 4.
That makes sense. I think it would've been more obvious had they said something like "2^5, or the number of bits to shift".

This a particularly rough piece of code. It could've been made MUCH more legible by adding some spaces and parentheses. Also, you can't just say "-8" because that number depends on what both "TILE_SIZE" and "_right" are equal to. The script wouldn't be so easy to adapt otherwise.
Well, sure, but since we do "-TILE_SIZE + TILE_SIZE -_right", we might as well just do "-_right". Parentheses wouldn't really change the fact that we're just subtracting and then adding TILE_SIZE. :)
 

TheouAegis

Member
Get out of your textbook notation. ^ is not the "power"symbol in GM (or some other languages), so the sooner you stop using it, the sooner your mind will be untrained and you won't accidentally use it incorrectly in code.
 
Top