While firmly rooted in the 4X genre, gr4Xity doesn’t look, feel, or play like anything else. The focus on emergent systems-based gameplay warrants taking a fresh look at data structures, execution models, and even the style of programming itself. This is especially true to support the complex interactive economy and artificial intelligence systems in development.
One of the riskiest endeavors game developers/publishers of any size can undertake is developing their own game engine. While relying on third parties carries its own risks, reinventing the wheel simply doesn’t scale. The joy of games, however, is in their diversity. Game developers can have fun too–and do so inventing new ways to take us new places.
State of the Art
Over the past fifteen years, Entity Component Systems (ECS) have grown in adoption as the heart of both independent and commercial game engines. ECS cleanly separate code (systems) from data (in components owned by entities). This allows for composition of complex behaviors from simpler individual elements–a much more flexible approach for systems-based gameplay than object-oriented methods based on inheritance.
While the ECS approach can be optimized for performance–systems run independently on each entity–these three core elements by themselves don’t provide a first-class means to handle interactions between related entities.
A recent essay by Sander Mertens, “Why it is time to start thinking of games as databases“, focuses on this concern:
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.
Mertens has continued to innovate as author of one of the most popular open-source ECS frameworks, Flecs, adding support for “entity relationships” in 2021. Inspired by logic programming in Prolog, this provides an interface to build explicit links between entities, as well as to identify linked entities for operation by systems. This enables constructing and querying graphs, including hierarchies and other kinds of relationships as a core part of building your game. Super cool!
While you can optionally attach components containing metadata to characterize relations (edges), Flecs at its core is based on an unweighted directional graph–all the arrows in the diagram above are the same thickness.
Reactive ECS like Entitas have innovated in a different direction. Instead of an explicit query language like Flecs is building, Entitas adds an additional structural element–groups–which listen to changes in entity composition and dynamically update pre-cached collections of entities for disparate processing by systems. And how can you not love their ASCII structural graph?
+------------------+
| Context |
|------------------|
| e e | +-----------+
| e e---|----> | Entity |
| e e | |-----------|
| e e e | | Component |
| e e | | | +-----------+
| e e | | Component-|----> | Component |
| e e e | | | |-----------|
| e e e | | Component | | Data |
+------------------+ +-----------+ +-----------+
|
|
| +-------------+ Groups:
| | e | Subsets of entities in the context
| | e e | for blazing fast querying
+---> | +------------+
| e | | |
| e | e | e |
+--------|----+ e |
| e |
| e e |
+------------+
This is a form of reactive programming, a powerful declarative technique for separating logic from control flow. The logic of group membership is declared once, and a separate system applies that logic at the appropriate time in the correct context. Flecs uses an underlying reactive system to power pre-caching for its more generalized query language.
Declarative programming is the secret sauce behind the success of two of the building blocks of the modern tech world–HTML for declaring the structure of and relationships between web pages and the SQL query language for declaring relationships between rows and columns of data tables. When you write a web page in HTML, you don’t tell the web browser step-by-step how to render it; instead the browser engine figures this out based on your declarations. When you write a SQL query, you don’t order about the database operation-by-operation; instead a query optimizer generates and executes a query plan based on your declarations. Declarative code is generally more flexible and more expressive, with a syntax that’s both more human-friendly and machine-friendly–more easily parsed and generated by other systems.
One of the main obstacles to wider adoption of graph databases in industry has been the lack of a declarative query language standard like SQL. First-generation graph database languages were primarily imperative, tasking end-users with control flow–and even second-generation declarative approaches typically lack a human-friendly syntax. For example, despite neo4j’s Cypher being “inspired by SQL“, it’s largely a wrapper around JSON, forcing users to toggle back and forth between two very different syntaxes in the same expression. String-matching is case-sensitive, forcing you to use archaic regular expressions for case-insensitive operations. Boo!
Done right, declarative programming is ideal for rule-based systems. Gameplay and simulation elements in gr4Xity are designed as rules. Can they be simply implemented as rules?
As Flecs author Sander Mertens put it in “Why Vanilla ECS Is Not Enough“:
ECS seems to be a good fit for declarative programming, where behavior is driven not by imperative statements (“do this”) but by declarations (“there shall be this”). After all, we create entities and assign components to them, and systems get executed as a result. Imperative code is only found in systems, and everything is great.
Or is it? Vanilla ECS says notoriously little about this.
Designing and implementing relational systems in support of rule-based emergent gameplay and advanced AI is an active area of experimentation–one that a game like gr4Xity stands to gain tremendously from.
Game economies are weighted directed graphs. Game design tools like Machinations take advantage of this, but what about game implementation? My virtual economy service architecture for Xbox Live, which powers everything from the Minecraft Marketplace to Microsoft Flight, is at its heart a graph database tracking directional transfers between source and destination accounts. But to Sander Mertens’s concern, the richness of this data is available ex-post to analysts and data scientists via structured data in a relatively high-latency database–not to agents in near-real-time in the game itself.
AI agents aptly operate over weighted directed graphs. Neural networks are themselves weighted directed graphs. In a future blog post, we’ll explore pathfinding over gr4Xity‘s “star lanes”, which are also weighted directed graphs– emerging dynamically from the gravitational relationships between your Arcship and the procedurally-generated stars.
Here is a beautiful example from another independent game developer, using directed graphs for procedural gameplay progression and illustrating some of the awesome potential of these data structures. Consider this earlier open-source experiment by the same developer utilizing the same techniques and illustrating some of the difficulties.
Currently authoring is done by using three different tools for drawing (creating/connecting nodes), moving nodes, and adding triggers.
Imperatively building and maintaining complex graphs is an exceedingly difficult problem. Fortunately, there may be a better way.
Embracing rule-based declarative programming to manage the chaos of game development and operations is what Chaoskampf Studios is all about. With over a decade of research and applied experience with graphs in artificial intelligence and the game industry–and stimulated by new inspiration from Flecs and Entitas–it’s time to trade reinventing wheels for launching rockets…
Declaring Graphecs
Graphecs is the first entity component system designed for reactive graphs between entities. Specifically, weighted directed graphs emerge and evolve dynamically based on declarative rules.
A counter-example might help illustrate. In Flecs, it’s up to you to manage the control flow around entity relationships, step-by-step in the C++ syntax–the epitome of modern object-oriented imperative programming. For example:
struct Eats {
int amount;
};
entity Apples = world.entity();
entity e = world.entity();
e.set<Eats>(apples, {2});In English:
- 1. Create an
Eatscomponent that stores an integeramount. - 2. Create an
Applesentity from the world context. - 3. Create an
eentity from the world context. - 4. Create an
Eatsrelationship frometoApples, setting theamountto 2.
Graphecs lets us generalize this pattern declaratively, in a much more human-friendly syntax freed from the constraints of the imperative object-oriented C++ style:
graphecs/create 'world context [
components: [is-eater is-eaten]
entities: [
Apples [is-eaten]
e [is-eater]
]
connections: [
Eats [is-eater?] [is-eaten?] [2]
]
]We’ve specified and created a game object using three types of things:
componentsdeclare data containers. Componentswith no datasets (names only) can serve as binary tags, aiding query composition and generalization.entitiesdeclare identified compositions ofcomponents. Here we define two entities, labeledeandApplesto align with the Flecs example, each tagged with acomponentthat can control how it interacts with othercomponents.connectionsdeclare dynamic relationships betweenentities. Each is identified by a name (in this caseEats), followed by two sets of queries that specify the source and destinationentities, here fromentitieswith theis-eatercomponentto those with theis-eatencomponent. Finally, a block of code is specified that determines the weight of any edge of thisEatstype betweenentities.
In Graphecs, relationships between entities (edges in the graph) can be constructed, weighted, and destructed reactively based on your declarative definitions. The Graphecs engine handles all necessary control flow so you can just count on the graph being there and up-to-date when you need it. While you can manually add/change/remove edges imperatively in system code, reactive declarations provide a more powerful and expressive primary modus operendi. Add a new entity with the is-eater component, and it’ll attach itself to Apples as well!
From the REPL, we can see a directional, weighted edge object has been created from e to Apples without us having to manually execute a set() command.
>> ? world/entities/e/components/eats/1
WORLD/ENTITIES/E/COMPONENTS/EATS/1 is an object! with the following words and values:
lid word! e
cid word! Eats
rid word! Apples
left object! [id is-eater Eats is-eater? Eats?]
right object! [id is-eaten is-eaten?]
weight integer! 2lid and rid are the unique identifiers for the source and destination entities, cid for the connection–together forming a compound key for the edge. In contrast, right and left are references to the objects containing these linked entities’ identified components, making their data available from the edge. Finally, there’s the weight itself, inferred as an integer type from the connection declaration.
Some quick notes on syntax. Square brackets [] are easy to type unshifted vs. the menagerie of curly brackets {}, angle brackets <>, and parentheses () oh my! in the Flecs example, so these are the primary structural delimiters in Graphecs. Lisp-style kebab-case is preferable to snake_case for identifiers, again avoiding awkward shifting for underscores and with greater availability of the hyphen on the numeric keypad. The parser utiliized by Graphecs is smart enough not to try to subtract literal words from each other!
The C/C++ use of = for assignment is unshifted versus the shifted colon : for declaration definitions in Graphecs, but the C-style thus requires a separate operator for logical tests (double-equals ==) which is confusing and bug-inducing for new programmers. Graphecs reserves the single equals symbol = for more intuitive comparison.
There’s no need to delimit statements in Graphecs with parentheses ala Lisp or terminate them with semi-colons ala C. Instead, semi-colons initiate unexecuted comments. The Graphecs syntax also avoids problematic and unnecessary comma-delimiting in sets, for example the lists of words available in the left and right entities referenced by the Eats edge above.
The specifications above in Flecs and Graphics don’t do anything–there are no systems–so this doesn’t approach being a game… yet. We’ll revise and expand this contrived example, illustrating fuller capabilities of Graphecs by introducing interactivity.
Example: Repeated 2nd-Price Auction
Let’s design a mechanism to allocate the supply of Apples according to demand from multiple hungry agents. Simplicity for demonstration purposes is the goal, so we’ll implement a truthful generalized second-price auction.
We’ll collect the configuration data we need in a context, starting with components.
Components
game-config: context [
components: [
demand [
quantity: 0
willingness-to-pay: $0
]
supply [
quantity: 0
marginal-cost: $0
]
]
...Instead of empty tags, we’ll store some data in our components (typing implicit from default values) to track a simple model of supply and demand and supply for foodstuffs, including reservation prices (in dollars) for buyer and seller.
Graphecs separates each component’s data elements into distinct contextual namespaces, such that an entity could have both demand and supply components with their own quantity counts. We’ll see how this is addressed with path notation further below.
Let’s also simply declare some entities composed of these components, overriding default values where desired:
entities: [
Apples [supply [quantity: 3]]
e [demand]
f [demand]
g [demand]
]We’ve added a couple more hungry entities (f and g) and given our Apples a limited supply. We’ll worry about initializing the reservation prices in our entities’ components elsewhere.
Collections
Similar to Entitas, reactive groups called collections are automatically created and maintained to make it easier to identify and iterate over entities with specified archetypes. In Graphecs, collections of archetypes are defined not only by unique combinations of components, but also connections and conditions.
Graphecs is really a graph-first entity collection system model, as collections generalize the tagging and segmentation roles of components.
Conditions
Conditions are core to the querying functionality of Graphecs. They allow hierarchically building new collections based on components, connections, and other conditions!
Each condition is declared with a question word identifier, a spec for the relevant archetype, and a block of code that return a logical true or false to set the condition for tagging and membership in collections. This code accesses one or more components available in the archetype using path notation, e.g. an entity’s supply/quantity is a separate counter than its demand/quantity.
conditions: [
has-demand? [demand?] [demand/willingness-to-pay > 0]
in-supply? [supply?] [supply/quantity > 0]
can-sell? [in-supply? in-demand?] [1 < length? in-demand]
]Conditions are also added as data-free tag components in entities belonging to the specified archetype so they can be easily evaluated in code elsewhere.
The can-sell? condition makes sure we have more than one bid to continue operating a 2nd price auction. Note how this depends on an in-demand? query that hasn’t been declared yet. So let’s do that!
Connections
When we declare the connections that define dynamic graphs, we can utilize these dynamically collected conditions to provide a clear separation between conditional and operational logic.
connections: [
in-demand [in-supply?] [has-demand?] [
right/demand/willingness-to-pay
]
]The in-demand connection declares a directional graph from suppliers with available quantity to demanders with a positive willingness to pay (WTP). This provides a mechanism for the principal, Apples, to receive messages from agents (e, f, and g) declaring their preferences.
The weight of edges needn’t be static but can reactively depend on the character of the source (left) and destination (right) entities. Here the weight is simply the positive WTP itself–demanding entities bid their full demand. How do we know it’s positive? The has-demand? condition guarantees it. Edges will only be created to entities with a positive WTP, and edges will automatically detach if a joined entity’s WTP falls to zero. This reactivity simplifies code and safe composition of behaviors. We’ll make good use of it elsewhere!
As mentioned, connections also generate dynamic collections, in this case the in-demand? collection referenced in the can-sell? condition further above.
Wait, how can the declaration of the can-sell? condition depend on the in-demand? connection when it hadn’t been “defined” yet? Both depend on the in-supply? condition. This is the vast gulf between declarative and imperative code. Imperative-style “variable definitions” only occur in systems code in Graphecs–declarative declarations are a fundamentally different concept. While imperative code is a linearizable set of code executed step-by-step, declarative programming can be spectacularly nonlinear.
Old-school C/C++/C#/Java developers may find this spooky, but this is how human language operates. Often we need to wait for additional context to evaluate the antecedent of a pronoun for example, with art in the ambiguity and unresolved uncertainty. It’s (what is?) no wonder linguists also utilize graphs.
As a result, declarative languages are generally more expressive and easier to learn than training people to iteratively “think like a computer” to reach the Zen of some “programmer mindset”. Though here we’re going for flexibility in expressiveness rather than ambiguity!
Edge Systems
Graph edges in Graphecs play a dual role, both as data contained within the source entity’s component as well as first-class citizens operated on directly by systems. Future plans include promoting edges to full entities capable of hosting arbitrary data components ala Flecs to support finer-grained system definitions as well as reacting to intersections between different graphs.
Currently, each edge-based system declaration consists of an identifier (eats here) that matches the identity of a declared connection, followed by three blocks of code. The first specifies a trigger that determines whether or not the system will execute on an edge in the graph each iteration. The next list determines the order triggered edges are processed by the system, an empty block ([]) defaulting to the order of creation. Finally, the third block of code is what’s actually conditionally executed in the specified order. Components from the source entity are accessible via the left context, the destination entity via the right context. All three blocks of code have direct access to each relevant edge’s weight.
What does this look like in practice?
edge-systems: [
in-demand [ ; operate on bids below reserve
weight < left/supply/marginal-cost
][ ; lowest bid first
a/weight < b/weight
][ ; retract insufficient bid
print [rid "didn't meet reserve price for" lid]
right/demand/willingness-to-pay: $0
]
]Here we’ll operate on edges of the in-demand graph from each source entity, but only when the bid is less than the seller’s reserve price. We reject failing bids in order from lowest to highest by setting each rejected buyer’s demand for the auctioned Apple to zero, which causes them to “retract” their failed bid. The edge disappears as soon as the target willingness-to-pay is zero because the has-demand? collection is reactively updated to remove the entity, which reactively then updates the in-demand graph which depends on this collection.
Reactivity in Graphics is itself processed as a graph!
Entity Systems
Let’s finally declare a more traditional entity-based system to execute our auction mechanism and allocate payouts accordingly, though the Flecs-like utilization of the graph by the system is anything but traditional. This is the most substantial block of imperative code declared in our configuration, executed each tick of the main event loop on each principal entity that can-sell?
entity-systems: [
auction [can-sell?] [
; imperatively operate on graph from principal
sort/compare in-demand func [a b] [
a/weight > b/weight ; highest bid first
]
winner: in-demand/1/right ; highest bidder
price: in-demand/2/weight ; second price
; output auction results to console
print [
winner/id "wins at" price ":"
in-demand/1/weight - price "consumer surplus"
"+" price - supply/marginal-cost "profit"
]
; transfer quantity from supply to demand, sating WTP
supply/quantity: supply/quantity - 1
winner/demand/quantity: winner/demand/quantity + 1
winner/demand/willingness-to-pay: $0
]
]- 1. This system imperatively operates on the principal’s
in-demandgraph, sorting it from highest to lowest bid using an anonymous comparison function, then identifying the highest bidder and second-highest price. Thecan-sell?condition guarantees we have a top two bids to operate over, so we don’t need to worry about any additional tests or control flow. - 2. Then print the results of this graph operation and identification to console.
- 3. Finally, update the principal and winning agent with the payoff structure. Setting the winner’s TWP to zero dollars stops them from bidding on additional units by reactively removing the edge between principal and agent, updating the appropriate tags and collections in the process. This reactivity means we don’t have to imperatively program any of this flow ourselves!
Another word on syntax! Graphecs counts inclusively, starting at one, so the indices of the first and second bids are 1 and 2 respectively as should be expected. This is much more friendly to humans working with countable things like sets of entities and edges. You won’t be manually wrangling pointer offsets in Graphecs like you would in C or C++, which is where exclusive (0-based) counting comes in handy. This is why human-friendly declarative languages like SQL use one-based counting.
Initializing Systems
Last but not least, we need some way to declare and initiate some sort of event loop. Staging systems to run on different schedules is common in ECS designs. Graphecs takes an optional set of entity systems with additional pre- and post-loop code–all together called initializers–that can accomplish this when starting gameplay, utilizing the initial data configuration.
initializers: [
random-demand [demand?] [
random/seed now/time/precise
][ ; randomize WTP for each buyer
demand/willingness-to-pay: random $10
][]
random-auction [supply?] [][
supply/marginal-cost: random $2
print ["How Do You Like Them" self/id "???"]
][ ; event loop
while [not empty? collections/can-sell?] [
execute
]
]
]
] ; end contextThe random-demand initializer resets the random seed so the program produces different outputs each time, then this and the random-auction initializers assign uniformly-distributed reservation prices to the agents and principal. Finally, the random-auction initializer kicks off a simple event loop that includes a call to the Graphecs execute function which operates edge and entity systems until the can-sell? condition no longer holds, at which point the program has nothing else to do so will exit.
All Together Now!
So far, all that is just data, blocks of configuration that could be stored in a separate file, even composed from multiple sources. Turning it into a live game context is easy:
>> graphecs/create 'second-price-auction game-configThe create function takes the configuration context and kicks off all the necessary code generation to populate the game context, setting a reference to it in the global context with the provided word ('second-price-auction).
This new game context includes a play function that executes any initializers, starting the game loop:
>> second-price-auction/playThis returns the following:
How Do You Like Them Apples ???
g wins at $6.43 : $1.91 consumer surplus + $4.74 profit
e wins at $6.35 : $0.08 consumer surplus + $4.65 profitPlaying the auction mechanism again yields different results with a different random seed, sometimes with one or more agents failing to meet the principal’s reserve price, so fewer apples are sold–sometimes none (and never all, since only one buyer is left for the last apple, insufficient for a 2nd-price auction).
>> second-price-auction/play
How Do You Like Them Apples ???
f didn't meet reserve price for Apples
g wins at $6.33 : $0.29 consumer surplus + $4.33 profit>> second-price-auction/play
How Do You Like Them Apples ???
e didn't meet reserve price for Apples
f didn't meet reserve price for ApplesVoilà!
Having previously built and simulated market mechanisms imperatively (this research was painfully programmed in Java!), Graphecs and its rule-based declarative approach is a huge breath of fresh air. The entire source “code” for this iterative multiparty auction mechanisms is less than 70 lines of highly-readable declarations–the only control flow the initiating while loop that repeatedly executes the game’s systems.
The full source Graphecs source for this example is here, though the Graphecs library itself is not yet publically available. Pre-compiled executables for MSDOS (zipped exe) and Linux (tgz) are provided so you can try it yourself. From the Windows command prompt for example:
C:\Temp>how-do-you-like.exe
How Do You Like Them Apples ???
e wins at $7.22 : $1.08 consumer surplus + $5.69 profit
f wins at $4.69 : $2.53 consumer surplus + $3.16 profitThe complex work of imperatively managing individual entities and their interactions is largely left to the game engine, reducing development time to focus more on new paths opened by rule-based design. In AAA games built on commercial game engines, making data available from one part of the game to systems in another can require large-scale rearchitecting and refactoring. With Graphecs, it’s simply a matter of declaring the appropriate graph structure.
I put “code” in quotes above because in Graphecs, code and data are the same thing. Graphecs is a rare homoiconic language, as is the Prolog language that inspired entity relationships in Flecs. Program code is data and can be manipulated by the language as such, enabling metaprogramming (dun dun dun). ECS developers are used to composing entity behaviors out of components; in Graphecs, everything is composable from simper building blocks.
Advanced applications allow modifying the core elements of Graphecs programs and thus changing dynamic behavior at run-time. Self-modifying code is particularly useful for evolutionary simulations and learning algorithms.
Example: Random Dynamic Graphs
Printing a few lines to console is cute. Let’s make things more visual and more interactive. We should be able to see edges being created and destroyed on demand by simple rules as conditions change. In this case, let’s make edges from green->yellow and yellow->red nodes… while we randomly change node colors.
This blog is long enough already, so I won’t break down the entire Graphecs source declarations for this example. But the idea is simple: we generate some entities with random values for a node component.
components: [
node [
radius: 0
position: 0x0
color: 0.0.0
blink-steps: 0
]
frame [title: ""]
...Each entity with a node component will be represented as a circle on the visual graph with a given radius placed at a pixel position with a color that will randomly change to another color after some number of timeframes (which itself will be randomized whenever the color changes, so the interval between each color cycling is random).
There’s also a frame component which stores the title of the window that’ll be opened. This will also handle drag interactions, allowing the user to move each node’s initial random position. How do we do that? With a dynamic graph of course!
connections: [
drag [node?] [frame?] [left/node/position]
go [green?] [yellow?] weight-edge
caution [yellow?] [red?] weight-edge
]The drag connection declares edges between entities with node components to any with the frame component, signaling the node‘s position in the frame as the edge’s weight. As a node’s position is changed by the user dragging with the mouse, this signal will reactively update the rest of the system.
We’ll also generate edges from green? to yellow? entities as well as from yellow? to red? As you may have guessed, these are simply conditional queries on a node’s color:
conditions: [
red? [node?] [node/color = red]
yellow? [node?] [node/color = yellow]
green? [node?] [node/color = green]
]The weighting for these color-based graphs is declared to come from the weight-edge “function”, which we can also define as just a block of code that will be evaluated in the correct context:
weight-edge: [
reduce [
average-color left/node/color right/node/color
min left/node/radius (4 / 3) * pi * (square left/node/radius) / (distance left/node/position right/node/position)
]
]This illustrates two powerful feature of Graphecs:
- Homoiconicity means we can compose code and data from simpler blocks of code and data, more quickly and cleanly than with more rigid languages. To use the same code to determine weights for both
goandcautiongraphs, we just defined a block of code with a word (weight-edge) and substituted that word in our declarative definitions anywhere we needed it. Just like natural language! - Graphecs edge weights aren’t limited to simple data types like integers as in our previous examples. Reactive weights can even be multi-dimensional, in this case a 2D set:
- 1. a reactive color defined by the arithmetic average of the linked
nodes’colors (separately defined based on a HSV color model) and - 2. a reactive thickness in (sub)pixels defined by a gravity model: the contribution to the gravitational force from the left node to the right is directly proportional to the left node’s mass (treating it as a sphere of uniform density) over the distance to the right node. If we took the product of this directional vector with the gravitational vector going the other direction, right to left, we would get the net gravitational force between the two nodes. Note that we cap the thickness by the radius of the source node, preventing it from blowing up if we move two nodes together.
- 1. a reactive color defined by the arithmetic average of the linked
Thanks to the power of the Red toolchain, this Graphecs program compiles to a native code executable with no external dependences. You can download and play with the Windows version (zipped exe). Let me know how it works for you in the comments! Graphecs is still in early development and changing rapidly along with gr4Xity.
Next Up
We’re still a ways from something recognizable as a “game”. Can this approach really scale to more complex interactive systems in a low-latency game loop? In our next post, we’ll build a variation on the “Hello World” of video games, Allan Alcorn’s Pong (1972). This will give us space to talk about input and rendering, as well as tackle some more complex challenges with graph-first solutions: collision detection and artificial intelligence.
Leave a Reply