Raycasting in GameMaker Studio 2 to implement hitscan weapons?

Question

I'm working on a 2D top-down shooter game in GameMaker Studio 2, featuring different weapons and obstacles all around the levels.

Since I don't need a high degree of simulation, I'm implementing simple physics for character movement and interaction (e.g. weapons, bullets, doors...) myself via GML rather than using the dedicated physics library.

Currently, shooting works as follows:

• The player presses the Left Mouse Button.
• A bullet object spawns, according to the current weapon.
• The bullet starts moving towards the mouse position at a given velocity.

Right now, the gameplay works quite well. However, I wanted to create different weapons with unique features, including different bullet speeds. And here's my problem.

I tried to increase bullet velocity values, but they started behaving strangely: When shooting against objects, hits occur slightly before visual contact. Sometimes, bullets 'warp' beyond small objects or corners as if a collision hasn't been detected at all.

There are two schematics, one for the general case:

And one for the collision with thin objects:

I think this is due to my code checking for collisions for given positions rather than sweeping along the expected motion trajectory. And, this doesn't work well with laser weapons and sniper rifles, since players expect them to be precise when shooting.

My initial implementation was the following:

Create Event:

b_damage = 25;
b_velocity = 100;
b_direction = point_direction(x, y, mouse_x, mouse_y);

Step Event:

var _xvel = lengthdir_x(b_velocity, b_direction);
var _yvel = lengthdir_y(b_velocity, b_direction);

var _coll = instance_place(x + _xvel, y + _yvel, obj_CollisionParent);

if ( _coll == noone )
{
    // No collision occurred, bullet can travel
    x += _xvel;
    y += _yvel;
}
else
{
    // Destroy bullet (shows sparks)
    instance_destroy();
    // Deal damage if an enemy was hit
    if ( _coll.object_index == obj_Enemy )
    {
        scr_DealDamage(_coll, b_damage);
    }
}

I then tried to increase precision by subdividing the collision check into smaller steps:

Step Event:

var _xvel = lengthdir_x(b_velocity, b_direction);
var _yvel = lengthdir_y(b_velocity, b_direction);

var _coll;
var _steps = 10;

for (var i = 0; i < _steps; i++)
{
    _coll = instance_place(x + _xvel/_steps, y + _yvel/_steps, obj_CollisionParent);

    if ( _coll == noone )
    {
        // No collision occurred, bullet can travel for 1/_steps distance
        x += _xvel / _steps;
        y += _yvel / _steps;
    }
    else
    {
        // Destroy bullet (shows sparks)
        instance_destroy();
        // Deal damage if an enemy was hit
        if ( _coll.object_index == obj_Enemy )
        {
            scr_DealDamage(_coll, b_damage);
        }
    }
}

Now, collision is more precise, yet it's far from perfect. I still cannot use high velocity values without increasing the number of _steps. Also, 100 collision checks per step for dozens of bullets seem too much for my CPU. I would like to improve this aspect of my game.

I would like to use a raycast-like function, similar to Unity's Physics.Raycast. I need to find the final impact position with a low computational effort so that I can make bullets travel instantly, draw impact particles at the right position, and show realistic bullet trails.

Answer 1

Without using a physics library, collision check works the old way: collision masks.

These are binary images, which GMS uses to perform collision checks between two instances at a time. If they overlap (i.e. if pixels from both images align), then a collision occurs. Since this approach is pixel-based, there are no vectors to work with, and we cannot define an actual raycast function–there's no such a thing as a 'ray' in pixel world!

'Pixel-casting'

Despite the above issues, we can exploit the collision check system and some maths to find a way to approximate a solution to the problem:

Given a distance and a direction, find the closest contact point against some objects.

In the past, YoYo Games provided some sample code in GMSX demos and different blog articles (such as this one). There's a function using collision_line() to compute the first contact along a segment. It is intended to be saved as a Script and called via GML. We can re-write it as follows:

// Internals
var xfrom = argument0;
var yfrom = argument1;
var xto = argument2;
var yto = argument3;
var obj = argument4;

// Probing distance
var dx = 0;
var dy = 0;

// Get the first hit
var first_instance = collision_line(xfrom, yfrom, xto, yto, obj, true, true);

// If hit, find the exact hit point
if (first_instance != noone)
{
    // Init probing distance
    dx = xto - xfrom;
    dy = yto - yfrom;
    // Start the search algorithm down to the pixel level
    while ( (abs(dx) >= 1) || (abs(dy) >= 1) )
    {
        // Bisect the probing distance
        dx /= 2;
        dy /= 2;
        // Check along the new collision line
        var instance = collision_line(xfrom, yfrom, xto - dx, yto - dy, obj, true, true);
        // If something is hit, keep track of it and reduce the total distance to check for
        if (instance != noone)
        {
            first_instance = instance;
            xto -= dx;
            yto -= dy;
        }
    }
}

// Set return array
var return_array = array_create(3, -1);
return_array[0] = first_instance;
return_array[1] = xto - dx;
return_array[2] = yto - (dy * 2);
return return_array;

Results:

This function implements a form of bisection method and adapts it to find the best solution. It ensures it will stop since it either finds no collision or a collision within a geometric constraint (the pixel-level size of our probing distance). It works as follows:

• The whole distance (xfrom, yfrom)⟶(xto, yto) is checked for collisions. If none is detected, the function returns the special object noone.
• If a collision occurs, the best approximation must be found.
  • During the first loop, it checks for collisions in the first half of the line, (xfrom, yfrom)⟶(xto - dx, yto - dy). This is because it first assigns values to dx and dy, and then divides them by 2, therefore finding the distance from the midpoint of the line.
  • If a collision occurs, it occurred in the first half of the line (thus, the first quarter of the original line, starting from (xfrom, yfrom)). Else, the initial collision occurred in the further half of the line, then it must look for it beyond the line midpoint. This is done by keeping the current dx and dy and re-assigning values for xto and yto.
  • Continue the search by subdividing the probing distance, until both its components go below 1, i.e. we reached the pixel-level precision.
• Return an array containing the latest object detected, and the X and Y coordinates (in room space) where the line intersected its collision mask.

Considerations

I tested this function under different conditions and found out that it typically converges, and finds a 'correct' solution, within 10 to 20 loops. If you double the check distance, you may need only one additional iteration, since you're splitting in half the total distance at each iteration.

Additional code can be added to include an upper limit to the number of total iterations:

var max_loops = 10;
var loops = 0;

...

while ( ( (abs(dx) >= 1) || (abs(dy) >= 1) ) && (loops < max_loops) )
{
    ...

    loops++;
}

...

While this ensures halting within a max number of cycles, it doesn't guarantee the solution found is acceptable, if a good approximation is what you need.

Finally, there are some edge cases in which the function returns the right object but the wrong collision point (that is, slightly further from the expected position):

This is due to the discrete nature of pixels, and especially rasterization. When reducing the collision line length, its original orientation isn't necessarily preserved and its pixels may move slightly around. This is likely due to the line-drawing algorithm GMS uses to draw pixels, whose implementation we don't know.

But, this is a minor inconvenience that is unlikely to occur (or to be noticed, at least) during a fast-paced shooting game. If need be, such a glitch could be concealed with appropriate use of graphic effects such as sparks or smoke. :)