For a long time I’ve been neglecting the orchards in the game. Only apples could be grown in them, and the art for them was mediocre. While this was ok, the townspeople in the game like variety in food, and just apples wasn’t making them happy, especially if there were no wild berries in the forest to collect.
 
So this week I added the new art required for having larger variety in the orchards. This is a somewhat tedious for each tree type. For performance reasons I can’t model every branch and leaf, which in some ways I think would be easier than generating low poly trees.
 
I have to make a lot of different resources to get the these trees into the game and usable in orchards. There’s the model itself, which has solid parts for trunks and main branches, textures on billboards for the finer branches, textures for the leaves, textures for ambient occlusion, a model representing the fruit when it’s harvested or moved from storage, and textures for that. Then there are sprites and text strings representing the fruit and seeds so that it can be shown in the user interface. Then there’s a whole bunch of data to configure. The tree needs to be setup as a growable item, configured to grow fruit dependent on temperature, and then tied into the game. Then the actual item that townspeople can use and eat needs to be configured as well.
 
Once it’s in game I generally tweak the artwork until I’m happy with it. Auto-detecting file changes and reloading resources is awesome for this. If you’re making a game, I highly recommend using a tool set that does this to reduce iteration time.

In the end, I have all these nice trees that hopefully look like pruned fruit trees in an orchard.
 
Maybe one day when I have nothing else to do I’ll write a tool to make the trees and textures for me, but writing a system like that would probably take more than the 8 hours or so of art and setup time it took to make these.
 
Before you yell at me, yes, I know there are tree generators out there, but my trees are very low poly and use custom shaders and model formats to expand billboards on the GPU and handle removing leaves in winter. I’m also one of those weird programmers that likes to write everything myself.

 
This week hasn’t seen many updates, but I’ve still been hard at work – although some of that hard work may have included backpacking through the mountains.
 
When I did get back in front of the keyboard, most of the time was spent on the mundane fixes that I can’t take screenshots of – bug and crash fixes, minor enhancements to the user interface, and tweaks to game balance.
 
However I did add a slew of new crops that can be grown in fields, and you can see one of them is pumpkins. I also added new plants that can be gathered from the forest. This coming week I’ll be adding more fruit trees that can be planted in orchards and possibly some more creatures that wander the forest…
 
I’ve also made some big additions to trading, allowing the player to setup automatic trades anytime a merchant stops by as well as being able to place custom orders for goods with the merchants.

I don’t like game design documents. After an initial prototype of the action is made, playing the game tells you what’s right and what’s wrong, what needs to be added and removed. After many revisions, if the document isn’t constantly updated, it becomes useless. I much prefer a list of tasks that specifies what needs to be added, removed, or changed. It’s flexible and shows at a glance what needs to be done, and what was done in the past.
 
I’ve followed this method for all of the development of Banished. I had a half page of notes scribbled in the middle of a notebook for the initial prototype, and after that it was the task list. Looking back through my implemented tasks I notice that crop rotation has been added, removed, added again, tweaked, and then removed. Whats going on there?
 
This is a good example of how I’ve been designing the game.
 
When I first added crop rotation, the game only had agriculture. The only way to produce food was in crop fields, orchards, and pastures. Hunting, gathering, and fishing were on the todo list, but a long way from being implemented.
 
I figured crop rotation would be a good addition to farming. Soil quality would be a resource to manage, just like everything else. Every few years, depending on the crop, a fallow crop could be planted and left to die and rot in the field which would restore the soil.
 
If I was building a farm simulator only, this would be fine. But the player is also balancing many other resource producing areas, building things, placing roads, and generally forgetting to switch to a fallow crop every once in a while. This can be devastating to the town if the food production is balanced closely with food consumption. It’s also annoying to click on 30 fields and change settings.
 
The obvious answer was to add a feature where you could plan crop rotation ahead of time and the farmers would plant a fallow crop every few years automatically. You would then balance multiple fields to have some produce and some lay open.
 
I starting thinking that this was strange – I added a feature that made the game less fun, and I was adding another feature to remove the annoyance. If you could setup the crop rotation schedule once and forget about it, why even have it? So crop rotation was removed.
 
A lot of time went by and hunting, gathering, and fishing among many other features were added to the game. At this point I decided I wanted agriculture to more difficult than hunting and gathering, so I added bug infestations to crop fields and orchards, and diseases to livestock in pastures.
 
