Comparing 2D Collision Detection and Hit-Testing Approaches in Godot 3

null

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

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.

The gap between initial position and next position is never checked with naive collision detection.

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!

At regular speeds, nothing weird happens
At higher speeds, the KinematicBody2D area collision detection works like a charm while the Area2D approach already skipped a lot on the ground

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.

At speeds where the player moves from one edge of the screen to the next in a split-second, even the KinematicBody2D hit detection shows problems

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.

Play the demo
Check out the code on GitHub

Receive new .