graph embedding
two week projectssss
these past few months have been kind of erratic wrt actually working on a concrete project. the two weeks before last (mar 16-31, i mean) i didn't actually do anything. kind of a mess.
but these two weeks (april 1-15) i did do something! specifically i got an embedding using loose edges working. previously i had gotten a very basic render working, and used it to draw some 'circuit' dungeons, but i never got the embedding or the expansions working, which meant that i couldn't actually generate a dungeon yet, i could just generate a template. these two weeks (and a little in late february because like i said i haven't been cleanly demarcating these things that well) i wrote an embedding that, for the most part, actually works.
here are some screenshots before i get to the part where i explain what still doesn't work
so there was a lot. most visibly, now there are hallways! that's a big step. what this means generally is that edges are now treated more-or-less the same as nodes, rather than being mostly ignored -- previously, edges weren't treated as things that could have collision, or store data, or have their changes be provided to the embedding, or anything like that. this also radically changed the way the hex embedding works, since in order to properly fix edges and nodes in place i needed to change the way it processed all the changes a lot.
but also while in the process of doing all that, i generalized the graph grammar code so that it wasn't always running in random. now it can run in any arbitrary monad. that's neat because it radically expands the ways in which this code can be used -- for example, it would be possible to run it through
but what that, and also some of the extensive debugging i did for the edge code, revealed to me is that this code is just lousey with strictness problems. in my mind, the code was all very simple and elegant: when looking for an expansion, the graph generator is capable of generating a lazy list of all possible expansions, which it tries one by one until it gets a match. then the rest of the (very long) list gets discarded and never has to be evaluated. as a part of that, too, we generate a graph embedding for every possible expansion, and go through the list until we find one that works, and then we discard and ignore the rest. if those are actually lazy lists, it's fine. it's a nice clean way of using haskell's laziness to our advantage.
but as you might be getting an inkling, that's not how things actually go. these lists of expansions are sequenced, which means we turn
in the mean time, the loose edges thing has definitely fixed one of the major problems of the generator. it's possible to make a dungeon with a skeletal 'starting' graph, that correctly positions various important rooms, and then goes on to subdivide without crushing everything together and perpetually making the level generation a big tree with no real interconnections. this can be really useful, though i'm only using it in the most basic ways so far. one of the things that this enables is proper graph nesting: making a big 'world map' graph, where each node in that graph is then expanded out using its own custom generator for its region type (e.g., city, cave, forest, etc), since i could write a skeleton-graph generator that places all the important outgoing connections to other zones in the right places and then trusts the graph expansions to turn that basic web into something a lot more complex. so that's very enthusing.
that being said, the embedder that i wrote still has a lot of limitations, and now even though my expansion code can handle a lot more contextful expansions, the embedder can still only place nodes very simply -- if you have a new node that's connected to three or more already-fixed nodes, then it'll always fail to embed that node. that's a big issue for things like lakes, rivers, or coastlines, that need to have structural edges in addition to their 'walking' edges to keep the graph layout coherent. that's probably the next big step to take, before i can demo out actual 'world maps' that e.g., start with lakes and rivers and canyons and coastlines and coherently keep water routes flowing all through them. that'll be neat to do, though.
definitely not for the next two-week project though; i'm really burnt out on graphs right now.
these past few months have been kind of erratic wrt actually working on a concrete project. the two weeks before last (mar 16-31, i mean) i didn't actually do anything. kind of a mess.
but these two weeks (april 1-15) i did do something! specifically i got an embedding using loose edges working. previously i had gotten a very basic render working, and used it to draw some 'circuit' dungeons, but i never got the embedding or the expansions working, which meant that i couldn't actually generate a dungeon yet, i could just generate a template. these two weeks (and a little in late february because like i said i haven't been cleanly demarcating these things that well) i wrote an embedding that, for the most part, actually works.
here are some screenshots before i get to the part where i explain what still doesn't work
- first embed test
- less buggy; no collisions
- room/room collisions
- denser graphs
- a false confidence that the code had all its bugs worked out
- first generations after monad generalization
- after big edge collision rewrite
- final edge generation
so there was a lot. most visibly, now there are hallways! that's a big step. what this means generally is that edges are now treated more-or-less the same as nodes, rather than being mostly ignored -- previously, edges weren't treated as things that could have collision, or store data, or have their changes be provided to the embedding, or anything like that. this also radically changed the way the hex embedding works, since in order to properly fix edges and nodes in place i needed to change the way it processed all the changes a lot.
but also while in the process of doing all that, i generalized the graph grammar code so that it wasn't always running in random. now it can run in any arbitrary monad. that's neat because it radically expands the ways in which this code can be used -- for example, it would be possible to run it through
IO to get an interactive graph expander. this also means eventually i'll be able to pull out the acc type variable (the graph accumulator state) and just use some kinda state monad, which will help simplify the types a little. a graph grammar's type is currently GraphGrammar m p q acc gr n e, and like, anything i can do to remove type variables from that is great.but what that, and also some of the extensive debugging i did for the edge code, revealed to me is that this code is just lousey with strictness problems. in my mind, the code was all very simple and elegant: when looking for an expansion, the graph generator is capable of generating a lazy list of all possible expansions, which it tries one by one until it gets a match. then the rest of the (very long) list gets discarded and never has to be evaluated. as a part of that, too, we generate a graph embedding for every possible expansion, and go through the list until we find one that works, and then we discard and ignore the rest. if those are actually lazy lists, it's fine. it's a nice clean way of using haskell's laziness to our advantage.
but as you might be getting an inkling, that's not how things actually go. these lists of expansions are sequenced, which means we turn
[m a] into m [a]. and because all of the items in the list might be running code in the monad, we have to evaluate the entire list. this means that this code needs to fully evaluate every possible expansion and embedding that's considered, even after the code has successfully found a match, because it's possible for the unpicked expansions to change the monad state (here it's random seed, but it could be anything). this is a big problem and it means the code is doing like, 10x, 100x, about as much work as it really needs to, and probably goes a large part towards explaining why it's so slow. so. that's not good. but it is nice to know about, because this is a huge place to try some kinda optimization, at which point this code will probably be, uhhh, way way faster. i just gotta figure out some limitations that would make that change possible. we'll see how that goes.in the mean time, the loose edges thing has definitely fixed one of the major problems of the generator. it's possible to make a dungeon with a skeletal 'starting' graph, that correctly positions various important rooms, and then goes on to subdivide without crushing everything together and perpetually making the level generation a big tree with no real interconnections. this can be really useful, though i'm only using it in the most basic ways so far. one of the things that this enables is proper graph nesting: making a big 'world map' graph, where each node in that graph is then expanded out using its own custom generator for its region type (e.g., city, cave, forest, etc), since i could write a skeleton-graph generator that places all the important outgoing connections to other zones in the right places and then trusts the graph expansions to turn that basic web into something a lot more complex. so that's very enthusing.
that being said, the embedder that i wrote still has a lot of limitations, and now even though my expansion code can handle a lot more contextful expansions, the embedder can still only place nodes very simply -- if you have a new node that's connected to three or more already-fixed nodes, then it'll always fail to embed that node. that's a big issue for things like lakes, rivers, or coastlines, that need to have structural edges in addition to their 'walking' edges to keep the graph layout coherent. that's probably the next big step to take, before i can demo out actual 'world maps' that e.g., start with lakes and rivers and canyons and coastlines and coherently keep water routes flowing all through them. that'll be neat to do, though.
definitely not for the next two-week project though; i'm really burnt out on graphs right now.
