The book is intended to be an homage / parody / satire / reflection on old game systems, old game books that were evocative, but not actually sufficient to be played as written, leaving players to come up with house rules to fill in the gaps.
Also, it's being largely written by AI. More on that in a later post.
I decided that a relevant thing to add to the book was a generated dungeon. The 1st Edition Dungeon Master's Guide had some tables to help you generate a random dungeon, and there were Dungeon Geomorphs, which were map tiles that you could lay out in random assortments, if you liked.
And, of course, every roguelike that's sufficiently like Rogue will have some sort of dungeon generation system, which typically separate the world into rectangular rooms connected by a network of tunnels.
A while ago, I stumbled across people getting excited about "Wave Function Collapse", a "new" algorithm that can be used to generate plausible content, given a small test sample. The animations I looked at were pretty, but the algorithm seemed to be a repackaging of constraint propagation, which I had been using for content generation for years, and had first seen in my AI class back in 1991, where the technique was used to find a consistent labelling of edges for doing image comprehension on a set of edges representing a computer vision view on a world of blocks.
The one thing that looks like it's different in WFC is that the frequencies of patterns are recorded, and when a pattern is matched as a basis to place new content, the input frequency data is consulted to pick a plausible successor. For example, if my input had straight corridors followed by more straight corridors 9 times out of 10, and a turn 1 time out of 10, I could use that to generate corridors that resembled the input by rolling a d10 and placing a turn 1 time out of 10, otherwise continue the corridor going straight.
One hesitation I've had about the various WFC implementations I've looked at is that they largely don't implement backtracking, meaning they can get stuck in dead ends. This is apparently not a show-stopper for people to use these implementations - the algorithm seems to get stuck rarely, and if it does, just restart, and it'll be fine. Typically.
So, I wrote a simple WFC / constraint system, without implementing backtracking, and it was generating dungeon maps pretty much to my liking, resembling the image at the top of this post. One feature I had in my tileset was stairs, which I didn't give the algorithm enough information to really deal with well. The generator would create loops with 3 stairways, all going down going one way around the loop. If you're familiar with Escher's "Ascending and Descending", or the Penrose stair illusion on which it's based, that's the same idea. Not really something I wanted accidentally appearing in my dungeons.
I added in some elevation tags, and I still ran into problems. Now, what was happening was that the generator was making portions of the map at wildly different elevations, and couldn't figure out how to merge them together. And, without backtracking, there'd be no way to adjust the placed tiles, so I'd have to restart. And restart. And again.
So, I rewrote the generator from scratch, this time with backtracking. One reason I had hesitated implementing backtracking myself, and why most of the WFC implementations avoided it, was that there was a lot of partial solution state that one kept around in a backtracking solution.
But I dove in, and got a backtracking placer working. It was slow, because of all the copying I was doing. And I was doing it recursively, so I was using up the program stack. And this began to be gross, so I unrolled my recursive loop to be an iterative loop. This let me control things differently, doing reckless things to my queue of partial solutions, including throwing away a big fraction of my work when I started to get pressed for memory, and doing a random shuffle of my queue to give it an opportunity to "jump out" of dead ends. I've had fairly good results in the past from periodically shuffling my iterative work queue to get away from local maxima. It sounds goofy, but you might try it and see if it helps you.
So, I had an iterative backtracking solver, and it was slow. Part of the problem, I'm sure, was the copying I was doing. Part of the problem was that I was using Python. I'm not really willing to rewrite this whole solver in C++ for performance - and the galling thing was that my WFC generator was able to make a reasonably-sized map (~17x22) in under a minute, while my backtracking generator was struggling to finish a map maybe a quarter of that size (8x10?) in a few hours.
So, maybe I don't need stairs. The whole reason I stepped away from the WFC implementation was that I had these non-local constraints that WFC didn't deal with well.
One thing that might be faster is to implement Knuth's "dancing links" algorithm, which I never have been able to entirely wrap my head around. It seems to allow you to do backtracking search in-place, which would be handy.
I went to my tileset data and turned off all my stair tiles, and got my old WFC implementation working again. The tunnel system looks like a block of uncooked ramen noodles, but I'm willing to go with that as an insane, but legal, generated dungeon. It also reminds me of the studies where they fed spiders a variety of drugs and looked at the kinds of webs those spiders spun.
Once this was in place, I got a feature working where each tile could specify how frequently it would appear in the output. For example, in early versions, there were a LOT of pits and one-way doors. I turned those down, and the dungeons look somewhat reasonable (still with the ramen tunnels, but I'm still OK with that).
I've also added some convenience constraints, blocking out the lower left hand corner so that I can paste in a legend of the various symbols used on the map. Not all dungeon maps need that, but my hand-drawn dungeon bits might not always be obvious to the reader. Is a circle with a star inside it a pentagram or a statue? At this level, a statue. Later on, we'll talk some more.
I intend to write out the map as a CSV to make it easy to do some editorial touch ups, and then read the edited CSV back to feed to the renderer.
And then I intend to move on to some deeper caves and caverns, with yet another generator, this one less tied to grid lines.
No comments:
Post a Comment