tl;dr: I ramble about world generation and Metroidvanias.
I had a bit of an epiphany earlier tonight and I realized that my efforts with world generation were approaching something that I hadn't quite put my finger on (at least not recently). If I subdivide the world into regions, I can give each region a unique theme or flavor and more clearly delineate progress through the world.
To illustrate this, I've colored the map by region in my visualization/driver/test program. The brighter cells indicates the room in which the player would find the "key" to unlock the next region. (In some cases, this might be an actual key, but whenever possible, it should be a new ability that lets the player access the next area...think high jump in Metroid, mist form in Symphony of the Night, etc.)
Of course, once I made this connection and was able to visualize the regions more clearly, I realized the balance is way off, so now I need to revise the algorithm to subdivide the world into more evenly sized chunks.
I'm thinking this will also allow me to pursue some earlier ideas I had for progress and flow which should hopefully give the world a more intuitive, handcrafted, designed feel...after all, isn't that really the goal of procedural content generation?
Since I feel like rambling about design a little more, it's worth mentioning that I was looking at maps of Metroidvania games for reference a while back when I was trying to come up with an algorithm for world generation. This one map of SotN in particular made a big impression:
It's easy to see how each region connects to every other region, and on a high level, you could draw a graph in which each region is represented by a node in the graph and edges are drawn between connected regions.
That concept was sort of where my world generation algorithm got started, but somewhere between conception and implementation, this goal got muddled and lost, and then accidentally rediscovered.
Back when I first started planning these algorithms, I didn't have anything playable, and it was harder to gauge how big the world should be relative to each individual "dungeon" area. (In light of recent changes, "room" might be a more appropriate term than "dungeon," but I'm sticking with my original vocabulary for now.) I was originally imagining that the individual dungeons would be larger, but I kind of like the size they're being generated at now, and in fact, I might even want to reel them in a bit more in the future. Having each dungeon represent a concise, isolated gameplay space allows me to draw parallels to Metroidvanias more closely. It's easy to compare these areas to individual rooms in SotN, and from there, I can also draw a comparison between the world layouts of each game. At that point, the worlds I'm generating no longer seem oppressively massive, nor does so much of the space seem potentially wasted. At the moment, the only unique feature of each region of the world is that one cell contains the key to the next region, but when I think about the world in Metroidvania terms, it's easy to imagine that I could fill some of the "wasted" space with safe rooms/save points, secret rooms, maybe even teleport rooms for faster travel across the larger floors.
I also realized as I was going over this stuff again that my current algorithm creates a very linear progression. Each region contains a key which allows entry to the next region, and the next region is connected only to the current one. Besides the obvious flaw of having only way to traverse the world from any one point to any other point, it's also less interesting to have each region be immediately adjacent to the next. I'd like to mix this up a bit so that, for instance, the final region of a floor might be immediately adjacent to the first, but it's inaccessible until the entire floor has been traversed. From the start, one has my goals has been that the player should always see the lock before they find the key, and mixing up the region order in this way would just help take that concept to the next level.
One of the more interesting developments to arise from all this is that I'm no longer sure whether I need or want to divide the world into multiple floors, as illustrated in my previous post. Having multiple floors is more of a roguelike trope, and the design for this game is starting to feel like more of a first-person Legend of Zelda with only very specific, cherry-picked elements of roguelikes, Shock-likes, and Metroidvanias. I do still like the idea of progressing lower and lower into a set of increasingly dark and twisted dungeon themes (I'll save that for another rambling design thread), but I can probably accomplish the same without actually fragmenting the world. It's definitely something to sleep on.
Okay, that's enough rambling. I'm going to go play some SotN now.