My time the past two weeks has been adding the code and menus for scenarios, in game goals, custom map setup, achievements, and winning/losing conditions. Part of me really dislikes making and laying out user interfaces – it takes quite a bit of iteration for nice layouts and a bunch of code that is tedious to write but unfortunately is unique to each menu. I suppose not every part of game development is always fun.
 
Building menus doesn’t give me much to talk about or show visually. But since images are better than walls of text, here’s an image of the new menu for picking scenarios. This menu is still changing, and these scenarios are just for testing and may not end up in the final game. But it will give you an idea of what I’ve been working on.
 
Scenarios are just one type of way to play the game. There’s also sand-box mode, with or without user defined goals, user selection of map sizes, difficulty, and terrain type. There are also plenty of achievements being added that players can work toward. I’m also trying to figure out details for a few tutorial scenarios that will introduce the game to new players.
 
Like most games, I’m way over my expected time budget, but I think the extra work on the game is worth it. Regardless, it’s a nice feeling to have a pretty stable build and be working on things near the bottom of my to-do list. It feels like the end of work on the game is in sight – whether or not that’s true.
 
It reminds me of one of my favorite programming quotes. “The first 90 percent of the code accounts for the first 90 percent of the development time. The remaining 10 percent of the code accounts for the other 90 percent of the development time.”
 
I wish it wasn’t true, but it is.

I’ve mentioned in the last few posts that I’ve been working on getting environmental effects and changes to the game. I’ve got rain and snow effects prototyped, as well as changes of lighting and fog as the seasons progress. There’s still a bit of tweaking and work to do to integrate them into the game properly, but so far I’m liking the visual differences that they bring.

Until I do get things properly integrated into the game and can make some video of the effects in action, here’s some screenshots…

Winter Storm

Autumn

Spring Rains

Summer

Apparently a lot of people assumed I was switching to DX11 and dropping DX9 support. I plan to make both versions available. The DX9 version should run on Windows XP and all newer versions of windows. The DX11 version actually will work with DX10 level hardware, and should work on Windows Vista and anything newer. Additionaly, there’s also both 64-bit and 32-bit versions of both the DX9 and DX11 executables. I don’t really need both versions, but the 64-bit version is slightly faster on a 64-bit system, and the 32-bit versions are needed for those without a 64-bit OS.

I originally thought to ship just the DX9 version since it will work on everything, but the DX11 version shows definite and impressive improvement in both CPU and GPU usage on some systems. For people that can take advantage of it, that’s a win. I like smooth framerate gameplay experiences, and I’m sure a lot of other users do as well.

As a side note, at the urging of a developer working on some newer console hardware, I did some additional performance tests for not just GPU performance, but testing CPU performance of DX9 vs DX11 both using instancing and a full set of draw calls. In most cases, while instancing didn’t increase frame rate by much, it saved a bit of CPU time. This gives more time for AI, pathfinding, and general gameplay code to run.

Today I’ve decided that code written for prototypes should ALWAYS be thrown away. No questions asked.
 
This morning I was changing a few vertex and pixel programs to support some of the new environmental effects I’ve been working on. This led me to remove some data from the terrain that used to be used for coloration. The color data is now stored in a compressed texture instead.
 
While cleaning up the C++ side of things, I noticed the terrain rendering data was laid out in almost the worst way possible – both for performance and memory. I can’t think of too many worse ways to do it.
 
I wrote that code while I was prototyping Banished – way back sometime in 2011. I probably wrote it in less than a day, and it worked for the prototype so I never looked at it again. Why would I? It never caused any problems and never required any additional features.
 
The terrain was using something awful, like 28 megabytes of memory. After fixing things up properly, it now uses 4.25 megabytes for rendering the exact same thing. As a happy side note, I got an immediate 10 FPS frame rate increase when i reduced the memory usage.
 
However, the first time I ran the game after reducing the memory I got a good graphics explosion. I mentioned this occuring previously – Graphics Explosion.
 
