Subgraphs and Function Graphs

In this post, I will discuss how we went about adding support for Subgraphs to our graph editor and Graph Interpreters. We’ll look at what Subgraphs are, why we need them, how we added them, how Subgraphs may be promoted to Function Graphs, and what room for improvement we currently see.

What’s a Subgraph? What are they good for?

A Subgraph is a graph contained within another graph. Analogous to code, you may think of a graph as a function that in turn calls another function: the Subgraph. We tend to denote the graph that calls the Subgraph as the Parent Graph. Many game engines and content authoring tools support Subgraphs, but there are lots of variations. Some just use Subgraphs as a simple grouping mechanism, in which a set of nodes can be collapsed into a single Subgraph Node. Others support Subgraphs through a full-on Function Graph concept, in which any piece of a graph may be exported as a reusable function. Common to both these approaches is that there exists a graph node, the Subgraph Node, that either contains a Subgraph or references a Function Graph.

As I see it, there are two main reasons for supporting Subgraphs:

• Grouping. Graphs tend to become messy monsters, and grouping pieces of it using Subgraphs is one way to create order. One other way of creating order I have been thinking about is adding support for creating colored, named background regions, but that’s for another time.

• Re-usability. Any Subgraph concept is a good stepping stone towards support for Function Graphs. Our goal was to first add support for Subgraphs where the actual Subgraph is contained within the Subgraph Node — i.e. the contained Subgraph can only be shared with copy-paste and modifications do not propagate between copy-pasted copies — and then, once we got that working, make it possible to export the Subgraph to a reusable Asset, which gives us something analogous to Function Graphs. Splitting work up into manageable chunks like this makes it more fun, since you see results more readily, and you don’t have to sit on a big branch for too long.

Inputs and Outputs

A Subgraph doesn’t do much unless it defines a set of Inputs and Outputs. We decided to add the definition of these Inputs and Outputs to all our graphs instead of having a separate type for Subgraphs. Here are all the properties that a graph object has in The Truth:

enum {
    TM_TT_PROP__GRAPH__NODES = 0, // subobject_set(GRAPH_NODE)
    TM_TT_PROP__GRAPH__CONNECTIONS, // subobject_set(GRAPH_CONNECTION)
    TM_TT_PROP__GRAPH__DATA, // subobject_set(GRAPH_DATA)
    TM_TT_PROP__GRAPH__COMMENTS, // subobject_set(GRAPH_COMMENT)
    TM_TT_PROP__GRAPH__INTERFACE, // subobject(GRAPH_INTERFACE)
};

You can see the nodes, connections, data, and comments, which were all there before — the new thing is the Interface. It is represented by a separate Truth type, with these properties:

enum {
    TM_TT_PROP__GRAPH_INTERFACE__INPUTS = 0, // subobject_set(GRAPH_INPUT)
    TM_TT_PROP__GRAPH_INTERFACE__OUTPUTS, // subobject_set(GRAPH_OUTPUT)
};

Each Input is an object with these properties (Outputs have the same properties):

enum {
    TM_TT_PROP__GRAPH_INPUT__DISPLAY_NAME = 0, // string
    TM_TT_PROP__GRAPH_INPUT__ID, // string
    TM_TT_PROP__GRAPH_INPUT__TYPE_HASH, // uint64_t
};

The Display Name is for representing these Inputs and Outputs in the UI. The ID is a unique identifier, so we can be sure to which Input or Output a connection goes. The Type Hash is the hash of the type name that the Input or Output expects.

There’s a good reason for adding this Interface directly to the graph instead of to some object specific for Subgraphs: Down the road, this approach will make it very easy to promote a Subgraph to an Asset (a Function Graph), but we’ll get back to that near the end of this post.

We also need two new graph node types: the Input Node and the Output Node. Below is a tiny example graph below with these two nodes present. These two nodes are used within the Subgraph, to make it possible to connect stuff to the Inputs and Outputs defined in the Interface.

The Input Node and Output Node dynamically create their connectors based on the set of Inputs and Outputs defined in the Interface of the graph they belong to. When designing this, we had to choose between having a separate node for each Input or coalescing all Inputs in a single Input Node. We chose to go with the latter, but for the convenience of the user, it is possible to spawn multiple Input nodes.

