How to handle lots of objects in a C++ game

Question

The question

Sorry about the title, could not seem to find a shorter/better description..

Here's the situation: I am making a simple game in which there is a big map (simple, but very big in size). There are also a lot of enemies on that map, but the action is exclusively around the main character (in a certain radius, which is a very small percentage of the map).

At each 'tick' (or step, or whatever you call it), there is a certain function called on each of those objects to determine their next move. For performance reasons, since I do not care about what happens outside of my scope of view (or at least, the very far away stuff), I'd like not to call that function on very foreign objects.

How can I manage these objects to make sure I always have a list of the nearby objects that is updated when I move around the map?

(I know it is tagged in C++, but any language will do - I'm not looking for code that much - It's more about the idea)

---

What I've already tried

I've tried a few alternatives:

• Alternative 1: Separate my map in "zones" and store a list of enemies in each zone. The problem with that is what happens when I'm on edges of those zones and (worse) when I'm on a corner (4 different zones around me). Also, it's harder to make the enemies switch zones if I run from one zone to another (but I had figured out something which could work...)
• Alternative 2: Scan the whole map and refresh the active enemies list each time I move x distance. That's a bit better since I don't have to worry abound bounds like Alternative 1, but I do have to scan the whole map each time.

I was now looking at Alternative 3, which is to mix those two solutions together.

However, I wanted to make sure there is not a more obvious solution.

Answer 1

Store your enemies in a k-d tree and do a spatial range search every few iterations. You need, however, a fairly sophisticated implementation which supports entries moving around and re-balancing - sometimes called adaptive k-d tree.

Answer 2

Okay, if you could answer the following questions, I'm sure some of us could help with the right data structure and procedure. How big is the map?Actual dimensions? Tell us a bit about the density of enemies?How many of them on an average?I guess you are going to use a random number of enemies for each game, or perhaps increasing number of enemies for each level.In any case what is the maximum number of enemies that you plan to have?

It would be really good only if all the characters/enemies move around instead of just around the main character.Only that will make the game truly exciting.I trust you are going to use a lot of random numbers for movements, but try to see if you can come up with simple yet realistic algorithms for their movements, instead of fully relying on random movements.I have used random a bit and they definitely are no where interesting.Maybe you could move the ones very near to the main character slowly and the ones very far away quickly.You could increase the enemies speed and power as level increases.Try to make it as exciting as possible.You can try the Caesar III game and see how well the movements of people are, simple movement but really nice. Bottom line is think about how you are going to move the enemies, and as far as possible try to move all the enemies for each tick to make the game really exciting.