Thursday, 23 April 2015

Simple Village Generation

Although I will be improving the village generator that I used in HarvestRL, this post will share my original method. It was rather simple, so people who want to quickly throw together a village might be interested in this.

First, here is what a typical village in HarvestRL looked like:

For those unfamiliar with dungeon generation, realize that you can use those algorithms to create pretty much anything even if they aren't supposed to be dungeons. That's a hint for what I did here. The full process worked somewhat like this.

1) Determine the space on the map to use for the village.
In this case, I used a random width and height between 40 and 60 tiles. This variation helped to keep the village from seeming too similar each time, and it also varied the population numbers.

2) Make a road into the village.
I picked a random point in the middle of the Southern edge of the village and created a path that went through that point. It started at the edge of the village and went into the middle of it. The end point was also randomized so that it didn't always stop right in the middle of the village, sometimes it stopped a little short. Then, I generated the other half that went from the edge of the village to the edge of the map. Once the path got a certain distance away from the village, I had it meander like a river. The path always led south out of the village, because I didn't want to make the farm's starting location too random.

3a) Divide the village space.
I used a Binary Space Partition (BSP) algorithm to break up the village area into smaller chunks. Libtcod already provided this. Defining the smallest space to be about 8x8, I worked with 3 levels of divisions to create a series of spaces. These I saved as rectangle objects. Although you could use the generated BSP Tree to store the connections between these rectangles, I didn't do that.

3b) Organize the partitions.
Each rectangle was a "plot of land" for a villager on which a building would be placed. The size of the building was randomized further (an inner rectangle), so that the spacing between buildings would be non-uniform. I stored this inner rectangle as a separate value in the same Building object (which at this point had two values: the rectangle for the plot of land, and the rectangle for the building). This step was performed while iterating over the leaves of the BSP Tree, and then I discarded the Tree since I didn't need it anymore.

3c) Discard rectangles over the village path.
Since the path was generated before the partitioning, each rectangle was checked to see if it overlapped with the path. If it overlapped the path, I didn't save it. This guaranteed an empty space where the path went into the village, so the entrance wouldn't feel too crowded. Since the rectangles varied in size and position, this could also affect the number of buildings (and hence population) in the village.

4) Randomize the type of building.
I made an enum containing all the types of buildings that I wanted to have in the village. Then, I added the required types of buildings to a list (in my case, the Harvest Shrine and the Shop), filled 3/4 of the list with homes, and then filled the remainder with random picks from the list of building types. A full list was equal in size to the number of buildings that were created. This ensured I had a safe distribution of homes, businesses/specialty places, and quest-required buildings. Due to lack of time on the 7DRL, most of the building types just reverted to homes.

5a) Assign building types.
At this point I have two lists: one of all the Building objects, and one for all of the building types to be created. Both lists are equal in size. First, I picked the largest building and made it the Shrine (the first building type in its corresponding list); obviously, this is not necessary for other games but it shows that the generation order does not have to be random. After this, I iterated over the list of buildings and gave each the next entry on the building type list. Thus, I could guarantee how many buildings of each type were created, and keep the possibilities random; the random choice of building types occurred in step 4, while step 5 decided where that building type would become instantiated in the village. This step could be improved, such as assigning types based on the relative positions of buildings, but it worked well for a quick village.

5b) Orient the building.
As I assigned building types, I also oriented the building. I picked a random edge of the building, labeled it the front, and stored that value (I just used a direction enum, the same enum used for movement directions). This step could be done more intelligently; for example, buildings close to the middle of the village would face outward and buildings near the edge of the village would face inward. You could easily calculate what is inward vs. outward by looking at the closeness of the building to the center of the village. I just left them random, except for the Shrine that always faced South.

6) Instantiate the building.
With all the details decided, I iterated over the building list and changed the terrain of the map. The outer rectangle was filled with grass, the edge of the inner rectangle was made a wall, and the inside of the inner rectangle was made a floor. Then I picked a random spot along the front wall, that was one tile away from either edge, and made that spot the door. A short dirt path was created from the door to the edge of the land plot. Some furniture was randomly placed in the building (which looks strange at times, since it's too random) and a random number of inhabitants were created (between 1 and 3).

The furniture and number of inhabitants was dependent on the building type. So, when you're playing the 7DRL and you enter a building containing one person and no furniture, that's because the building was not actually a home. Note that building types could also be other village features, like a graveyard or a garden or a fountain. Again, I had that in the code but never finished it so sometimes you'll find a village with big open spaces between buildings. For a more intelligent method of creating interiors, you could use plans that can change in orientation. The only plan I had was for the Shrine, but it was so hard-coded that I couldn't change the orientation (hence why the Shrine had to face South). I had already spent enough time on other stuff in the game that I didn't want to make the room plans better, but I can do it now.

7) Create a town wall.
I thought about doing this but didn't in the end. However, it is pretty easy to add if you want. You already have the borders of the village saved, so just create a wall around the edge of it and leave an opening when you come across the path.

So, that's the algorithm in a very broad sense. Since it uses BSP it still seems somewhat blocky, and that's why I want to use something different in the Extended Edition of Rogue Harvest. However, if you want to generate a village with a few hours of coding then this works. You'll need a BSP implementation, but you might be using that for dungeon generation anyway.

On that note, the area around the village was generated in an even simpler way. Notice that the edges of the map are non-uniform but in a somewhat smooth manner:

What dungeon generation algorithm does this? The Cellular Automata one, that's what. I created a grid with a one-tile border, randomly seeded a few other places, and ran the automata algorithm a few times. Then, I took it and used that to create the edges of the map (the mountains) and rocky places in the middle. This created the valley for the village, and it was created before the village; that way, when I generated the village, terrain around the village could be cleared and buildings wouldn't be lost to random mountains cropping up in someone's backward.

I also used a random seeding of the same grid, and ran it just once to create the grass and stones that litter the valley. Even though you don't need to have something as elaborate as this for open wilderness areas, I highly recommend having something other than stretches of plain grass (the .'s in my case). With a map as big as this game used, having pure grass looks very unappealing. A similar problem could exist with too much variety though, or having a display with confusing meaning; for example, using lower-case letters to represent enemies as well as trees and other wilderness features could be confusing for the user to interpret.

So, there you go. This whole process took me about 5 or 6 hours to think of, plan, and code. While it definitely has some areas for improvements, it's pretty good for a simple outdoors village.

No comments: