Comparing 2D Collision Detection and Hit-Testing Approaches in Godot 3
I played around with Godot and found that when my player character moved too fast, it would not collect items in its path.
Here’s a short visual comparison of two approaches to move things in an engine like Godot. If you don’t know Godot: it is an engine, tool, and IDE to create cross-platform 2D and 3D games and GUIs. It’s basically Unity, but open source.
This is a classic hit test/collision detection problem. In the past, the game prototypes I programmed myself were rather simple and slow-paced, so I thankfully never encountered this problem before, because it requires a couple of tricks if you have to program the engine yourself.
Play the demo
Check out the code on GitHub
Update 2022-04-26: Thanks to my good friend Daniel, who is much smarter than I ever will be, I compared the results from Godot 3.2 (from 2020, at the original time of this post) with Godot 3.4.4 (latest version as of today). Godot 3.2 produces the same different results you can see in the videos here. But with Godot 3.4.4, there’s no difference anymore. Both behave the same!
Using Area2D and manual hit detection
My naive approach in Godot was to make the player an Area2D with a collision shape and change its position according to player input. This combination will fire events (aka “signals” in Godot parlais) when other objects enter and leave the area. I got this approach from the “Your First Game” tutorial and was happy to roll with it as I initially found the plethora of 2D nodes I could select overwhelming.
Here’s a simple back-of-the-envelope calculation to illustrate the problem: Your character starts at position (x=0, y=0). Say it’s 10x10 pixels large, and your collision detection uses this size relative to the position to see what the character is interacting with, so the covered rectangle is (min_x=0, min_y=0, max_x=10, max_y=10). You now move it to the right at a pace of 100 pixels per frame. In the next frame, the covered rectangle now is (min_x=100, min_y=0, max_x=110, max_y=10). That’s basically a jump. You skipped over the whole area from (x=11, y=0) up to and including (x=99, y=10).
That is how you can clip through walls, and walk over items or through enemies if your speed is too high.
Prevent clipping with KinematicBody2D and Godot’s physics engine
To prevent clipping in Godot, your next best bet is a KinematicBody2D. That’s a 2D shape that participates in Godot’s physics engine calculations. You can apparently get a lot of physics for free, like standing on platforms, sliding down slopes, and letting 2D boulders tumble down and collide with each other and propagate forces. A KinematicBody2D, though, only triggers the calculation callbacks – you have to implements the effects yourself. With a player character that should collect coins and not be deflected by them, this sounds like a good approach!
The transition in code is rather straightforward, too. Instead of the _process callback on every tick, you hook onto the _physics_process callback and use the built-in movement methods to let the Engine do the rest.
Compare the traditional “just change the position” approach with Area2D …
extends Area2D
# -1 for moving left, +1 for moving right
var velocity: float = 0
# Pixel per second
var speed: float = 100
# Built-in callback for key presses
func _input(event: InputEvent) -> void:
self.velocity = 0
if Input.is_action_pressed("ui_right"):
self.velocity = +1
if Input.is_action_pressed("ui_left"):
self.velocity = -1
# Built-in callback for every tick of the game loop.
# `delta` is the fraction of a second.
func _process(delta: float) -> void:
self.position.x += self.velocity * self.speed * delta
… with a physics-based KinematicBody2D:
extends KinematicBody2D
var velocity: float = 0
var speed: float = 100
func _input(event: InputEvent) -> void:
self.velocity = 0
if Input.is_action_pressed("ui_right"):
self.velocity.x = +1
if Input.is_action_pressed("ui_left"):
self.velocity.x = -1
# Built-in callback for physics processing,
# run before the `_process` callback.
func _physics_process(delta: float) -> void:
var velocity_vector = Vector2(self.velocity, 0)
self.move_and_collide(velocity_vector * self.speed * delta)
Both approaches are quite short, and both share a lot of code. These are GDScript node scripts, each attached to a player node in Godot.
The move_and_collide method is described as such:
If the engine detects a collision anywhere along this vector, the body will immediately stop moving.
This is the crucial difference: the engine detects collision along this vector. So the whole space between start and finish is checked, basically.
With this approach, I found I don’t even need to make the coins physics-based objects, since the collision detection events are triggered in the same way.
In this video, you see how an Area2D-based player character triggers collisions with the ground at higher and higher speeds, compared to KinematicBody2D-based characters.
The Area2D variant breaks down as soon as the game loop tick-based updates skip floor tiles; the physics-based approach calculates in-between collisions for much, much longer.
But at much higher speeds, even there you will see this begins to break down.
I wonder if I would have to utilize ray-tracing in Godot to check for collisions along the ray in the direction of the movement. Or maybe there’s a knob I can turn to increase the hit detection accuracy at higher speeds. (It does not help to chop the movement into e.g. 100 steps and call move_and_collide 100 times on 1/100th of the vector. Tried that. I guess the detection happens after the method call.)
If I would have to write this stuff in my own engine, it’d look like this:
// Let's ignore Y-axis and height for the example
struct Space {
let x: Int
let width: Int
}
var playerSpace = Space(x: 0, width: 10)
func moveRight(by speed: Int) {
let old = playerSpace
let new = Space(
x: playerSpace.x + speed,
width: playerSpace.width)
let spaceBetween = Space(
// Start to the right of the old space:
x: old.x + old.width,
// End just before the new space:
width: new.x - old.x - old.w)
playerSpace = new
consumeCoins(in: playerSpace)
consumeCoins(in: spaceBetween)
}
For collision detection that actually puts a stop to player movement, you cannot just set the new position via old.x + speed, but you have to intercept the movement and utilize something like walls(in: spaceBetween).first.x (or .last.x when you move left).
I’ll have to experiment with physics bodies in Godot some more and see if collision detection is 100% accurate even at ridiculous speeds when both objects are physics-based, and not just the player, moving on top of Area2D objects.