graphgram is a library for generating graphs using a transformative graph grammar.
This is useful if you want random graphs that have predictable structural motifs or patterns in them.
The motivating use case is procedural generation of story paths or maps in interactive fiction (i.e. games),
and the pioneering example of this is Joris Dormans' roguelike Unexplored
as described in this RPS article.
(A formal mathematical introduction to graph grammars can be found in these slides by Matilde Marcolli.)
The way that graphgram works is as follows. A basic graph grammar consists of a set of transformation rules.
Each such rule contains, at minimum, a left-hand side and a right-hand side: the rule has the form LHS → RHS.
- The left-hand side is a pattern that is used to match a subgraph of the current graph, using Ullman's 1976 subgraph isomorphism search algorithm.
- The right-hand side specifies a subgraph that will be pasted in as a replacement for the matching subgraph.
Beyond simply matching subgraph topologies, graphgram offers considerable flexibility in the way that the LHS pattern-matching occurs.
Each node and edge in the graph can have a label which can be a string or an arbitrary JSON object.
There is a simple query language for matching labels (or the user can define their own label-matching function).
The grammar specification also allows for constraints limiting the number and type of transformation rules that can be applied to generate any single graph.
The library can be called via the API of the Grammar class, or using the command-line tool bin/transform.js.
Grammars are specified using a JSON schema that is documented here.
All graphs generated by graphgram are directed.
Undirected edges can be represented using two directed edges, one pointing forwards and one backwards.
Dungeon grammar
The default grammar for the CLI, for demo purposes, is a dungeon-generation grammar that is fairly close to the following:
{
name: 'dungeon-grammar',
start: 'START',
rules:
[{ lhs: 'START', rhs: ['entrance', 'x', 'boss'] },
{ lhs: 'x', rhs: ['x','x'], limit: 3 },
{ lhs: 'x', rhs: { node: ['fork', 'x', 'die', 'x'], edge: [[0,1],[1,2],[0,3]] }, type: 'ending', limit: 3 },
{ lhs: 'x', rhs: { node: ['fork', 'x', 'live', 'x'], edge: [[0,1],[1,2],[0,3]] }, type: 'ending', limit: 3 },
{ lhs: 'x', rhs: { node: ['fork', 'x', 'x', 'x'], edge: [[0,1],[0,2],[1,3],[2,3]] }, type: 'fork', limit: 2, delay: 2 },
{ lhs: 'x', rhs: { node: ['crossroads', 'x', 'x', 'x', 'x'], edge: [[0,1],[0,2],[0,3],[1,4],[2,4],[3,4]] }, type: 'fork', limit: 1, delay: 2 },
{ lhs: 'x', rhs: { node: ['door', 'x1', 'x'], edge: [[0,1,'enter'],[1,2,'exit'],[0,2,'bypass']] }, limit: 3 },
{ lhs: 'x', rhs: { node: ['fork', 'x', 'x', 'x', 'rescue', 'x', 'x'], edge: [[0,1],[1,2],[2,3],[0,3],[3,4],[4,5],[5,6],[3,6],[1,4,'rumor']] }, type: 'rescue', limit: 1 },
{ lhs: 'x', rhs: { node: ['door', 'x1', 'x', 'rescue', 'x', 'x'], edge: [[0,1,'enter'],[1,2,'exit'],[0,2,'bypass'],[2,3],[3,4],[4,5],[2,5],[1,3,'rumor']] }, type: 'rescue', limit: 1 },
{ lhs: 'x', rhs: { node: ['chest', 'chest_contents', 'x'], edge: [[0,1,'open'],[1,2],[0,2,'ignore']] }, limit: 3 },
{ lhs: 'chest_contents', rhs: 'trap', weight: 2 },
{ lhs: 'chest_contents', rhs: 'treasure' },
{ lhs: 'chest_contents', rhs: 'weapon' },
{ lhs: 'x', rhs: { node: ['vial', 'vial_contents', 'x'], edge: [[0,1,'drink'],[1,2],[0,2,'ignore']] }, limit: 3 },
{ lhs: 'vial_contents', rhs: 'potion' },
{ lhs: 'vial_contents', rhs: 'poison' },
{ lhs: 'x', rhs: 'x1', delay: 10 },
{ lhs: 'x1', rhs: 'trap' },
{ lhs: 'x1', rhs: 'monster' },
{ lhs: 'x1', rhs: 'weapon', limit: 2 },
{ lhs: 'x1', rhs: 'treasure', limit: 3 },
{ lhs: 'x1', rhs: 'scenery', weight: 2 }
]
}
The full flexibility of matching any subgraph and replacing it with another subgraph of arbitrary topology (possibly with some overlap/reuse of nodes and/or edges from the matched subgraph) can be quite daunting and is probably overkill for most purposes.
In recognition of this, graphgram offers a few syntactical shortcuts for common types of transformation rule and graph
(corresponding to sequence grammars, context-free grammars, and so on).
These are fully described in the documentation for the JSON schema for the `Grammar`` class.
One of these syntactical shortcuts is heavily used by the above dungeon grammar: all the transformation rules in that grammar have a single node on the left-hand side. This means that the subgraph matching algorithm is not being heavily exercised by this grammar; it is effectively a context-free node replacement grammar.
The simplest kind of rule in this grammar has the form:
{ lhs: 'chest_contents', rhs: 'weapon' },
This simply means "replace a node whose label is chest_contents with a node whose label is weapon".
An example of a slightly more elaborate rule is
{ lhs: 'START', rhs: ['entrance', 'x', 'boss'] }
This replaces the node labeled START with a sequence of three nodes:
entrance→x→boss.
The edges connecting consecutive nodes are added by default when an array of node labels is given. This corresponds to inserting a sequence of nodes at a particular point (as in a string transformation grammar). For an example of a rule where the replacement subgraph is not just a linear chain, so that its topology must be specified explicitly, consider the following:
{ lhs: 'x', rhs: { node: ['fork', 'x', 'die', 'x'], edge: [[0,1],[1,2],[0,3]] } },
This replaces a node labeled x with a subgraph containing four nodes labeled (respectively)
fork (node 0), x (node 1), die (node 2) and x (node 3).
The edge clause in the rhs of this rule contains three tuples of the form [v,w] where v and w represent the indices of
(respectively) the source and target nodes in the replacement subgraph.
Thus, the subgraph contains a fork node that has edges to two new x nodes, the first of which then leads to a die node.
The first node on the RHS inherits the edges that are incoming to the LHS node, and the last node on the RHS inherits its outgoing edges
(this behavior can be overridden, as described in the JSON schema).
The actual rule that appears in the example grammar is slightly different from this:
{ lhs: 'x', rhs: { node: ['fork', 'x', 'die', 'x'], edge: [[0,1],[1,2],[0,3]] }, type: 'ending', limit: 3 },
The type and limit fields indicate that this rule has type "ending" and can only be used if fewer than 3 rules with that type have already been applied.
For examples of more sophisticated subgraph replacement rules that include context and nontrivial topology on the LHS, as well as compound expressions for matching/replacing node and edge labels, see the level.js example grammar which generates levels for the "roguelike snakelike" game nemato.de.