In the image above, you may have noticed the + at the bottom of the Input and Output Nodes. When connecting to it, it looks at the other end of the connection and uses that name and type to create a new Input or Output. This is currently the main way to add new Inputs and Outputs. In addition, there is a panel where you can rename and delete them. This is another reason for displaying all Inputs or Outputs instead of having separate nodes for each; with separate nodes, it would make no sense to have a + connector.

The Subgraph Node: A Node with a Graph Inside

The third, and final, new node type required is the Subgraph Node. We have an optional generic data blob associated with all nodes. In the case of the Subgraph Node, this data blob contains a graph object; the Subgraph.

The Subgraph Node looks at the Interface of the graph it contains and, similarly to the Input and Output nodes, dynamically creates connectors for all the Inputs and Outputs. It also has the handy + connector for creating new Inputs and Outputs. Double-clicking the Subgraph Node opens the Subgraph it contains, switching current graph view to view that graph.

Actually creating Subgraphs

Now that we have all the nodes required we should ask ourselves: How do we actually create the Subgraph? One way is to just create a Subgraph Node and open the empty Subgraph (double-click the node) and add stuff to it. But the user probably wants something more powerful, such as selecting a bunch of nodes and turning those into a Subgraph. Here we could re-use the code we already had for copying nodes between graphs: copy-paste.

In the image above I have selected a bunch of nodes. Selecting Create Subgraph will do the following:

• Create a Subgraph Node at the center of the area that the selected nodes occupy.

• “Cut & Paste” all selected nodes and all connections between the selected nodes to the Subgraph contained inside the new Subgraph Node.

• Use the dangling connections — i.e. those connections that have one node in and one node outside the selection — to figure out sensible Inputs and Outputs.

• Replace all dangling connections: In the Parent Graph, we replace them with connections to the Subgraph Node. In the Subgraph, we spawn Input Nodes and Output Nodes and replace the dangling connections with connections to those nodes. See the two images below.

Interpreting it

The Machinery has one Interpreter for each of the two graph types in the engine: The Entity Graph and the Creation Graph. The Entity Graph is for gameplay scripting, while the Creation Graph is for managing resources in the CPU-GPU borderland. Tobias has blogged about the Creation Graph here and here. It’s the Interpreter’s job to actually run the graph: Each node type has code associated with it that takes some inputs, does some computations, and sends out the result to any nodes down the line. At first, adding Subgraphs into this mix sounded a bit hard. The Interpreter does a lot of pre-calculations based on the nodes and connections, and only after that runs the actual node-specific code. Throwing another graph into the middle of the interpretation processes was begging for trouble, so we settled for a simpler approach: Flattening the graph.

What this means is that instead of recursively handling Subgraphs during interpretation, we do a pre-pass where all the Subgraphs are expanded. The first thing the Graph Interpreter does is that it imports the graphs from The Truth into some acceleration structs, using the tm_graph_importer_api. This API used to have only a single function: import, but now it has two:

struct tm_graph_importer_api
{
    tm_graph_import_result_t (*import_shallow)(const struct tm_the_truth_o *tt, uint64_t graph_id, const struct tm_graph_node_type_i *types, uint32_t num_types, struct tm_temp_allocator_i *ta);
    tm_graph_import_result_t (*import_flattened)(const struct tm_the_truth_o *tt, uint64_t graph_id, const struct tm_graph_node_type_i *types, uint32_t num_types, struct tm_temp_allocator_i *ta);
};

import_shallow does not expand Subgraphs, it does exactly what the importer did before: It goes through the Truth object of the graph and creates acceleration structures for performantly reasoning about the graph. This is the function that the graph editor uses since it just wants to show the Subgraph Node, but not it’s contents, with the possibility of double-clicking it, opening the contained Subgraph.

import_flattened adds a pre-pass to the import process. Internally, it starts off by calling a function named flatten_graph, which adds all the nodes, connections, etc to lists, except for Subgraph Nodes, Input Nodes, and Output Nodes. If it stumbles upon a Subgraph Node it will instead recursively call flatten_graph, which will continue to add all nodes, connections, etc to the same lists. Whenever it finds an Input Node or Output Node inside a Subgraph, it will ignore the node. But it won’t ignore the connections to it, it will patch them to the matching connections on the Parent Graph’s Subgraph Node. When this is done it continues the import in the same manner as import_shallow.

