In the last post I mentioned that while working on my colony simulator game for the r/roguelikedev summer event, I ran into a situation where my data structures made me unhappy. I was implementing a job system, where a colonist would keep track of what job they're doing, what items they're holding, and where they are standing. It looked like this before I rewrote it:

Object relationships diagram
Diagram: objects that point to each other

Let's start with inventory. Colonists need to know what items they're holding. Items need to know where they are located, either on the ground or in a colonist's inventory. This is a two-way relationship. To simplify, let's assume a colonist can hold only one item, and a ground tile can have only one item. To have a colonist pick up an item from the ground:

  1. Set onGround[item.pos] to null.
  2. Set colonist.inventory to item.
  3. Set item.pos to colonist.

All three of these have to happen to keep the data consistent. And I need to check preconditions too:

  • Ensure item.pos is the same as colonist.pos.
  • Ensure colonist.inventory is null.

This is a reasonable implementation. But what happens when the complexity goes up? There are a lot more things to keep in sync when the colonist takes a job, the job points to the colonist, the job points to the item, the colonist points to the item, the item points to the job, and so on.

I wanted to simplify. I remembered my times working on business apps, where I could store this type of data in relational databases. The main idea is to store data in a way that eliminates redundancy. For inventory, I could store it like this:

Item Location
apple 3 x=5, y=8
apple 4 x=9, y=1
apple 5 Fred

I can put an index on both the Item and Location columns. That lets me look things up in both directions:

  • Where is apple 3? Look it up in the table using the Item column, and find the Location is 5,8.
  • What is in location 9,1? Look it up in the table using the Location column, and find the Item is apple 4.
  • What is Fred holding? Look it up in the table using the Location column, and find the Item is apple 5.

If I want Wilma to pick up apple 4, I can look it up in the Item column, and change Location to Wilma. There's only one change, not three like before.

But I don't have a relational database in the game. Instead, I can store this data in an array, and implement the indexing as two hash tables, one for Item and one for Location. Then I can encapsulate this in a Table data structure.

For the job system, it gets a bit more complicated. Transport jobs are of the form:

Colonist Take Item From Location To Location
Barney apple 3 x=5, y=8 x=3, y=1
Wilma iron 14 x=9, y=1 x=5, y=5

Production jobs are of the form:

Colonist Work in Location And produce item duration
Betty x=3, y=1 apple pie 20min
Pebbles x=5, y=5 pickaxe 40min

And that's it. The tables store all the information in one place, instead of it being scattered among many objects. I can ask things like

  • Is location 3,1 reserved by a job? Look it up in the To Location column. Answer: yes
  • Who is going to pick up iron 14? Look it up in the Take Item column. Answer: Wilma
  • Is the crafting table at 3,1 being used? Look it up in the Work in Location column. Answer: yes
  • What is Pebbles doing? Look it up in the Colonist column of both tables.

I can also iterate over all jobs to run their simulation code. And tables are easier to serialize than a graph of objects.

At this point you might be wondering how this relates to ECS. I think the main difference is that ECS is a subset of the kinds of things relational databases do.

  • E = Entity, typically a "game object", represented as unique id in the database
  • C = Component, represented as a table in a relational database
  • S = Systems, represented as a query involving a join of one or more tables

But neither inventory nor jobs are a "game object". They're separate tables with information about other entities. And most importantly, I want to have lookup on multiple columns. Most ECS implementations I've seen assume that lookups should be only on the entity id.

I think it's good to look at other things a relational database can do, as I think many of them will turn out to be useful in games. These relationship tables are just one example, and some ECS implementations have added them. Range queries, including spatial indices, are another example. Queries like "what objects are within 20 meters of Fred?" are just another type of database query.

For the summer r/roguelikedev event, I didn't build a generic reusable Table data structure, but I did implement a non-generic table for the jobs system. I was pretty happy with how it went, but there were some quirks that I glossed over in the description above. In particular, some queries worked better when the transport jobs table and the production jobs table were combined, and some worked better when they were separate. In a relational database, I could build a "view" so that I could have both, but I didn't implement that here. I hope to get some more experience by implementing non-generic tables several times. After that, I hope I'll have an idea of what I want in a generic table implementation.

Labels: ,

4 comments:

nornagon wrote at January 05, 2024 4:22 PM

I discovered this same pattern independently when working on a roguelike game, it felt like a lightbulb went off when I realized that I could resolve the conundrum of whether items should store their locations or locations their items or both by giving the answer: "neither!", and instead storing an item-location pair in a table, with indexes, just like a database. I never made the connection that ECS is a subset of a relational database, though—that feels like an important insight!

Amit wrote at February 20, 2024 12:08 PM

Yes, "neither" is a good answer that we sometimes miss!

I think there are lots of things from relational databases that we could adapt for use in games. For example some relational databases support indexing by lat/long. That's similar to what we need for a spatial partition data structure. Relational databases support sorting/filtering, and that might be similar to what we need for a action point turn queue.

Dylan Sprague wrote at April 29, 2024 10:54 AM

I wonder if you could just use a relational database as your source of truth - embedding SQLite is fairly straightforward for a desktop app, and there are WebAssembly-based versions for running it in the browser. You could use the database schema to enforce your invariants and keep data normalized, with a layer of code to map it to data structures for game logic. I'm not sure what the performance would be like for real-time games, though.

Amit wrote at April 29, 2024 2:02 PM

Dylan: I think it's a reasonable thing to try! I didn't here because sqlite wasm is much bigger than I wanted.