Choosing a Data Structure for the Game World

We’re constantly refactoring our code behind the scenes, and as far as I’m concerned, that’s okay. You know what? It’s not just okay, it’s an excellent strategy for this project. I generally advocate for the leanest code to solve the most immediate problems. The code will grow and change as needed once we learn more over time. I’ve seen so many developers try to guess every wrinkle in the face of legitimate unknowns, and the most common results I’ve observed are analysis paralysis and overengineering. I think it’s usually more important to just get it done than to do it perfectly.

This is how I picked a data structure for entities when putting Lolo into a puzzle room. Honestly it wasn’t a profoundly consequential decision (a two-way door) so I just picked a LinkedList and moved on. And yet retrospection is foundational to growth, especially in creative endeavors. So now let’s revisit that data structure through the lens of what we’ve learned since.

At a high level, we’ve tried to keep the game engine abstract from the renderer, file system, controller input, or any other “external” stuff. This means the game data knows nothing about LibGDX or how to talk to OpenGL or how to read from a gamepad. With the right abstractions, it doesn't need to know, and that's a good thing for separation of concerns. Consequently, the engine has only one entry point, the EggerworldEngine class, edited and with comments removed for clarity:

public class EggerworldEngine {    public GameRoom gameRoom;    EngineState gameState;    EngineDrawer renderer;    public EggerworldEngine(JSONObject puzzleData) {        this.gameRoom = new GameRoom(puzzleData);        this.gameState = EngineRoomNotYetActive.enterState(gameRoom);        this.renderer = new EngineDrawer();    }    public GameResult update(LinkedList<GameCommand> commandsForThisUpdate) {        return gameState.update(gameRoom, commandsForThisUpdate);    }    public void render(ScreenDrawer drawer) {        gameState.render(drawer, gameRoom);    } }

JSON data is passed into the constructor to instantiate a GameRoom. The state of the game is advanced by one frame when calling the update() method. The game is drawn to a screen by passing a ScreenDrawer to the render() method. External code is responsible for calling update() and render() sixty times per second (or not, if that’s desirable), but the engine largely doesn’t care how it’s being called or what graphics technology powers the ScreenDrawer. This design has tons of implications, a big one being GameCommand objects (i.e. game input) can only be passed to the engine via the update() method’s parameter, creating a strong relationship between game inputs and individual frames.

Coming back to the GameRoom class where the entity data structure lives… conceptually it’s a gigantic C struct of all the game world data at one point in time, or on one frame. The EngineState class, on the other hand, is entirely stateless and only holds the logic about how to advance all the GameRoom data to the next frame.

This separation of logic and data might be anathema to object-oriented design, and indeed it doesn’t fit the OOD mindset as I understand it. But like all things, OOD has strengths and weaknesses, and I prefer a more functional connection between a game’s state and its data. For one, this separation makes it very easy to swap out the GameRoom at a moment’s notice. This trivializes things like saves and rewinds, though that will have its own blog post a bit later. Frankly, if we were coding in anything other than Java, I would probably make EngineState a function instead of a state machine.

I’ve mentioned Java before a couple times across a few posts. Why are we using Java?

I hope I don’t forget to pay that one off

So now we come to the central question of how the GameRoom class stores all of its entities, or more specifically, what data structure to use. Let’s create a list of all the things we know we need from our data structure. Laying everything out should make it easy to narrow our choices down.

1. The number of entities may change during gameplay, for example when an entity fires projectiles. This means we should use a data structure that can efficiently grow or shrink dynamically.

2. The chest containing the gem for Lolo to collect must access Lolo specifically to see if he’s collecting the gem. We muse therefore use something with random access, in other words something that can retrieve specific entries quickly.

3. We must iterate over the whole collection every update to instruct all entities to update, so we need something that can efficiently iterate over the whole collection frequently.

4. The collection must be “stable” so every update occurs in the same order every time. If the order of every entity’s update isn’t stable, one entity might sometimes perform its update before another, inexplicably changing what each of them decide to do. I want fully deterministic behavior, so we must be able to sort the entries and iterate over them in the same predictable order every time.

LinkedList satisfies requirement #1 because it’s very easy to append entries and pop items out of anywhere in the list. However, it does not satisfy requirement #2 because random access requires the application to traverse possibly the whole list to find the desired entry. Not our dinosaur.

Okay, what about TreeMap? Trees are self-sorting so it satisfies requirement #4 intrinsically. But everything else has a slight cost; insertion for trees is O(log (n)) where n is the number of entries (translation: TreeMap gets just a tiny bit slower the larger the collection gets). Iteration and retrieval have similarly small but present penalties on TreeMap. Definitely not our dino.

But at least TreeMap is a vegetarian. With the, you know, leaves and the… look, if you don’t get it yet then it’s just not your joke Used with permission from original photographer Becky Ginther, who hosts this image on her blog

Time to get serious. Instant access, easy traversal, dynamic size… what about HashMap? Yes, now we’re playing with power.

There’s Lolo, and he’s got the Power

HashMap stores entries with an associated key, and that key can be used to instantly get that entry back from the map. Our GameRoom class can store the HashMap as a private member variable and manage the generation of unique keys for new entities through an addEntity() method. Iterating over every entry is easy if we can remember every key. Requirements 1, 2, and 3 are solved!

Wait… was there a fourth? Oh, right, we want stable iteration. We could achieve stability ourselves with both a HashMap for entries and a separate LinkedList of the keys we’re using, in order, just for iterating. Thankfully we don’t have to, because Java’s robust standard API includes the LinkedHashMap class for precisely this purpose. A quick look at the Standard API reveals LinkedHashMap  is just a HashMap that also encapsulates a LinkedList to guarantee order anyway. Boom; we're back with one additional data structure, extra stable.

I think this will be a good first pass. We shouldn’t optimize too much ahead of time since so much could still change that would obviate any optimization we do now. Still, every entity updates every frame even if it doesn’t do anything, like Alma who makes meaningful calculations every frame versus rocks and trees which do nothing. We could separate entities by “active” and “static”, but let’s save that for if we need to.

Lolo’s intelligence is totally up to you, the player. So tell me: how smart is he?

This analysis is very specific to Eggerworld, so other games’ code may shake out differently. And maybe you know a better way to do this! Leave your thoughts in the comments.