The two Graph Interpreters now use import_flattened. Switching them to use this function is the only change I needed to do inside the Graph Interpreter when adding support for Subgraphs — the Interpreters have no clue what Subgraph is.

Function Graphs: Reusable graph assets

I promised early on that our strategy should allow us to easily move from only supporting Subgraphs (the Subgraph is contained inside the Subgraph Node and can only be used once) to Function Graphs. Function Graphs are reusable Subgraphs that have been promoted to an Asset instead of living inside the node.

In The Machinery, an Asset is a thing that can be displayed by the Asset Browser. Each Asset has these properties in The Truth:

enum {
    TM_TT_PROP__ASSET__NAME = 0, // string
    TM_TT_PROP__ASSET__DIRECTORY, // reference(ASSET_DIRECTORY)
    TM_TT_PROP__ASSET__OBJECT, // subobject(*)
};

Name is the filename to be displayed in the Asset Browser. Directory is a reference to a Truth object representing a directory. Object is the actual thing that the Asset contains, it can be of any type. The Object also dictates the file extension to be displayed after the filename, by the use of a File Extension Aspect, essentially a piece of data that may be associated with any The Truth type. If the Object implements the File Extension Aspect, then that aspect will tell the Asset Browser which extension the Asset should have.

Back to the problem at hand: Function Graphs. In the image below we see a Subgraph Node (named Check Direction, you can name the Subgraph Nodes using the label field available on all nodes). We’ve added a context menu item to it called Create Subgraph Prototype. When chosen, it will clone the Subgraph contained inside the Subgraph Node and then wrap it inside one of those Assets described above. This is done by creating a new Asset object in The Truth and setting the Object property to the Subgraph just cloned. The Name of the Asset is taken from the label of the Subgraph Node. The Directory is set to be the one currently viewed in the Asset Browser. The new Asset is then added to the Asset Browser so that it shows up properly.

The new Asset is shown below, it has the extension entity_graph because this Subgraph came from an Entity Graph. A Subgraph Prototype from the Creation Graph would have the extension creation_graph, as dictated by the File Extension Aspect **on the Asset’s Object.

The only thing that remains is to make the Subgraph Node somehow use this Asset. We do this using our prototyping system. We create an Instance of the Object contained inside the Asset and assign it as the Subgraph Node’s Subgraph. Double-clicking the Subgraph Node will now open this Instance. Any changes to the Asset will be reflected in the Instance, but the user may also create overrides inside the Instance, changing, moving, or removing any node or connection.

We now have functionality equal to that of Function Graphs, the user can create additional Subgraph Nodes that use the same Asset as Prototype. This is done using the Prototype picker that is visible while the node is selected, as shown in the gif below. Choosing a Prototype in this picker will replace the node’s current Subgraph with an Instance of that Prototype.

Future improvements

I am quite pleased with how all this turned out, but there are some issues that I would like to address at some point:

• It is currently only possible to add Inputs and Outputs using the + connector. There exists disabled code for manually adding them, but we currently have no good way of figuring out which types to make available to the user — i.e. we have no central point where we store a list of ‘blessed types’ that may be used within a graph, the node’s themselves may use any type on their connectors. One idea I had as I was writing this sentence is to iterate over all the registered node types, look at all the connectors and assemble a list of those types.

• The Creation Graph currently has it’s own concept of inputs and outputs, used for parameterization of the Creation Graphs and making it possible for one Creation Graph to reference another. There are some striking similarities to the stuff I built for Subgraphs, such as input nodes, etc. But there are some differences. We are still on the fence about combining these two concepts.

• It would be nice to have a way to quickly spawn Subgraph Nodes with a prototype already set, avoiding a two-step. We could do this by enumerating all Assets that contain a graph, and show those in the node-spawning menu.

• The flattening of the graph that we do for the interpreter is a simple approach. But it has two problems, the first is that it does not support recursion, allowing it would cause a stack overflow while expanding the graphs. The second is performance. We may want to add some ‘caching’ of the graphs down the line, making sure that any graph only has to be imported from The Truth once. It may even store the result of the compiled graph — although that would require us to reason about what values the Inputs had during compilation, as this affects the result. Both these problems probably mean that we have to stop flattening the graph in the future, and instead move the expansion of Subgraphs to the interpreter. However, I’m certain that the current way was a good idea, just to get this big ball rolling.