Collision Detection essay

[ChrisShade]

Hello there, I'm new here.

So I have this collision detection essay that I need to write with 2 game engines, I already wrote Unity's portion, and now I need to write another game engine's collision. My friend directed me to GameMaker and someone on the Discord server said to post it here. The question is about a common detection issue of a small object moving at high speeds 'tunneling' through a collider without being detected.

So my questions are,
1. How does GameMaker's collision detection work?
2. What could cause the 'tunneling' issue?
2. What are the approaches to fix the aforementioned 'tunneling' issue?

 

[PhallicSpleen]

gamemakers default collision system doesn't do anything for tunneling. You have to program tunneling solvers from the ground up using trig-type functions as you could find here. https://www.gmlscripts.com/script/Computation/Geometry/ Look into lines_intersect(x1,y1,x2,y2,x3,y3,x4,y4,segment), or even point_in_polygon(x,y,polygon). Then you can look up any video lecture where programmers talk about tunneling and just transpose from whatever language, (most likely C++), to game maker... its the same logic.

 

[ChrisShade]

When you say program tunneling solvers, as in programming the trig-type functions to solve the tunneling problem where a small object moving at high speed would be on one side of the collider in one frame, and on the other side of the collider in the next without being detected?

 

[Yal]

gamemakers default collision system doesn't do anything for tunneling. You have to program tunneling solvers from the ground up using trig-type functions as you could find here. https://www.gmlscripts.com/script/Computation/Geometry/ Look into lines_intersect(x1,y1,x2,y2,x3,y3,x4,y4,segment), or even point_in_polygon(x,y,polygon). Then you can look up any video lecture where programmers talk about tunneling and just transpose from whatever language, (most likely C++), to game maker... its the same logic.

Trigonometry is a bit excessive, you can use collision_line to check the movement vector for collisions... for simple bullets a single line might be enough, for larger shapes you could use 4 (one line for each corner of the bounding box).

 

[Hyomoto]

The "tunneling" problem is also referred to as the bullet through paper problem. At least, that's how I learned about it. I haven't heard of it described as tunneling, so if you haven't heard of my term for it, that might help with Google searches.

To clarify a bit of what has been posted, the problem is complex but hardly GMS-specific. The problem occurs when you test whether a location is free as a basis for movement. It the object is moving quick enough, the thickness of the "walls" isn't the issue here (having sufficiently thick walls can prevent it, and thinner walls are more susceptible, but the issue isn't a function of the wall), then that test will be beyond the solid object and seen as free. This is a fairly common speed running trick, and one of the more notorious examples is Super Mario 64's parallel dimensions.

So, how to solve? Ironically, Mario does try to solve this issue: it's just any system may fail if speed is sufficient. The bullet through paper problem is fairly benign, you could test along a vector in increments small enough to avoid the clipping issue. That's what Mario does: it makes three tests along the movement vector. The glitch in Mario occurs because they build up speeds that move so far in a single frame they can pass through multiple parallel dimensions. It's ridiculous and frankly not much worth worrying about. Capping Mario's speed solves the issue (as later revisions did). Other wall piercing tricks occur because of overlapping boundaries between floors and ceilings. Those aren't quite the same problem: Mario moves through the ceiling, but it's for a different reason than speed.

Of course that's just Mario and I'm just demonstrating that the issue isn't GMS or Unity specific. As was mentioned, GMS doesn't handle this issue, the programmer will have to. As has been suggested, a potential solution in GMS specifically is to use collision_line() which could be thought of as casting out a ray and checking for collisions along it. If you did that from the four corners of your object you would know if a collision occured. I believe you can even sort the list by distance now, so you can check which corner a collision occured on easily. A bit expensive potentially, but workable. The Mario solution is also possible, instead of testing the final location of a movement, break it down into increments and test several times along that vector. The simplest solution is just to avoid thin walls. If your thinnest wall is thicker than your max movement speed then the issue shouldn't be able to occur. Tricky players might find as a way, but if the fastest the player can move is three pixels per frame then walls that are four pixels wide will should never have this issue. At least not in general gameplay.

As a nice little aside, if you ever wondered why the death plane exists (a z position below which the player dies or is teleported back to safety) it's a naive solution to the problem. Even really good protection and detection may fail, so developers often put in a "catch all" at the bottom of the world just in case.

 

[Yal]

This is a fairly common speed running trick, and one of the more notorious examples is Super Mario 64's parallel dimensions.

Actually, parallel dimensions is caused by the game using both 16-bit and 32-bit ints at once for object coordinates, so the low-precision coordinates used for level geometry are overflowed if you go far enough out of the bounds of a level (causing the level data to repeat infinitely and report collisions) while the high-precision coordinates used for objects correctly represent that you're too far away to collide. This is why some things stop existing in the parallel universes while others still are interactible.

(Of course, you can only get into the parallel dimensions by abusing the BLJ glitch to build up unintended massive speeds, which is what lets Mario clip through walls)


Mariokart 64 definitely has wall-collision issues that can be abused, though, and this video goes in-depth with exactly how and why they're broken:

One of the most interesting aspects is that wall collisions are always checked using an axis-parallel coordinate comparison ('cuz, you know, rectangles are just easier), so hitboxes get deformed the more diagonal a wall is. If two walls align just right, there's a large chunk in the corner where there's simply no hitbox at all, making it much easier to clip through a wall.

Mariokart Wii also has an interesting bug where collisions with walls and ground are treated differently (walls will always make you bounce off proportional to your current speed, while you smoothly land on ground), and this can be used when terrain incorrectly was assigned the wrong type... "horizontal walls" (looks like ground but collides like walls) are innocuous geometry that acts as bounce pads:

Re death planes, Dark Souls 1 is an interesting case that has three types of death planes: normal ones that instantly kill you (used for bottomless pits) and "deterred" death planes where you're marked as dying from fall damage the next time you touch ground (they're used for cases where the fall damage formula normally wouldn't kill you, but you'd somehow break the game if you COULD survive the fall - most notably they're used around the Bell Gargoyles arena so you can't run away from the boss by dropping to the floors below). But both of these are hitboxes, so it's possible to get around them and fall infinitely; the third and final type of death plane is a failsafe that kills you if you fall for a certain amount of time, even if you didn't actually land on something. (It's actually a pretty good solution, since some of the slippery geometry lets you softlock yourself into an infinite fall-slide you can't get out of - some other games like Zelda: Wind Waker lets you actually softlock the game this way while in Dark Souls you will die even if you're stuck)

 

[ChrisShade]

Another question for my essay is on how to optimise your game engine performance in detecting collision among game objects. Some of the aspects (but not limited to) in this optimisation can be in terms of the responding time, computational power, resources used, etc.

Any ideas come to mind? This part is more general and not limited to GameMaker.

 

[Yal]

The two big techniques used to optimize computations are "do them less often" and "do them with less precision".

"Less often" examples:

• Split objects up in batches based on proximity and only check collisions on a per-batch basis
• Only check collisions when you are moving
• Don't check for collisions every update frame

"Less precision" examples:

• Using rectangle hitboxes or point/radius checks whenever you can get away with it
• Do a simple check first and then a more complex one later if you need the precision (e.g. see GM's bounding box / precise collision duality)
• Use fewer larger hitboxes if you don't need more precision (e.g. a large invisible marker for cutscene or area transitions is often good enough, even if there's a small risk players can bypass it at the seams)