Detecting 2D object collisions in the Marmalade SDK

Hello to all! I want to share my experience in developing applications for the Marmalade SDK.

I want to remind you that Marmalade is a great tool for creating multiplatform applications. You can write applications for both LG TVs and mobile devices (based on Android, Bada, iOS, Symbian and Windows Mobile).
In this article you will find:

• the process of creating an application under the Marmalade SDK;
• collision detection of convex polygons using projection construction;
• determination of the reaction to the collision (the withdrawal of the object by the minimum path).

A little preface. Once, for one project, I needed to implement a check for collisions of various objects. And I was very surprised by the fact that, despite the fact that almost no game can do without checks for collision and intersection of objects, it is not so easy to find ready-made solutions and simple examples for such a task. Especially with more or less clear explanations. I had to implement independently.
')
I want to warn you in advance that all the code in the article is written in C ++.

A description of collision checking was found at one of the sites using projection construction. This method is relatively simple and fast enough. Probably the biggest drawback is that it is suitable only for convex polygons. But this problem can be solved by dividing a concave polygon into two or more convex ones.

So let's start with the simple creation of a Marmalade project.

In Marmalade, everything starts with the file mkb, so consider it. Create a file in the project folder test2d.mkb and the source folder. In the mkb file we write the following:

#!/usr/bin/env mkb
files {
[Source]
(source)
main.cpp
entity.cpp
entity.h
}
subprojects {
iw2d
}


In the "files" tag we describe the list of files of our project. We will only have three files that are in the “source” folder (indicated by the contents of the parentheses). In the “subprojects” tag, we will list the Marmalade libraries that we will use. In this case, we only have an ode library for working with 2d graphics.

Create three empty files (main.cpp, entity.cpp and entity.h) in the “source” folder, and then run test2d.mkb. As a result, Marmalade will generate the necessary data for the development environment (in my case, this is the “build_test2d_vc10” folder for Visual Studio), as well as the “data” folder with the project settings.

The project has been created, now let's start writing the code.

The primary task is as follows:

• create several objects on the scene;
• we realize the management of one of the objects (the control will be carried out by the keyboard: arrows - movement, 1 and 2 - rotation);
• We implement a check for collisions of a managed object with the rest of the objects in the scene, as well as provide an adequate response to the collisions.

So, consider the code of the main.cpp file, in which we will perform initialization, create the necessary shapes and objects, implement the main application loop, and also perform data cleansing when the application terminates.

  #include "iw2d.h" #include "iwArray.h" #include "entity.h" #include "s3eKeyboard.h" #include "s3eDevice.h" #include <time.h> #include <s3e.h> #define FPS 30 #define MOVE_SPEED 100 #define OBJECT_DIMENSION 50 /***************************************************************/ int main(int argc, char* argv[]) { s3eResult result = S3E_RESULT_SUCCESS; /*      2D  */ Iw2DInit(); /*    */ uint32 width = Iw2DGetSurfaceWidth(); uint32 height = Iw2DGetSurfaceHeight(); /*    "" */ int wall_size = MAX(width, height); /*    */ CIwArray<CEntity*> arr_objects; /*  3    */ /*    */ CIwSVec2 m_Verts1[5]; CIwSVec2 m_Verts2[4]; CIwSVec2 m_Verts3[4]; /*  1 */ m_Verts1[0] = CIwVec2(-OBJECT_DIMENSION, -OBJECT_DIMENSION); m_Verts1[1] = CIwVec2(OBJECT_DIMENSION, -OBJECT_DIMENSION); m_Verts1[2] = CIwVec2(OBJECT_DIMENSION, 0); m_Verts1[3] = CIwVec2(0, OBJECT_DIMENSION); m_Verts1[4] = CIwVec2(-OBJECT_DIMENSION, OBJECT_DIMENSION); /*  2 */ m_Verts2[0] = CIwVec2(-OBJECT_DIMENSION/2, OBJECT_DIMENSION + OBJECT_DIMENSION/2); m_Verts2[1] = CIwVec2(OBJECT_DIMENSION/2, OBJECT_DIMENSION/2); m_Verts2[2] = CIwVec2(OBJECT_DIMENSION/2, -OBJECT_DIMENSION/2); m_Verts2[3] = CIwVec2(-OBJECT_DIMENSION/2, -OBJECT_DIMENSION/2); /*  3:  */ m_Verts3[0] = CIwVec2(-5, wall_size/2); m_Verts3[1] = CIwVec2(5, wall_size/2); m_Verts3[2] = CIwVec2(5, -wall_size/2); m_Verts3[3] = CIwVec2(-5, -wall_size/2); /*  ,    */ /*  ,     */ CEntity *main_object = new CEntity(CIwSVec2(width/2, height/2), &m_Verts2[0], 4, 0xFFff0000); arr_objects.append(main_object); /*         ,   . */ CEntity *tmp_object = new CEntity(CIwSVec2(width/2, height/2), &m_Verts1[0], 5, 0xFF0000ff); tmp_object->SetAngle(IW_ANGLE_PI/3); arr_objects.append(tmp_object); tmp_object = new CEntity(CIwSVec2(50, 50), &m_Verts1[0], 5, 0xFF0000ff); tmp_object->SetAngle(IW_ANGLE_PI/2); arr_objects.append(tmp_object); /*  4 "" */ tmp_object = new CEntity(CIwSVec2(0, height/2), &m_Verts3[0], 4, 0xFFff0000); arr_objects.append(tmp_object); tmp_object = new CEntity(CIwSVec2(width, height/2), &m_Verts3[0], 4, 0xFFff0000); arr_objects.append(tmp_object); tmp_object = new CEntity(CIwSVec2(width/2, 0), &m_Verts3[0], 4, 0xFFff0000); tmp_object->SetAngle(IW_ANGLE_PI/2); arr_objects.append(tmp_object); tmp_object = new CEntity(CIwSVec2(width/2, height), &m_Verts3[0], 4, 0xFFff0000); tmp_object->SetAngle(IW_ANGLE_PI/2); arr_objects.append(tmp_object); /*     */ int time_between_frames = 1000/FPS; /*    */ uint32 timer = (uint32)s3eTimerGetMs(); while(result == S3E_RESULT_SUCCESS) { /*    */ s3eKeyboardUpdate(); /*     .    . */ if (s3eDeviceCheckQuitRequest()) break; /*       .      */ uint32 now_time = (uint32)s3eTimerGetMs(); int delta = now_time - timer; if (delta < 0) delta = 0; /*        */ main_object->Move(CIwSVec2::g_Zero); main_object->Rotate(0); /*             */ if ( (s3eKeyboardGetState(s3eKeyLeft) & S3E_KEY_STATE_DOWN) ) { main_object->Move(CIwSVec2(-MOVE_SPEED, 0)); } else if ( (s3eKeyboardGetState(s3eKeyRight) & S3E_KEY_STATE_DOWN) ) { main_object->Move(CIwSVec2(MOVE_SPEED, 0)); } else if ( (s3eKeyboardGetState(s3eKeyUp) & S3E_KEY_STATE_DOWN) ) { main_object->Move(CIwSVec2(0, -MOVE_SPEED)); } else if ( (s3eKeyboardGetState(s3eKeyDown) & S3E_KEY_STATE_DOWN) ) { main_object->Move(CIwSVec2(0, MOVE_SPEED)); } if ( (s3eKeyboardGetState(s3eKey1) & S3E_KEY_STATE_DOWN) ) { main_object->Rotate(-IW_ANGLE_PI / 2); } else if ( (s3eKeyboardGetState(s3eKey2) & S3E_KEY_STATE_DOWN) ) { main_object->Rotate(IW_ANGLE_PI / 2); } /*    */ Iw2DSurfaceClear(0xffffffff); /*    */ for(int i=0; i < (int)arr_objects.size(); ++i) { arr_objects[i]->Update(delta); } /*     ().      . */ main_object->SetColour(0xff00ff00); /*      ,   . */ int try_count = 10; bool b_collide; do{ b_collide = false; /*      */ for(int i = 0; i < (int)arr_objects.size(); ++i) { /*       */ if(arr_objects[i] != main_object){ /*  .  vec_reaction  ,   . */ CIwVec2 vec_reaction = main_object->CollideRect(arr_objects[i], true); if(!vec_reaction.IsZero()){ main_object->SetColour(0xff000000); b_collide = true; } } } --try_count; /*      ,   ""  ,      . */ } while(b_collide && try_count > 0); /*    */ for(int i=0; i < (int)arr_objects.size(); ++i) { arr_objects[i]->Render(); } /*     */ Iw2DSurfaceShow(); /*        . */ int32 wait_time = (uint32)time_between_frames - ((uint32)s3eTimerGetMs() - now_time); if(wait_time<0)wait_time = 0; timer = now_time; s3eDeviceYield(wait_time); } /*      */ for(int i=0; i < (int)arr_objects.size(); ++i) { delete arr_objects[i]; } /*   */ arr_objects.clear_optimised(); /*       2d . */ Iw2DTerminate(); return 0; } 

