Best way to store a large amount of game objects and update the ones onscreen

Question

Good afternoon guys! I'm a young beginner game developer working on my first large scale game project and I've run into a situation where I'm not quite sure what the best solution may be (if there is a lone solution). The question may be vague (if anyone can think of a better title after having read the question, please edit it) or broad but I'm not quite sure what to do and I thought it would help just to discuss the problem with people more educated in the field.

Before we get started, here are some of the questions I've looked at for help in the past:

1. Best way to keep track of game objects
2. Elegant way to simulate large amounts of entities within a game world
3. What is the most efficient container to store dynamic game objects in?

I've also read articles about different data structures commonly used in games to store game objects such as this one about slot maps, but none of them are really what I'm looking for. Also, if it helps at all I'm using Python 3 to design the game. It has to be Python 3, if I could I would use C++ or Unityscript or something else, but I'm restricted to having to use Python 3.

My game will be a form of side scroller shooter game. In said game the player will traverse large rooms with large amounts of enemies and other game objects to update (think some of the larger areas in Cave Story or Iji). The player obviously can't see the entire room all at once, so there is a viewport that follows the player around and renders only a selection of the room and the game objects that it contains. This is not a foreign concept.

The part that's getting me confused has to do with how certain game objects are updated. Some of them are to be updated constantly, regardless of whether or not they can be seen. Other objects however are only to be updated when they are onscreen (for example, an enemy would only be updated to react to the player when it is onscreen or when it is in a certain range of the screen).

Another problem is that game objects have to be easily referable by other game objects; something that happens in the player's update() method may affect another object in the world.

Collision detection in games is always a serious problem. I need a way of containing the game objects such that it minimizes the number of cases when testing for collisions against one another.

The final problem is that of creating and destroying game objects. I think this problem is pretty self explanatory.

To store the game objects then I've considered a number of different methods. The original method I had was to simply store all the objects in a hash table by an id. This method was simple, and decently fast as it allows all the objects to be looked up in O(1) complexity, and also allows them to be deleted fairly easily. Hash collisions would not be a major problem; I wasn't originally planning on using computer generated ids to store the game objects I was going to rely on them all using ids given to them by the game designer (such names would be strings like 'Player' or 'EnemyWeapon4'), and even if I did use computer generated ids, if I used a decent hashing algorithm then the chances of collisions would be around 1 in 4 billion.

The problem with using a hash table however is that it is inefficient in checking to see what objects are in range of the viewport. Considering the fact that certain game objects move (as well as the viewport itself), the only solution I could think of in order to only update objects that are in the viewport would be to iterate through every object in the hash table and check if it is in the viewport or not, updating only the ones that are in the valid area. This would be incredibly slow in scenarios where the amount of game objects exceeds 500, or even 200.

The second solution was to store everything in a 2-d list. The world is partitioned up into cells (a tilemap essentially), where each cell or tile is the same size and is square. Each cell would contain a list of the game objects that are currently occupying it (each game object would be inserted into a cell depending on the center of the object's collision mask).

A 2-d list would allow me to take the top-left and bottom-right corners of the viewport and easily grab a rectangular area of the grid containing only the cells containing entities that are in valid range to be updated. This method also solves the problem of collision detection; when I take an entity I can find the cell that it is currently in, then check only against entities in it's cell and the 8 cells around it.

One problem with this system however is that it prohibits easy lookup of game objects. One solution I had would be to simultaneously keep a hash table that would contain all the positions of the objects in the 2-d list indexed by the id of said object.

The major problem with a 2-d list is that it would need to be rebuilt every single game frame (along with the hash table of object positions), which may be a serious detriment to game speed.

Both systems have ups and downs and seem to solve some of each other's problems, however using them both together doesn't seem like the best solution either.

If anyone has any thoughts, ideas, suggestions, comments, opinions or solutions on new data structures or better implementations of the existing data structures I have in mind, please post, any and all criticism and help is welcome.

Thanks in advance!

EDIT: Please don't close the question because it has a bad title, I'm just bad with names!

Answer 1

This is a pretty big question and I think you might be better served by asking each part separately.

That said, two of your points (viewport and collision) are essentially about accessing "nearby" objects efficiently. The way to do this is to use some kind of spatial data structure (aka spatial index).

The simplest one is to have a two-dimensional array (if your world is two-dimensional), where each array element corresponds to a 'tile' or 'chunk' of the world (divide world coordinates by tile size to get an array index) and is a list of every object which intersects that tile. (Note that an object may therefore be listed in multiple tiles.) Your objects also store their locations and sizes, and any time that changes, you remove the object from the old positions in the array and add it to the new ones.

(That last part is key: the information is stored in two ways (in the object, and in which parts of the array have the object) and kept in exact synchronization. This is an important general technique for allowing different operations to both be efficient, and it is why we call the data structure an index: it stores no new information, but allows getting an answer to a specific question efficiently.)

More complex data structures such as quad trees avoid establishing a fixed chunk size (so you don't slow down due to lots of objects in a small space or waste memory for few objects in a big space).

A lot has been written on these topics; I hope this answer gives you the keywords you need to learn more.