Why it is time to start thinking of games as databases

In the previous blog post, Building Games in ECS with Entity Relationships, I talked about the benefits of treating relationships between entities as first class citizens in a game. In this new blog post I’ll dive deeper into one of those benefits, and the futuristic capabilities it could unlock.

Sit back, relax and make yourself comfortable. This is a long one.

Part 1: Intelligent Agents

Imagine an NPC sitting in a space bar, minding her own business, when a human player walks in. This particular player just came back from a raid on a nearby space station and obtained a valuable artifact. This space station happened to belong to the NPC’s faction.

The NPC is no direct match for the player, so she decides to post a mission in the sector to take back the artifact from the player, in return for good standing with the faction. Within seconds the mission is accepted.

As soon as the player clears the planet, he is ambushed and forced to surrender the artifact back to the faction.

What would it take to empower agents in games to behave like this? Artificial intelligence is rapidly advancing to a point where we should expect to see in-game agents come up with self-directed goals and creative ways to achieve those goals. This will make game worlds feel more alive and immersive, and it could happen sooner than you think.

However, for an agent to truly act in this way we have to overcome a hurdle: the information it needs is locked up in data structures that don’t make sense without the game source code. To read this data in any meaningful way, an agent would have to write and execute code on the fly, which is a bad idea for more reasons than I care to list. So what’s the next best thing?

We could give agents an interface to query the game world.

There is a reason that we don’t see a lot of querying in games: queries imply using a database and those are, put plainly, too slow. Not only would we have to find a way to run thousands of queries per second and get the results back in time, we’d also have to synchronize the entire game world with the database at high frequency.

So where does that leave us? Should we start writing our own query engines? That’s a rhetorical question, bear with me.

What if these query engines not only already exist, but are at the core of many existing games? What if instead of synchronizing our game world with some database or library, the game world itself can be queried?

I’m talking of course about Entity Component Systems, which have gained popularity in recent years as an architecture for game development:

Disclaimer: I am the author of Flecs

Queries are a fundamental part of ECS. Take this (Flecs) code example:

world.system<Position, const Velocity>("Move")
  .each([](Position& p, const Velocity& v) {
    p.x += v.x;
    p.y += v.y;
  });

Here, Position, Velocity is the query of a “Move” system. This query finds all entities with at least the Position and Velocity components which the system then moves around.

Great! So we have a queryable entity framework. Does that mean we can start unleashing hordes of AI agents on our game worlds? Well maybe… but probably not yet.

You see, many ECS query engines were not (and still aren’t) designed as a mechanism to find facts about game worlds. Their purpose is to pull the right bits of data from memory so game code can do it’s job. This has loads of benefits (I talked about those at length in other posts), and for that reason ECS queries are great and an extremely useful things to have.

However, if I were an agent roaming an ECS game world, and all I could do was ask questions like “does this thing have Position?”…

We owe it to our agents to do better than that.

Part 2: Interesting Questions

What is an interesting question? An interesting question is a question that has an actionable answer (disclaimer: this is not an official definition, I’m totally making this up). Here are some examples of interesting questions:

• Is there anyone in this tavern that belongs to a rival faction?
• Which vendors in this city sell healing potions?
• What items are missing from my inventory if I want to craft a sword?
• Which spell would deal the most damage to my opponent?
• On which tiles can I build a windmill?
• In which ways can I interact with this object?
• What equipment can I mount on my spaceship?
• Where is the item I need for my active quest?
• How does a game answer interesting questions?

At first glance these questions have nothing in common with each other, and trying to build a query engine that could answer any of them, let alone all of them, seems like a futile thing to even attempt.

And yet, not only can we write an engine that can answer these questions. We can write one that does so efficiently by using a simple algorithm that has been known since the 1950s called backtracking (not to be confused with backpropagation). If we treat backtracking like a black box, this is what the inputs and outputs of the algorithm look like:

A black box with backtracking

To see how this works, let’s take one of the questions as example:

Which vendors in this city sell healing potions?

First we have to provide backtracking with a source of entities and facts. Facts are atomic bits of information we store about entities in our game world. A few examples of possible facts are:

• The entity is a river tile
• The inventory contains a sword
• The NPC’s faction is the Targaryens
• The player can cast healing spells
• The vendor is located in Whiterun
• The vendor sells swords

The third thing we have to provide is a list of constraints. We can think of constraints as filters that we apply to entities in the world. Without any constraints, backtracking would yield all entities. Conversely, by stacking constraints we can get ever more specific results.

Here are the constraints for our question:

1. The entity needs to be a vendor
2. The vendor needs to be in the same city as me
3. The vendor needs to sell healing potions

Note how with each constraint the list of possible answers shrinks:

1. [all vendors]
2. [all vendors in the city]
3. [all vendors in the city that sell healing potions]

Herein lies the magic of backtracking: it quickly eliminates large numbers of entities that don’t answer the question, so that evaluating each successive constraint takes less work.

In what is kind of a poetic turn of events, backtracking happens to also be at the core of the Prolog language, which was used in early artificial intelligence systems for tasks like complex planning and automated reasoning. It seems fitting to repurpose this old but powerful technology for the next generation of intelligent systems.

Now that we have a grasp of how entities, facts and constraints allow us to ask many kinds of interesting questions, let’s see how this translate into…

Part 3: A Query Engine for Games

It looks like we have everything in place to achieve what we set out to do initially: To provide in-game agents with a query interface so they can ask interesting questions about the world. We have:

• an Entity Component System with entities, facts and a query engine
• the knowledge to deconstruct interesting questions into smaller computable elements

But can we combine the two? Can we retrofit an existing ECS query engine so that it can support backtracking, or would that be like trying to force a square peg into a round hole?

Well, let’s take a closer look at our ECS query:

Position, Velocity

Does anything stand out? No? Nothing? What if I rewrite it like this:

1. The entity must have Position
2. The entity must have Velocity

It almost seems like I should be able to do…

1. [entities with Position]
2. [entities with Position and Velocity]

Could it be that…

That’s right, ECS queries are lists of constraints, which is what makes them a great candidate to solve with backtracking. Not only that, both Flecs and EnTT implement variations of backtracking to do exactly that!

Does this mean that both libraries can answer interesting questions? No!

As you may have noticed, all of the questions required more than one entity to answer. Take our previous example:

Which vendors in this city sell healing potions?

The entities involved in this query are:

• The player
• The city the player is in
• The vendors
• A healing potion

There aren’t many interesting questions you can ask about a single entity (is it a Tree? no? is it a Rock? no?), so a prerequisite for our query engine is that it should support facts that involve more than one entity. What’s a fact that involves more than one entity?

Right, that’s an Entity Relationship.

Part 4: The Rest of the Owl

If you’ve made it this far, congratulations. You’re halfway through.

We now have a rough outline for what the query engine will look like. To turn this into an actually useful thing though we still have some ways to go. Let’s again use this query as example to see why:

Which vendors in this city sell healing potions?

Say the player is in his home. His home is in the city of Whiterun. As we all know, there is a vendor in Whiterun that sells (or rather, buys) potions. To find this vendor, can we match the player’s location with the location of the vendor? Well no:

• The player is located in his home
• The vendor is located in Whiterun

To resolve this query, we need to consider a third fact:

• The player’s home is in Whiterun

And if we wanted to be strict about it, also this fourth fact:

• Whiterun is a city

We could easily make this scenario more complex. What if the vendor actually isn’t created as a Vendor but as a Shop which inherits from Vendor? The query engine now needs to consider a fifth fact:

• All shops are also vendors

And we still haven’t gotten to the part where we test for healing potions. What if there are many different kinds of healing potions?

In an upcoming blog post I’ll delve deeper into how we can actually build a query engine with supporting data structures that is capable of efficiently evaluating even complex queries like these.

