![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
okay so, graph code
my two-week projects have been kind of erratic recently, or maybe i've been biting off increasingly more as i get more and more settled into doing them (i mean i have been doing them for more than a year now, which, is a while). lots of things that aren't really finished.
anyway this time i wanted to improve my graph generator by adding 'loose' or 'stretchy' edges
so in the abstract, a graph grammar system is incredibly flexible and very powerful. however, my implementation of graph grammars, and the specific expansions and embeddings that i'm using, are really quite limited, and they hamstring the system a bunch and limit me to only generating a pretty constrained subset of what's actually possible.
the biggest stumbling block i've been having is the case of distant nodes. there are three parts to this: one, the embedding code needs to generate an embedding as the graph is expanded, rather than all at once at the end -- this is so impossible graphs are rejected instantly when they happen, rather than maybe staying around for a lot of further calculation before needing to be rejected; two, my embedding never moves already-placed nodes around, it only places new nodes -- this is because moving nodes arounds is very difficult to do algorithmically and would require a lot more code to do physically; and three, in this embedding all nodes with an edge between them need to be adjacent.
what this means is that if a new dungeon graph is started with a start and an end room, then those rooms need to be adjacent, and no further graph expansion can push them apart. expansions might sever the link between the start and end rooms, for example to place a hallway between them, but that would just add a 'hallway' room that runs along the two rooms, not a hallway that pushes between them to separate them.
(this also comes up if/when i get graph embedding on a larger graph working -- when i was working on polyhedra, it was pretty trivial to make a graph out of a polyhedra by assigning a node to each face and an edge to each edge, and then it could be possible to embedd e.g., a world map graph onto an arbitrary polyhedra. but that would have weird coverage (like the world map only spanning half of the actual world shape, or w/e) unless it was possible to kind of knit a 'minimal' graph across the entire surface, say by generating a subdivided polyhedra and then using the original, non-subdivided polyhedra as a graph overlay, and then expand from there. but that would generally require having nodes in the knitted graph that have edges between them, despite not representing faces that are edge-adjacent on the actual subdivided polyhedra.)
so what i really wanted to do was add some form of 'loose' edge, that denotes connectivity but that doesn't imply that the shapes need to be directly adjacent. then i could generate a dungeon that's got a start-to-end initial graph with a big long loose edge between the rooms, and so then graph expansion could start by cutting into that edge.
(this also also comes up when thinking about graph subdivision -- generating one big 'world map' and then having each node in that graph generate its own area graph. if the world graph spits out, say, that the forest is connected to the town and the canyon and the river, it's difficult to figure out how to generate a starting graph that correctly places the respective exits to the town, canyon, and river areas while still retaining enough free space for the deck of 'forest' graph expansions to do something interesting. but if it's possible to just place those nodes correctly to start and hook them all to some central room with loose edges, then the graph is still very minimal while still having the placement guarantees that are needed.)
it turns out for dungeon graphs, what a 'loose' edge represents is pretty clear already: it's a hallway, and an expansion that happens along that edge can just place the new room somewhere where it overlaps with the hallway, and then cut the hallway into two pieces.
so this two week project was about doing that. i did... part of it?
partly the thing is that since haskell lets you divorce code so thoroughly, this was really about changing like three separate libraries:
also, when i actually render these things,
so i ended up doing the first item entirely, which is just abstract data-shuffling, and parts of the second and third items -- i have some new collision code written, but not enough to actually use, and i can successfully generate an initial graph for a circuit-based dungeon (or, theoretically, a linear start-to-end dungeon). i also figured out the rendering for hallways, which is neat because these are officially the first concave shapes that this setup can render!
i have some in-progress screenshots of what those graph outputs look like:
anyway this time i wanted to improve my graph generator by adding 'loose' or 'stretchy' edges
so in the abstract, a graph grammar system is incredibly flexible and very powerful. however, my implementation of graph grammars, and the specific expansions and embeddings that i'm using, are really quite limited, and they hamstring the system a bunch and limit me to only generating a pretty constrained subset of what's actually possible.
the biggest stumbling block i've been having is the case of distant nodes. there are three parts to this: one, the embedding code needs to generate an embedding as the graph is expanded, rather than all at once at the end -- this is so impossible graphs are rejected instantly when they happen, rather than maybe staying around for a lot of further calculation before needing to be rejected; two, my embedding never moves already-placed nodes around, it only places new nodes -- this is because moving nodes arounds is very difficult to do algorithmically and would require a lot more code to do physically; and three, in this embedding all nodes with an edge between them need to be adjacent.
what this means is that if a new dungeon graph is started with a start and an end room, then those rooms need to be adjacent, and no further graph expansion can push them apart. expansions might sever the link between the start and end rooms, for example to place a hallway between them, but that would just add a 'hallway' room that runs along the two rooms, not a hallway that pushes between them to separate them.
(this also comes up if/when i get graph embedding on a larger graph working -- when i was working on polyhedra, it was pretty trivial to make a graph out of a polyhedra by assigning a node to each face and an edge to each edge, and then it could be possible to embedd e.g., a world map graph onto an arbitrary polyhedra. but that would have weird coverage (like the world map only spanning half of the actual world shape, or w/e) unless it was possible to kind of knit a 'minimal' graph across the entire surface, say by generating a subdivided polyhedra and then using the original, non-subdivided polyhedra as a graph overlay, and then expand from there. but that would generally require having nodes in the knitted graph that have edges between them, despite not representing faces that are edge-adjacent on the actual subdivided polyhedra.)
so what i really wanted to do was add some form of 'loose' edge, that denotes connectivity but that doesn't imply that the shapes need to be directly adjacent. then i could generate a dungeon that's got a start-to-end initial graph with a big long loose edge between the rooms, and so then graph expansion could start by cutting into that edge.
(this also also comes up when thinking about graph subdivision -- generating one big 'world map' and then having each node in that graph generate its own area graph. if the world graph spits out, say, that the forest is connected to the town and the canyon and the river, it's difficult to figure out how to generate a starting graph that correctly places the respective exits to the town, canyon, and river areas while still retaining enough free space for the deck of 'forest' graph expansions to do something interesting. but if it's possible to just place those nodes correctly to start and hook them all to some central room with loose edges, then the graph is still very minimal while still having the placement guarantees that are needed.)
it turns out for dungeon graphs, what a 'loose' edge represents is pretty clear already: it's a hallway, and an expansion that happens along that edge can just place the new room somewhere where it overlaps with the hallway, and then cut the hallway into two pieces.
so this two week project was about doing that. i did... part of it?
partly the thing is that since haskell lets you divorce code so thoroughly, this was really about changing like three separate libraries:
Data.GraphGrammaritself needs to start caring about edge data, and it needs to do things like e.g., provide a lens for embedding edge shape data into the edge type, in addition to providing a lens for embedding node shape data into the node type. it also needs to start tracking new edges, and providing them to the embedding function in the same way it tracks new nodes -- basically it's been treating edges as unimportant, second-rate values for a while since i haven't ever actually been using edge data for anythingShape.HexEmbeddingneeds to figure out how to do something with that new edge data. this means a new type (LooseEdge Hex, specifically) for use as edge data, plus new hex collision code inShape.Hexthat can handle the relevant shapes. my currently-existing collision code is incredibly slow in all cases save for hex/hex collisions, so i need to figure out, at the very least, good hex/line and line/line collisions.Generator.DungeonGenneeds a new generator that actually uses these new types to design new kinds of dungeons that use loose edges.
also, when i actually render these things,
graphToSVG needs to understand what the new edge data type means and how it can be rendered correctly.so i ended up doing the first item entirely, which is just abstract data-shuffling, and parts of the second and third items -- i have some new collision code written, but not enough to actually use, and i can successfully generate an initial graph for a circuit-based dungeon (or, theoretically, a linear start-to-end dungeon). i also figured out the rendering for hallways, which is neat because these are officially the first concave shapes that this setup can render!
i have some in-progress screenshots of what those graph outputs look like:
