Managing Entities

  1. Summary
  2. Definitions
  3. Objectives
  4. Article
    1. Theory
    2. The Entity
    3. The EntityList
    4. Making EntityList extensible
    5. EntityLayer & EntityLayers
    6. Alternative Data Structures
  5. Expanding
  6. Code Download
  7. Applet
  8. Next Article

Summary

Managing the vast number of objects in your game could be time consuming. Especially when you have short-lived objects in your game like particles, bullets, and animations. This article discusses a method which utilizes arrays to store Entities and storing Entities in layers.

Definitions

  • Entity – something that could be drawn, is updated, and can expire.

Objectives

  • To design a simple Entity list which handles updating, drawing, and pruning expired entities.
  • To design a class for storing layers of entities to control drawing and update order.

Article

Theory
The idea here is to build a simple data structure that handles drawing, updating, adding new entities, and removing old entities. Using the built in data structures of whatever language you use could be fine, but there is always room for improvement. When you start dealing with thousands to hundreds of thousands of objects, how you manage updating, drawing, adding, and removing is very important.

This article presents a method that uses an array that prunes out expired entities while it’s updating entities.

The positives of using a self-pruning array:

  • No copying (or iteration) needs to be done to remove an entity, it’s removed when the list is being updated and realizes one of it’s entities have expired.
  • Arrays are more efficient to iterate over (opposed to linked structures), the processor is tuned to handle arrays better (with caching and prefetching to mention a few)
  • Arrays are simpler to understand than linked structures.
  • Insertion order is maintained

The negatives:

  • An array can take up more memory than a singly linked list (however, you can add in simple logic to an array to say “over x seconds, if x% of the array is unused, shrink the array” – if memory is limited)
  • A developer might unknowningly use an expired entity, it’s not removed from the list immediately upon expiration (easily fixed by checking the expiration flag, or ordering when updates are made of certain things)
  • Must be resized if the underlying array is not big enough (however, a game could allocate it’s maximum amount of space required. This methodology ensures more controlled memory usage and avoids unnecessary calls)

As you can see the positives outweigh the negatives greatly (the negatives are situational).

At the end of the article I go over the alternative structures I’ve used aside from the self-pruning array.

The Entity

The Entity interface is the core to any game or game engine. We might as well go straight to the code, it’s simple enough based on our objectives.

Lets break it down:

Draw needs to be called every frame, we pass in the frame information (GameState) and the graphics used to draw then Entity.

Update will be called whenever the game is ready to progress it’s game state to the next step. This is dependent on the game loop implementation you are using.

Whether or not this Entity is expired and is ready to be removed from the game. This should return true if expire() was called, or if the implementing Entity is ready to go.

Tells the Entity implementation that it needs to be removed from the game, whether it wants to or not. The implementation needs to assume that this method could be called many times over a single update, and needs to be coded accordingly.

This method is called once by the EntityList when it is being pruned. This is essentially the deconstructor for an Entity.

The EntityList

The EntityList is the data structure which manages the array of Entites and prunes out the expired ones. Here’s what the initial version of this class looks like:

As you can see we made EntityList implement Entity! This means we could have an EntityList within another EntityList within another EntityList. EntityList inception to the third degree one might say.

EntityList is also given typical collection methods like add() and size(). Note that there is no remove, that auto-magically happens when an entity expires.

You could also make this an interface, so you could provide a specific implementation depending on the scenario.

No onto the implementation! Firstly, the class level variables:

Now method implementations, with the least complex first:

Constructors

State

Utility Method

The pad method grows the capacity of the array by 50% (unless that’s not enough to add count entities)

Add Methods

Expiration Methods

Draw Method

Update Method

Finally, the code you’ve all been waiting for!

Given the comments, it should be easy to follow. Now that we have the basic implementation, there’s more we can do with this.

Making EntityList extensible

We can make the EntityList a little more extensible. Here’s functionality I typically add to my EntityList, most of you could benefit from it as well.

  • Make the entity list generic (EntityList<T>) so you can optionally specify an Entity implementation (ex: Particle) and anything using the EntityList doesn’t have to cast it. If you want an EntityList with any implementation of Entity, just create a EntityList<Entity>.
  • Add a getter to the EntityList: given an index return an entity.
  • Add a clear method
  • Add protected methods that are called during certain events, so a class could extend EntityList and be notified of those events
    • onUpdate( Entity, GameState, int ) – notify extending class when an entity was updated
    • onExpired( Entity ) – notify extending class when an entity has expired or removed
    • onAdd( Entity, int ) – notify extending class when an entity was added to the list
  • Add an Iterator to iterate over the entities in this list. This is typically frowned upon in Java games (it creates a lot of garbage, trust me). Typically an Iterable class returns a new Iterator each time, we’re going to cache it and reuse an iterator.
  • Shrink the array if there’s x% percent free for y seconds.