Then I thought, “I can make crop rotation fun. It will make farming slightly harder. I’ll add it back and make it better.” And so I did. I left out the fallow crop this time, and just required a different crop to be planted. You could still leave a crop to die in a field and it would restore the soil. I also experimented with different lengths of time required between rotations. Large farm towns were still annoying. Even more so when you only had to rotate a crop every few years, making it even easier to forget. I thought of having a user interface that would show all farms and you could change crops in one place rather than clicking. I even rethought auto rotation.
 
Last week, after a long discussing with my play-tester, I decided the crop rotation was getting pulled again. Other than crop fields, no other food production method required constant monitoring. If you had no farms and a town setup well, it could be self sustaining, barring any disasters. Crop rotation didn’t fit this – a few farms and a few years of not rotating crops and the townsfolk start dying of hunger.
 
In addition, if farms were left open to restore the soil quality, that meant more space for farms, and less space for buildings. I’d rather have players build a larger town than use up most the space for farms. If I wanted that, I could just reduce the amount of food each crop field produces. Hunting and gathering already takes a lot of open space, and farming is the method players can use to build larger towns on the limited land.
 
So now, once again, there’s no more soil quality or crop rotation in the game. I don’t really feel like I wasted time, artwork, or code by trying this feature several times and then removing it. I still feel like crop rotation is a good idea, but it’s not actually fun. It doesn’t add to the game. There’s still a lot of things to think about while playing, and I don’t think the majority of players are going to miss it, or even realize there were features I tried out and then removed from the game.
 
Now I have to update the website and remove the references to managing soil quality…. maybe.

Pathfinding seems simple. Find the shortest, or a least a good path from point A to point B. As humans we do this all the time. We do it unthinking while driving in the car, walking through a city, or looking at a map of roads. Making it work in a game is not so easy.

Pathfinding is the one system in the game that I am constantly fixing and making better. I’ll think I’ve gotten it right, and two months later the game grinds to single digit frame rates because the pathfinder is working overtime, or an AI will stand dumbly in the forest and freeze to death.

The core of the pathfinding system is A*. It’s fairly easy to implement and works well. When a path exists from point A to point B, A* finds it fast. When the path doesn’t exist A* searches a huge section of the map, only to fail. Because my maps are large, even an optimized implementation can’t run fast enough to handle the failing case, especially when hundreds of AI’s need to move from place to place.

Let take an example scene. This area has a bunch of buildings, roads, trees, bridges, and water. The AI’s need to navigate the area to get from their home to the market and to their jobs.

Besides finding a valid path around buildings, A* allows you assign weights to movement in different areas. This makes some areas easier to pass than others. When searching for a path, it makes the people prefer roads, but if cutting across a large farm is faster than following a road around it, the people will do it. It also makes people avoid tight clusters of trees or rocks, but if that’s the only way to go, they’ll go through them.

I can dynamically set these weights in game. For wild animals like deer, the weights are very high for roads and buildings, so they’ll generally stick to the wilderness, avoid settlements, and have no problem crossing a river.

The path weights look like this.

In this image, the roads have the lowest weight (orange), open areas are next (green), then farming/stockpile areas (yellow), then trees, rocks, and other obstacles (grey). Water (blue) and buildings (black) are not passable.

I worked hard to optimize this whole system. From my initial implementation to what I have now was probably a 20x speedup. A* needs a whole lot of record keeping. It needs to keep a bunch of sets and priority queues of information. Since the map is constant size, much of this data can be preallocated. However there is a dynamic priority queue that uses a custom AVLTree with a constant time memory allocator for high performance. After all the optimization it’s still too slow to handle the failure case quickly.

After researching a bunch of other pathfinding optimizations, I came to the realization that I was trying to optimize the wrong thing. Most of the time the game engine wants to know if an AI can get from point A to point B. I was using A* to make this determination, and throwing the path information away. The only time A* is important is when an AI actually starts walking, otherwise I just need to know that a path does or doesn’t exist.

I went with the simplest thing possible: a large table that can be used to lookup the A to B accessibility. For this I turned back to my software graphics rendering roots, and implemented a fast flood fill. The code flood fills all regions that are connected with an identifier. When the fill is complete, any unvisited areas are then flood filled with a different identifier. This continues until the entire map is filled.

