Login / Register

Latest official blog posts

Small Ideas, Big Changes

1st October 2019

As I've been working lately, I've been very aware that seemingly simple things I wanted to have in a new game have huge implications on the difficulty of making a game and engine.

The first thing I wanted to change from the previous game was the ability for the camera to look up toward the horizon. In Banished the camera always looked down, and the higher the camera got, the more the ability to look up was limited.

This was great for performance - it limited the number of objects drawn, and no graphics models needed simpler level of detail (LOD) versions. The terrain was simple. I didn't have to have a fancy sky drawn, nothing had to be drawn past the mountains at the edge of the map. The drawback was that you couldn't ever see the whole settlement once it got large. You also couldn't move around very quickly.

Now with that simple change - looking up, and zooming farther out there's more work to do. All models need some of LOD to keep the triangle count down and keep highly detailed objects from aliasing in the distance. The terrain now has LOD as well. Having LOD on the terrain makes texturing it and having decals on it harder. And brings in other problems like objects disappearing or floating because the terrain is less detailed in the distance. I also have to draw to the horizon, ocean or mountains, the sky, the sun.

Drawing shadows also takes more time. Instead of a single shadow map based on what's visible, to draw to the horizon takes multiple shadow maps, various tricks for distant shadows, and more complex pixel shaders. This also increases CPU load as 4 shadow maps are drawn instead of 1.

The renderer also has to change to handle this. While it works just fine, it's slow. Instead of dealing with say 4000 visible objects in view, my current test scenes are dealing with 40000. So the renderer has to be changed to handle culling away and drawing 10 times the number of objects in the same amount of time as before. Granted GPUs are a bit faster than before, but CPU time hasn't increased the same way.

After the camera change, the next change I thought wouldn't be so bad is arbitrary layout of buildings. No grids. Grids were great in Banished because it made lots of things simple. Pathfinding was on a grid, placement of objects was on the grid, everything used the grid.

But I want to see organic layouts. I'd like farmed land to follow terrain and butt up against a river. I'd like buildings and roads to placed in whatever natural way they end up being.

But with the grid gone, lots of things are more complicated. Placing objects now requires checking an arbitrary shape against everything else already placed. This requires a spacial subdivision structure to be fast. It's also harder to visually convey the overlap and how far you might have to move something to get it to fit.

It also adds a little friction to placing buildings. With a grid, you might place 2 buildings and leave space inbetween for something else - because you know its size. With arbitrary sizes, rotations, and shapes this can get harder, and potentially frustrating. When you do want to line up objects, its not as easy either.

Because things are arbitrary, I'm no longer limited to square regions - players can create any shape for an area - which is great, but makes the user interface more complicated. At the same time it can add friction to the experience because you have to spend time layout out areas if you don't want the results of a quick click-and-drag.

I've been working on making placing arbitrary objects and regions as painless as possible, but it's challenging.

As I wrote about last month, pathfinding has also gotten more complicated. However with the complexity comes flexibility. I have pathing setup such that characters can always walk between buildings, reducing the chance of getting stuck, and decreasing search time while running the A-Star algorithm. Search time is also decreased due to much more open area.

Thankfully, graphics doesn't get anymore complicated, it was written to handle things in any orientation from the start.

These two seemingly simple changes have caused my game engine to get slightly more complicated. What is hardest is that there's even more tiny details than I've written about that I keep running up against that were unknowable until I ran into them. I've spent more time making the features work than expected.

In the end, these changes are good - even I went back to building a grid based game with limited camera. It's just surprising to see how far reaching a simple design decision can be.

View comments »

Recurring Nightmares

12th August 2019


Almost every project I've worked on has a bit of code that always causes chronic problems. Some code gets written and it seems to work well in development and testing. Then someone on the team creating real world data causes it to malfunction.

So then the programmers fix the issue, and everyone continues on their merry way, until, some different real world data causes it to malfunction.

This cycle continues until the game ships. I'm not sure this problem comes from poor development - it's just that code can be so complex, no one can envision all the ways it will be used or all the ways it can break.

I've even seen this happen across multiple projects that reuse a game engine. A feature might be used flawlessly on one game, and unchanged, it breaks on the next game in development because it's being used differently or with different requirements.

I've seen this happen across all fields. Graphics, physics, collision, AI, audio, animation, controller input, even movie playback!

Sometimes, once true real world requirements of a system are known, a full rewrite helps the chronic bugs. Or eventually all the edge cases are discovered. Sometimes not.

Unfortunately I've got an issue like this now. A while back I decided I wanted to support arbitrary placement of objects. Any shape, any rotation, with potential intersections, added and removed dynamically to the play field. I ended up implementing an algorithm from a paper called Fully Dynamic Constrained Delaunay Triangulations. It's a bit complicated, but was fun to implement and works really well. The paper covers all the cases needed to be robust, but there are really tricky issues that come up.

Right now it handles pretty much whatever I throw at it. It makes nice big triangular maps of pathable space that I can run A-Star on for pathfinding, and the map can be analyzed quickly to allow different sized units.

Here's some pretty pictures of it, and some test paths that have a non-zero unit radius.



So every few weeks, the random level generator ends up placing objects in configurations that breaks my code. Arghghgh. Sometimes it breaks building a map. Sometimes it breaks when quitting and a specific object is removed. The worst is if it breaks when I place an object manually, because it's really hard to find and recreate the exact placement that caused the issue.

And so I stop whatever task I was doing, and start debugging the triangulation code. This is not easy - Some maps have 20,000 objects, and 175,000 triangles in the pathing mesh. I end up doing a mix of visual and code debugging. By drawing the pathing mesh at the point the error occurs, as well as before and after, and stepping slowly through the code to figure out what is happening, I can figure out what's causing the bug. It usually takes me several hours to determine the problem. Sometimes more. Finding a quality fix is typically hard. So I take a break, sleep the night, and generally have a good idea for a solution in the morning. Implement and test.

Then I wonder, "Okay, What was I doing before I ran into this bug??"

For this triangulation system, the culprit is floating point math. Every time. The algorithm is good. I haven't had to change the major details of it a single time since I got the initial implementation working. But because math on a computer is an approximation using a fixed number of bits, math that works out on paper does not always behave the same way on a computer.

For example, one of my issues dealt with computing the circumcircle of a triangle. The algorithm just didn't work at far distances from the origin until I wrote the math three different ways to find the most numerically stable and accurate implementation. On paper the math should have resulted in exactly the same result for all three methods!

Another issue arose because I was testing a large circle against a point which laid exactly on its perimeter, but the test failed because of lack of numerical precision. I've also had failures do to nearly degenerate triangles. And other crazy things that are hard to describe concisely.

I'm pretty sure some of the worst bugs to fix properly in my programming career are due to floating point imprecision. We have a long history, and we are not friends.

When I started making games professionally the fix would be to test using an epsilon. For example instead of

if (x == 0.0) { ... }

I would write something like

if (abs(x) < 0.00001) { ... }

In the right case this can be good. But in most cases is very bad. Because without the right epsilon and knowing what x is and always will be, you are potentially creating false positives in addition to fixing the original problem. I avoid this whenever possible.

My goto solution now is to use geometry analysis to determine an answer that needs high precision. Can I make an inference of the result using vertices, edges, and faces, and their relation to each other? Can I write the algorithm to be fault tolerant of values slightly under or over the desired one? If not, can I rewrite the math such that I'm never using values orders of magnitude away from each other?

Having fixed so many small cases - about one a month, I do consider going back to a simple grid for pathfinding. But I purposefully chose this route as the most flexible. I do wonder if I'll ever get this piece of code to be fully stable. At least it works today and it generates lovely paths for units to follow.


Only time will tell if I get all the kinks worked out - at least until the next project that uses it in a different way.

View comments »

Art Test

30th January 2019

I've been tired of looking at grey flat land with test objects, so I spent a bit of time doing some art tests. It's hard for me to have any feelings about a game without visuals. Yes, the gameplay can be in place, and it might be fun, but for me it misses something undefinable without the visuals - partly charm, warmth, completeness, but something more as well.

At the same time, since I've still in a very much prototype phase of development, I don't want to spend days on each art asset, or hours making shaders.

So I arrived at a prototype art style that is certainly subject to change, but for now gives me something more concrete to build on where I can add detail later.

It looks like this:


So now I can quickly model general shapes, play with color and shading, without spending a ton of time getting high resolution assets built.

A bunch of other things had to be done to make this happen. I had to start a proper terrain generation system specific to the game that incorporates gameplay features instead of just being specific to terrain. This was fairly quick implement do to previous work.

I also had to rewrite the shadowing system I had from Banished - previously the camera couldn't look up to the horizon, but now I'm allowing a much more flexible camera, so I need to render to the horizon and handle shadows in any configuration. Not hard, but a bit of a change from a single shadow maps to cascaded shadow maps.

Also due to the camera changes I now have some new rendering systems to handle more objects and need to create LOD objects for things far away - another thing that I didn't have in Banished. And another reason to have a quick prototype art style. Each asset now needs multiple models for close, mid, and far view distances.

I'm allowing a large zoom out distance, so you can look over a fairly large area. Here's the same terrain as the previous image from far away.


Obviously it still needs, ocean, and sky - but usually I'm testing close up in the middle of the island looking down, so it's not an immediate need.

I may end up with something in-between this style and Banished's style, or something completely different. Or I may stick with it - I've got plans for far more assets than the previous game required, so faster art creation might be a really good thing.

View comments »