The two core mechanics of Roguelike games are permadeath and procedural generation. The developer of the original Rogue, Michael Toy, used procedural generation for two reasons. Firstly, storage space was low on old machines, and having handcrafted levels would increase the game size. Secondly, using procedural generation ensured a new experience each run, making the game entertaining for the developer as well. Even the creator of the game could be surprised and experience a feeling of discovery as they played the game.
I've been interested in procedural generation since I was a little kid. My first real encounter with it was in Spore, but I only became aware of it when I discovered Minecraft. I was amazed at how computers could create unique and complex worlds by following simple rules.
A level in Rogue.
In early roguelikes, all of the gameplay took place in the dungeon. It wasn't until later iterations that they began to have overworlds and towns. These towns were places to buy and sell items, get quests, and train your character. Over time, towns in roguelikes became more complex and more important to the gameplay loop.
The main town in Angband, an early roguelike game.
I want the overworld to be a big part of RustGarden, and I want to incentivize exploration. The player will have to travel to towns to get access to different items and weapons, to get quests, to discover lore about the history of the world, and to scour ruins for treasure and passage to deeper levels of the world. Each town needs to have its own unique history, character, and culture. If they all look the same and provide the same services, there will be no point in exploring.
In early testing, I started off town generation with a very basic method. All it did was scatter squareish buildings of random size across the map, then connect them with paths. Later, I added preset schematics to scatter handmade buildings as well. While it sometimes created some interesting results, it obviously didn't have the necessary variety that I wanted for RustGarden.
Some images of towns generated using the old algorithm
To create more variety easily without having to handcraft dozens of different algorithms, I turned to an image generation technique called 'Wave Function Collapse.' The algorithm is complex, but essentially works by taking a sample image, recognizing patterns and rules in the sample image, and then creating an output image that follows the rules. Here's a video that shows it in action:
The applications for procedural generation are obvious. Instead of having to create an individual algorithm for each kind of structure you'd like to make, all you need to do is crack open MS Paint and create a little image to feed through the algorithm. Once I got wave function collapse to work and got some sample images together, I managed to already get a good deal of diversity in village generation. But as I repeatedly tested out and studied the variety, I noticed some issues.
WFC output is pretty homogenous. It's not possible to impose a large-scale structure on it. If I wanted one part of the village to be agriculture and the other to be town, for example, I couldn't just draw crops on one side of the sample image and houses on the other. No, if I wanted villages with different zones, I would have to break up the map myself. The other problem is that while WFC is good at creating a lot of unique structures from pretty simple samples, the more specific your sample becomes, the less diversity of output. So WFC isn't good for setting objects like doors or chests or furniture.
To solve the first problem, I implemented Binary Space Partitioning. Anybody who's done any amount of roguelike development will know what that means. It's usually used for generating dungeons, but I decided to use it for urban planning! It simply randomly splits the map into sections, and then randomly splits those sections into smaller sections until the sections are of a desired size. Once I split the map into sections, I could assign each section of the map a different wfc blueprint. this article on roguebasin explains BSP
A visualization of BSP
Solving the door part of the second problem was pretty easy. I already had algorithms for punching out doors in walls from when I developed the dungeon generator. Basically, there are two functions, doorify() and loopify(). Doorify just goes through each wall tile. If there are floor tiles on either side of it and no A* path between those floor tiles, it punches out the wall tile, and then places a door if so instructed.
doorification in action
Loopify ensures that if there are places where loops can be made, they will be made. This sounds complicated but is actually pretty simple. Like doorify, it goes through each wall tile. If there are floor tiles on either side of the tile and the length of the A* path to get from one to the other is greater than 8, it will punch out the wall tile and create a door. This sounds trivial at first but is actually really important in roguelikes. You want there to be a lot of loops and alternate paths in your maps so the player isn't constantly backtracking. this blog made me aware of this problem
loopification in action
Here is one example of what the villages looked like by this point:
If you look carefully, you can tell how the BSP algorithm split the map up. Right now there are only town zones and agricultural zones, each which select from their own basket of blueprints. I plan on adding new zones in the future.
Next I had to tackle the issue of distributing furniture into the villages. I wanted each room in the village to have a purpose and have items and furniture distributed into each room depending on said purpose. The first step was to write an algorithm that can delineate the rooms.
The algorithm holds a list of lists called 'rooms', where each sublist holds the position of each floor tile in each respective room. The algorithm goes through each floor tile in the map, and if the tile is not already in any of the sublists, it gets a floodfill of all the floor tiles around it and adds that to the list as a sublist. This worked well, except it counted the outside world as an enormous room. This was easy enough to fix. Any rooms that have floor tiles that are on the edge of the world chunk are simply removed.
Getting all the rooms and their tiles
From there, the next step is to designate the rooms and decide what their purpose is. The largest room is always designated as the town hall, and it will have the mayor NPC in there as well as some desks, statues, chests, etc. Any room fewer than 6 tiles is designated as a bedroom. Rooms larger than this are "special rooms", which are chosen from a possible list. Some examples include libraries, shops, kitchens, etc. If there are any rooms left over after we're done, they are designated as barracks for now.
In the future, I want the possible special rooms to be influenced by the village's place in the world. For example, if the village chunk is adjacent to watery areas, a fishery could be added. If ruins are nearby, a mechanic's shop could be added.
Once we have the designation, can start distributing furniture based on each room's designation. For now, furniture is just distributed by setting a furniture tile on an edge of the room where it will not obstruct the door. In the future there will be a more sophisticated system. Also, there is a function which, when given a room, will return a tile outside a door to the room which opens to the outside world. This is used to place signs outside of the door to show what kind of room is inside.
Libraries have bookshelves and tables, kitchens have an oven and tables, and town halls have a single desk. Bedrooms and barracks have beds and chests.
The end product of the village generation algorithm, for now.
The immediate next steps going forward are to place furniture with more logic, to add more kinds of rooms and zones, create many more WFC blueprints, and to make the kinds of rooms be influenced by surrounding game areas. Also, there needs to be more kinds of walls and floors in villages. For now I have been using stone tiles, but there should be other choices, like wood, adobe brick, metal walls, glass walls, etc.
