Legacy GM Collision on a grid ((sub-pixel perfect), no overshooting)

Simon Gust

Member
I’ve been wanting to create a collision system for objects moving on a grid that works the same like CardinalCoder’s object based collision.
Turns out to be extremely complicated to get this to work.

The reason is probably the addition of several quality-of-life aspects.
- sub-pixel perfection
- no overshooting
- support for every rectangular bounding box size.

As of now, I have a solution allthough the sub-pixel perfection isn’t working by default
because the bbox_ variables are integers.

This prototype is not tested very much and it isn’t very optimized.
I am searching for ideas and improvements.
I still need to find an alternative to the bbox variables.
CardinalCoder's method looks inviting, will look into that.

Before you ask questions:
Yes, I’ve seen Ariak’s grid collisions, I just find it hard to implement and manage.
And coding collisions myself gives a far greater feeling of accomplishment.

Here is a basic implementation so you don’t have to code it yourself
CREATE
Code:
x = 64;
y = 64;

hspd = 0;
vspd = 0;

wdt = 32;
hgt = 32;
grid = 0;

for (var i = wdt-1; i >= 0; i--) {
for (var j = hgt-1; j >= 0; j--) {
    grid[i, j] = 1;
}}

for (var i = 1; i < wdt-1; i++) {
for (var j = 1; j < hgt-1; j++) {
    if (random(5)) grid[i, j] = 0;
}}

for (var i = 1; i < 10; i++) {
for (var j = 1; j < 10; j++) {
    grid[i, j] = 0;
}}

enum cell {size = 16}
STEP
Code:
var spd = 6.00; // normal speed
if (keyboard_check(vk_shift))
{
    spd = 25.00; // overshoot speed
}
else
if (keyboard_check(vk_control))
{
    spd = 3.48723; // sub-pixel speed
}
hspd = spd * (keyboard_check(ord("D")) - keyboard_check(ord("A")));
vspd = spd * (keyboard_check(ord("S")) - keyboard_check(ord("W")));
And here is the collision code (no scripts)
Code:
/// collision
/// scr_grid_collision(x+hspd, y+vspd) // potential script
// save fraction of position for later
var xfrac = frac(x);
var yfrac = frac(y);

// floor position
x = floor(x + 0.0001);
y = floor(y + 0.0001);

// save potential new position
var x_new = x + hspd; //argument0; // potential argument
var y_new = y + vspd; //argument1; // potential argument

// remember speed
var xspd = hspd;
var yspd = vspd;

// set bounding boxes
var lft = bbox_left;
var top = bbox_top;
var rgt = bbox_right;
var bot = bbox_bottom;

var flag = true;

// start looping down the height of the player
var y1 = top;
var y2 = bot + cell.size;
for (var j = y1; j <= y2; j += cell.size)
{
    // define deadzone
    var yy = min(j, bot);
    var grid_y = yy div cell.size;
 
    // horizontal collision
    if (xspd < 0) // left
    {
        // start looping down the path of the player
        var x1 = lft + xspd;
        var x2 = lft;
        for (var xx = x1; xx <= x2; xx += cell.size)
        {
            // define deadzone
            var grid_x = xx div cell.size;
        
            // check for collision
            var tile = (grid[grid_x, grid_y]);
            if (tile == 1)
            {
                // set new potential position
                x_new = max(x_new, (grid_x * cell.size) + (x - lft) + cell.size);
                hspd = 0;
                flag = false;
            }
        }
    }
    else
    if (xspd > 0) // right
    {
        // start looping down the path of the player
        var x1 = rgt;
        var x2 = rgt + xspd + 1;
        for (var xx = x2; xx >= x1; xx -= cell.size)
        {
            // define deadzone
            var grid_x = xx div cell.size;
        
            // check for collision
            var tile = (grid[grid_x, grid_y]);
            if (tile == 1)
            {
                // set new potential position
                x_new = min(x_new, (grid_x * cell.size) + (x - rgt) - 1);
                hspd = 0;
                flag = false;
            }
        }
    }
}

// move player
x = x_new;
if (flag)
    x += xfrac;

// update bounding boxes
var lft = bbox_left;
var top = bbox_top;
var rgt = bbox_right;
var bot = bbox_bottom;

var flag = true;

// start looping down the width of the player
var x1 = lft;
var x2 = rgt + cell.size;
for (var i = x1; i <= x2; i += cell.size)
{
    // define deadzone
    var xx = min(i, rgt);
    var grid_x = xx div cell.size;

    // vertical collision
    if (yspd < 0) // up
    {
        // start looping down the path of the player
        var y1 = top + yspd;
        var y2 = top;
        for (var yy = y1; yy < y2; yy += cell.size)
        {
            // define deadzone
            var grid_y = yy div cell.size;
        
            // check for collision
            var tile = (grid[grid_x, grid_y]);
            if (tile == 1)
            {
                // set new potential position
                y_new = max(y_new, (grid_y * cell.size) + (y - top) + cell.size);
                vspd = 0;
                flag = false;
            }
        }
    }
    else
    if (yspd > 0) // down
    {
        // start looping down the path of the player
        var y1 = bot;
        var y2 = bot + yspd + 1;
        for (var yy = y2; yy >= y1; yy -= cell.size)
        {
            // define deadzone
            var grid_y = yy div cell.size;
        
            // check for collision
            var tile = (grid[grid_x, grid_y]);
            if (tile == 1)
            {
                // set new potential position
                y_new = min(y_new, (grid_y * cell.size) + (y - bot) - 1);
                vspd = 0;
                flag = false;
            }
        }
    }
}

// move player
y = y_new;
if (flag)
    y += yfrac;

A draw event is required too
Code:
// draw player
draw_self();

// draw grid
for (var i = 0; i < wdt; i++) {
    var xx = i * cell.size;
for (var j = 0; j < hgt; j++) {
    var yy = j * cell.size;
    if (grid[i, j] == 1) {
        draw_sprite(spr_grid, 0, xx, yy);
    }
}}
The sprites you would have to make yourself.
I used a grid cell size of 16 x 16
My sprite was something like 28 x 44.

Shoutouts to
@CardinalCoder64 and @Ariak
 
Last edited:

Bingdom

Googledom
For the grid collisions, I found this script from heartbeast and I've been using it ever since.
Code:
///place_grid_meeting(x,y,grid)
var xx = argument0;
var yy = argument1;
var grid = argument2;

//Remeber our position
var xp = x;
var yp = y;

//Update the position for the bbox calculation
x = xx;
y = yy;

