Tile Collision Line?

SQGTDev

Member
I need to code a collision line for tilemaps, and I’ve been tearing my hair out all day trying to figure out how.

I basically just need to define two points (x1, y1, x2, y2) and get each tile that the line overlaps, but despite being decent enough at GML I can’t seem to understand everything I look at online.
 

NightFrost

Member
Bresenham's line algorithm should be a good starting point, although it is designed to avoid choosing adjacent squares that are at right angles to the line's direction. So if the line is mostly horizontal, vertically adjacent squares will not be selected. The examles at the wiki link should make that clearer. However it should give you an idea on how to step along the coordinates to catch all the squares the line passes across.
 
A

Ampersand

Guest
I've created a sort of tile-based ray-cast that is very similar to Bresenham's line algorithm, however for my project I needed lines to be congruent from flipped points while also always treading only adjacent squares. I used it to check across ds_grids, but could likely be used with tiles (or you could just generate a grid map for rough checks, then based on the tile type check within that tile for precise collisions). Let me know if you'd like to see it. But definitely a supercover implementation of Bresenham's line algorithm is what you're wanting.
 

SQGTDev

Member
Bresenham's line algorithm should be a good starting point, although it is designed to avoid choosing adjacent squares that are at right angles to the line's direction. So if the line is mostly horizontal, vertically adjacent squares will not be selected. The examles at the wiki link should make that clearer. However it should give you an idea on how to step along the coordinates to catch all the squares the line passes across.
I've created a sort of tile-based ray-cast that is very similar to Bresenham's line algorithm, however for my project I needed lines to be congruent from flipped points while also always treading only adjacent squares. I used it to check across ds_grids, but could likely be used with tiles (or you could just generate a grid map for rough checks, then based on the tile type check within that tile for precise collisions). Let me know if you'd like to see it. But definitely a supercover implementation of Bresenham's line algorithm is what you're wanting.
Thanks for the advice! I managed to find a good implementation of Bresenham's line that does exactly what I want it to do!
I found it from here: http://playtechs.blogspot.com/2007/03/raytracing-on-grid.html and tweaked it.
The only thing I don't like is that it seems to check pixel by pixel thus overlapping each cell multiple times, which is tanking the fps_real when the line gets long.
What I need to do is somehow get the distance to the next cell so I can calculate that cell only once and move on to the next one which would be a huge and necessary speed boost.
I'll keep fiddling with my code to see if I can make that happen, and if I do I'll post what I have again.

Code:
var cell, cellX, cellY, loopX = x1, loopY = y1;
var xDelta = (abs(x2 - x1));
var yDelta = (abs(y2 - y1));
var error = xDelta - yDelta;
var n = (1 + xDelta + yDelta);
xDelta *= 2;
yDelta *= 2;
var xSign, ySign;
switch (x2 > x1)
{
    case true:
        xSign = 1;
        break;
    case false:
        xSign = -1;
        break;
}
switch (y2 > y1)
{
    case true:
        ySign = 1;
        break;
    case false:
        ySign = -1;
        break;
}

for (; n > 0; --n)
{
    //cell = tilemap_get_at_pixel(tilemapID, loopX, loopY);
    cellX = tilemap_get_cell_x_at_pixel(tilemapID, loopX, loopY);
    cellY = tilemap_get_cell_y_at_pixel(tilemapID, loopX, loopY);
    draw_tile(tileset, 1, 0, 16 * cellX, 16 * cellY);
    if (error > 0)
    {
        loopX += xSign;
        error -= yDelta;
    }
    else
    {
        loopY += ySign;
        error += xDelta;
    }
}
 
A

Ampersand

Guest
Mine does not overlap or double-count spaces. It basically creeps the grid by only adjacent cells, only adding new cells. Lemme look at it and pull any game-specific code and add some comments, and I'll edit in a few. Edit: more specifically, it adds all the cells traversed by a line to a data structure and then sorts them based on how the line is traveling.

All in all my method was finding the intersection points similar to Bresenham's method, and hard-traveling them at a grid resolution rather than a pixel resolution so that it won't double count a space or skip to a caddy-corner space. In my testing it seems to work entirely as intended.