For the remainder of this blog though, I’ll go over what entities, facts and queries actually look like in Flecs, which to the best of my knowledge is the only ECS currently capable of doing everything we just talked about.

The next part is definitely a bit on the dryer side, so unless you’re really interested in knowing the ins and outs of what a query language for games actually looks like, this is a good moment to skip to the end.

Entities and Facts

This is mostly a recap of what I talked about in Building Games in ECS with Entity Relationships. If you read that post you can safely skip this section.

Entities in an ECS are unique things, to which we can attach facts. Facts take one of two forms:

// Entity has component Component
Component(Entity)

// Entity has relationship (Relationship, Target)
Relationship(Entity, Target)

With this notation we could create an entity called Bob with component Position, which creates a single fact:

Position(Bob)

In the Flecs C++ API, this would be written down like this:

flecs::entity Bob = world.entity()
  .set(Position{10, 20});

Note that this fact is associated with a value {10, 20}. While this is very important for game systems, for the query engine we can mostly ignore it as the value doesn’t change which entities a query matches with.

A relationship, or a fact with two entities, can be written down like this:

// Bob likes Alice
Likes(Bob, Alice)

In C++ code, a relationship looks like this:

flecs::entity Alice = world.entity();
flecs::entity Bob = world.entity()
  .add<Likes>(Alice);

The next sections are about queries. Note that while the examples are written down using the Flecs query DSL, the same queries can also be created in the C/C++ APIs, and in the various language bindings.

Trivial Queries and Operators

Trivial queries are queries where all of the elements (called “terms”) are matched against a single entity. An example of a trivial query is the one that should look very familiar by now:

Position, Velocity

Query terms can have operators. For example, this query finds all entities that have Position but do not have Velocity:

Position, !Velocity

Some operators apply to multiple terms. This query finds all entities with Position that have Circle or Rectangle:

Position, Circle || Rectangle

Components can be matched optionally. The following query finds all entities with Position and optionally matches Velocity.

Position, ?Velocity

Relationships

Queries for relationships look very similar to trivial queries, except that they specify a relationship and relationship target. The following query finds Faction entities allied with Targaryen:

Faction, (AlliedWith, Targaryen)

Just like regular terms, we can apply operators to relationship terms. This query finds factions that are not allies with Targaryen:

Faction, !(AlliedWith, Targaryen)

We could also query for factions that are allied with Targaryen or Stark:

Faction, (AlliedWith, Targaryen) || (AlliedWith, Stark)

Wildcards

What if we want to find all alliances for all factions. For this we can use wildcards, as shown in the following example:

Faction, (AlliedWith, *)

The result of this query could look something like this:

Stark, (AlliedWith, Baratheon)
Stark, (AlliedWith, Targaryen)
Targaryen, (AlliedWith, Stark)
Baratheon, (AlliedWith, Stark)

Note how the Stark entity is matched twice by this query, once for each instance of its (AlliedWith, *) pair.

Alternatively, we may want to find entities that have any AlliedWith relationship pair, in which case we use the _ wildcard:

Faction, (AlliedWith, _)

The result of this query would look like this, with * indicating that there may be multiple matches:

Stark, (AlliedWith, *)
Targaryen, (AlliedWith, *)
Baratheon, (AlliedWith, *)

Wildcards can appear as any part of the term. The following examples are all valid wildcard queries:

// Find all entities that have any relationship with entity 'Stark'
(_, Stark)
// Find all components for all entities
*
// Find all entities with at least one component
_
// Find all pairs for all entities with wildcards
(*, *)
// Find all entities with at least one pair
(_, _)

Static Joins

Flecs queries can join data from different entities. The simplest form of this is a static join, where the joined entity is known at query creation time. The following query shows an example of a static join, where CurrentLevel is matched on the Game entity:

Position, Velocity, CurrentLevel(Game)

The Game entity between the parenthesis is called the term source. Because we know the entity at query creation time, this is called a static source. We can apply operators just like we can with regular terms:

Position, Velocity, !NightTime(Game)

This query won’t return any results unless the Game entity has the NightTime component.

Singletons

Singletons are a special case of static joins. The following example shows a query that returns a Game singleton:

Position, Velocity, Game($)

In Flecs, singletons are components that are added to themselves, which means we can rewrite the query to this without changing its meaning:

Position, Velocity, Game(Game)

We wouldn’t call static joins static, unless we also had:

Dynamic Joins

Dynamic joins retrieve a component from an entity that’s only known at query evaluation time. This is also known as a dynamic source.

Consider again this example of a wildcard query:

Faction, (AlliedWith, *)

What if we wanted to only find alliances that are at war? We would have to match AtWar on whatever is matched by the * wildcard.

The way that we can do this is by replacing * with a query variable as is illustrated in the following example:

Faction, (AlliedWith, $ally), AtWar($ally)

The ally variable forces the target of the AlliedWith pair to be the same as the source of the AtWar term, effectively joining the two terms!

Let’s modify this query so that we find:

• All faction entities
• That have an ally
• That is trading with the faction

Here we run into an interesting problem. How do we actually specify that the target of TradesWith is our original faction?

Faction, (AlliedWith, $ally), TradesWith($ally, ???)

If no explicit source is assigned to a term, Flecs automatically assigns a builtin variable called $this. With $this we can solve our problem:

Faction($this), AlliedWith($this, $ally), TradesWith($ally, $this)

Dynamic joins are a powerful tool when converting interesting questions to queries. Say we wanted to find whether a family member of a faction that is at war with one of our allies, is married to a member of our own faction. We could express this with dynamic joins:

Faction($this),                    // Find all factions
AlliesWith($this, $ally),          // with an ally $ally
AtWar($ally, $other),              // which is at war with $other 
MemberOf($person, $other),         // which has a family member $person
MarriedTo($person, $marriedTo),    // who is married to $marriedTo
MemberOf($marriedTo, $this)        // where $marriedTo is of the faction

Relationship Traversal

A limitation of dynamic joins is that we can’t find components that are an unknown number of steps away from our starting point.

Say we’re writing a UI system where widgets inherit Style from their parents. How would we write a query for this?

Let’s try to do this with dynamic joins first:

Widget, (ChildOf, $parent), Style($parent)

That works, but only if our direct parent has Style. What if it could be any parent? Maybe we can use multiple variables with optional operators?

Widget, 
(ChildOf, $parent), 
?Style($parent), 
?ChildOf($parent, $grandparent), 
?Style($grandparent),
?ChildOf($grandparent, $greatgrandparent), 
?Style($greatgrandparent),
...

Right so that doesn’t really work.

What we need is a way to traverse a relationship for an unknown number of steps, until we found a component. In Flecs this is done with query traversal operators. Here’s what that looks like:

Widget, Style(up(ChildOf))

This means “traverse ChildOf upwards until Style is found”. Because this is a common thing to do ChildOf can be left out:

Widget, Style(up)

We can extend this query to also support Style on the widget entity by adding the self traversal operator:

Widget, Style(self|up)

Relationship traversal is why queries in Flecs automatically match components inherited from prefabs. The traversal expression for inheritance is:

Widget, Size(self|up(IsA))

This behavior can be overridden by only providing the self operator:

Widget, Size(self)

Trait Queries

A trait is a property added to a component. Examples of traits often seen in games are Serialized or Networked. In Flecs, components are entities, and traits are components added to components. This means trait queries are business as usual for the query engine.

Adding a trait to a component uses the regular ECS API:

// Registration of networked component
world.component<Position>()
  .add(Networked);

// Entity with networked component
world.entity().set(Position{10, 20});

We can now write a query that matches all entities with networked components like so:

Networked($component), $component($this)

Component Inheritance

Inheritance is the ability to match entities by the base type of a component. Imagine we’re writing an RPG with a character class hierarchy:

Now let’s say we want to be able to write systems that:

• Iterate all units
• Iterate all units of a specific class (MeleeUnit, RangedUnit)
• Iterate all units of a specific type (Warrior, Archer, Wizard, Warlock).

Without inheritance we have a few options, none of them great. The first option is to just add all tags to entities explicitly:

flecs::entity my_warlock = world.entity()
  .add<Unit>()
  .add<RangedUnit>()
  .add<MeleeUnit>()
  .add<Warrior>()
  .add<Wizard>()
  .add<Warlock>(); // ugh...

The second option is equally unsexy, and requires us to enumerate lists of possible options in our queries:

// Query for all units
Warrior || Archer || Wizard || Warlock

// Query for all ranged units
Archer || Wizard || Warlock

Inheritance lets us clean up this code considerably. First we setup the inheritance relationships (note how these are relationship traits):

world.component<Unit>();
world.component<MeleeUnit>().is_a<Unit>();
world.component<RangedUnit>().is_a<Unit>();
world.component<Warrior>().is_a<MeleeUnit>();
world.component<Archer>().is_a<RangedUnit>();
world.component<Wizard>().is_a<RangedUnit>();
world.component<Warlock>().is_a<Wizard>().is_a<Warrior>();

To create a warlock entity, we can use the following code:

flecs::entity my_warlock = world.entity().add<Warlock>();

The warlock entity will now get matched by both of these queries:

// Query for all units
Unit

// Query for all ranged units
RangedUnit

Transitivity

If Lydia lives in Whiterun, Whiterun is a city in Skyrim and Skyrim is a province of Tamriel, does Lydia live in Tamriel?

That, in a nutshell, is transitivity. In Flecs transitive relationships are marked with the Transitive trait:

world.component<LocatedIn>().add(flecs::Transitive);

This tells the query engine to automatically traverse LocatedIn in the appropriate direction (up or down). Consider the following example:

LocatedIn(Lydia, $Location)

This query would yield:

$Location = Whiterun
$Location = Skyrim
$Location = Tamriel

We could also ask “in which city does Lydia live?”

LocatedIn(Lydia, $Location), City($Location)

This would yield:

$Location = Whiterun

Alternatively, we could also ask what is located in Skyrim:

(LocatedIn, Skyrim)

This could yield:

Lydia,
DragonBorn,
Whiterun,
...

Query Scopes

Sometimes we want to treat the output of several terms in a query as a single result. Say that we want to find all villages in Skyrim that do not have a vendor that sells potions. We could express this with the following query:

Village($village), 
LocatedIn($village, Skyrim), !{ 
  LocatedIn($vendor, $village)
  Vendor($vendor),
  Sells($vendor, Potions)
}

With this query, if a village contains any vendor that sells potions, the not operator in front of the group will negate the result, and the village will not match the query.

And that is how you draw an owl [1]

Concluding Remarks

Here I should probably say something about how we now achieved all of the goals we set out to achieve at the start of this blog post. How we can let intelligent agents roam our game worlds, have them ask interesting questions, and bathe in emergent behaviors as our worlds come to life.

Can we really though? GPT4 offers glimmers of hope:

Honestly though, there is still a lot of work left before this vision can turn into reality. This includes the obvious (LLMs seem to require a small fortune to train and run at scale), as well as things that I think are still missing from the query engine, such as the ability to incorporate theory of mind (“does faction A think I have an alliance with faction B”).

Regardless, it’s exciting stuff to work on, and it has been a lot of fun seeing what the community has already built with it! Even if this does not end up being used by hyper intelligent NPCs, we still got some useful tools out of it along the way :)

If you’ve enjoyed this blog post, consider giving the Flecs project a ⭐️

GitHub - SanderMertens/flecs: A fast entity component system (ECS) for C & C++

Also check out the Discord community which has lots of amazing people working on bleeding-edge projects:

Join the flecs Discord Server!

[1] https://design.tutsplus.com/tutorials/how-to-draw-an-owl-with-ink-liners--cms-28656