GM:S 1.4 Collision on a grid ((sub-pixel perfect), no overshooting)

Discussion in 'Advanced Programming Discussion' started by Simon Gust, Apr 24, 2018.

Tags:
  1. Simon Gust

    Simon Gust Member

    Joined:
    Nov 15, 2016
    Posts:
    3,148
    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: Aug 16, 2018
    brogolem35 likes this.
  2. Bingdom

    Bingdom Googledom

    Joined:
    Jul 1, 2016
    Posts:
    1,677
    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).
     
  3. Simon Gust

    Simon Gust Member

    Joined:
    Nov 15, 2016
    Posts:
    3,148
    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.
     
  4. Bingdom

    Bingdom Googledom

    Joined:
    Jul 1, 2016
    Posts:
    1,677
    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 is not true. This script works perfectly fine for any reasonable 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.
     
    Last edited: Apr 24, 2018
  5. Simon Gust

    Simon Gust Member

    Joined:
    Nov 15, 2016
    Posts:
    3,148
    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.

    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.

    Not outing myself here, I haven't touched slopes yet. Your point is valid.
     
  6. RujiK

    RujiK Member

    Joined:
    Jun 21, 2016
    Posts:
    157
    I made a pretty solid 3d collision engine that works with sub-pixel movement speeds. Here is what it looks like:
    [​IMG]

    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.
     
    NeZvers, CMAllen, hippyman and 2 others like this.
  7. Simon Gust

    Simon Gust Member

    Joined:
    Nov 15, 2016
    Posts:
    3,148
    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;
    
     
    RujiK likes this.

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice