Every time something is built in the Knights Province, terrain needs to be flattened. It’s a relatively small detail that does not affect gameplay much, but I think it adds to how responsive and interactive the terrain feels. Roadworks and buildings carving themselves into the world. Flattening is used pretty much every time something gets built on terrain – roads, fields, houses and so on. It is also one of those systems that normally goes unnoticed when it works correctly. You place a house somewhere, Builder arrives, terrain underneath gets flattened, house gets built, everyone is happy. Sometimes terrain is just too steep and then buildings just can not be placed there.
As with many things in the game, something that looks simple from the outside turned out to be considerably less simple once I started digging into it.
Legacy approach
Terrain flattening was in the game since Alpha 1 (and long before that). For the most of the time, it did its job just fine. It worked on a tile-by-tile basis. Given a tile that needs to be flattened, it looked at nearby terrain heights, calculated average and adjusted tile corner heights to make it flatter.
The legacy flattener had 2 hard problems and one soft problem.
The first hard problem is that a single tile flattening does not happen in isolation. While the Builder is doing his work, units are walking around, roads can be placed nearby, neighbouring terrain can change, another building can start construction and so on. Flattening one tile may make the neighbor tile become too steep and unwalkable. The legacy flattener algorithm mostly handled that well, but occasionally there would be a unit stuck on now-unwalkable terrain and the game would crash because of that.
The second hard problem was related to the flattener trying to flatten the terrain and entering an endless loop of flattening one tile, making the neighbor tile too steep. Then going to correct neighbor tile flatness and in doing that – breaking the original tile flatness again. Rinse and repeat ~5800 times to get the stack overflow crash.
The third soft problem was that sometimes terrain just would not become visually flat enough for buildings to look nice on it. Building corners hanging in the air do not look nice.
As you see, there are two different kinds of missing success criteria here. The flattener needs to be robust enough to not crash a game by breaking walkability or getting itself stuck, but it also needs to produce terrain that actually looks reasonably good (flat) afterwards.
Crashes happened just rarely enough to not warrant immediate fix and the visual flaw was not glaring enough. Yet they kept nagging me .. and this is where most of the fun begins.
Bonus to that, the legacy code has also accumulated quite a few quirks and patches over the years. It works, but it is unwieldy, results are not always nice nor predictable.
With that exposition, the goal sounds simple enough: make terrain flattening more reliable and look nicer. As usual, “simple enough” was the dangerous part.
Attempt #1 – “Lets plan better!”
Roads and fields flattening is more or less trivial, one tile is almost always easy to make flatter. Buildings – that’s where the meat is.
My first idea was to make the flattener smarter in the first place by letting it consider the whole building site before doing anything (and hopefully weeding out bugs leading to crashes while doing so). Instead of deciding tile-by-tile, it would make sense to inspect the whole house area, make up a flattening plan and then execute that plan. If a house needs a rectangular-ish patch of flat terrain, then surely it should be better to first decide what the final terrain should look like and then just apply all required changes when Builder works on it.
Small caveat – the plan is still being executed in the real game world. It may be constrained by unchangeable terrain (like mountains or water or pre-existing buildings around). The real game world has a lot of dynamic circumstances too – a porter might walk past the building site or onto a tile that has not been flattened yet. A road or another building might get placed nearby. Builders could get killed or die of hunger mid-work.
Suddenly a carefully prepared plan is based on assumptions that can change at any tick and are no longer true. So while planning the whole operation in advance looked nice on paper, it did not really solve the main problem – algorithm resilience to external events.
In other words, planning made the algorithm better at answering “what terrain shape would I like to end up with under this one house?”, but it missed answering the “how does it work together with everything else that is going on around?”. And the latter was exactly where most of the old crashes were coming from.
Detour #1 – tests
At about this point I realized that I need to add some synthetic game tests for flattening. For example:
- Flatten a house area on a hill
- Flatten a house area on a slope
- Flatten next to an idle unit
- Flatten close to a mountain
This turned out to be quite useful – it checked the algorithm in a controlled reproducible environment (testing for errors) and it also presented the algorithm’s functionality in isolation (testing for nicer looks).
It also made iteration much less annoying. Instead of trying to manually reproduce some weird terrain setup in an actual match, I could run the same scenario over and over and immediately see whether a change fixed it or merely moved the problem elsewhere.
In the same attempt I also decided to change house construction flattening strategy to work more incrementally. Instead of flattening the whole construction area once and assuming it is now good forever, a Builder would flatten all tiles once and then revisit the most uneven ones once again to make them less uneven. That covered the “quality” problem.
That kinda worked, but due to dynamic obstacles outlined above – it did not. There were too many unforeseen issues and it did not sound reasonable to pre-plan for all of them. This attempt failed. The problem was harder than it seemed.
Attempt #2 – “Let’s try AI”
At this point I thought: okay, flattening seems like a nice contained problem. It has known inputs (terrain heights, tiles to flatten) and known results (flatter tiles). Why not try using AI for it? Not quite as simple as “make me a better terrain flattener”, of course.
The first step was actually to formulate the specification. What exactly does the flattener take as input, what can it change? What exactly is the flattener supposed to aim for? What situations does it need to handle? What is it allowed to rely on? What must it never do? What happens when some terrain just cannot be flattened? How important is the final terrain shape compared to getting there safely? And so on. Listing and ranking requirements alone was quite useful.
Once all requirements were written down, I used AI to go over them again. Was anything forgotten? Were some requirements actually saying the same thing twice? Were there contradictions or vague parts? What were the hard constraints and what was merely a wish for? After some back and forth I had something resembling a proper spec.
This was probably the first genuinely useful result of the AI experiment, regardless of what happened to the code afterwards. The game has been using this system for years, but I never really had to write down in one place what “good terrain flattening” actually means.
Then came the algorithm selection. I asked for several possible approaches and compared them based on things like: whether they satisfy the requirements, how easy they are to reason about, how robust they should be, and, importantly, how simple the implementation would be. I would not want to get stuck with a magical algorithm I could not understand (nor debug) in the future.
I will not bore you with algorithm names and their O(n) complexity here. As it turned out later – that was not what mattered. Sufficient to say, the problem of flattening is kinda known to the world, but is not something as trivial as Bubble-Sort.
One of the approaches looked quite promising (not too complex, not too flaky), so the next step was obvious: ask AI to implement it. And surprisingly enough, after fixing the usual assortment of small issues in the generated code, it actually started working quite well in the synthetic tests. Very well, even.
There was only one tiny problem. It was slow. Not slightly slow. Not “maybe optimize this later” slow. It was more like roughly **1000 times slower** than the legacy flattener. Flattening a single Woodcutters house building site on an XL map would take like 10 seconds (rather than 14ms). Which is when I realized that performance was never actually part of the specification. My bad, xD.
Technically AI did what I asked for. Just not within any remotely sensible amount of computations appropriate for the project. Real-time games have a strict budget, either do it in under one tick/frame time or be gone. That was a nice reminder that specifications have an annoying property: things you forget to specify tend to become problems later.
Detour #2 – making flatteners replaceable
At this point it became obvious that I would probably be trying several different implementations. So before going further, this was a good time to refactor the flattening code itself. Previously the flattener was tied into the surrounding code (it knew about terrain, terrain kinda knew about it, Builders would access it directly when asking for tile-flattening). Replacing it meant changing more things than I wanted. Some abstractions and some cleanups were due, so that different flattening implementations could be swapped in and out much more easily.
This also meant I could keep the old implementation around as a baseline instead of immediately replacing it. Which turned out to be very useful later.
From this point on I could run the same test against Legacy, Planner and AI flatteners or whatever new experimental implementation to come. That sounds like a small infrastructure change, but it made comparisons and reasoning between algorithms much less subjective.
It also removed some of the pressure to make “The New Best Flattener”. A failed implementation could simply stay there for comparison and lookups, which is much nicer than repeatedly ripping the old code out and putting it back again.
Attempt #3 – Second chance for AI, now with performance on the table!
Okay. Same idea again, except now performance is explicitly on the table and is a cornerstone part of the requirements. Surely this should fix it.
So I updated the specification and let AI take another shot at the implementation, this time with much stricter performance expectations.
And code started appearing, first it was like 400 lines of code. Then some more code for incremental flattening passes and it became 700. Then there were some things that were not added in the first pass and it became 1100 lines. Tests were almost passing, revealing some edge-cases, and the implementation kept growing and growing.
Each individual part usually had a reason to exist, but the whole thing gradually became harder and harder to understand. And eventually it had all the signs of collapsing under its own weight. There were too many interacting rules, too many special cases and too many places where asking AI to change one behaviour caused it to make a change in 3 different places that affected one another. Surely not a good sign.
This was the point where “AI can write things faster than I can” stopped being particularly enticing. Generating another hundred lines was easy. Understanding why those hundred lines were necessary, whether they overlapped with something already there and what would break after changing them – was not.
In a way this was the opposite failure of attempt #2. The first AI implementation had a relatively understandable problem: it was hilariously slow. This one had a much worse problem for long-term maintenance – the thing was growing monstrously and I understood that I did not understand the thing I was about to start maintaining.
Performance-wise it was much faster than attempt #2, yet still much slower than the original code. More importantly, it never did satisfy all synthetic tests. Complexity itself became the problem. So that one went onto the pile as well.
Attempt #4 – fine, let’s do it by hand
After those 3 failures, which looked and felt like trying to eat too big a piece of a cake in one bite, I decided to go back to something I actually understood well – take the legacy algorithm and improve it myself. After all, it kinda worked for 99% of the games for many years. Maybe it’s not so bad and just needed a little oiling, instead of a redesign from scratch. Just look at the existing flattener, identify its weak spots, cover them with tests and rework them into a better version of themselves.
At first this went pretty well. The old algorithm already had one huge advantage: it had survived in the game for years. I could keep the parts that worked and improve the parts that sometimes did not. Unfortunately I made another mistake here. I was refactoring and adding new functions as I went without thoroughly testing it while reworking it. The implementation became more and more elaborate and, once it was at a checkpoint where I started running proper tests, it turned out to be… complex, slow, and faulty. Different route, remarkably similar destination. 🙂
Still, Legacy2 was not entirely wasted work. It explored quite a few useful directions and showed which changes seemed promising and which ones were probably not worth pursuing. It demonstrated that Legacy flattener had a lot of good in it, that could be taken as a basis for improvement. But Legacy2 clearly was not something I could ship in Alpha 14.
Detour #3 – Testing in the actual game
After going through all of this, I started to realize that my testing approach itself needed to be dialed up a notch. Small synthetic tests are very useful, especially when trying to reproduce one specific edge case, but terrain flattening interacts with far too many systems to rely on those tests alone. A flattener might successfully pass a test like “build a house on a slope” and still fail after 40 minutes of a real game because two Porters decided to exchange places next to a building site on a road near a mountain at just the wrong moment.
So I switched my main test rig from testing a dozen of specific edge cases to overall in-game stability. Good thing, that I now have 2 monster workstations that can churn 10000 games in a single evening xD.
The idea was simple: stop trying to imagine every weird interaction myself and let the game produce them. Thousands of simulated games will happily find combinations that I would never think of writing as a synthetic test. On the other hand, I also realised that I have to work towards solutions that prefer generalised robust solutions over an assortment of specific ones.
The next question was – what are the actual numbers, which maps are actually the worst for terrain flattening? After running a couple of thousands of automated games on all the stock maps, one of the particularly problematic ones turned out to be **Around the Mountain** followed by (with a big gap) the “Jealous Neighbours”.
That also makes some sense. There are just a few maps with lots of slopes, constrained terrain and starting locations close to mountains. Such areas naturally exercise the flattener much more than the majority of mostly flat open maps.
Having a problematic map is a gift when you want to make a problem disappear. So I started establishing a baseline. Using the original **Legacy** flattener, I ran around 2700 automated 60-minute games on the map. Across those runs, the flattener-related code crashed roughly 20 times. This gave me something much more useful than “this new version seems better”, now it became “this new version crashes half as often”. Of course, comparing other key metrics for degradations was also important. For example, a flattener algorithm that never does anything won’t crash, but it would also halt town development and thus resulting town size would be 0. So I checked that town and economy development were unaffected.
Now I can actually compare implementations on something that really quantifies the 2 hard problems described in the article intro. Does a change reduce the crash count? Does it introduce a new type of failure? Does it make performance noticeably slower? Can it really survive a thousand games instead of just ten nice-looking test cases? This is probably something I should have been doing much earlier.
With that in place and rigged .. mind you, it was not a piece of cake either, some quality time was spent on patching the game runner to work well between 2 workstations, but that’s a story for another time.
Now I also had to add a metric for the flattening quality – how much flatter the average (or median) building site had become. It is rather simple – take the difference between highest and lowest vertices within a house area. That also covers the third problem from the article start. Now it’s possible to objectively say if one algorithm is better or worse (on average or in 10/90 percentiles).
For example, a perfectly horizontal terrain would have a difference of zero, while a badly crumpled up one would have a difference of 40. Of course these numbers are not a perfect description of how a nice terrain looks, but it is simple, deterministic and good enough for comparing thousands of construction sites against each other. Absolute values are not important, relative difference between flatteners – is.
So by this point I finally had measurements for all three problems: crashes caused by reckless terrain changes, failures where the algorithm gets itself into trouble, and the actual flatness of completed building sites. Performance could be monitored alongside them as well.
Attempt #5 – back to Legacy, again
So this brings me to the current attempt. Instead of replacing the old algorithm completely, I am back to working directly on the original Legacy flattener. This time, however, I already have a few useful insights and tools from all previous attempts.
The AI attempts helped to formulate much clearer requirements for what the flattener should and should not do. Manual attempts gave me some neat directions for improvements and faith in the old algorithms core. The synthetic tests provide quick feedback for specific edge-case situations. And large automated game runs provide an actual stability baseline.
So the plan became rather boring, which is probably a good sign. Take the Legacy algorithm. Make one reasonably small refactoring or improvement. Run the small tests. Run the larger stability tests every now and then. See whether things actually got better. Rinse and repeat. Goodbye enormous rewrites and no attempts to make the perfect terrain flattening algorithm in one go.
An important difference in this workflow is that every change now has to justify itself. If some clever improvement makes terrain 1% flatter but doubles execution time or increases the crash rate, it is probably not an improvement. If a trivial two-line change removes a whole class of failures, it probably is.
And that was a rather different experience from the previous attempts. Instead of having a big new algorithm that was either “working” or “not working”, I could see individual changes move individual numbers. Some did nothing and got reverted. Some helped quality but hurt performance. Some fixed one synthetic test and made no measurable difference in large runs. And occasionally something small made a very obvious improvement.
So what did change in the algorithm itself:
- Overall refactoring without changing the algorithm made it clearer and ready for new changes;
- Incremental flattening made house area flattening better. It also made flattening longer in some cases, which is arguably not so bad for uneven terrain;
- Avoid evaluation of vertices behind unwalkable tiles;
- More careful comparison of surrounding tiles that were walkable and become unwalkable due to flattening of some tiles
All tests are passing now. Simulations show that the old flattener crashed ~22 times in 6000+ runs, and new one – zero. Flattening quality improved by 5%. I’m cautiously optimistic.
Due to algorithms simplicity, performance also remains in roughly the same ballpark as Legacy.
Zero crashes in 6000 runs does not mean there are no crashes left, of course. Terrain flattening has already demonstrated that it is quite good at hiding rare edge-cases. But compared to where this started, it is a rather encouraging result.
There are still some things I want to improve and some more simulations I want to run before calling this a day. But unless another exciting edge case appears, this version should make its way into Alpha 14.
In hindsight, the biggest improvement here may not even be the new flattener itself. It is exercising LLMs and spec development, test harnesses and formulation of correct metrics. The algorithm can still be improved (or even replaced) later, but now those improvements won’t have to be based on whether a couple of hundreds of houses on some bunch of maps looked okay when I noticed them by chance.
Phew, that was quite a journey for moving a few terrain vertices around. 🙂
