Indie game storeFree gamesFun gamesHorror games
Game developmentAssetsComics

Simple, Accurate Collision Detection

A topic by Turnaround Games created Mar 03, 2019 Views: 1,881 Replies: 4
Viewing posts 1 to 3
(1 edit) (+1)

The general advice when making games is to use existing tried and tested libraries as much as possible. The idea is that you can then focus on the actual game rather than its implementation. However, I've always found it much more fun to create things from scratch, so I do :)

I recently made Amazeballs, a game where you shoot paintballs in an invisible maze in order to navigate yourself to the exit. For this game I needed a 2D collision detection system.

I have previously used a system of having axis-aligned bounding boxes (“hitboxes”) associated with every object which can collide or be collided with. When you update an object’s position, you loop through all other objects and see if the bounding boxes intersect. If they do, there is a collision.

For instance, let’s imagine that we had three objects in the world, A, B and C, and wanted to update the position of C. We would calculate the new position of C and see if it intersects with A or B. See below:

In this case the movement applied to C would mean that it interacts with B; therefore, there is a collision.

However this method has one major drawback.

Each time the physics engine updates, it has to calculate the new position of each object and check if it intersects with any of the other objects. The amount by which each object is moved is typically set by the frame rate and given as a “delta time”. Delta time is the number of milliseconds each frame last, often abbreviated to “dt”.

For example, if an object were traveling at 5 meters per second and the screen was updated every 16 milliseconds (60 frames per second) then the object would move 0.08 meters each frame (5 meters per second × 0.016 seconds).

However, if the user had a less powerful machine and could only run the game at 30 frames per second, then the screen would be updated every 33 milliseconds. In this case the same object traveling at 5 meters per second would now travel 0.16 meters each frame (5 meters per second × 0.033 seconds).

This means that if two users, playing on different machines, were to run at a wall, it would be possible for the 60 frames per second user to be blocked, and the 30 frames per second user to pass right through. This is because the new position doesn’t intersect with the wall, and so no collision was detected. This is called clipping.

There are common preventions for clipping. For instance you can dictate that the user’s machine must be able to run the game at a minimum frame rate, and then ensure all walls are thick enough that you cannot clip through them. However, I never really liked that the behaviour of the game could be affected by the user’s machine…

Therefore I used the Amazeballs project to try out an alternative method for implementing collision detection. This time based on line segment intersections.

The player is represented as a single point and the walls are represented as line segments i.e. no longer as boxes.

Now when a player moves, a new movement line segment is created with one end being the player’s starting position and the other end being the potential new position. Then all the walls are looped through to see if this movement line segment intersects with them. If it does, then there has been a collision.

It is now no longer possible to clip through walls!

In the case of low frame rates (large delta time), the movement line segment gets longer, but still intersects with the wall. This means that the collision is always detected. So the game’s physics engine runs exactly the same, regardless of the user’s machine.

Although it wasn’t needed in Amazeballs, this line intersection method can also be extended to objects which have an area. One way of doing this is to bound each object with a series of line segments; just like a hitbox but it doesn't have to be a rectangle. Now when you update the position of an object, you create movement line segments for each of the points of the hitbox. You then see if any of them intersect with the line segments of the other objects hitboxes. And that’s it!

Thanks for taking the time to read this post and I hope at least some of you found it useful / interesting.

If you want to see it in action head over to Amazeballs. It’s a free game which runs in the browser and only takes a few minutes to play :)


Turnaround games

homepage - twitter - reddit

Associated reddit discussions: r/gamedev and r/IndieDev

This really isn't about adressing the hitbox issue that some new people might have problems, your fix is about ways to do things for users who have high FPS and low FPS. What should really be adressing is the game's engine and the game optimize to play for older systems. FPS has nothing to do with hitbox.

You are fundamentally wrong. FPS has everything to do with, well, everything. Games need math to be calculated every frame, the time the frame takes to calculate changes how you perceive the game. For example, if you didn't implement a delta time into your movement code, your character's speed would be frame-dependent, which would make it run slower or faster on different computers.

Same thing goes for collisions. If your computer didn't check for a collision on time, you might get that collision checked after you moved into a wall, which is how you get characters clipping into walls and then being pushed away. This post has a pretty good fix for that.

I recommend you don't criticize people's post when they're trying to help others, unless the information is wrong. But that requires you to double, triple, quadruple check your criticism.  

FPS is the game engine speed, what you thinking is the speed of the character that is not related to the engine of the speed. This is why you think the character is able to do something impossable.  I can test many engines with 1x1 pixel block and the speed of said character will not matter because the hitbox stops it everytime. Only when the engine is poorly made is the reason for character to pass through the 1x1 pixel.

Delta timing is not to be used on all games, frames is also commonly used as this engine runs only in frames: the engine does not make the character slow or faster. Delta timing is just a check based timing event and it has nothing to do with speed of the character.

As i said collision will always stop character/object, the engine only effects the world and it's rules. The clipping has been proven fact of many years of bad angle and size of the hitbox. There is nothing about the character being able to by pass a collision without seeing a mistake in the code.

I suggest you learn more about programing than relaying on engines and plugins, what you see vs what is coded is very different.