(mouseover/click to play GIF)

This is a small post about a method for figuring out collision_line's "contact point" in GameMaker - in other words, obtaining not just whether there's something on the way, but also the nearest point on the nearest matching entity.

Most commonly desired for "hitscan" weapons and laser-sights, but has many uses.

Theory

The approach is a classic use case for binary search: the built-in function won't return a contact point, but we can call it multiple times, cutting the segment to check in half on each iteration until we have pixel precision.

So, for example, if we've checked and there's an object between the points, we'll check if there's anything between source point and halfway through.

If there is, we'll check between source point and 1/4 way through through next.

If there isn't, we'll check between halfway through and 3/4 way through next.

Each iteration halves the search space and after log2(distance)+1 iterations we have pixel precision.

Code (GM2022+ and LTS)

function collision_line_point(x1, y1, x2, y2, obj, prec, notme) {
    var rr = collision_line(x1, y1, x2, y2, obj, prec, notme);
    var rx = x2;
    var ry = y2;
    if (rr != noone) {
        var p0 = 0;
        var p1 = 1;
        repeat (ceil(log2(point_distance(x1, y1, x2, y2))) + 1) {
            var np = p0 + (p1 - p0) * 0.5;
            var nx = x1 + (x2 - x1) * np;
            var ny = y1 + (y2 - y1) * np;
            var px = x1 + (x2 - x1) * p0;
            var py = y1 + (y2 - y1) * p0;
            var nr = collision_line(px, py, nx, ny, obj, prec, notme);
            if (nr != noone) {
                rr = nr;
                rx = nx;
                ry = ny;
                p1 = np;
            } else p0 = np;
        }
    }
    return [rr, rx, ry];
}

The script returns an array containing hit instance ID as element 0, hit point X as element 1, and hit point Y as element 2. If there are no matching instances between points, instance ID is set to noone while hit point XY are set to destination point.

It's used as following:

var r = collision_line_point(x, y, mouse_x, mouse_y, obj_some, true, true);
draw_line(x, y, r[1], r[2]);
if (r[0] != noone) {
    // r[0] holds the nearest (hit) instance.
}

Code (GameMaker: Studio)

Note: enabling "fast collision system" in Global Game Settings helps a bunch - that makes GM use R-Trees for collision checking instead of picking through all of the instances each time.

/// collision_line_point(x1, y1, x2, y2, obj, prec, notme)
var x1 = argument0;
var y1 = argument1;
var x2 = argument2;
var y2 = argument3;
var qi = argument4;
var qp = argument5;
var qn = argument6;
var rr = collision_line(x1, y1, x2, y2, qi, qp, qn);
var rx = x2;
var ry = y2;
if (rr != noone) {
    var p0 = 0;
    var p1 = 1;
    repeat (ceil(log2(point_distance(x1, y1, x2, y2))) + 1) {
        var np = p0 + (p1 - p0) * 0.5;
        var nx = x1 + (x2 - x1) * np;
        var ny = y1 + (y2 - y1) * np;
        var px = x1 + (x2 - x1) * p0;
        var py = y1 + (y2 - y1) * p0;
        var nr = collision_line(px, py, nx, ny, qi, qp, qn);
        if (nr != noone) {
            rr = nr;
            rx = nx;
            ry = ny;
            p1 = np;
        } else p0 = np;
    }
}
var r = array_create(3);
r[0] = rr;
r[1] = rx;
r[2] = ry;
return r;

Code (GameMaker 8.x)

Can't return arrays in vintage GM versions so the script stores the coordinates in a pair of global variables.

/// collision_line_point(x1, y1, x2, y2, obj, prec, notme)
var x1; x1 = argument0;
var y1; y1 = argument1;
var x2; x2 = argument2;
var y2; y2 = argument3;
var qi; qi = argument4;
var qp; qp = argument5;
var qn; qn = argument6;
var rr; rr = collision_line(x1, y1, x2, y2, qi, qp, qn);
var rx; rx = x2;
var ry; ry = y2;
if (rr != noone) {
    var p0; p0 = 0;
    var p1; p1 = 1;
    repeat (ceil(log2(point_distance(x1, y1, x2, y2))) + 1) {
        var np; np = p0 + (p1 - p0) * 0.5;
        var nx; nx = x1 + (x2 - x1) * np;
        var ny; ny = y1 + (y2 - y1) * np;
        var px; px = x1 + (x2 - x1) * p0;
        var py; py = y1 + (y2 - y1) * p0;
        var nr; nr = collision_line(px, py, nx, ny, qi, qp, qn);
        if (nr != noone) {
            rr = nr;
            rx = nx;
            ry = ny;
            p1 = np;
        } else p0 = np;
    }
}
global.collision_line_point_x = rx;
global.collision_line_point_y = ry;
return rr;

And that's it. Have fun!

Related posts:

• GameMaker: collision versus 3d array
• GameMaker: collision_* into array
• GameMaker: line between objects
• screen_redraw in GameMaker: Studio
• GameMaker: Custom pseudorandom number generators!