It seems to be nothing complicated. Now let's consider the objects themselves, in which the following features will be implemented:

• the object has a shape and color;
• the object can change position (move) and rotate;
• the object can react to collisions with other objects;
• an object can draw itself;

Let's look at the description of our class of objects (entity.h file). It fairly clearly describes the capabilities of the object.

  #pragma once #include "iw2d.h" #include "iwArray.h" #include "IwMath.h" class CEntity{ private: CIwMat2D m_MatLocal; /*    */ iwangle angle; /*    */ iwangle angle_velocity; /*    */ CIwSVec2 m_MoveVelocity; /*   */ uint32 m_NumPoints; /*   */ CIwSVec2 *m_Points; /*   */ CIwVec2 *m_PointsMod; /*  */ CIwVec2 *m_Axis; /*   */ uint32 colour; public: /*  */ CEntity(CIwSVec2 position, CIwSVec2 *verts, int num_verts, uint32 colour = 0xff000000); /*  */ virtual ~CEntity(); /*   */ void Update(int speed); /*   */ void Render(); /*     */ void SetAngle(iwangle angle) {this->angle = angle % IW_ANGLE_PI;}; /*     */ void Rotate(iwangle rot_angle) { angle_velocity = rot_angle; } /*     */ void Move(CIwSVec2 move_velocity) { m_MoveVelocity = move_velocity; } /*    */ void SetColour(int colour){this->colour = colour;} /*      */ const CIwVec2 *GetVerts(){ return m_PointsMod; } /*   */ int GetNumVerts() {return m_NumPoints;} /*   .         */ CIwVec2 CollideRect(CEntity *other, bool b_uncollide = false); private: /*    */ void UpdateVerts(); /*      */ /*         */ /* b_revert -   . */ bool TestOverlaps(CEntity *other, CIwVec2 &min_axis, int &min_t, int b_revert); /*          */ void GetInterval(const CIwVec2 *verts, int count, CIwVec2 axis, int &min, int &max); }; 

