Manual Content: Collisions overlap by up to 0.5 pixels, which should be explained better why this is so

[JonathanHackerCG]

Description

This is an old issue (September 2022) which I am reporting as a new ticket in order to clarify, because it is regularly misunderstood and poorly explained. This ticket is an overview, but the README, sample project, and linked ticket all provide additional context.

The issue is this, excerpt from the documentation:

For two instances to be in collision, their bounding boxes have to overlap. At a pixel level, an overlap is counted when the centre of that pixel is covered.

For example, if you're trying to collide with a bounding box covering the area from (0.0, 0.0) to (16.0, 16.0), the edge of your mask has to touch the area between (0.5, 0.5) and (15.5, 15.5) for a collision to be counted.

While it is documented and apparently considered intended behavior, this overlap is absolutely unacceptable for any projects desiring to render subpixels. Rendering subpixels is an entirely valid use case (a stylistic decision alone), often desired for low resolution games that wish to break the pixel boundaries in favor of smooth movement or flexible scaling or rotation.

When rendering subpixels, this 0.5 pixel overlap is blatantly visible. Furthermore, the behavior is very nonintuitive, leading to completely invisible bugs in games that aren't rendering those subpixels, where the overlap still affects their collisions.

Finally, there is no good explanation for WHY this behavior is intended, nor any official or simple workarounds. This makes subpixel rendering combined with even the most basic collision code a nearly insurmountable challenge for new GameMaker programmers.

For evidence of the severity of this problem, please consult this original ticket, as well as the following forum threads containing the issue (and the difficulty within to identify and explain the problem).

• https://github.com/YoYoGames/GameMaker-Bugs/issues/5098
• https://forum.gamemaker.io/index.php?threads/how-do-people-make-low-resolution-games-in-gamemaker.114220/
• https://forum.gamemaker.io/index.php?threads/im-so-frustrated-with-subpixel-collisions-my-collisions-arent-working.113831/
• https://forum.gamemaker.io/index.php?threads/understanding-bounding-box-being-off.113837/
• https://forum.gamemaker.io/index.php?threads/problems-with-move-and-collide-function.112816/

Steps To Reproduce

1) Create a box above a floor. 2) Cause the box to "fall" to collide with the floor using move_and_collide(0, 2, obj_floor); 3) Print/draw the coordinates of the box, and observe that its resting position overlaps with the floor.

OR Run the attached project (can extract the .yyz). Observe that at any different speed, either the blue box (move_and_collide) or the teal box (place_meeting) will overlap the floor by up to 0.5 pixels.

Which version of GameMaker are you reporting this issue for?

IDE v2024.6.2.162 Runtime v2024.6.1.208

Which operating system(s) are you seeing the problem on?

Windows 10.0.22631.0

Which platform(s) are you seeing the problem on?

Windows

7035ae02-06f3-4953-9902-33580ac3f7dc

README.txt

[JonathanHackerCG]

The orange box in the sample project is using my custom move_and_collide_subpixel which works by directly comparing the bounding boxes. This function works as intended, at least in this test case. It may be a suitable workaround for others with this issue, as well as a reference for GameMaker to improve the native behavior.

