(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 asked about for "hitscan" weapons and laser-sights, but has many uses.

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.

Therefore, on first iteration the algorithm checks if there's anything between source point and halfway through. If there is, the algorithm checks between source point and quarter way through. If there isn't, the algorithm checks between halfway through and three quarters way through. After log2(distance)+1 iterations, the exact nearest contact point and instance are discovered.

The code is straightforward, being a literal translation of algorithm outlined:

/// 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, rx, ry;
rr = collision_line(x1, y1, x2, y2, qi, qp, qn);
rx = x2;
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;
r[0] = rr;
r[1] = rx;
r[2] = ry;
return r;

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.

If you add it to your project as collision_line_point, it can be 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.
}

Another thing to note - if you are using GameMaker: Studio 1, enabling "fast collision system" in Global Game Settings helps the performance, as R-Trees are then utilized for spatial collision detection.

And that's it. Have fun!

Related posts:

• GameMaker: collision versus 3d array
• GameMaker: collision_* into array
• GameMaker: line between objects
• GameMaker: Statics and method overriding
• GameMaker: trace/log function with position information