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.

Sunday 19 April 2015

UI Redesign

Given the reviews from the 7DRL Challenge, and my own annoyances with the previous version, I have started the remake of Harvest RL by changing the UI.

First, I wanted to add mouse support. This has been the brunt of my work so far, mainly because of how I coded the UI to begin with. At this point though, mouse support is almost complete. The last thing I need is to get mouse targeting and looking to work properly. Then I'll add the Game Options screen to allow disabling of mouse support (for those who really dislike it) and call that feature complete.

Second, I wanted to change the inventory. There were several complaints about using shift+t to throw items, as an example. Although I had little difficulty with upper-case letter commands, I want to address it for others. The reason I chose this control scheme was so that lower-case letters could be used to select an item, and then upper case letters would interact with the chosen item. After thinking about it more, I realized that I could just use a separate window for the chosen item with the necessary commands. That way lower-case letters could be used for both item selection and item interaction. Two key-presses are needed for things like throwing anyway (even if you use "throw" + "choose item"), so I just needed to make minor changes to the inventory for this to work.

There's a picture of the new inventory screen here. I also added the ability to view (and remove) equipment and put in buttons for the mouse, instead of just key-command tooltips. I'm not satisfied with the button coloring yet, but their functionality is good.


Third, I wanted better info for allies and enemies. There is now a list of enemies on the screen, with health information. Attitude and status effects will be shown there too, but right now that's not even included in the AI yet. After I restore the status effects that I took out from my previous framework (due to it not working right) then I can get hunger, tiredness, and stunning connected to it. That should greatly improve some of the UI issues with those things. Hunger and tiredness need mechanical changes, but I'll work on that later.


Lastly, some people might notice that I'm using a different font. Although I particularly liked the previous font (it's the one I use for Dwarf Fortress all the time), the sizing of this new one gives me a lot more options. I could take inspiration from CogMind and use multiple fonts, but I'm not going to; I'm already experimenting with a different library for drawing routines, and it will cause any work that I do on multiple font rendering to be useless.

This is then the official start of a new version of this game, which I think I'm just going to call Rogue Harvest: Extended Edition. I might change the name later, but it's the tentative name for now. Once these minor UI changes are working properly, I'll put up a proper development plan and do more regular updates.

Saturday 4 April 2015

HarvestRL New Update

As it turns out, there were still several bugs in the previous version, some of which were quite major. I fixed these, added a better intro screen, and greatly optimized the loading times. This may have introduced a minor loading bug, but that's not too important for me. As of version 1.02, I am considering this game complete. It's not great, but it's finished.

That being said, I am taking this and expanding it into a new game. I'm trying to decide if I want to call it HarvestRL2 or HarvestRL:X (for expanded) or just a totally different name. The goal will be similar, but with a different time scale. Currently you can finish the game in 10 or 15 days (potentially even 3 though most of the village dies in that scenario), and I wanted something longer to bring about more interesting aspects of the farming.

In addition, there are major UI problems. The ASCII stuff is fine, and even the way I've displayed information works, but the control scheme does not. I'm going to experiment with a different library since I'll have to make some major changes anyway, see where that takes me, and go from there. I plan to merge the code from this project with another one that involved random world generation but never saw the light of day.

For now, you can get the latest version of HarvestRL here.