/// @func move_and_collide_subpixel
/// @desc Subpixel perfect replacement for GM's move_and_collide.
/// Works directly off of bounding boxes instead of pixel centers.
/// Only works for rectangular collision masks. Slower than native collisions.
/// @arg    {Real} dx
/// @arg    {Real} dy
/// @arg    {Asset.GMObject|Id.Instance} object
function move_and_collide_subpixel(_dx, _dy, _obj)
{
    var _xinit = x;
    var _yinit = y;
    #region Horizontal
    var _max_dx = bbox_right - bbox_left;
    var _num_dx = abs(_dx) / _max_dx;
    if (_num_dx > 1)
    {
        _dx /= _num_dx;
    }

    repeat (ceil(_num_dx))
    {
        if (_dx != 0)
        {
            if (_dx > 0)
            {
                var _inst = instance_place(ceil(x + _dx), y, _obj);
                if (instance_exists(_inst))
                {
                    _dx = min(_dx, _inst.bbox_left - bbox_right);
                }
            }
            else
            {
                var _inst = instance_place(floor(x + _dx), y, _obj);
                if (instance_exists(_inst))
                {
                    _dx = max(_dx, _inst.bbox_right - bbox_left);
                }
            }
            x += _dx;
        }
    }
    #endregion
    #region Vertical
    var _max_dy = bbox_bottom - bbox_top;
    var _num_dy = abs(_dy) / _max_dy;
    if (_num_dy > 1)
    {
        _dy /= _num_dy;
    }

    repeat (ceil(_num_dy))
    {
        if (_dy != 0)
        {
            if (_dy > 0)
            {
                var _inst = instance_place(x, ceil(y + _dy), _obj);
                if (instance_exists(_inst))
                {
                    _dy = min(_dy, _inst.bbox_top - bbox_bottom);
                }
            }
            else
            {
                var _inst = instance_place(x, floor(y + _dy), _obj);
                if (instance_exists(_inst))
                {
                    _dy = max(_dy, _inst.bbox_bottom - bbox_top);
                }
            }
            y += _dy;
        }
    }
    #endregion
    return (_xinit != x || _yinit != y);
}

[yerumaku]

In fact, such problems are solved by rounding coordinates after operations on coordinates. Your calculated coordinates should be separate variables, and the coordinates of the objects should be a rounding of these calculated ones.

You can also render the game into a small surface, which you can then stretch and draw into the surface of the application.

In GameMaker, you need to write additional functions and add additional variables, and using built-in variables should be very careful. For pixel games (and for others too), it is advisable to round coordinates and scale through surfaces and cameras.

By the way, if you round the coordinates only when rendering, then you can also get artifacts.

[yerumaku]

move_and_collide_subpixel

Go to a special community discord and post your solutions there. https://discord.com/channels/724320164371497020/1047095400278020136

[jackerley]

I apologise if you feel that the reasoning for the collision rules haven't been satisfactorily explained. Let me try and provide some of the reasoning.

Firstly, if we treat the bound box as being the full size i.e. for a 16x16 sprite at x,y a bound of [x,y,x+16,y+16] and we have another instance at x+16,y with a bound of [x+16,y,x+32,y+16] then visibly these two sprites won't overlap, but if we do a bound overlap test then we get overlaps occurring due to floating point inaccuracies, whereas visibly there is no overlap. Previously we treated the bound as being [x,y,x+15,y+15] which would avoid any overlap but would lead to any collision check at [x+sprite_width-0.5,y] failing. This was attempted to be handled by the runner internally by extending the bound when performing the collision test, but this led to false results when scaling and rotation were added in. (You can go back to this behaviour by enabling Collision Compatibility Mode if you prefer)

Secondly, if you are using precise collisions, these are only evaluated at pixel centres, first a bound box check is used to exclude any non-overlapping bounds and then collisions are checked at pixel centres. Enforcing the rule that rectangle collisions only occur if they cross a pixel centre means that our precise and rectangle collisions will avoid any inconsistencies between the two methods and mean that a rectangle bound will behave the same whether it is a wxh solid or a precise mask that fills wxh.

The only reason that you are seeing an issue in your sample project is that you are using a camera at 160x90 and then using a view of 1280x720 to view it at, this means that your collision calculations are being done in the 160x90 space but you're then rendering at 1280x720 so you see "subpixel" differences that would otherwise not be visible. If you change to actually rendering at 160x90 by resizing your application surface, you'll see that no overlap is visible. Of course the movement of the boxes will be more stepped if you are then rendering at 1280x720 as the resolution is less. The alternative is to make your camera cover 1280x720 which then keeps the smooth movement, but will require some scaling.

I hope this helps to explain why the rules are there even if they at first seem mathematically wrong.

Fritz

[KingDevyn]

Firstly, if we treat the bound box as being the full size i.e. for a 16x16 sprite at x,y a bound of [x,y,x+16,y+16] and we have another instance at x+16,y with a bound of [x+16,y,x+32,y+16] then visibly these two sprites won't overlap, but if we do a bound overlap test then we get overlaps occurring due to floating point inaccuracies, whereas visibly there is no overlap.

