GameMaker: Finding collision_line’ point of collision

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.

Looks like this in action:

The code is also 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:

One thought on “GameMaker: Finding collision_line’ point of collision

Leave a Reply

Your email address will not be published. Required fields are marked *