GMLscripts.com

Nocturne

Member

Registered: 2015-03-17

Posts: 1

collision_line_bresenhams

Expand/// collision_line_bresenham(x1, y1, x2, y2, object, resolution, notme, first);

//  This script uses Bresenham's algorithm for finding all the grid squares that
//  fall along an interpolated straight line vector. The line is given in room coordinates 
//  and the grid is calculated using the "resolution" argument. So, if your game uses an 
//  8x8 pixel grid (for example), the resolution would be 8.
//
//  The script can be used to return the first instance found along the vector or all of the 
//  instances from along the full length of the vector. Instances will be returned in a 
//  DS Queue, which will need to be destroyed to clean up the memory when no longer 
//  required.
//
//  		x1            The initial x position in room space, real
//  		y1            The initial y position in room space, real
//  		x2            The final x position in room space, real
//  		y2            The final y position in room space, real
//  	 	object        The object or instance ID to check for, real/id value
//     		resolution    The grid resolution to use (for example 8, 20, 32, etc...), real
//       	notme         Whether to check for the calling instance (false) or not (true), boolean
//        	first         Return only the first instance found (true) or not (false), boolean
//
//  More Info: http://www.roguebasin.com/index.php?title=Bresenham%27s_Line_Algorithm
//
//  GMLscripts.com/license


var ts = argument5;
var ts_h = ts / 2;
var x1 = floor(argument0 / ts);
var y1 = floor(argument1 / ts);
var x2 = floor(argument2 / ts);
var y2 = floor(argument3 / ts);
var obj = argument4;
var notme = argument6;
var first = argument7;

var xx = x1;
var yy = y1;
var inst = noone;
var inst_q = ds_queue_create();

if point_distance(x1,y1,x2,y2) != 0
{
do {
    if abs(y2 - y1) > abs(x2 - x1) {
        if y1 < y2 {
            yy++;
            }
        else {
            yy--;
            }
        xx = x1 + (x2 - x1) * (yy - y1) / (y2 - y1);
        }
    else {
        if x1 < x2 {
            xx++;
            }
        else {
            xx--;
            }
        yy = y1 + (y2 - y1) * (xx - x1) / (x2 - x1);
        }
    inst = instance_position((xx * ts) + ts_h - sign(x1 - x2), (yy * ts) + ts_h - sign(y1 - y2), obj);
    if inst != noone {
        if notme && inst == id continue;
        ds_queue_enqueue(inst_q, inst);
        if first return inst_q;
        }
    }
until xx == x2 && yy == y2;
}

return inst_q;

As a first script submission to the forums (please, be gentle!), I present to you my interpretation of Bresnham's algorithm, in this case used to find one or more instances along an interpolated line. I used this in my Fog of War asset and it works really well and figured that it could be very useful for people. Let me know what you think...

Last edited by Nocturne (2015-03-17 18:26:10)