2D Collision Detection System

 

Introduction

This article describes how to detect collisions between various objects in 2D environment. I created this collision detection system 2 years ago to use it in the game engine I'm currently developing. Programming is my hobby - I'm not a professional developer and I'm not familiar with all the technologies existing in the game physics and maybe that's why I've never seen such a collision detection method like mine. I suppose there is already such a collision detection system but I didn't found it yet, so please if you know articles that describe a similar collision detection method, please let me know. Also, I'll be very glad to hear your opinion and suggestions about my 2D collision detection method. Thank you.
The archive attached to this article contains a demo program that shows some of the abilities of my collision detection system. Run 'Rust_Engine.exe' executable in order to start the demo application. Here is some description how to use the demo application:

Keys

• E - create object
• W - move object
• Del - delete all objects

Mouse

• Middle Button Click on object - delete current object
• Single Left Click on object - select the current object
• Double Left Click on object - select all objects
• Single Right Click on object - opens the properties of the current object
• Single Click on the playground - deselect all objects

Rust Engine demo also presents sound manipulation, animation, texture supporting, sorted drawing (isometric projection) and Act - React system, but anyway these things are not in the interests of this topic, maybe I'll explain how to create such interesting things another time :). Note that the used language is VB.NET, but the described method is universal and can be written in all languages in the Visual Studio family.

Background

Instead of using only objects coordinates to detect a collision, my collision detection system will show you how to use mostly the playground as a source of information whether there is an object on the field or not. The collision detection method I'm about to explain doesn't need to know the exact count of objects in case of detecting collisions. Now imagine that your standing on the tiles in your bathroom. How many tiles are there under your feet? Let's suggest that there are 4.


Now let's think about this bathroom tiles as the pixels of your game world playground. Let's associate an integer array to all the pixels in your playground. To do that, we could declare an array like intWorldArr(224) As Integer. If we have playground 15 x 15 pixels then our array will contain 225 elements, one element for each pixel. And if we have an object that is 2 x 2 pixels, our object will occupy 4 pixels of the playground. If each pixel corresponds to an element into the integer array that represents the playground - intWorldArr(224) - then how to find that element the pixel refers to. It would be stupid to iterate through all 225 elements in case we need to find the element we need. To solve this problem, we will use the coordinates of the pixel and another integer array of which count of elements will be equal to the height of our playground - 15. So, we will declare another integer array - something like intStartNum(14) As Integer. Now look at the picture below - you can see that the numbers of the pixels in the first vertical column from left are colored in green. These green numbers are the values of each element in intStartNum(14) array. The first element has value 1, the second has value of 16 and so on each value grows with 15 (width of our playground) till it reach 211. Let's take a look at the purple object - its coordinates are x = 9 , y = 9 and its size is 2 x 2 pixels. Let's give a name to this object, for an example 1. Object 1 is placed on 145, 146, 160 and 161 pixel of our playground. So Object 1 will write its name into 145, 146, 160 and 161 element of intWorldArr:

Hide   Copy Code

intWorldArr(145) = 1
intWorldArr(146) = 1
intWorldArr(160) = 1
intWorldArr(161) = 1

That's how Object 1 will inform other objects about its presence. Looks good but how to find the number of the pixel that Object 1 stands on? Here comes to help us the second integer array intStartNum(14). If you already noticed in the picture below - adding the x coordinate of some pixel to the green number of its y coordinate will return the number of the pixel you are looking for. For an example Object 1 has coordinates x = 9, y = 9. To find the element into intWorldArr that corresponds to that location, we can do this simple task (objPrpl will be the purple object from the picture below):

Hide   Copy Code

intWorldArr(objPrpl.x + intStartNum(objPrpl.y)) = 1

This operation also assigns the name of the objPrpl into 145 element of intWorldArr. Now detecting collision between two or more objects is a piece of cake. You can use 0 for passable areas - if your object "see" that there is 0 or its name "into" the pixel he wanted to move, the movement will be allowed, if there is another number in the pixel in front of our object, the movement will be forbidden.



Let's now make a summary of all that was shown above:
1^st: You need to make an integer array (intWorldArr) the size of which would be equal to the count of pixels in your playground.
2^nd: Create another array (intStartNum) the size of which will be equal to the height (in pixels) of your playground. intStartNum will contain the first numbers of all pixels in the first left column of playground field - see the first picture above.
3^rd: Create an array that will hold all your objects (objects array). It is very important that the name of each object be equal to its subscript in the objects array - this will help you to determine which of your objects collide and take proper action after collision occurs.
4^th: Choose special numbers for your game world. For an example ' -1 ' = passable area. If ' 0 ' is your passable area, then when you assign names to your object, add 1 to avoid of creating one 'ghost' object that will fill the playground with passable numbers - ' 0 '.

Air Units Problem

You may say that this collision detection system is designed for detecting collisions only between ground units, and you're almost right. The biggest problem of this collision detection method is handling with the flying objects. Since there is only one layer of the playground if air unit are standing above ground unit, the positions of the ground unit shall be overwritten by the name of the flying unit above. And the ground unit shall became 'ghost' object and other units will stop notice its presence. To avoid such a confusion, you may add a second playground layer where flying units will move - for an example AirWorldArr(224). I know this is not a very elegant solution because it will lead to more memory consumption, but I'm still working on the problem. Any ideas from you are more than welcome!

Code Example

REM: the method that fills intWorldArr with the name of the moving object:

Sub FillWrldArr(ByVal HeroBody As ObjectBody, ByVal szeWrldSize As Size)

     Dim intStartPos = HeroBody.intLeft + intStartNum(HeroBody.intTop)
     Dim intEndPos = HeroBody.intRight + intStartNum(HeroBody.intTop)

     For i = 0 To HeroBody.intHeight
        For i2 = intStartPos To intEndPos
            intWorldArr(i2) = HeroBody.intName
        Next
            intStartPos += szeWrldSize.Width
            intEndPos += szeWrldSize.Width
      Next
 End Sub