The colors in the image above represent the different identifiers. Before pathing from point A to point B, the game simply looks in the accessibility map at points A and B. If they have the same identifier an AI can make the trip. If not, they’ll move onto doing something else. This is very fast and takes so much less time than running A*.

When a building, bridge, or something else is placed that could change the accessibility information, the flood fill is simply performed again. This is fast and doesn’t show up on any profiling I’ve done.

There are other things to consider while pathfinding. For example, an AI could already be walking from A to B when the route is cut off, so AI’s constantly have to check the accessibility map, and either re-path or cancel the current task.

All that pathing and flood fill code I just described is only about 350 lines of C++. Strange that a small amount of code has caused me so many performance issues and headaches….

Those screenshots yesterday were nice, but the video of the same town is even better. Enjoy!

Over the last few days I’ve made fixes to some hard-to-find bugs that have been plaguing the game for a long time. Many of these bugs only show up in extended play. I’ve also done some performance optimization to handle higher populations.

And so today I played the game for a long while to stress test my fixes. Below are some screenshots of the resulting town. This town uses only hunting, gathering, and fishing for food.

When I started this game, I knew AI was going to be a hard thing for me. I’m used to writing graphics code and low level system where the code execution paths are nearly the same every frame. For all the games I worked on in the past, I never looked into how the NPCs made decisions.

I wanted the people in the game to do all manner of tasks. They’d live in houses, walk to their jobs, do the work, cut down a tree, go eat lunch, collect firewood, and go get a new shirt from the market. I had no idea how to make this happen or where to start. I tinkered with getting the AI to do simple things, and then built on that.

I broke down all the things an AI could do into simple core tasks, which I call ‘Actions’. These are tasks such as moving to a location, picking up an object, storing or retrieving something out of inventory, creating new objects, or playing animations.

The AI then maintains a queue of actions to complete. Lets say I want to get an AI to collect food from storage and bring it to their home. The code would look something like this:

// head to the storage facility or market
ai.AddAction(MoveTo(storageLocation, Animation_Walk));

// get something out of inventory and display it.
ai.AddAction(PlayAnimation(Animation_BendDown));
ai.AddAction(RetrieveFromStorage(storageLocation, foodType));
ai.AddAction(PlayAnimation(Animation_StandUp));

// go home
ai.AddAction(MoveTo(homeLocation, Animation_Walk));

// drop inventory
ai.AddAction(PlayAnimation(Animation_BendDown));
ai.AddAction(DepositInventory(homeLocation));
ai.AddAction(PlayAnimation(Animation_StandUp));

Each item in the queue is executed until it finishes – MoveTo completes when the AI gets to the target. PlayAnimation completes once the animation finishes. Other actions like DepositInventory execute immediately and the next action is run.

I call these chains of execution ‘Behaviors’. The game has a lot of different behaviors, from how to hunt animals, to how to work at a building and use one resource to make another resource. Adding new behaviors and actions is easy. I could make two people walk toward each other, play an animation and play audio that shows they’re talking to each other, then go about their business with just a few lines of code. (But I’d have to make the animation and audio first….)

This came out as a very nice system and is very extensible. But then there is the hard part. How does the AI choose which behavior it should be using at any given time?

Each AI has a set of needs that may or many not be urgent. They might need to stock their home with food or firewood. They might be sick and need a doctor. They might be cold and need to go home and warm up, or hungry and need to eat. They might have low health and decide to visit an herbalist. They AI might be a child and depend on parents for keeping the home stocked.

In the best case all needs are met and the AI should just do some work so the town can prosper – if they have a specific profession and workplace this is easy – but if there is no work available they need to help around town with general labor.

These things don’t sound like nice programming tasks. This is where I ask myself if I’ve made too complex of a simulation….

But to deal with it I turned to something I do know. State machines. There are different states of working versus attaining needs, and there are different versions of each of those for when an AI is a child, student or adult. Each time the action queue is empty, it signals the AI to make a new choice or change states based on needs.

The needs are prioritized based on severity – freezing to death is more important to take care of compared to getting a new tool. Deciding what job to work on is handled simply by ranking jobs based on urgency and distance from the AI.

Each state is simple. Here’s what the normal and attain needs states looks like:

void State_AdultWorking()
{
  // check to see if the ai is doing something
  if (IsBusy())
    return;

  // do more work, idle, or change state
  if (AreNeedsMet())
  {
    if (!GetNewTask())
      ChangeState(AdultIdle);
  }
  else
    ChangeState(AdultAttainNeeds);
}

void State_AdultAttainNeeds()
{
  if (IsBusy())
    return;

  if (AreNeedsMet())
    ChangeState(AdultWorking);
  else if (IsFreezing() && CanAttainWarmth())
    ChangeState(State_AttainWarmth);
  else if (IsSick() && CanAttainDoctor())
    ChangeState(State_AttainDoctor));
  else if (IsHungry() && CanAttainFood())
    ChangeState(State_AttainFood);
  else if (IsUnhealthy() && CanAttainHealth())
    ChangeState(State_AttainHealth);
  else if (!HasClothing() && CanAttainClothing())
    ChangeState(State_AttainClothing);
  else if (!HasTools() && CanAttainTools())
    ChangeState(State_AttainTools);
  .... // lots more needs omitted.
  else
    GetNewTask(); // couldn't attain any needs! try doing work instead, will retry later
}

I implemented all this and then decided this wasn’t really AI – it’s a conglomeration of state machines, fifos, priority queues, and a few conditionals. But magically when hundreds of AI’s are running the state machine and executing behaviors, it looks awesome and the town is alive with activity.

This system could easily be extended to give the AI’s more personality. I could have different states for lazy workers that idle more often than not, or people that won’t work when their health is low or if they have to walk too far. But for now everyone is a well behaved, hard-working citizen.

This week I was planning on building a really big town to test end game play. The screenshot above shows about as far as I got. Unfortunately I ran into a lot of bugs and gameplay issues that I’ve been ignoring for a while. So I fixed them instead.

I’ve been wanting an alternative fuel source to replace firewood, so mines can now result in coal as well as iron ore. This can reduce the need for so much forest area at the expense of having more miners. The people in the game can then use either coal or firewood to heat their homes. Coal can also be used in by blacksmiths to make steel tools which last longer than iron tools.

Buildings like the mine that result in large numbers of resources are no longer removable from the landscape. The upside of these buildings is that they produce massive amounts of iron, coal, and stone. The downside is that while the player can remove the wooden or stone part of the structure, they leave a heap of dirt or a pit in the ground, and the land is wasted forever.

I also did some experiments with absolutely huge maps. This led to me to see some obvious areas of the code that need optimization. The game still runs fairly well with huge maps, but I’ll have to play the game to the point where 1000′s of AI’s are running to see if performance can be maintained over such a large area.

I also tweaked crop rotation some more – the player is dealing with so many things that not having to rotate which crops so frequently is much better.

Despite all those game changes, most the time was spent tracking and fixing bugs. I fixed stuck tool-tips, some random ui bugs, path finding bugs, and some crashes in ai code. I made a bunch of bug fixes to the video interface, especially dealing with switching between full screen and windowed mode. Not a bad week.

I’ve gotten a lot more questions about the game through email, posted on forums, in comments, etc. Here’s some answers to the most common questions.

Q: What date is the game going to be released?

A: I don’t know! When it’s done. I’m not a big company that sets release and milestones dates. However I’d like the game to be complete by the end of summer 2013. If I need more time to make a quality game, I’ll take more time.

Q: Can I help build the game?

A: I’m amazed at how many people are willing to help build the game. The excitement over it is fantastic! But I started this game to challenge myself and learn new things, and I want to finish it myself. However, thanks for the offers!

Q: How long does it take to build a large town? How large is the map area?

A: In eight hours of play, if no major disasters occur, I generally fill about 1/8 of a map. I haven’t yet built a town large enough to not have room to expand. I believe it would take me more than a couple days of play on a single town to fill a map to the point where I couldn’t grow anymore. I am experimenting with even larger maps – the performance and memory usage of the maps will determine the largest size.

Q: Can you make multiple towns and trade in between them?

A: Each town is isolated. AI Merchants will occasionally visit your town to trade but otherwise each town must survive on it’s own.

Q: Will there be different area types to play in?

A: I plan on having more mountainous play areas where there is less land to settle on. Different climates will also be available for changes in difficulty. I may do a few other landscape types with lakes or oceans but I haven’t fully decided on these yet.