Instead of stepping through how to do these things, I’m just going to dump the code here. It should be easy enough to follow.

(checkout the source code for full documentation)

EntityLayer and EntityLayers

But wait, there’s more!

Lets organize our Entities into layers! The EntityList already maintains insertion order, but sometimes we want certain types of things updated before other types of things. Sometimes we want things drawn in the background before the things drawn in the foreground!

EntityLayer is just an EntityList that has the following additional properties:

  • index – the index of the layer
  • visible – whether or not this entire layer is drawn
  • enabled – whether or not this entire layer is updated

The implementation is easy enough:

That was easy, let’s finish it off with EntityLayers. Note the s. You can rename this if it ends up being confusing to you.

With EntityLayers you can use an enum for the layer ordering. You could pass in LayerEnum.class to the constructor of EntityLayers and there will be as many layers created as there are constants in LayerEnum. When you do that, you can optionally use the add and getLayer methods and pass in a LayerEnum constant like so:

I hope you realize the usefulness of organizing your world into EntityLayers!

Alternative Data Structures

Here are a few data structures commonly used by me in different scenarios. I’ve included notable positives, negatives, and neutral remarks for each one.

Singly Linked List (a typical LinkedList implementation like java.util.LinkedList)

  • Removal involves iterating over the list until the entity is found.
  • Not as processor friendly as an array-based structure.
  • Requires constant allocation of nodes for every entity added (could use a node cache).
  • Uses only required space.

Self-Pruning Linked List

  • Not as processor friendly as an array-based structure.
  • Requires constant allocation of nodes for every entity added (although could use a node cache).
  • Uses only required space.
  • Removal is done during iteration, like our EntityList.

Doubly Linked List

  • Not as processor friendly as an array-based structure.
  • Requires constant allocation of nodes for every entity added (although could use a node cache).
  • Uses twice required space (since another node reference is required).
  • Removal can be done as soon as expire() is called, no need for pruning.
  • I use this for index’s in spatial databases. A spatial entity has a single doubly linked node which it uses throughout it’s life. The index’s of the spatial database each are a linked list consisting of the nodes of the entities in that index (and index may be a rectangle in space where it’s entities are entities in the rectangle).

Self-Pruning Binary Tree (something I’ve used for implementing a Scene Graph)

  • Not as processor friendly as an array-based structure.
  • Requires constant allocation of nodes for every entity added (although could use a node cache).
  • Uses twice required space (since another node reference is required).
  • Has layering built in.
  • Great for Scene Graph implementation.
  • Insertion is trickier since layer’s are involved. Typically insertion isn’t done on a tree in the same sense. The tree is built in such a way that insertion doesn’t require traversing the tree and finding the appropriate node.
  • The “left” node is the sibling to the current node. The “right” node is the first child node. When updating and drawing you iterate over the children and call draw/update. They do the same thing for.

Array List (a typical List implementation like java.util.ArrayList)

  • Removal involves iterating over the list until the entity is found.
  • May have wasted space in the array.
  • More processor friendly than a linked structure.

Self-Pruning List (hey, that’s what we just implemented! I wanted to re-iterate it)

  • May have wasted space in the array.
  • More processor friendly than a linked structure.

Back-Copying List

  • May have wasted space in the array.
  • Does not preserve insertion order.
  • More processor friendly than a linked structure.
  • Less copying than a Self-Pruning List.
  • Instead of copying the live entities over the expired ones (like Self-Pruning List), the last entity in the list is copied over the recently expired entity. This results in far less copying but insertion order is not maintained. This is easily implemented by iterating over the entities starting from the back and moving towards the front.

Expanding

So, what more could you possibly want to do?

  • Create an EntityContainer class that has similar method signatures to EntityList.
  • Create the most useful implementations of the above mentioned Alternative Data Structures.
  • Set a maximum capacity on the EntityList. add(Entity) will return boolean, and the other add methods would return the number of entities able to be added to the list. This is useful if you utilize the EntityList as a list of particles and you don’t want more than X particles on the screen at once.
  • Add time modifiers to EntityLayer so time moves slower or faster for everything in that layer.
  • Add Iterator to EntityLayers so you can iterate over all the entities in each layer if need be.
  • Add more methods to EntityLayers for managing the state of it’s layers.

I hope this article helps you out in some fashion, even if you aren’t making a game from scratch.

Code Download

The code was written in Java and uses Java2D for drawing. Java2D was chosen because it is part of the Java SDK and it doesn’t require any external libraries. This code is easily translatable to other languages and other graphics libraries.

Source Code

Applet

When shown, click on the applet to explode some balls!

Show

Next Article

The next article I’ll be talking about something far less involved, but useful nonetheless: Probability! When you have 4 items, and each one of them have an x% chance of occuring, how do you quickly pick one at random based on the probability?

2 thoughts on “Managing Entities

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">