correct pattern to handle a lot of entities in a game

Question

In my game I usually have every NPC / items etc being derived from a base class "entity". Then they all basically have a virtual method called "update" that I would class for each entity in my game at every frame. I am assuming that this is a pattern that has a lot of downsides. What are some other ways to manage different "game objects" throughout the game? Are there other well-known patterns for this? My game is a RPG if that changes anything

Answer 1

First of all, this question doesn't really have anything to do with design patterns. This is closer to optimization, though it's lacking a performance problem. So, question #1: is your current entity system a performance bottleneck? If no, don't worry until it actually is.

If it already is, there's a few things you can do:

1. Sort entities by type (or store them in separate arrays and iterate through them separately). This will ensure that entity code is reloaded no more times than it's necessary.
2. Update some entities less often. The easiest way to do that is to increment an internal delta time value for each entity (or a group) and actually update the entities when it reaches a certain value, at which point it is cleared (set to 0) again.
3. Merge many entities into one and internally use algorithms that fit the data best.

Answer 2

You could keep an Array of entities that need to be updated. Every time a entity is changed, it calls a callback function (or notifies the class holding the Array in other way) so it is added to the Array, and the Array is cleared after all updates are done. It may be slower if you're 'updating' (calling update methods of) most of the entities every frame anyway.

Answer 3

First of all, define "a lot," and check that there really is a problem. You can easily handle thousands of game entities with your model on even modest hardware with no performance problems to speak of (assuming you don't have something really silly going on in one of the update functions themselves).

That said, there are some superior design approaches to use in the general sense. The usual mantra is to make use of component based design of some form. In other words, favor composition over inheritance. Don't have classes inherit from entity instead, have the entity be a container for component objects, which then either contain (preferable) or contain logic (also very useful, though some specific forms of component based design ban logic components).

The advantage to this approach from a performance perspective is that you can remove any need to call update() on components that have no logic, and hence from any entities that have no logic components. If you have an item that just lays on the ground, and hence has nothing to update and has no logic components, it won't be touched during your update loop.

You can also just keep the update() method on components and entities. Really, honestly, it scales just fine even in many larger AAA titles, so long as you don't have a ridiculous number of objects live at any given time, and apply some sense to how your entities/components are allocated and iterated over in memory. The performance bottlenecks in most games are completely outside of the logic update loop, and are off in the specialized systems that do many many operations, e.g. the physics/collision system, graphics, resource streaming, path-finding, etc. These are all things that you should never do in an update() method of an entity/component, no matter what the design of your engine is; these belong in specialized, optimized systems.

The true advantage of a component based design (whether it's a rigidly adhered-to entity system design or the complete spaghetti-like chaos of Unity's component system, or something sensible that falls in between) is that it allows a separation of logical modules, it facilitates data-driven design of game object behavior, and through those allows for a greatly increased rate of game design iteration and hence a better game made with less time/money/bugs. Components also make hooking up an editor to your game data quite a bit easier, as well as allowing designers to make new types of in-game entities without needing to wait for a programmer to make every little change.

In other words, worry less about the number of objects or performance, and worry more about how easy it is to totally change up and tweak large parts of your game design. Virtually no well-known successful game has ever gone from initial design to release without having some massive changes to the game's direction somewhere in the middle, usually after building enough of the game to get a prototype in front of players and find out how well the design ideas actually work. The more flexible and future-proof your object design is, the better off you'll be.

The main introductory article on the topic is http://cowboyprogramming.com/2007/01/05/evolve-your-heirachy/.

There's also a great set of slides from Scott Bilas, who worked on Dungeon Siege and helped pioneer the use of components in game engines (back before just about everyone started using them): http://scottbilas.com/files/2002/gdc_san_jose/game_objects_slides_with_notes.pdf