I started in the same position as you looking at people's implementations of Breshenam's line algorithm, only to find the same issues: non-congruency, multiple checks per cell traveled, more precision than necessary (considering precise collision checks can be added in many ways once you've found a "blocked" cell, I chose to save performance time on the grid checks)

Defining globals and filling the map grid:
Code:
globalvar cell_size, grid_map, grid_w, grid_h ;
cell_size = /*your grid size*/ ;
globalvar grid_map ;
grid_map = ds_grid_create(floor(room_width / cell_size), floor(room_height / cell_size)) ;
for(var i = 0 ; i < ds_grid_width(grid_map) ; i ++ ;)
{
    for(var j = 0 ; j < ds_grid_height(grid_map) ; j ++ ;)
    {
        if /*cell is blocked*/ //modify this as you wish, check for collision objects etc. at i * cell size and j * cell size and mark it as an obstacle
        {
            grid_map[# i, j] = 1 ;
        }
        else
        {
            grid_map[# i, j] = 0 ;
        }
    }
}
The script in the draw event, so you can visualize it:
Code:
///draw_cast_supercover(origin_x, origin_y, direction, distance)
//
//Find our start and end cells
var lyte_x = floor((argument0) / cell_size) * cell_size + cell_size / 2 ;
var lyte_y = floor((argument1) / cell_size) * cell_size + cell_size / 2 ;
var lyte_end_x = floor((lyte_x + lengthdir_x(argument3, argument2)) / cell_size) * cell_size + cell_size / 2 ;
var lyte_end_y = floor((lyte_y + lengthdir_y(argument3, argument2)) / cell_size) * cell_size + cell_size / 2 ;

//Draw actual cast line
draw_line_colour(lyte_x, lyte_y, lyte_end_x, lyte_end_y, c_white, c_white) ;
draw_circle_colour(lyte_x, lyte_y, 3, c_white, c_white, false) ;
draw_circle_colour(lyte_end_x, lyte_end_y, 3, c_white, c_white, false) ;

//Set travel variables
var lyte_dir = point_direction(lyte_x, lyte_y, lyte_end_x, lyte_end_y) ;
var lyte_rad = point_distance(lyte_x, lyte_y, lyte_end_x, lyte_end_y) ;
var list_cells = ds_priority_create() ;

var delta_x = lyte_end_x - lyte_x ;
var delta_y = lyte_end_y - lyte_y ;
var x_cells_traveled = floor(delta_x / cell_size) ;
var y_cells_traveled = floor(delta_y / cell_size) ;
var xdir = sign(x_cells_traveled) ;
var ydir = sign(y_cells_traveled) ;

//Travel
var denominator = abs(x_cells_traveled * 2) ;
for(var i = 1 ; i < denominator ; i += 2 ;)
{
    //Show grid intersections, and "travel" the intersected cells
    var xx = lyte_x + lengthdir_x(lyte_rad * (i / denominator), lyte_dir) ;
    var yy = lyte_y + lengthdir_y(lyte_rad * (i / denominator), lyte_dir) ;
    draw_circle_colour(xx, yy, 3, c_blue, c_blue, false) ;
    ds_priority_add(list_cells, 2 + (xdir > 0), i / denominator) ;
}

var denominator = abs(y_cells_traveled * 2) ;
for(var i = 1 ; i < denominator ; i += 2 ;)
{
    //Show grid intersections, and "travel" the intersected cells
    var xx = lyte_x + lengthdir_x(lyte_rad * (i / denominator), lyte_dir) ;
    var yy = lyte_y + lengthdir_y(lyte_rad * (i / denominator), lyte_dir) ;
    draw_circle_colour(xx, yy, 3, c_blue, c_blue, false) ;
    ds_priority_add(list_cells, (ydir > 0), i / denominator) ;
}

//Draw start cell
draw_set_alpha(.5) ;
var current_cell_x = floor(lyte_x / cell_size) ;
var current_cell_y = floor(lyte_y / cell_size) ;
draw_rectangle_colour(current_cell_x * cell_size, current_cell_y * cell_size,
                              current_cell_x * cell_size + cell_size, current_cell_y * cell_size + cell_size,
                              c_lime, c_lime, c_lime, c_lime, false) ;
var q_length = ds_priority_size(list_cells) ;

//Draw traveled cells up to terminal cell in order
for(var i = 0 ; i < q_length ; i ++ ;)
{
    var temp_list = ds_priority_find_min(list_cells) ;
    current_cell_x += parse_cast_x(temp_list) ;
    current_cell_y += parse_cast_y(temp_list) ;
    ds_priority_delete_min(list_cells) ;
    if grid_empty(current_cell_x, current_cell_y)
    {
        draw_rectangle_colour(current_cell_x * cell_size, current_cell_y * cell_size,
                              current_cell_x * cell_size + cell_size, current_cell_y * cell_size + cell_size,
                              c_lime, c_lime, c_lime, c_lime, false) ;
        //here you could light up a cell, change its value, or even save the list as another list of move-coordinates, or simply return false for collision
    }
    else
    {
        draw_rectangle_colour(current_cell_x * cell_size, current_cell_y * cell_size,
                              current_cell_x * cell_size + cell_size, current_cell_y * cell_size + cell_size,
                              c_red, c_red, c_red, c_red, false) ;
        //here you could do nothing, or if for collision checks you could return a collision true (and then do some line slope checks or something based on the type of tile for more precision)
        break ;
    }
}
draw_set_alpha(1) ;

//All done
ds_priority_destroy(list_cells) ; //free list
and the necessary streamlining scripts (parse_cast_x, parse_cast_y, grid_empty):
Code:
///parse_cast_x(0-3)
switch(argument0)
{
    case 0: return 0 break ;
    case 1: return 0 break ;
    case 2: return -1 break ;
    case 3: return 1 break ;
}
Code:
///parse_cast_x(0-3)
switch(argument0)
{
    case 0: return -1 break ;
    case 1: return 1 break ;
    case 2: return 0 break ;
    case 3: return 0 break ;
}
Code:
///grid_empty(cell_x, cell_y)
//returns whether the grid_map is empty and we can travel through the space
//Not as necessary, could be replaced directly, mainly to allow multiple types of free and blocked cells and to limit the casts to the grids to avoid ds_grid errors
if argument0 < 0 or argument0 >= grid_w or argument1 < 0 or argument1 >= grid_h or grid_map[# argument0, argument1] = 0
{
    return false ;
}
else
{
    return true ;
}
It could likely be streamlined. This was for a project that's on the backburner and hasn't gotten the optimization treatment yet. I keep thinking this would be loads of fun to do in a turn-base/grid-based RTS so that ground units can't see past mountain tiles or through forest tiles, while other units perhaps can (I feel an Advance Wars type game could be done with a lot more intensive of strategic elements)

I was able to push thousands of casts per frame without taking performance hits, and the levels I did notice performance hits at were likely because of the fact that I was accessing grids so much with each cast (and then having to draw the lighting based on all these constant changes). Should work well for anything as intensive as or less so than that.

Please @ me if this doesn't plug in and draw you grid lines. Might take a little modification, I did my best to clean it up so it could be plugged right in. Let me know if you need any help!

This is all from my Fog of War project that you can find on my GitHub. It is essentially under an MIT License: use, modify, and distribute as you wish, as long as the license remains intact and you contact me for commercial use (no royalties or anything, just like to know where my code goes :) )
 
Last edited by a moderator:

Paskaler

Member
I have some code for such a thing, and I'll post it when I get home. The line will go exactly to a side of a tile and then stop, if you need that kind of precision.

EDIT:

Here's the code I said I'd post:

Code:
///raycast(x, y, direction, dist)
/*

    Replace the following with your own macros/global variables:
        macro tile_size - Size of your tiles(8, 16, 32, ...)
        macro tile_bit_shift
            - Used for rounding down numbers to a tile index
            - x >> tile_bit_shift is the same as doing (x div tile_size) * tile_size, just a little bit faster
            - It depends on your tile_size:
                - 8x8    = 2
                - 16x16 = 4
                - 32x32 = 5
                - 64x64 = 6

        global.collision:
            - ds_grid with all the collision data
            - I stored strings inside since I had more types than just solid and not solid
            - If you only have those two, replace the lines:
                wall_h = global.collision[#tx, ty] == 'solid'; -> wall_h = global.collision[#tx, ty];
                wall_v = global.collision[#tx, ty] == 'solid'; -> wall_v = global.collision[#tx, ty];

        global.col_width - The width of global.collision grid
        global.col_height - The height of global.collision grid

        And a final note:
            I'm not a 100% sure exactly how all of this works :) since this is modified
            code that I got from someone else on the forum a while back.
            I sadly don't remember the name,
            but I do remember that the original code was based on a tutorial: http://lodev.org/cgtutor/raycasting.html


*/

var xx = argument0;
var yy = argument1;
var angle = argument2;
var distance = argument3;

var ang_sin = dsin(angle), ang_cos = dcos(angle), ang_tan = dtan(angle);

var hwall_x, hwall_shift_x, hwall_y, hwall_shift_y;
var vwall_x, vwall_shift_x, vwall_y, vwall_shift_y;

if ang_sin > 0 {
    hwall_y = (yy div tile_size) * tile_size - 0.01;
    hwall_shift_y = -tile_size;
} else {
    hwall_y = (yy div tile_size) * tile_size + tile_size;
    hwall_shift_y = tile_size;
}

hwall_x = xx + (yy - hwall_y) / ang_tan;
hwall_shift_x = -hwall_shift_y / ang_tan;
  
if ang_cos < 0 {
    vwall_x = (xx div tile_size) * tile_size - 0.01;
    vwall_shift_x = -tile_size;
} else {
    vwall_x = (xx div tile_size) * tile_size + tile_size;
    vwall_shift_x = tile_size;
}

vwall_y = yy + (xx - vwall_x) * ang_tan;
vwall_shift_y = -vwall_shift_x * ang_tan;
  

var dist_h = 0, dist_v = 0;
var wall_h = false, wall_v = false;

while dist_h < distance {
    dist_h = point_distance(xx, yy, hwall_x, hwall_y);
    var tx = clamp(hwall_x >> tile_bit_shift, 0, global.col_width - 1);
    var ty = clamp(hwall_y >> tile_bit_shift, 0, global.col_height - 1);
    wall_h = global.collision[#tx, ty] == 'solid';

    if wall_h {
        break;
    }
  
    hwall_x += hwall_shift_x;
    hwall_y += hwall_shift_y;
}
  
while dist_v < distance {
    dist_v = point_distance(xx, yy, vwall_x, vwall_y);
    var tx = clamp(vwall_x >> tile_bit_shift, 0, global.col_width - 1);
    var ty = clamp(vwall_y >> tile_bit_shift, 0, global.col_height - 1);
    wall_v = global.collision[#tx, ty] == 'solid';
  
    if wall_v {
        break;
    }
  
    vwall_x += vwall_shift_x;
    vwall_y += vwall_shift_y;
}

if wall_h or wall_v {
    if dist_h < dist_v and wall_h {
        var hit_info;
        hit_info[2] = dist_h;
        hit_info[1] = hwall_y;
        hit_info[0] = hwall_x;
        return hit_info;
    }
    if dist_v < dist_h and wall_v {
        var hit_info;
        hit_info[2] = dist_v;
        hit_info[1] = vwall_y;
        hit_info[0] = vwall_x;
        return hit_info;
    }
} else {
    var hit_info;
    hit_info[2] = distance;
    hit_info[1] = yy + lengthdir_y(distance, angle);
    hit_info[0] = xx + lengthdir_x(distance, angle);
    return hit_info;
}
 
Last edited:

SQGTDev

Member
Sorry for the long wait (I don't tend to log on super often) but I managed to get it working.
Funny thing was that all I needed to do was use tile cells themselves as pixels. I figured they're square and in a grid like pixels are.
It isn't as good as the code you guys posted but thanks a ton! I hope this helps anyone else looking for how to solve this issue.

Code:
/// @description scrCollisionLineTile(x1, y1, x2, y2, tilemapID, wrapHorizontal, wrapVertical)

var x1 = argument0, y1 = argument1, x2 = argument2, y2 = argument3, tilemapID = argument4;
var cellStartX = tilemap_get_cell_x_at_pixel(tilemapID, x1, y1), cellStartY = tilemap_get_cell_y_at_pixel(tilemapID, x1, y1);
var cellEndX = tilemap_get_cell_x_at_pixel(tilemapID, x2, y2), cellEndY = tilemap_get_cell_y_at_pixel(tilemapID, x2, y2);
var cell, cellX = cellStartX, cellY = cellStartY;
var xDelta = abs(cellEndX - cellStartX);
var yDelta = abs(cellEndY - cellStartY);
var n = (1 + xDelta + yDelta);
var xSign, ySign;
switch (cellEndX > cellStartX)
{
    case true:
        xSign = 1;
        break;
    case false:
        xSign = -1;
        break;
}
switch (cellEndY > cellStartY)
{
    case true:
        ySign = 1;
        break;
    case false:
        ySign = -1;
        break;
}
var error = xDelta - yDelta;
xDelta *= 2;
yDelta *= 2;

for (; n > 0; --n)
{
    cell = tilemap_get(tilemapID, cellX, cellY);
    switch(tile_get_index(cell))
    {
        case -1:
            cellValues[@ 0] = 0; //cell
            cellValues[@ 1] = 0; //cellX
            cellValues[@ 2] = 0; //cellY
            exit;
            break;
        case 0:
            break;
        default:
            cellValues[@ 0] = cell; //cell
            cellValues[@ 1] = cellX; //cellX
            cellValues[@ 2] = cellY; //cellY
            exit;
    }
    if (error > 0.5)
    {
        cellX += xSign;
        error -= yDelta;
    }
    else
    {
        cellY += ySign;
        error += xDelta;
    }
}
cellValues[@ 0] = 0; //cell
cellValues[@ 1] = 0; //cellX
cellValues[@ 2] = 0; //cellY
 

R-Hat

Member
Nevermind. I'm a noob again after 12 years, hehe.

The point is, the error message ds_grid "index out of bounds" is misleading. When it says
writing[12,1], grid size is [12,12]
Looks perfectly all right, right? 12 is not greater than 12.
Well, the problem is, the first number means 13, i.e. 0 to 12. The latter means 12, i. e. 1 to 12.
Yes, the error was entirely my own, a forgotten = sign in a for loop in a different script.
 
Last edited:

DarK_SaCoR

Member
Sorry for the long wait (I don't tend to log on super often) but I managed to get it working.
Funny thing was that all I needed to do was use tile cells themselves as pixels. I figured they're square and in a grid like pixels are.
It isn't as good as the code you guys posted but thanks a ton! I hope this helps anyone else looking for how to solve this issue.

Code:
/// @description scrCollisionLineTile(x1, y1, x2, y2, tilemapID, wrapHorizontal, wrapVertical)

var x1 = argument0, y1 = argument1, x2 = argument2, y2 = argument3, tilemapID = argument4;
var cellStartX = tilemap_get_cell_x_at_pixel(tilemapID, x1, y1), cellStartY = tilemap_get_cell_y_at_pixel(tilemapID, x1, y1);
var cellEndX = tilemap_get_cell_x_at_pixel(tilemapID, x2, y2), cellEndY = tilemap_get_cell_y_at_pixel(tilemapID, x2, y2);
var cell, cellX = cellStartX, cellY = cellStartY;
var xDelta = abs(cellEndX - cellStartX);
var yDelta = abs(cellEndY - cellStartY);
var n = (1 + xDelta + yDelta);
var xSign, ySign;
switch (cellEndX > cellStartX)
{
    case true:
        xSign = 1;
        break;
    case false:
        xSign = -1;
        break;
}
switch (cellEndY > cellStartY)
{
    case true:
        ySign = 1;
        break;
    case false:
        ySign = -1;
        break;
}
var error = xDelta - yDelta;
xDelta *= 2;
yDelta *= 2;

for (; n > 0; --n)
{
    cell = tilemap_get(tilemapID, cellX, cellY);
    switch(tile_get_index(cell))
    {
        case -1:
            cellValues[@ 0] = 0; //cell
            cellValues[@ 1] = 0; //cellX
            cellValues[@ 2] = 0; //cellY
            exit;
            break;
        case 0:
            break;
        default:
            cellValues[@ 0] = cell; //cell
            cellValues[@ 1] = cellX; //cellX
            cellValues[@ 2] = cellY; //cellY
            exit;
    }
    if (error > 0.5)
    {
        cellX += xSign;
        error -= yDelta;
    }
    else
    {
        cellY += ySign;
        error += xDelta;
    }
}
cellValues[@ 0] = 0; //cell
cellValues[@ 1] = 0; //cellX
cellValues[@ 2] = 0; //cellY
Great algorithm. Thank you!
 
Top