I'm sure I'm missing something, but what do floating point inaccuracies between two 16x16 sprites with bouds of [x,y,x+16,y+16] and [x+16,y,x+32,y+16] have to do with the scenario? Shouldn't the value of the right side of the bounding box (x+16) be compared with the left side of the other bounding box (x+16) and evaluate (x+16) <= (x+16) to return that there is no collision? This arithmetic works in GML. It's not clear in the given explanation why similar arithmetic couldn't be applied for the bound overlap test.

[jackerley]

For a good explanation of floating point maths comparisons take a look at https://embeddeduse.com/2019/08/26/qt-compare-two-floats/

[KingDevyn]

For a good explanation of floating point maths comparisons take a look at https://embeddeduse.com/2019/08/26/qt-compare-two-floats/

Sorry if it wasn't clear, I know how floating point inaccuracies work. My question was, what do they have to do with the aformentiomed scenario? Are you suggesting the value represented by 'x' in both bounding boxes were actually two different values that were approximatly equal? If that's the case, why introduce a new bug to hotfix well known and documented float rounding errors? The hotfix in that case doesn't offer a reliable collision check at half pixel precisions either.

Is it a matter of the epsilon needing to be set to 0?

[JonathanHackerCG]

I was on vacation, so didn't get a chance to reply. I have several questions/clarifications. Furthermore, please understand, I am not asking for clarification or additional documentation, I am arguing this behavior is incorrect and should be changed.

The alternative is to make your camera cover 1280x720 which then keeps the smooth movement, but will require some scaling.

Just so I understand, the recommended solution to preserve my desired art style is to independently scale all of the sprites? Understand that (1) doing that programmatically renders the room editor useless (2) doing that with the assets prevents using more than one scale factor and is also an incredible unnecessary overhead.

I understand that the 0.5 pixel overlap covers up floating point inaccuracies and preserves consistency between precise collisions and other types. My complaint is this: that is only true if the minimum desired visual distance is 1 pixel. The permitted overlap should actually be generalized as 1/2 of the minimum desired visual distance. In my example that is 0.25 pixels visual distance for a collision overlap of 0.125. This is an art style choice that should not be restricted by an unchangeable engine behavior.

Potential Solutions

• Allow users to specify the permitted collision overlap to any value, similar to setting epsilon.
• Allow users to set the resolution/scale of collision masks separate from sprites.
• Add another collision mask type for only rectangular collisions that don't care about matching pixel-precise collisions.
• Add another collision function that can detect instance bbox_coordinates directly (similar to my workaround code above).

If any of those solutions seem feasible, I am happy to write a more detailed separate feature request.

[KingDevyn]

@jackerley Sorry to bother, but from the described scenario it's not logically clear how floating point math comparisons have to do with the scenario this collision system seems to be trying to fix. Is there a reasoning for these collision rules? I've reviewed your comments a couple of times now and I think you might be mistaken on the math. Either that or the explanation is incomplete, but the only extrapolation I've been able to land on of the given scenario still doesn't math out. Granted none of us are owed an explanation, but I think it might be worth your time to review the logic that led you to believe this collision system was a solution to some problem.

For me personally this collision system's inconsistencies at a subpixel level have been the source of several misalignment bugs and I'd urge you to reconsider if the cost of allowing some subpixel overlaps to not be considered collisions is worth the trouble for the developer. Has the situation you were trying to explain been a thorn in the side of more developers than thorns introduced if collisions were geometrically consistent with their bounding box values? Does this system remove all the thorns it seeks out to remove, or only some of them at a surface level? And how easily removed are the thorns it removes on the dev side compared to the new thorns it creates under the current collision system?

Developers can round their instance's movements to the nearest 1/(2^x)th of a pixel if they want to avoid floating point rounding errors affecting their collisions (float errors still affect collisions in the current system by the way, allowing slight bbox overlaps doesn't stop this, which is part of why I'm confused about the situation you tried to explain earlier). Alternatively, if bbox values in the sprite editor could be set to floats for rectangle collisions, devs could also set collision boxes to half a pixel smaller on each side to simulate a similar behavior to the current system. It just feels so wrong to me that an 4 pixel wide mask can pass through a 3 pixel wide gap. Please think about that scenario and ask yourself if whatever this behavior is trying to fix is worth breaking the fundamentals of geometry like that among other ways.