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.