Jump to content

Like
0Likes
Dislike
Using Layers for constant time collision detection and response.


Collision Detection Collision Response 2D
By working in layers, we can have collision detection/response between objects in different layers in constant time with no indexing.

4: Adsense

Introduction


You'll find many other articles online about collision detection, so why write yet another one? First of all, because I want to, and second because I wish that when I was starting do learn this stuff, somebody would have told me that working in layers would make my life so much easier. Collision detection which is the
real topic of the post is only one of the things that is made simple thanks to the layer approach.

Detecting collisions


Dividing your scene in layers is something totally conceptual, you don't "need" to do it. However I find that it makes things simple to divide up your game world into groups of similar objects and to paint and update them independently.

So how is this going to help us detect collisions? Well, thanks to this layered approach, we're going to skip spatial indexing, Separating Axis Theorem, and other things that are all hard to implement correctly.

Let's start with two layers, the first layer contains a monster while the second contains an obstacle.

Since these layers will be drawn independently, we will end up with a bitmap containing our obstacles and one containing the monster. We'll later draw them on screen sequentially

Attached Image: collisionDetecionPost1.jpg

We'll select a restricted number of pixels around the monster to probe the bitmap containing the obstcles on front of him. If a pixel position is not transparent in the "obstacle bitmap" we have collision!

Attached Image: collisionDetecionPost3.jpg

Since the obstacle bitmap acts as a spacial index, we don't need to build one ourselves and since it's a map, the entire operation is constant time.

The probe pixels where crudly set in a semi circle around the monster because it always moves forwards and a circle is a suficient aproximation for this particular 2D game.

Responding to collisions


The probe pixels are set at a specific angle around the monster meaning that based on what probes are activated, we can calculate the collision angle, more or less precisely depending on how many probes we have.

Attached Image: collisionDetecionPost5.jpg

The collision angle is an approximation that we could improve by having more points but again, performance, general apearance and ease of implementation will take priority.

in response to the collision, we want to give the monster a push at an angle which is the reflection of it's speed relative to the collision.

Attached Image: collisionDetecionPost6.jpg

Where the collision response vector is given by:

response = speed - 2(dot(speed, normal)) x normal

Interesting Points


In this example, the monster always move forwards but if the collision angle is at an obtuse angle with the speed vector (something hitting it from behind). we'll need to change the collision response a little. I beleive we can get away with simply inverting the collision normal but I haven't tried it out to be honest.

Another thing to look out for is that the collision response should be at least a little stronger than the force pushing towards the collision, otherwise, the monster would slowly sink into the obstacle.

Conclusion


What I mostly want to share is that viewing and coding your game in layers will give you a lot of flexibility for game development, it's part of building a propper MVC architecture.

About the Author(s)

Software engineer in the geo-spacial industry in Belgium. Game developer hobbyist.

License

GDOL (Gamedev.net Open License)

1 Comments

May 18 2017 05:03 PM
I believe this article is a bit high level and could use more detail (and/or perhaps a sample implementation) on the approach described. It seems to be aimed at beginning developers, but would probably leave them with an idea they may be unable to put into use without further help.

Note: GameDev.net moderates article comments.