I am currently developing a prototype game for mobile devices in which the user will see several objects on the screen and will have to touch them one by one in the correct order to win. I guess it that you can say that it is similiar to a Whack a Mole game, but instead of having moles popping up on the screen, I will have several objects moving around.

I am having some difficulties in implementing a collision detection algorithm for this game, thefore I would like your recommendation on what is the best method to use.

For example suppose an object is moving in a given direction, then I could use the SAT to check if it collides with other objects. If it does collides, then it will stop and move in another direction which is randomly chosen.

Another option would be to divide my screen into square or hexagonal tiles. This way I could just check if the tiles are free or occupied before moving the objects.

My game be 2D and will use a top-down ortographic projection and I am developing it using Cocos2d-X and Marmalade SDK. I am not using any physics engine, because my game does not require them (the objects just have to move around, they don't bounce or need any sort of physics behavior).

  • \$\begingroup\$ What have you tried? Is your game tile-based? What shape are your objects and how many of them are there? \$\endgroup\$ – Anko Jun 14 '14 at 16:45
  • 1
    \$\begingroup\$ So far I tried approximating my objects as circles and have them moving around on the screen. I have around 7 to 14 objects and my game isn't tile based. I just thought about using tiles, because it seems like a simpler approach in my case. \$\endgroup\$ – Felipe Jun 14 '14 at 17:14
  • \$\begingroup\$ If your 7 to 14 objects are well-approximated by circles and all you need to be able to do is detect taps on them, I can imagine everything working beautifully if you just iterate over their centres and check if the distance of each from the tap position is less than than the circle radius. \$\endgroup\$ – Anko Jun 14 '14 at 17:18
  • \$\begingroup\$ Hi, yes this is working very well. However I still have some problems with the collision detection between the objects themselves. \$\endgroup\$ – Felipe Jun 14 '14 at 17:22
  • \$\begingroup\$ For each object, iterate over the others and do the same check? \$\endgroup\$ – Anko Jun 14 '14 at 17:50

Real-time collision detection in gaming has two stages: the broad phase and the narrow phase:

In the broad phase you decide which pairs of objects may collide. If you have a low number of objects (and I suppose you have since they will all pop on the screen), you can check every object with every other object. Keep in mind that the complexity will be O(n*n), but this is reasonable for something below 50 objects and is not complicated at all. If you really want to optimize it you should be using a different data structure, such as a quad-tree.

In the narrow phase you decide if a pair of objects is actually colliding. This phase heavily depends on the shape of your objects. You can enclose every object in a bounding volume, which will approximate the geometry of the object. This will do the job if the collision detection doesn't have to be very precise. One of the most trivial bounding volumes is the sphere and the collision check is just the boolean value of ( Distance( sphere1.center, sphere2.center ) < sphere1.radius + sphere2.radius ).

You decide which pairs are to be checked for collision in the broad phase and then you check them in the narrow phase. If the narrow phase says they're colliding, you should resolve the collision, which means changing the direction in which the object moves.


Not the answer you're looking for? Browse other questions tagged or ask your own question.