Suppose we want to create a graph grammar that makes rectangular grids.
A first cut at it would be something like "expand outwards from any edge that hasn't already been used", something like this:
o-o o-o-o
| | => | | |
o-o o-o-o
with the appropriate tags used to keep track of whether we already expanded or not. The problem with this is that while it's locally correct (everything is a square) it's not globally correct. The toplogy is all wrong, so even if we had the rules to stitch things together, it wouldn't fit.
Instead, we need a design where there is only one rule that can be applied at any given time, and this rule maintains invariants that preserve global structure. (This strips out most of the point of using a graph grammar and makes it more like a conventional programming language, but I should at least be able to demonstrate that it's possible.)
My idea here is to work on just one edge at a time, with a "mouse" (or turtle, if you prefer) adding squares on until it reaches the end, then turning the corner to work on the next edge. I mark the nodes "e" for one on the boundary of the grid, "c" for the corners, and "i" for internal nodes.
c-------c
| | | | |
v-e-i-i--
| | | |
e------
| | | |
c------
c-------c (moving down)
| | | | |
e-i------
| | | | |
v-e------
| | | |
c------
c-------c (down again)
| | | | |
e-i------
| | | | |
e-i------
| | | | |
v-c------
c-------c (turn the corner)
| | | | |
e-i------
| | | | |
e-i------
| | | | |
e-e------
| |
c->
Here's the Soffit grammar which implements this design:
{
"version" : "0.1",
"start" : "X->Y->Z [h]; X2->Y2->Z2 [h]; X->X2 [v]; Y->Y2[v]; Z->Z2[v]; X[c]; Y[c]; Z[up]; X2[c]; Y2[e]; Z2[c]",
"C->M [h]; C[c]; M[up];" :
"C->M [h]; C[e]; M[e]; A[left]; B[c]; A->B [h]; A->C[v]; B->M[v];",
"M->R [v]; L->R [h]; L[e]; R[e]; M[left];" :
"M->R [v]; L->R [h]; L[e]; R[i]; M[e]; N[left]; N->M[h]; N->L[v];",
"M->R [v]; L->R [h]; L[c]; R[e]; M[left];" :
"M->R [v]; L->R [h]; L[c]; R[i]; M[e]; N[left]; N->M[h]; N->L[v];",
"M->C [v]; C[c]; M[left];" :
"M->C [v]; C[e]; M[e]; A[c]; B[down]; A->M[h]; A->B[v]; B->C[h];",
"M->T [h]; T->B [v]; T[e]; B[e]; M[down];" :
"M->T [h]; T->B [v]; T[i]; B[e]; M[e]; N[down]; M->N[v]; N->B[h];",
"M->T [h]; T->B [v]; T[e]; B[c]; M[down];" :
"M->T [h]; T->B [v]; T[i]; B[c]; M[e]; N[down]; M->N[v]; N->B[h];",
"M->C [h]; C[c]; M[down];" :
"M->C [h]; C[e]; M[e]; A[c]; B[right]; M->A[v]; A->B[h]; C->B[v];",
"M<-L [v]; L->R [h]; L[e]; R[e]; M[right];" :
"M<-L [v]; L->R [h]; L[i]; R[e]; M[e]; N[right]; M->N[h]; R->N[v];",
"M<-L [v]; L->R [h]; L[e]; R[c]; M[right];" :
"M<-L [v]; L->R [h]; L[i]; R[c]; M[e]; N[right]; M->N[h]; R->N[v];",
"C->M [v]; C[c]; M[right];" :
"C->M [v]; C[e]; M[e]; A[up]; B[c]; M->B[h]; C->A[h]; A->B[v];",
"B->M [h]; T->B [v]; T[e]; B[e]; M[up];" :
"B->M [h]; T->B [v]; T[e]; B[i]; M[e]; N[up]; T->N[h]; N->M[v];",
"B->M [h]; T->B [v]; T[c]; B[e]; M[up];" :
"B->M [h]; T->B [v]; T[c]; B[i]; M[e]; N[up]; T->N[h]; N->M[v];"
}
And here's what it looks like after 40 iterations:
(Graphviz isn't smart enough to know which orientation I wanted.)
From working on examples, here's a few things I've been thinking of adding:
- Text output, either as dot or as an ASCII diagram
- "Save as soffit" so a large diagram can be used as a start position or pattern
- Ruleset output / visualization
- Run multiple rulesets
- Wildcard on the right graph to include all elements already in the left graph, in case we're just adding some items.
- "Why doesn't X match" --- this would be hard, but useful for debugging
- Output stats on which rules get used.
- Movie mode--- would need to initialize positions from the previous layout to have any chance of this working.