GameMaker: Finding collision_line’s point of collision

Find collision_line's point of collision in GameMaker (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:

12 thoughts on “GameMaker: Finding collision_line’s point of collision

  1. two questions.
    1. Can i get more explanation on which part dose what?
    2. Can i make it check for tiles instead of objects?

  2. I’m beyond stupid. Scratching my head and wondering for hours why the script isn’t working, just to found out I put the code in the step event and not draw event. Thank you so much!

    • For those with latest versions of gm2 (if the script isn’t working).

      function collision_line_point(argument0,argument1,argument2,argument3,argument4,argument5,argument6)
      {
      *script code*
      };

  3. I dunno if you’ll ever see this again but thanks Vadim. This helped me immensely as I was trying to make a light that didn’t penetrate through walls properly.

  4. Hi, sounds good but I still dont get it 100%. I tried it but “collision_line_point” is no valid function. And where do I have to put in the code, in a step event or in script (I´m relative new to GM).
    Is it possible to hand over the gmx file of above shown video?!
    BR
    Timo

    • You add a script called “collision_line_point”, and paste the shown code into it. The demo shown in the GIF was made in GMLive rather than GM itself, so it would likely be a bit less intuitive.

  5. Wonderfully more efficient than what I’ve been doing. This will help a great deal with optimization.

    I’ve been using a for loop, with a direction to check every 4 pixels for 1024 pixels for a grappling hook. This will help a ton with optimization. Thanks c:

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.