The way between graph rewrite and procedural generation
There is large gap between old-school drawing on tilemap of dungeon to create rooms, then connecting them by narrow tunnels, and more abstract ways of versatile procedural generation for different games.
I tried to make Godot plugin for procedural generation using Godot native node tree hierarchy, having some knowledge of string rewriting grammar (which I learned after watching video about lock-key generation). There isn't a way to make any graph using tree and string rewriting can't “split” and then “reconnect” verticies somewhere (or it would make it closer to term rewriting and more confusing and cumbersome), so grammar created in that way would produce linear connections of, for example, multiple rooms with inability to create mesh between some of them.
Gap between graph rewrite and category theory
My gusto was extinguished the moment I realized that conceptualizing good enough rewrite system won't be easy task. Mission graphs that are present on this article or graphs from this introduction to graph rewriting for procgen aren't abstract enough and don't provide enough information on how to implement. Comparing rules of “match and replace” to complexity of PBPO+ shows how much of control over graph is lost. What if we want subgraph that doesn't have any edges coming to A? or if we want to have exactly two edges going in and other subgraphs of same verticies won't work?
 |
 |
| Graph from “Generating Missions and Spaces for Adaptable Play Experiences” shown at www.boristhebrave.com | Example from “A PBPO+ Graph Rewriting Tutorial” |
Problem with Match-Replace rule – cannot control context
Category theory studies morphisms and objects, keeping structure, or something like that. Basically it is already formalized, complex framework that could be used in naming things correctly and choosing good rewriting system. Unfortunately there isn't much material that connects category theory objects to programming, especially in non-functional languages. In other words I have nice looking PBPO+ morphisms, but I don't know where to even start. And we still didn't precised what vertex or edge should contain as object in such plugin.
What we have and what we want
Cyclic dungeon generation of Unexplored has multiple phases which are quite a inspiration. First they create nodes that don't have static positions or space occupied – only prepositions between each other, giving relative positions and size. Then those nodes are snapped to grid of level, setting their position. Process of this mentioned in linked video is unknown to me.
Other than string rewrite prototypes, there is only framework given by Godot. Simple level could be generated by tree of root Tilemap and something like TileGenerator-derived children nodes. Such TileGenerator could be implementation of virtual (Node class) Generator and would specify that it extends Tilemap class. Everything could be implemented in custom TileGenerator script with algorithms operating on local tiles, digging through stone tiles to create rooms, tunnels and then copying tiles to above Tilemap, allowing building trees with TileGenerators.
One could export some variables to constructor parameters and instantiate such dynamically. One could use limiting tiles occupied space or some border, so that child (which is being evaluated and then result are sent above) of some TileGenerator needs to respect boundaries. But where is graph rewrite in it? It lacks dynamic of swapping things by rules, connecting and disconnecting, changing properties of edges and verticies.
More thinking must be done, lemme know what You think :}