Let's look at the implementation of the class itself. Special attention should be paid to the methods: CollideRect and TestOverlaps .

  #include "entity.h" CEntity::CEntity(CIwSVec2 position, CIwSVec2 *verts, int num_verts, uint32 colour ): m_MatLocal(CIwMat2D::g_Identity), m_MoveVelocity(CIwSVec2::g_Zero), angle(0), angle_velocity(0) { this->colour = colour; this->m_NumPoints = num_verts; m_Points = NULL; m_PointsMod = new CIwVec2[m_NumPoints]; m_Axis = new CIwVec2[num_verts]; m_MatLocal.t = position; m_Points = verts; } CEntity::~CEntity() { if(m_PointsMod)delete m_PointsMod; delete m_Axis; } void CEntity::Update(int speed) { angle += (angle_velocity * speed) / 1000; angle = angle % IW_ANGLE_2PI; m_MatLocal.SetRot(angle, false); if(!m_MoveVelocity.IsZero()) { m_MatLocal.t += ( m_MoveVelocity * speed) / 1000; } UpdateVerts(); } void CEntity::UpdateVerts() { if(!m_Points) return; /*    */ for(uint32 i = 0; i < m_NumPoints; ++i) { m_PointsMod[i] = m_MatLocal.TransformVec(m_Points[i]); } /*   */ for(uint32 i = 0; i < m_NumPoints; ++i) { /*      */ m_Axis[i] = m_PointsMod[(i + 1) % m_NumPoints] - m_PointsMod[i]; /*  */ m_Axis[i].Normalise(); /*     */ m_Axis[i] = CIwVec2(-m_Axis[i].y, m_Axis[i].x); } } void CEntity::Render() { /*    */ Iw2DSetColour(colour); if(!m_Points)return; /*      */ Iw2DSetTransformMatrix(m_MatLocal); /*   */ Iw2DFillPolygon(m_Points, m_NumPoints); /*   */ Iw2DSetColour(0xff00ffff); Iw2DFillArc(CIwSVec2::g_Zero, CIwSVec2(5,5), 0, IW_ANGLE_2PI); } CIwVec2 CEntity::CollideRect(CEntity *other, bool b_uncollide) { /*   ,       */ int min_t(0); CIwVec2 min_axis(CIwFVec2::g_Zero); /*         ,   */ /*   ..      ,      */ /*        ,  ,    . */ if(!TestOverlaps(other, min_axis, min_t, false))return CIwVec2::g_Zero; if(!other->TestOverlaps(this, min_axis, min_t, true))return CIwVec2::g_Zero; /*   ,      */ if(b_uncollide){ CIwVec2 fvec = min_axis * min_t; /*   */ m_MatLocal.t += fvec; /*  . */ UpdateVerts(); } return min_axis * min_t; } bool CEntity::TestOverlaps(CEntity *other, CIwVec2 &min_axis, int &min_t, int b_revert) { /*   ,     */ const CIwVec2 *other_corner = other->GetVerts(); int other_corner_count = other->GetNumVerts(); /*       */ for (uint32 i = 0; i < m_NumPoints; ++i) { int aMin; int aMax; int bMin; int bMax; /*           */ GetInterval(m_PointsMod, m_NumPoints, m_Axis[i], aMin, aMax); GetInterval(other_corner, other_corner_count, m_Axis[i], bMin, bMax); /* ,       */ if ((aMax <= bMin) || (bMax <= aMin)) { /*   .  */ return false; } /*   .  ,   ,      */ /*               */ int t = 0; if(aMax >= bMin) { t = bMin - aMax ; if(min_axis.IsZero() || ABS(min_t) > ABS(t)){ min_t = t * (b_revert?-1:1); min_axis = m_Axis[i]; } } if(bMax >= aMin) { t = bMax - aMin; if(min_axis.IsZero() || ABS(min_t) > ABS(t)){ min_t = t * (b_revert?-1:1); min_axis = m_Axis[i]; } } } return true; } void CEntity::GetInterval(const CIwVec2 *verts, int count, CIwVec2 axis, int &min, int &max) { min = max = axis.Dot(verts[0]); for (int i = 1; i < count; i++) { int value = axis.Dot(verts[i]); min = MIN(min, value); max = MAX(max, value); } } 

Well, that's all, our application is ready. Now we compile it and see the results.



I want to note that the application is quite simple and works with some error. To remove it, you can, for example, use floats. It would also do well to add a coarse, but faster, primary collision check. You can also change the reaction of objects to collisions (for example, to bounce objects in a collision) and much more.

Any criticism, comments, additions and corrections are welcome.

When writing this article, one resource dedicated to collision detection algorithms turned out to be very useful. With good visual flash-examples.