okay gamedev challenge status post time!
there's technically another like, 36 hours before it's "over", but i think i've pretty solidly hit the limit of what i can add in that time.
so when i made the last post-mortem post i was all, yes, 3d rendering, that's what i'll be working on next, and if you've been following me on mastodon or on my programming tumblr you have probablyyyy noticed that's not what i've been working on. instead, i started working on the graph generator again! since i mean, i did only work on it for a week last time.
that's mostly because right after i made that post, i 1. watched some gdc, including a randomized lttp run, and 2. did some bloodborne chalice dungeon crawling. so i was like "hey you know what's neat? random dungeons and random unlock trees", and that got me thinking about getting back into working on a dungeon generator. or, specifically, a dungeon unlock flowchart.
so when i left off last time, i had a working graph embedding that drew nice hexagonal graphs.
i initially wrote down a bunch of 'power-ups' which each had a bunch of different powers, because one of the neat things about the lttp randomizer is that it considers alternatives: you need the master sword OR the cape to cross the barrier. you need the book of mudora OR the titan's mitt and the flute to enter the desert palace. i, uh, also basically instantly threw those away, since alternatives are (probably???) a lot trickier to solve for. instead, i mostly focused on 'keys' and 'locks'.
but this wasn't specifically a key/lock update, it was more just a generalized "improve the graph generator" effort. there were several things i got working additionally, that were maybe just as important: first, differently-sized rooms, and then differently-shaped rooms. (the rendering for those is actually still super ad-hoc, since i wasn't able to generalize it. so literally only hexes of any size + those three shapes (1x2, triangle, diamond) are supported. also, even if i fixed the renderer, only convex shapes work for the placement code i've written. so there are some serious limitations here that i'd like to fix.)
i also started experimenting with actual generators -- sure, i put together this big graph expansion framework, but that's kind of useless without an equally-intricate set of instructions to build the graphs. everything i'm using right now is really rudimentary, and is still mostly just "randomly pick a room, randomly place it against an existing room", and there's a whole world of more complex operations that i'm totally not using right now.
but the main thing are the lock-and-key puzzles i got working. there are only a few basic expansions that i'm using:
so those are all comparatively simple expansions, and they all preserve connectivity (if a room was reachable at the start of an expansion, it's still reachable at the end). so i can just run those expansions as much as i want, and it'll slowly complicate the dungeon layout.
it would actually be possible to add in alternatives fairly easily (like, an expansion that places two side rooms with a key each, and then adds in a room with two locked doors connected to it), and then trust the other expansions to complicate that further, but i haven't actually experimented with that much. something that would be much harder to handle would be 'small keys', as in, one-use key tokens that each unlock any one of a number of small key doors. i think just having random graph expansions would end up with cases where it could be impossible to progress if you use your keys to open the wrong doors.
(the next major step contentwise would be to make different expansions based on different room types, like e.g., have a forest-with-river zone that generates cosmetic, un-traversable 'across the river' edges, and only allow one-way unlockable exits when they transform a stream edge, and then render that in-game as knocking over a tree. add in more shapes of things, and have certain room types only be certain shapes, to allow for hallways and rooms and the like. stuff like that could add a lot of character to certain zones, since you'd traverse them in different ways. right now the dungeons are pretty uniform in structure, since the same expansions are running across the entire thing.)
there are a few really big limitations of this system, currently. one, the embedder is kind of dumb and can only place new rooms, not move existing rooms around. this actually has some really major repercussions in terms of generation implications: if any two rooms are generated next to each other, they will always be next to each other, even if we run a million expansion iterations. it's impossible for a new room to push them apart. which means it's impossible to, say, start the generation off with a few locked-circuit iterations, to make a bunch of loops, and then run the rest of the expansions to spread those loops out, so that the entire map (in most cases, statistically) will end up looping back on itself at the ends.
two, it's impossible to separate edges unless they're specifically matched on: there's no way to say "split this room in two and move half of its edges to the new room", for example. that means it's also impossible to recursively subdivide a room. imagine generating a simple map, but where all the nodes are huge hexes with lots of space inside them. then turn each node into its own dungeon level, making sure to put rooms at the correct places along the edges of the hex so that they end up maintaining proper connectivity. that's a major goal for this project, and it's still totally impossible.
third, it's basically impossible to propagate information through the dungeon. i had a planned expansion that was "find a room with an open connection and a locked connection, and then in the room of the open connection add a new room, with that connection locked with the same key" (to spread out locked doors so that each key isn't ever only used in one room, basically), and it's not actually possible currently to say "the same key", because that information is only known in the matched subgraph, and only used in the expanded graph, and actually those two things can't share information at all. likewise, i kinda wanted to have a 'difficulty' level, that rose by one with each step, except again the state of the matched node is only known in one place, and it's not where the data for the expanded node is.
i have a few ideas for fixing those things, or at least some of them, but the code is really not there yet. so i think this is a really neat thing that i've put together, but also there's sooooo much left to do before it's what i would call 'finished'.
still, on the whole i'm really pleased with this! it's an actual use for this code i've had sitting around for a year, and in these two weeks i've taken it from "here's some hexagons" to something that could be an actual, genuine map layout for a game. it still needs a lot of work, though, even for that: adding start/finish lines, or enemies, or boss rooms, etc, even ignoring all that complicated algorithmic junk above. but pretty good progress for two weeks, and i'm pretty hyped for whatever it is i decide to work on for the next two weeks.
also i've been doing this by having the embedder output an .svg file of the graph, and so far i've just been taking screenshots and posting pngs. but here are some Original, Authentic svg images:
a few ~50-room dungeons:
a few ~100-room dungeons:
(there are other in-progress shots/blurbs on my code screenshot tumblr if you want to read the whole backlog)
there's technically another like, 36 hours before it's "over", but i think i've pretty solidly hit the limit of what i can add in that time.
so when i made the last post-mortem post i was all, yes, 3d rendering, that's what i'll be working on next, and if you've been following me on mastodon or on my programming tumblr you have probablyyyy noticed that's not what i've been working on. instead, i started working on the graph generator again! since i mean, i did only work on it for a week last time.
that's mostly because right after i made that post, i 1. watched some gdc, including a randomized lttp run, and 2. did some bloodborne chalice dungeon crawling. so i was like "hey you know what's neat? random dungeons and random unlock trees", and that got me thinking about getting back into working on a dungeon generator. or, specifically, a dungeon unlock flowchart.
so when i left off last time, i had a working graph embedding that drew nice hexagonal graphs.
i initially wrote down a bunch of 'power-ups' which each had a bunch of different powers, because one of the neat things about the lttp randomizer is that it considers alternatives: you need the master sword OR the cape to cross the barrier. you need the book of mudora OR the titan's mitt and the flute to enter the desert palace. i, uh, also basically instantly threw those away, since alternatives are (probably???) a lot trickier to solve for. instead, i mostly focused on 'keys' and 'locks'.
but this wasn't specifically a key/lock update, it was more just a generalized "improve the graph generator" effort. there were several things i got working additionally, that were maybe just as important: first, differently-sized rooms, and then differently-shaped rooms. (the rendering for those is actually still super ad-hoc, since i wasn't able to generalize it. so literally only hexes of any size + those three shapes (1x2, triangle, diamond) are supported. also, even if i fixed the renderer, only convex shapes work for the placement code i've written. so there are some serious limitations here that i'd like to fix.)
i also started experimenting with actual generators -- sure, i put together this big graph expansion framework, but that's kind of useless without an equally-intricate set of instructions to build the graphs. everything i'm using right now is really rudimentary, and is still mostly just "randomly pick a room, randomly place it against an existing room", and there's a whole world of more complex operations that i'm totally not using right now.
but the main thing are the lock-and-key puzzles i got working. there are only a few basic expansions that i'm using:
- take any two connected rooms, and on one end add a key. on the other end, add one or two locked doors leading to dead-end treasure rooms
- take any one room. add an open edge to a new room, and move a random percentage of the first room's keys to the new room
- take any two rooms that have an open (not locked or one-way) edge between them. break that edge, and in its place add a looping circuit: add a new room, and add edges between it and the two initial rooms so that there's some random combination of open, one-way, or one-way unlockable edges between the three rooms, pointed so that you can always run a loop around them (there's also a version of this that runs on a single room, adding two new rooms with a looping circuit)
- take any two rooms that have an open edge between them. keep that edge, and add one room off each room (with the new connections maybe being one-way or one-way unlockable), with the two new rooms connected through a locked door. one of the two new rooms will have a third new room attached, with the key.
so those are all comparatively simple expansions, and they all preserve connectivity (if a room was reachable at the start of an expansion, it's still reachable at the end). so i can just run those expansions as much as i want, and it'll slowly complicate the dungeon layout.
it would actually be possible to add in alternatives fairly easily (like, an expansion that places two side rooms with a key each, and then adds in a room with two locked doors connected to it), and then trust the other expansions to complicate that further, but i haven't actually experimented with that much. something that would be much harder to handle would be 'small keys', as in, one-use key tokens that each unlock any one of a number of small key doors. i think just having random graph expansions would end up with cases where it could be impossible to progress if you use your keys to open the wrong doors.
(the next major step contentwise would be to make different expansions based on different room types, like e.g., have a forest-with-river zone that generates cosmetic, un-traversable 'across the river' edges, and only allow one-way unlockable exits when they transform a stream edge, and then render that in-game as knocking over a tree. add in more shapes of things, and have certain room types only be certain shapes, to allow for hallways and rooms and the like. stuff like that could add a lot of character to certain zones, since you'd traverse them in different ways. right now the dungeons are pretty uniform in structure, since the same expansions are running across the entire thing.)
there are a few really big limitations of this system, currently. one, the embedder is kind of dumb and can only place new rooms, not move existing rooms around. this actually has some really major repercussions in terms of generation implications: if any two rooms are generated next to each other, they will always be next to each other, even if we run a million expansion iterations. it's impossible for a new room to push them apart. which means it's impossible to, say, start the generation off with a few locked-circuit iterations, to make a bunch of loops, and then run the rest of the expansions to spread those loops out, so that the entire map (in most cases, statistically) will end up looping back on itself at the ends.
two, it's impossible to separate edges unless they're specifically matched on: there's no way to say "split this room in two and move half of its edges to the new room", for example. that means it's also impossible to recursively subdivide a room. imagine generating a simple map, but where all the nodes are huge hexes with lots of space inside them. then turn each node into its own dungeon level, making sure to put rooms at the correct places along the edges of the hex so that they end up maintaining proper connectivity. that's a major goal for this project, and it's still totally impossible.
third, it's basically impossible to propagate information through the dungeon. i had a planned expansion that was "find a room with an open connection and a locked connection, and then in the room of the open connection add a new room, with that connection locked with the same key" (to spread out locked doors so that each key isn't ever only used in one room, basically), and it's not actually possible currently to say "the same key", because that information is only known in the matched subgraph, and only used in the expanded graph, and actually those two things can't share information at all. likewise, i kinda wanted to have a 'difficulty' level, that rose by one with each step, except again the state of the matched node is only known in one place, and it's not where the data for the expanded node is.
i have a few ideas for fixing those things, or at least some of them, but the code is really not there yet. so i think this is a really neat thing that i've put together, but also there's sooooo much left to do before it's what i would call 'finished'.
still, on the whole i'm really pleased with this! it's an actual use for this code i've had sitting around for a year, and in these two weeks i've taken it from "here's some hexagons" to something that could be an actual, genuine map layout for a game. it still needs a lot of work, though, even for that: adding start/finish lines, or enemies, or boss rooms, etc, even ignoring all that complicated algorithmic junk above. but pretty good progress for two weeks, and i'm pretty hyped for whatever it is i decide to work on for the next two weeks.
also i've been doing this by having the embedder output an .svg file of the graph, and so far i've just been taking screenshots and posting pngs. but here are some Original, Authentic svg images:
a few ~50-room dungeons:
a few ~100-room dungeons:
(there are other in-progress shots/blurbs on my code screenshot tumblr if you want to read the whole backlog)
