As part of my final project of Algorithms and Data Structures, we have to develop an open world game in C++. I already got developed most of the game, but I haven't coded the collisions with the enemies.

First, I'll explain how the game works. It's an open world game, where there are 10 regions. The world is a big map, where only a small portion of it has to be visualized in the screen . The world is 40 screens x 40 screens, where each screen is 1900 x 1080 pixels.

In this world, there are 250 000 enemies that are distributed in all the regions, so that each region has 25 000 enemies.

Besides, there is a main character that has to travel around this world doing missions, collecting items and killing enemies.

Now, my problems raises here, what is the most efficiency way to check if the main character collides with any enemy, so that when he attacks this enemy and kill him I can eliminate the enemy from the world?

In order to solve this problem, I assigned each region a list of enemies, so that the amount of enemies to validates reduces significantly. I also have a function that returns the region where the main character is.

Then, to check for collisions I do this:

for ( Number of Enemies in the Region)

  if ( MainCharacter is colliding with an Enemy and MainCharacter kills the Enemy)
     delete Enemy from the Region

I think this way is pretty inefficient since I have to validate all the enemies in the region and I just want to validate the enemies that are closer to the main character or are visible in the screen.

How should I improve the collision detection so that it's more efficient?

I hope I made my self clear and I would really appreciate any help you can provide.


The simplest way I could think of is to use a grid (2D if your enemies can only move on the xz plane and 3D if they can move up and down too). You will have to hold an additional reference to the grid cell inside your enemy objects, and also in the player object. This way, you will still have to iterate over all enemies in your map, but only check collisions for those that have the same grid reference as the player.

You will have to update the grid reference based on the object's position inside your update function.

Also, watch our for edge cases such as an enemy being in more than one grid cell.

  • \$\begingroup\$ This is a very simple approach, a great way of cutting n^2 down. In reference to the edge cases part you can generally just check in a 3x3 grid around the object you're checking for to ensure that you don't miss any collisions. \$\endgroup\$
    – Shaun Wild
    Jun 27 '16 at 8:23
  • \$\begingroup\$ @ShaunWild That's a lot of extra work if you can easily verify whether or not the bounding box is entirely contained by a single cell. \$\endgroup\$
    – Dan
    Jun 27 '16 at 12:45
  • \$\begingroup\$ +1 because put in the right direction. What you describe rasemble spatial hashing: conkerjo.wordpress.com/2009/06/13/… , but , as described in link , may be better hold references to enemies inside cells \$\endgroup\$ Jun 28 '16 at 9:44

I'm not entirely sure why you're checking each enemy for collisions if you're only worried about collisions with the player. If the player can only ever collide with enemies, then if you only check the player for collisions with enemies rather than all the enemies for collisions with the player, you would go from 25,000 enemies x 60fps = 1,500,000 checks per second down to 1 player x 60fps = 60 checks per second. Literally just:

void CheckForKills()
    if(MainCharacter is colliding with something)
        Enemy enemy = something;
            delete Enemy from Region;

No loop required. Having said that, I think that the absolute best way is to use something like a delegate. If you look at an established Game Engine like Unity, it uses an event to detect when a collision occurs and upon that collision invokes a method called OnCollisionEnter(). Then, in theory, you would go from 1,500,000 checks per second down to "only when a collision actually happens".

  • \$\begingroup\$ But the main character not only collides with enemies, but also with items that are all around the world. Your function CheckForKills() makes a lot of sense, but I can't find an implementation in C++ for that function. \$\endgroup\$
    – Drako
    Jun 27 '16 at 17:02
  • \$\begingroup\$ Look at my answer. If you use my approach, you can perform collision detection on ANY kind of object that is within (i.e. associated) with a tile. So if a tile has 2 trees and 5 enemies, you know the exact # of objects to check collision against. Assuming your tiles are small, this should be a rather inexpensive loop. \$\endgroup\$ Jun 28 '16 at 1:37

First thing to consider: You have your giant world broken up into manageable regions. So why not break up a region into more manageable pieces, like sub-regions? By doing this you can further break-down the total # of objects to check for collision detection. But this is just a side note.

Now, here is where you can achieve very quick collision checking for your game...

Assumption: A region within your game is composed of tiles. If so, what if a tile object has information about the enemies on it?

Now, the moment the main player enters any tile, you can quickly (and cheaply) know what enemies you are potentially colliding with (a tile object can have a list of enemies that are in it). Or, alternatively, you can have a mapping table that says "this Tile has these enemies in it".

So ultimately, based on the user's (x, y) location on the map, you can instantly know (i.e. in 1 single step) the tile object you are in AND quickly know the # of enemies to do further/deeper collision detection on (likely a small list of enemies).

The only thing to consider now is that you have to update a tile's enemy list based on every enemy running around the map (but that should be very cheap as well). It's all about the references.

* Updated * After reading from Deno's answer, I believe my approach is similar in style. But what I am suggesting in my answer is that you can totally avoid any kind of checking within a loop. Because basically you know the tile that you are in, and each tile knows what enemies are in it.

Pseudo-code below:

  1. get tile T that the main player is in.
  2. check if tile T has any enemies from its enemy list (or based on a mapping/lookup table).
  3. do whatever collision detection you want.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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