//Check for x meeting
var x_meeting = (grid[#bbox_right div CELLSIZE, bbox_top div CELLSIZE] == WALL) or
                (grid[#bbox_left div CELLSIZE, bbox_top div CELLSIZE] == WALL)

//Check for y meeting
var y_meeting = (grid[#bbox_right div CELLSIZE, bbox_bottom div CELLSIZE] == WALL) or
                (grid[#bbox_left div CELLSIZE, bbox_bottom div CELLSIZE] == WALL)
             
var center_meeting = grid[# xx div CELLSIZE, yy div CELLSIZE] == WALL;
             
//Move back
x = xp;
y = yp;

return x_meeting or y_meeting or center_meeting;
Use this script like you would with object collisions.

You could probably optimize this script by only having center_meeting, then move back by bbox_* offset depending on the direction you are going. This solution would work well if the bounding box was symmetrical from the origin.

For the overshooting, you can just call this script as normal, incrementing by cell size.

You can find out bbox offsets by putting the instance at 0,0 and read from there or alternatively, through the sprite_get_bbox_* functions (with the latter, you'll have to take account of the origin).
 

Simon Gust

Member
For the grid collisions, I found this script from heartbeast and I've been using it ever since.
Use this script like you would with object collisions.

You could probably optimize this script by only having center_meeting, then move back by bbox_* offset depending on the direction you are going. This solution would work well if the bounding box was symmetrical from the origin.

For the overshooting, you can just call this script as normal, incrementing by cell size.

You can find out bbox offsets by putting the instance at 0,0 and read from there or alternatively, through the sprite_get_bbox_* functions (with the latter, you'll have to take account of the origin).
I know that this exists, it is what I use as of currently.
It does work very well but like the I said,
The collisions need to be sub-pixel, no overshooting (while loops do work, but it's not very efficient to check every pixel), this script only works for 1x1 character to cell ratio size.
The script doesn't work with slopes nor half tiles.

I want to code collisions, not copy them from someone.

I'll look into sprite_get_bbox functions.
 

Bingdom

Googledom
(while loops do work, but it's not very efficient to check every pixel)
It would be fine to move by increments of cell size. Once there's a collision, step back and perform the sub-pixel perfect collision as normal.

this script only works for 1x1 character to cell ratio size.
This is not true. This script works perfectly fine for any reasonable size.

The scriptdoesn't work with slopes nor halftiles.
Since this script returns true if there's a possible collision, you then can run another collision script to read information about the tile and perform what is necessary. This isn't super efficient, but I do like to have things modular.
 
Last edited:

Simon Gust

Member
It would be fine to move by increments of cell size. Once there's a collision, step back and perform the sub-pixel perfect collision as normal.
That is true, but even if you move pixel by pixel from there, it is only pixel-perfect, not sub-pixel perfect. It doesn't get preciser than teleporting to the bounding box of the grid.

This is not true. This script works perfectly fine for any reasonable size.
Reasonable being 2x cell size at max, any further and you have to write a lot of code or use for-loops to loop across the bounding box in increments of cell size.

Since this script returns true if there's a possible collision, you then can run another collision script to read information about the tile and perform what is necessary. This isn't super efficient, but I do like to have things modular.
Not outing myself here, I haven't touched slopes yet. Your point is valid.
 

RujiK

Member
I made a pretty solid 3d collision engine that works with sub-pixel movement speeds. Here is what it looks like:


In my case the easiest solution was to strip out the decimals and then add them back after the movement code.

Like so:
Code:
var xfrac = frac(x);
var yfrac = frac(y);
x = floor(x+0.0001);
y = floor(y+0.0001);

...

//After movement code:
x+=xfrac; //allow fractional movement without doing the work for it
y+=yfrac;
Whenever there is a collision on the x axis, I set the xfrac back to 0. Same for the y axis.

Also I round the velocity so that I'm always doing collision checks on an integer position. Like this:
Code:
//vel_y = velocity on the y axis. Probably will have a decimal
var y_top = y + mask_y + ceil(vel_y-0.001); //top of bbox + velocity. No fractions
var y_bot = y + floor(vel_y+0.001); //bottom of bbox + velocity. No fractions
Hopefully that helps a little.
 

Simon Gust

Member
I made a pretty solid 3d collision engine that works with sub-pixel movement speeds. Here is what it looks like:
In my case the easiest solution was to strip out the decimals and then add them back after the movement code.
Hopefully that helps a little.
That works very well, thank you.

Updated main post
New script
Code:
/// collision
/// scr_grid_collision(x+hspd, y+vspd) // potential script
// save potential new position
var x_new = x + hspd; //argument0; // potential argument
var y_new = y + vspd; //argument1; // potential argument

// remember speed
var xspd = hspd;
var yspd = vspd;

// set bounding boxes
var lft = bbox_left;
var top = bbox_top;
var rgt = bbox_right;
var bot = bbox_bottom;

var flag = true;

// start looping down the height of the player
var y1 = top;
var y2 = bot + cell.size;
for (var j = y1; j <= y2; j += cell.size)
{
    // define deadzone
    var yy = min(j, bot);
    var grid_y = yy div cell.size;
 
    // horizontal collision
    if (xspd < 0) // left
    {
        // start looping down the path of the player
        var x1 = lft + xspd;
        var x2 = lft;
        for (var xx = x1; xx <= x2; xx += cell.size)
        {
            // define deadzone
            var grid_x = xx div cell.size;
         
            // check for collision
            var tile = (grid[grid_x, grid_y]);
            if (tile == 1)
            {
                // set new potential position
                x_new = max(x_new, (grid_x * cell.size) + (x - lft) + cell.size);
                hspd = 0;
                flag = false;
            }
        }
    }
    else
    if (xspd > 0) // right
    {
        // start looping down the path of the player
        var x1 = rgt;
        var x2 = rgt + xspd + 1;
        for (var xx = x2; xx >= x1; xx -= cell.size)
        {
            // define deadzone
            var grid_x = xx div cell.size;
         
            // check for collision
            var tile = (grid[grid_x, grid_y]);
            if (tile == 1)
            {
                // set new potential position
                x_new = min(x_new, (grid_x * cell.size) + (x - rgt) - 1);
                hspd = 0;
                flag = false;
            }
        }
    }
}

// move player
x = x_new;
if (flag) 
    x += xfrac;

// update bounding boxes
var lft = bbox_left;
var top = bbox_top;
var rgt = bbox_right;
var bot = bbox_bottom;

var flag = true;

// start looping down the width of the player
var x1 = lft;
var x2 = rgt + cell.size;
for (var i = x1; i <= x2; i += cell.size)
{
    // define deadzone
    var xx = min(i, rgt);
    var grid_x = xx div cell.size;

    // vertical collision
    if (yspd < 0) // up
    {
        // start looping down the path of the player
        var y1 = top + yspd;
        var y2 = top;
        for (var yy = y1; yy < y2; yy += cell.size)
        {
            // define deadzone
            var grid_y = yy div cell.size;
         
            // check for collision
            var tile = (grid[grid_x, grid_y]);
            if (tile == 1)
            {
                // set new potential position
                y_new = max(y_new, (grid_y * cell.size) + (y - top) + cell.size);
                vspd = 0;
                flag = false;
            }
        }
    }
    else
    if (yspd > 0) // down
    {
        // start looping down the path of the player
        var y1 = bot;
        var y2 = bot + yspd + 1;
        for (var yy = y2; yy >= y1; yy -= cell.size)
        {
            // define deadzone
            var grid_y = yy div cell.size;
         
            // check for collision
            var tile = (grid[grid_x, grid_y]);
            if (tile == 1)
            {
                // set new potential position
                y_new = min(y_new, (grid_y * cell.size) + (y - bot) - 1);
                vspd = 0;
                flag = false;
            }
        }
    }
}

// move player
y = y_new;
if (flag) 
    y += yfrac;
 

Simon Gust

Member
Some time has passed and I'm ready for the next issue:
Consider this:

upload_2019-12-4_12-16-27.png

I (the Player, red), want to jump into this opening on the left which is slightly taller than my player.
Now, with the collision code I have right now (at the top), the Player jumps straight past the opening.

This is because the vspd (vertical Velocity) is so great that the collision checks happen when the Player is slightly too short of the opeing ->

upload_2019-12-4_12-20-1.png

and the next step, the Player is slightly too far ->

upload_2019-12-4_12-20-46.png

What can I do?
I've been thinking and to my mind come 2 Solutions:
- make multiple checks during collision checking. Say instead of going all horizontal and then all vertical, mix them and dividide the process in 3-4 steps.
or
- implement Delta Timing and uncap frame rate (9999fps)

Is either of These something I should do or is there a simpler solution?
Or should this already work but there is an error in my Code.

The current Code is this
Code:
/// collision
/// scr_grid_collision(x+hspd, y+vspd) // potential script
// save fraction of position for later
var xfrac = frac(x);
var yfrac = frac(y);

// floor position
x = floor(x + 0.0001);
y = floor(y + 0.0001);

// save potential new position
var x_new = x + hspd; //argument0; // potential argument
var y_new = y + vspd; //argument1; // potential argument

// remember speed
var xspd = hspd;
var yspd = vspd;

// set bounding boxes
var lft = bbox_left;
var top = bbox_top;
var rgt = bbox_right;
var bot = bbox_bottom;

var flag = true;

// start looping down the height of the player
var y1 = top;
var y2 = bot + cell.size;
for (var j = y1; j <= y2; j += cell.size)
{
    // define deadzone
    var yy = min(j, bot);
    var grid_y = yy div cell.size;

    // horizontal collision
    if (xspd < 0) // left
    {
        // start looping down the path of the player
        var x1 = lft + xspd;
        var x2 = lft;
        for (var xx = x1; xx <= x2; xx += cell.size)
        {
            // define deadzone
            var grid_x = xx div cell.size;
        
            // check for collision
            var tile = (grid[grid_x, grid_y]);
            if (tile == 1)
            {
                // set new potential position
                x_new = max(x_new, (grid_x * cell.size) + (x - lft) + cell.size);
                hspd = 0;
                flag = false;
            }
        }
    }
    else
    if (xspd > 0) // right
    {
        // start looping down the path of the player
        var x1 = rgt;
        var x2 = rgt + xspd + 1;
        for (var xx = x2; xx >= x1; xx -= cell.size)
        {
            // define deadzone
            var grid_x = xx div cell.size;
        
            // check for collision
            var tile = (grid[grid_x, grid_y]);
            if (tile == 1)
            {
                // set new potential position
                x_new = min(x_new, (grid_x * cell.size) + (x - rgt) - 1);
                hspd = 0;
                flag = false;
            }
        }
    }
}

// move player
x = x_new;
if (flag)
    x += xfrac;

// update bounding boxes
var lft = bbox_left;
var top = bbox_top;
var rgt = bbox_right;
var bot = bbox_bottom;

var flag = true;

// start looping down the width of the player
var x1 = lft;
var x2 = rgt + cell.size;
for (var i = x1; i <= x2; i += cell.size)
{
    // define deadzone
    var xx = min(i, rgt);
    var grid_x = xx div cell.size;

    // vertical collision
    if (yspd < 0) // up
    {
        // start looping down the path of the player
        var y1 = top + yspd;
        var y2 = top;
        for (var yy = y1; yy < y2; yy += cell.size)
        {
            // define deadzone
            var grid_y = yy div cell.size;
        
            // check for collision
            var tile = (grid[grid_x, grid_y]);
            if (tile == 1)
            {
                // set new potential position
                y_new = max(y_new, (grid_y * cell.size) + (y - top) + cell.size);
                vspd = 0;
                flag = false;
            }
        }
    }
    else
    if (yspd > 0) // down
    {
        // start looping down the path of the player
        var y1 = bot;
        var y2 = bot + yspd + 1;
        for (var yy = y2; yy >= y1; yy -= cell.size)
        {
            // define deadzone
            var grid_y = yy div cell.size;
        
            // check for collision
            var tile = (grid[grid_x, grid_y]);
            if (tile == 1)
            {
                // set new potential position
                y_new = min(y_new, (grid_y * cell.size) + (y - bot) - 1);
                vspd = 0;
                flag = false;
            }
        }
    }
}

// move player
y = y_new;
if (flag)
    y += yfrac;
 

Simon Gust

Member
Update:
I've been working on alternatives and have got a solution to the problem above.
The problem is just that this code does not work well with high speeds and enteties may clip trough the floor.

upload_2019-12-6_21-6-48.png
yellow: double for-loop checking range
red: actual collision check range

Code:
// width and height of entity
var w = 12;
var h = 20;

// remember initial speed
var xspd = hspd;
var yspd = vspd;

// position next step
var xnext = x + hspd;
var ynext = y + vspd;

// detection range around the player
var x1 = (bbox_left div cell.size) - 1;
var x2 = (bbox_right div cell.size) + 2;
var y1 = (bbox_top div cell.size) - 1;
var y2 = (bbox_bottom div cell.size) + 2;

// fix variables
var xx1 = -1; var yy1 = -1;
var xx2 = -1; var yy2 = -1;

// start lookup up the grid
for (var i = x1; i < x2; i++) {
    var xx = i * cell.size;
for (var j = y1; j < y2; j++) {
    var yy = j * cell.size;
   
    // check for collision
    var tile = grid[i, j];
    if (tile == 1)
    {
        // which tiles are potentially in the way next step
        if (xnext + w/2 > xx && xnext - w/2 < xx + cell.size && ynext > yy && ynext - h < yy + cell.size)
        {
            if (y <= yy) // player not touching the floor quite yet
            {
                xx2 = i; 
                yy2 = j;
                if (xx2 != xx1) vspd = (yy - y); // limit vspd to meet floor
            }
            else
            if (x + w/2 <= xx) // player not touching the right wall yet
            {
                xx1 = i;
                yy1 = j;
                if (yy1 != yy2) hspd = xx - (x + w/2); // limit hspd to meed right wall
                if (xx2 == xx1) vspd = yspd; // not getting stuck code
            }
            else
            if (x - w/2 >= xx + cell.size) // left side less than left wall
            {
                xx1 = i; 
                yy1 = j;
                if (yy1 != yy2) hspd = xx + cell.size - (x - w/2); // limit hspd to meed left wall
                if (xx2 == xx1) vspd = yspd; // not getting stuck code
            }
            else
            if (y-h >= yy + cell.size) // player top not quite hitting their head
            {
                xx2 = i; 
                yy2 = j;
                vspd = yy + cell.size - (y-h); // limit vspd to meet ceiling
                if (yy2 == yy1) hspd = xspd; // not getting stuck code
            }
        }
    }
}}

// move entity
x += hspd;
y += vspd;

If anyone has an idea, I'd apreciate it.
 

TheouAegis

Member
Code:
//if hitting a wall horizontally
{
    var sy = y - y mod cell.size;  //snap to the grid
    if vspd > 0
        sy += cell.size;  //make sure you snap the right direction lol
    var n = sy - y;
    if sign(n) == sign(vspd) && abs(n) < abs(vspd)  //make sure you didn't snap too far
    {
        //check for free gap at (x+hspd, sy)
        //if no collision there, move into the gap (y=sy; x+=hspd)
    }
}
Just an idea.
 

Simon Gust

Member
Okay good news, I've been able to solve the issue with the clipping.
Code:
//if hitting a wall horizontally
{
    var sy = y - y mod cell.size;  //snap to the grid
    if vspd > 0
        sy += cell.size;  //make sure you snap the right direction lol
    var n = sy - y;
    if sign(n) == sign(vspd) && abs(n) < abs(vspd)  //make sure you didn't snap too far
    {
        //check for free gap at (x+hspd, sy)
        //if no collision there, move into the gap (y=sy; x+=hspd)
    }
}
Just an idea.
I forgot that you posted this but I will have a look at it and try to come up with another alternative.
But for now, the clipping that occurred was caused by a logic error.

Basically, the double for loop that was checking every tile in the potential way set vspd to a value so that the player will perfectly meet that tile if it would collide or overshoot it.
The problem was that the checks overwrote themselves and put out results heavily influenced by code order which is terrible.
Basically if the player falls on uneven terrain, y was set to the latest tile found below the player even if it was not the closest.
I fixed this by just putting simple min() and max() to the evaluations.

But only this didn't fix it because the total area being checked was also too small for speed values that are too big.
Of course I tried to increase that area but with the old code, the result was the player falling through the world permanently.
Now with both things fixed, it works very well.
Code:
// width and height of entity
var w = 12;
var h = 20;

// remember initial speed
var xspd = hspd;
var yspd = vspd;

// position next step
var xnext = x + hspd;
var ynext = y + vspd;

// sides
var rgt_next = x + w/2 + hspd;
var top_next = y - h +   vspd;
var lft_next = x - w/2 + hspd;
var bot_next = y +       vspd;

// detection range around the player
var x1 = min(bbox_left,  lft_next) div cell.size - 1;
var y1 = min(bbox_top,   top_next) div cell.size - 1;
var x2 = max(bbox_right, rgt_next) div cell.size + 1;
var y2 = max(bbox_bottom,bot_next) div cell.size + 1;

// fix variables
var xx1 = -1; var yy1 = -1;
var xx2 = -1; var yy2 = -1;

// start lookup up the grid
for (var i = x1; i < x2; i++) {
    var xx = i * cell.size;
for (var j = y1; j < y2; j++) {
    var yy = j * cell.size;

    // tile detected is solid
    var tile = get_type(i, j);
    if (global.SOLID[tile])
    {
        // which tiles are potentially in the way next step
        if (xx < rgt_next) && (xx + cell.size > lft_next) && (yy < bot_next) && (yy + cell.size > top_next)
        {
            if (y <= yy) 
            {
                xx2 = i; 
                yy2 = j;
                if (xx2 != xx1) vspd = min(vspd, yy - y);
            }
            else
            if (x + w/2 <= xx) 
            {
                xx1 = i;
                yy1 = j;
                if (yy1 != yy2) hspd = min(hspd, xx - (x + w/2));
                if (xx2 == xx1) vspd = yspd;
            }
            else
            if (x - w/2 >= xx + cell.size)
            {
                xx1 = i; 
                yy1 = j;
                if (yy1 != yy2) hspd = max(hspd, xx + cell.size - (x - w/2));
                if (xx2 == xx1) vspd = yspd;
            }
            else
            if (y-h >= yy + cell.size)
            {
                xx2 = i; 
                yy2 = j;
                vspd = max(vspd, yy + cell.size - (y-h));
                if (yy2 == yy1) hspd = xspd;
            }
        }
    }
}}

// move entity
x += hspd;
y += vspd;
 
Top