Q: Did Cultures, Stronghold, and Settlers influence the game design?

A: Believe it or not, I haven’t played any of those. I have played the various versions of Black & White, Anno, Sim City, and Dwarf Fortress. While I wasn’t really thinking about those games while designing nor was I trying to emulate them, they probably had an influence on me.

Q: What sort of disasters can occur? Is there more to it than just city building?

A: You can lose people from starvation, overpopulation, disease, hypothermia, harsh winters and dry summers, and deaths from working dangerous jobs. Your fields and orchards can suffer pest infestation, and livestock can develop diseases. I plan on adding fires and a few other disasters as well.

Q: Can I build a castle?

A: Not yet. The largest building is the town hall. If and when combat is added, buildings such as keeps, castles, and barracks are definitely a possibility.

Q: Do people get better at their jobs over time?

A: The people don’t get directly better at their jobs because they work them for a long time. I tried this, and while it’s neat simulation for small populations, once the population reaches several hundred it’s not very fun or useful. Micro-managing what job each person is doing, and making sure they are using their skill-set is just tedious. This is especially true when you have to shuffle people among multiple jobs to deal with losses from disasters. There’s enough complexity in the game as it is.

However there is education in the game. After a citizen has undergone a few years of education, any job that they work at will produce more resources. For jobs that don’t produce anything, such as teachers and doctors, their work will be completed faster.  By keeping a large majority of the population educated you can increase production and have more people on less land. While people aren’t happy about switching jobs, they’ll still do a good job when they do so.

Q: What are the hardware requirements for the game?

A: I don’t have exact requirements yet. I’d like the requirements to be as low as possible, so that a lot of people can play. The game will run on a machine that has a DX9/Shader Model 2.0 level video card, and it only uses a single CPU core. It takes about 250-350M RAM. My development system is a i7 920 @ 2.67GHz with a NVIDIA GeForce GTX 280. This setup runs the game at 60 FPS. There are graphics options to dial back the quality for speed.

Q: Will there be goals to reach while building a town or is the game just an open playground?

A:  Both. For those that like trying to meet goals and reach achievements the game will have them. For those that just like free form play you can disable any goals and play as you wish.

Q: Will society upgrade technologically and culturally?

A: No. The era of the game is fixed. There are simple upgrades you can make in the game, but you can’t get to the industrial revolution. Wood houses can be replaced by stone, you can eventually make better tools, have better education, and make better clothes, but you won’t be discovering machine guns and microchips.

Q: Can roads only be in straight lines? Is everything placed on a grid? I want to build curved roads!

A: Everything is on a grid. When I started building this game a grid seemed fine for the prototype, and it stayed.  I’d love to have free form layout, curved roads, and placement of buildings at any angle. To change this now would require massive effort. If I ever make a sequel it will have free form layout, larger landscapes, and building on hills. (Talk about getting ahead of myself…)

Q: Will there be mod support?

A: I’m surprised by the number of people that have asked about this. I didn’t intend to make the game moddable. If there’s enough demand for it, I’d think about releasing a tool set, but it isn’t a focus of the development at the moment.

 Q: Will there be multiplayer? Can I trade with other players?

A: The game is old school – single player only.

The game now has paved cobblestone roads! People move much faster on them but they use up stone to build them. The square in the image costs a lot to build, but it sure looks nice.

While the stone roads are useful for gameplay, I’ve got a few ideas for other items that can be built purely for making a nice looking town, such as fences, walls, and planted trees. While not really needed, I enjoy games that let me make a good looking city with a nice layout in addition to a city that performs well. Small details can add a lot to this. I probably won’t get to this until the game is almost done, unless I get bored one day and just want to make artwork.

Speaking of getting bored – now that the game is somewhat large, there are a lot of small unrelated tasks to complete. It’s nice to be able to switch what I’m working on day to day. It helps to keep up my motivation, focus, and sanity – I can just pick anything on my task list and work on it. Earlier in the week it was audio, yesterday was textures and a small amount of code, today is mostly code. This weekend I’ll probably play the game and work on balancing. Or more likely I’ll relax and go mountain biking. I think switching it up often (and taking days off) helps to not to obsess or worry about the small details, and the development time is faster overall.

Edit: Can I really talk about faster development time when I’ve been working on it for two years???