Jobs table implementation for r/roguelikedev project

From Red Blob Games's Blog

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:

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:

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:

Production jobs are of the form:

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: programming , structure