Using Layers for constant time collision detection and response.

Published May 18, 2017 by Emeric Beaufays, posted by olgalatepu
Do you see issues with this article? Let us know.
Advertisement

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 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! 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. 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. 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.

Cancel Save
0 Likes 3 Comments

Comments

jbadams
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.
May 18, 2017 11:03 PM
olgalatepu

Alright, that makes sense. I'll try to find some time to improve it then

May 26, 2017 06:04 PM
niu2x

interesting、

 

December 24, 2018 11:08 AM
You must log in to join the conversation.
Don't have a GameDev.net account? Sign up!

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

Advertisement

Other Tutorials by olgalatepu

11787 views
Advertisement