Part 1 - Exploring Graphs and Trees

Graphs and Trees to Start

I was chatting with my colleague about generating maps for a 2D role playing game the other day after getting super excited explaining picking ProjectXyz back up and looking into Unity3D more. He was expressing interest in algorithms for procedural generation and storing data in trees or graphs as an optimal data structure for the scenario we were going over.

It stuck with me though. I've been putting a lot of thought into game state management and wanting to address it by using a generic layering/stacking approach. By that, I mean that I want to find a way to take base game state, allow mods or plugins to overlay their state, allow game patches to overlay their state, and then save game data to be overlaid on top of all of that. Conceptually, I believe I can create a generic system for doing this stacking of game data, which I'll be referring to as my Delta State Algorithm, but I've been struggling with a starting point.

But the trees and graph concept stuck with me because the properties of trees and graphs that my colleague was referring to seemed to line up with how I envisioned this algorithm working. A graph or a tree just might be the right structure to represent this game state and the deltas between them, so I wanted to start mocking up some ideas.

A Map is a Game Object... And so is Everything Else?

Confusing subheader? You bet. But it's because it was an odd realization.

I've been re-writing the same back end for an RPG for years now. Literally, it's probably been at least 10 years that I've started, progressed, and scrapped such a game. But one thing I borrowed from Unity3D development was the idea of components and component-based design. I was far too married to object hierarchies, and these would eventually result in me having to refactor a TON of code. If you couple that with the fact I wasn't using dependency injection properly (see this little primer article), it meant my refactoring efforts got to the point where it just made sense to start over.

So I was working with loading maps from TMX or Tiled map formats, and after getting these to load I was putting some thought into how I wanted to save/load my game objects. My game objects are essentially containers of components, and the containers have no properties at all. What does that mean in practice? My Actor/NPC game object class is the exact same class as an equippable item! It's just "GameObject". The difference between them is the variation in the components that I attach to them. In my mind, I figured I'd need some sort of hierarchical serialization paradigm where my game object would serialize itself, then the components would serialize themselves within that process, and if I could have components with components... You get the idea. But this could sort of be represented by a tree structure.

After the discussion with my colleague about trees and graph structures for maps, I connected some dots. Really the tiles and placed objects on a map were just... game objects as well. And that means that my thought process behind hierarchical serialization aligns well with some of the properties he was referring to for maps as graphs/trees. This suggests that "world state" for a game where everything is a "GameObject" with components attached to them (where some of those components can contain other GameObjects) could be represented by a graph or tree data structure

What About Tabulated and Listed Data Sets?

So we've come up with a starting point for "World Data" being represented by a graph. However, if we go back to my initial goal, I want plugins/mods/patches to be able to get applied to base "Game State" data.

What's the difference between world and game state data?

These are just my terms so I should try and clarify. The world data is the data the player sees in the playable world. It's the status of the objects and the maps they are interacting with. Game state data is the superset of this data and all of the other lookup data for loading content into the game. So this OTHER data includes things like the possible stats players and items can have, the types of monsters that can spawn (not the instances of the spawned monsters, because that's the world state data), the possible dialog entries, etc... This type of data is really well represented in a relational database where we can create lists of data entries.

But if we take a step back, can't that relational database content also be represented as a graph?

Could I have:

• A node called "Stats" as a parent to a "Life" node that is a parent to a "StatRange" node, and "LocalizedNameResource" node?
• A node called "BaseItems" as a parent to a "Sword" node that is a parent to a "DamageRange" node, "RequiredStats" node, and "EquippableSlots" node?
• A node called "MonsterSpawns" as a parent to a "Skeleton" node that is a parent to...

You get the idea. I generally think about this data in a relational database paradigm (and perhaps it's much faster to edit the data this way or look it up this way). However, if I can transform this data into the same type of graph structure I want to use for world state, then it means my delta state algorithm would work on not only world state data but also ALL game state data. ## So Everything in the Graph? Always? This is an important question, and I think one that without actually explicitly thinking about was causing me some headaches and keeping me from progressing down exploring more of my delta state algorithm.

I mentioned that some of the game state data feels better represented in a relational database. It might be much faster to add/remove or look them up when the data feels like it's just a list of records when you contrast that with a graph. But why not have multiple storage mechanisms?

The delta state algorithm serves a very important goal: Layer deltas of data on top of a base set to get a new set.

That's it though. So once I have that final transform of data that represents the new game state, who says I can't transform it into a different format?

Maybe the world state is still better represented as a graph. So things like maps with tiles and game objects in the world still are super efficient to work with in graph form. Maybe things like dialog entries or definitions of player stats are better represented in a relational database... I could populate a database with the necessary data based on the graph data though. And the really cool part? A save game, which is probably the delta that changes the most, probably shouldn't have the extra game state data in it (likely just has world state deltas represented). So... if a relational database is better suited for the remaining game state data, this could get generated and cached, and then only regenerated when different mods/plugins/patches are applied!

Concluding Thoughts

To summarize some of the major thoughts discussed in this article:

• Game objects with components can be represented by nodes in a graph just like maps with tiles on them.
• Other game state that feels better suited for relational databases can still be transformed into nodes in a graph for working with deltas.
• Once a final game state is calculated (based on base state + deltas for mods/plugins/patches + delta for save game), data can be transformed back into the most suitable form to work with
• Data does NOT have to exist in only one form! We can transform it as we need to work with it more effectively.

While this article was a bit of a brain dump, this the thought process that got the ball rolling for starting to design this delta state algorithm. In my next post in this series, I want to discuss a quick look at undo/redo approaches used in applications and how they might be similar (or different) to how the delta state algorithm might work.