This was a particularly fine example of sorta awesome terrible graphics errors. At leat it was easily fixable.
 
As a side note, I’m somewhat amazed at my memory usage level. Two weeks ago, I saw the DX9 renderer using 310Meg on a fresh map. Today my DX11 renderer using 74Meg. Woo.
 
Maybe I should skim the rest of the code for remnants of the prototype…

Shortly after my last post here, I added wandering nomads to the game. They occasionally come to the town, and the player can either allow or deny them citizenship. There might be consequences of turning them away too many times…. but that’s a feature for another day.

After adding the nomads I was in a graphics sort of mood, and so I started looking at adding some atmospheric effects to the game – mist, fog, rain, snow, and changing lighting conditions throughout the year. I was looking at the shader programs that make the game pretty, and started wondering about graphics performance – thinking I should look at optimizing things before adding more GPU overhead. Which is very dangerous for me, being a graphics programmer. I can tinker forever trying this and that to make the same scene display at a higher framerate.

So I took a long road down optimization lane, and with it came some serious coding and learning a new graphics API. This is probably too long and has too much information about graphics programming, so I understand if you feel like saying TL;DR, finish the game already.

Lets look at my test scenes. One is a view over a town in winter, and the other is the same town seen from high above.

The first scene has 2409 objects submitted to the GPU, and consist of ~817,000 triangles.

 
The second scene has 4617 objects submitted to the GPU, and consists of ~1,243,000 triangles.

 
From early on my graphics engine has been able to render the same object in multiple locations with a single draw call. This is called instancing. So instead of having to call Draw() 2409 times for the first scene, the engine can batch all similar trees together, or all the rocks together, or all the houses together and submit them in 411 calls to Draw(). This is good since each draw call requires some state change for the GPU, and it (usually) saves CPU time as well.

Up until last week, my engine used DirectX 9.0c and shader model 2. I initially chose this for the widest possible support of video cards and older computers. If you know anything about shader model 2, it doesn’t support instancing. So if you want it, you have to fake it. This is done using data repetition. Each mesh is repeated in memory some number of times, but each repetition has a different ‘id’ encoded with each vertex. This id is used to look up into a table of transforms. (A transform for those non-graphics people is just a location, orientation, and scale…) This is very much like hardware skinning – the deformation that takes place to bend a model around its skeletal structure. Due to limitations on the number of constants that can be set for shader model 2, the engine can draw up to 52 objects at once.

To draw multiple copies of an object the graphics code does something like:

device->SetVertexShaderConstantF(transformListIndex, transformData, 
	transformCount * 4);
device->DrawIndexedPrimitive(D3DPT_TRIANGLELIST, startVertex, 0, 
	numVertex * instanceCount, startIndex, primitiveCount * instanceCount);

The vertex shader then does something like this

uniform float4x4 tc_transforms[52];

struct input
{
	float4 position : POSITION;
};

float4x4 localToClip = tc_transforms[input.position.w];
float4 localPosition = mul(localToClip, float4(input.position.xyz, 1.0));

This method works great, and is very fast. However the mesh vertex and index data are repeated 52 times! Think about the memory requirements for this in the scope of all the meshes in the game…. For dynamic vertices, like particle systems, drawing instaces is worse, since the engine has to manually copy the data N times, and set the vertex id value. memcpy() starts to show up on the profiler for heavy scenes.

To alleviate this memory requirement (which is getting huge, btw), I decided to try the instancing method available in shader model 3. In shader model 3, you can mark a vertex stream as instanced. This was pretty quick to add to the engine. I’ve got all the graphics code isolated to a few files, so in a few hours I had this new method working. Instead of shoving transforms into vertex constants, they instead get copied into a vertex buffer. At draw time, you do something like:

device->SetStreamSourceFreq(1, D3DSTREAMSOURCE_INSTANCEDATA | 1);
device->SetStreamSourceFreq(0, D3DSTREAMSOURCE_INDEXEDDATA | instanceCount);
device->DrawIndexedPrimitive(D3DPT_TRIANGLELIST, startVertex, 0, 
	numVertex * instanceCount, startIndex, primitiveCount);

You then change the vertex declartion to include the ‘instance’ inputs, and the shader then loads the transform like so:

struct input
{
	float4 position : POSITION;
	float4 w0 : TEXCOORD0;	// transform row 1
	float4 w1 : TEXCOORD1;	// transform row 2
	float4 w2 : TEXCOORD3;	// transform row 3
	float4 w3 : TEXCOORD3;	// transform row 4
};
float4x4 localToClip = transpose(float4x4(input.w0, input.w1, input.w2, input.w3));
float4 localPosition = mul(localToClip, float4(input.position.xyz, 1.0));

After changing all the vertex layouts and vertex programs to do this, I took some frame rate results. The scene was tested at 1600×900, 2xMSAA, 2x anisotropic filtering, 2048 shadow map, and a 5 tap PCF kernel for sampling the shadow map. The test machine is an i7 920 @ 2.67Gh with a NVIDIA Geforce GTX 280.

 
What!?! Why is the shader model 3 method 10-20% slower? This sort of thing frustrates me. I make a change that’s supposed to be either faster or the same speed, and it’s actually slower. After making sure I wasn’t doing something bad when filling the transform buffer, I pulled out a GPU profiler to see where the difference was.

You’ve probably heard talk about games being either vertex bound or pixel bound. This just means that the GPU is spending more time working on the vertices of triangles, or more time on filling pixels on screen. The truth is that most games are both pixel and vertex bound at different times. If a game uses shadow maps, it’s probably vertex bound while rendering the shadow map. Modern GPU’s are crazy fast for filling pixels that are used for shadow maps. So fast in fact that the GPU spends most it’s time loading vertex data and running vertex shaders and that isn’t fast enough generate enough work for the pixel pipline, even with load balancing.

My game is bound like this. It’s also vertex bound on characters and animals – they’re small on screen, but the GPU is spending more time deforming the meshes than shading pixels. This probably means I need lower poly meshes and LOD’s but that’s a another task for another day.

However for other objects, when the game is rendering buildings and terrain, more time is spent on pixels than on vertices.

What’s happening to make the shader model 3 version slower is that the areas that are vertex bound become more vertex bound because of the load of additional data per vertex. When drawing an object for a shadow, the shader model 2 version only has to load 8 bytes of data. The shader model 3 version has to load 72 bytes. This is a lot more memory traffic, and the only explanation I have for the slow-down.

While the shader model 3 version is slower, the memory consumption of the application drops from 270Meg to 172Meg. That’s nearly 100 megabytes of repeated mesh data!

At this point, I have an idea to have both low memory usage and faster render time, but I know it’s going to take a few days to implement. Really, the game runs fine, I should focus on gameplay features, and I don’t need to write a DirectX 11 render path but….

I don’t think DX10/11 is very well accepted, or used widely as of yet. If I have a question about something in DX9, I can google for it and have an answer in seconds. The same can’t be said of DX11. There are very few examples. And while the documentation is there, there are a lot of hidden issues that you only find by reading the debug output from DX11 once you start using it. I’d hate to be someone who never used DX9 and jumped right into DX11.

I had a very slow start getting DX11 up and running. Apparently automatic updates installed Internet Explorer 10 on my development machine, which breaks the DX11 debug output. It also breaks PIX – a tool that lets you capture a frame of a game and examine all the GPU calls and state. I use it all the time to take the guess work out of rendering errors. It’s like a debugger for graphics.

The fix for this is to use Windows SDK 8.0. At the same time I figured I’d update to Visual Studio 2012. Once compiling with the new SDK, I discover that XAudio 2.8, which is all that ships with SDK 8.0, isn’t available for Windows 7. So I hack things up to use the old SDK to get XAudio 2.7 while still using the new DirectX 11.1. This all finally works, but PIX is still broken.

Finally I just uninstall IE10 and related updates since I don’t use it anyway. Now PIX works, and the DX11 Debug layer works. And Back to Visual Studio 2010. On with coding….

The DirectX graphics interface for my engine is only about 60K of code, so writing the same small bit for DX11 was pretty quick. I spent more time writing a shader generation system so that I didn’t have to write different vertex and pixel programs for shader model 2/3 vs 4. Texture sampling and shader inputs and outputs are significantly different between the different shader models. I also spent a fair amount of time debugging and make sure I wasn’t doing anything to cause the GPU to stall.

In shader model 4, there is this great input called SV_INSTANCEID. It gives you the index of the instance that the GPU is working on. This is exactly what my initial implementation did, but as I don’t have to supply the index myself there is no need for data repetition.

The draw call becomes

context->DrawIndexedInstanced(primitiveCount, instanceCount, 
	startIndex, startVertex, 0);

The shader looks like:

cbuffer tc
{
	float4x4 tc_transforms[128];
};
struct input
{
	float4 position : POSITION;
	uint instanceid : SV_INSTANCEID;
};

float4x4 localToClip = tc_transforms[input.instanceid];
float4 localPosition = mul(localToClip, float4(input.position.xyz, 1.0));

This is fantastic. DX11 also uses the least memory while running the game. 94Meg for the test scene.

While writing the DX11 implementation and reworking the vertex and pixel programs for shader model 4, I found a bunch of items such as unneeded input assembler loads, floating point exceptions, and render state that was making things slower needlessly. Because of those fixes, my shader model 2 implementation runs at 130FPS instead of the original 103FPS. Also fantastic.

Here’s my final resulting frame rates for my two systems. All results are GPU limited. CPU time is under 4ms in all cases.

The first scene has 2409 objects, and has ~817,000 triangles.
The second scene has 4617 objects, and has ~1,243,000 triangles.

Test System 1
i7 920 @ 2.67Ghz, NVIDIA Geforce GTX 280
1600×900, 2xMSAA, 2X Ansiotropic, 2048 Shadow Map, 5 Tap PCF shadow kernel

 
Test System 2
i5 M480 @ 2.67 Ghz, NVIDIA Geforce 610M
1280×720, No MSAA, Trilinear, 1024 Shadow Map, 5 Tap PCF shadow kernel

 
What does this tell me? It tells me I still possibly have something wanky in my DX11 implementation since it’s still 0.8ms slower than the DX9 shader model 2 version. However on the laptop GPU, the results are phenomenal. A decrease of nearly 10ms in the first test scene, and 12ms in the second scene is pretty amazing just for an API change.

It also tells me that I probably won’t ship the shader model 3 version. While is does use less memory, I’d prefer a better gameplay experience for those with older systems and video cards, and I can tweak the memory used for each model. Trees and rocks can have the full 52 copies of the mesh data, but buildings, and other things that will never reach 52 on screen at once can have only 2-5 copies. This will bring down memory consumption to reasonable levels, although it does require a per-asset tweak.

The DX11 memory usage is really good, and I could probably get the DX9 version down even further by not using the D3DPOOL_MANAGED flag on resources, but then alt-tabbing away and back to the application becomes annoying since I have to manually load all graphics resources from disk again. I’d much rather have the switch be immediate.

Was this week and a half of trying different instancing methods worth it? For sure. The original implementation now runs 2ms faster (103 to 130 FPS), and those with DX10 level video cards will get a performance boost on some systems. While writing the DX11 code, I treated it as a different platform. This makes me more confident about porting the game to other systems (like ones that use OpenGL), as the functionality is now there for making ports and dealing with different data per platform.

Now back to that mist, fog, rain, snow, and changing lighting conditions….

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!