Recurring Nightmares

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.

19 Comments

    Louis
    August 12, 2019 1:38 pm

    I still love reading these devlogs. I don’t always understand them. But.. I find it fascinating to an inside look at what is going on in the brain of a developer in the trenches.

    Keep it up! Can’t wait to see more of what you create.

    Redketchup
    August 12, 2019 3:31 pm

    Please dont go back to a dumb pathfinding like Banished. I wish you make it so it is conscious of the height too. It was stupid to see citizens jump 100 yards up and down cause the is a floor at 100 yards high. in world of warcraft, the caracter is aware of this, and wont be able to climb if it is too high or too steep. We can use 3D pathing. make your pathing 3 dimensions please. it can open many possibilities like a bridge over and citizens pass under it… you can make tunnel below something else and citizens wont be thrown up or down because they were walking on the ground !

    Mike
    August 12, 2019 4:27 pm

    Like Louis said, it’s fun reading these blog posts, even long after the Banished project was finished. But the behind the scenes of your new project is incredible to see the woes and accomplishments of it.
    Sounds tough, but I’m glad you’re persevering through it. Excited to see the concept come together! Keep up the hard work. 🙂

    Martijn Zandvliet
    August 12, 2019 7:25 pm

    Have you considered fixed point numbers? Gives you the same precision everywhere in the world, the origin is no longer special. You also get a constant epsilon regardless of relative number magnitudes. And they’re fully deterministic in principle.

    If your particular implementation using fixed point then contains a bug, that bug should show everywhere, not in special locations.

    You’d still have to reason about required precision given the geometry of expected cases, and you’d potentially have to deal with integer overflow, which float doesn’t have. Definitely sounds like a case that might be worth the trade though!

    Another thing that came to mind is homogeneous/projective coordinates to gain more control over precision far from the origin, but if you stick to floating point it would mean tagging an extra one on per point, which means you might as well make everything doubles…

    Good luck, and thanks for sharing this. 🙂

    jensenthecat
    August 12, 2019 9:57 pm

    So impressed that you share your problems and experiences.
    I know a little, just enough to know that I can’t comment on your work, but enough to know that it is really hard slog.
    I’m sure I speak for many others when I say that we are longing to see the result of all your labours.
    Good luck and please keep including us in your persistent quest for perfection. (It doesn’t have to be perfect just good enough for beta…)

    OpblaasHaas
    August 13, 2019 4:30 am

    Like pretty much everybody here, i love these Devlogs, please keep doing them. I was getting kind of worried because the last one was some time ago, and it made me wonder if there was a way to support you in any other way besides buying Banished again.

    Not sure if it was ever mentioned, but are there any plans to setup something like a Patreon or a donation page?

    Stefan
    August 13, 2019 2:44 pm

    I do love your dev blogs indeed, keep going!

    After giving up on triangulations/Nav Meshes.
    Now I wonder what happened to your carribian islands approach you used in Banished?
    It converts the far to fine grained grid into an handy abstract graph.

    Some years ago it was an eye opener to see your Gamasutra interview about and I compared it later with Rimworlds region map approach and some papers on hierarchical pathfinding.
    And I think there is a lot potential still to allow fine grained but massive grids, especially when each hierarchy is using well selected abstract nodes and their edge costs are based on the exact pathfinding costs of the lower level(trade off between map update cost and path quality).
    There is potential to interlace levels, eg. calculate long abstract path but use a fine grained path for just a few abstract steps ahead.

    I hope you are getting back on this matter and I’d love to hear more about in future dev blogs.

    Guntha
    August 13, 2019 5:49 pm

    As soon as I read “arbitrary placement of objects”, I knew you were going to talk about floating point trouble. I encountered several projects that used them where they shouldn’t have (an architecture app while working professionally, where it was decided early on that there wouldn’t be any restrictions, but at least we didn’t require collisions or pathing, and a 3D game with Quake-style world creation I began on my free time using a custom engine). The most sensible solution I can think of for these problems is to add restrictions, but I see you’re more ambitious than that 🙂

    Keep up the good work!

    Tom
    August 14, 2019 1:58 am

    Yeah, the float issue happened to me too in Unity game engine (surprisingly more often when you are far away from the coordinates world center). Solution can involve scaling everything, moving the content and the camera near the world origins…

    Gary
    August 14, 2019 2:46 am

    Always enjoy these Dev blogs (missed them a lot when Banished was actually released). Thanks!

    Gabriel
    August 14, 2019 5:08 pm

    Finally a new entry! I can’t wait to know more about this new project of yours

    EFE
    August 15, 2019 5:32 am

    Hi Luke, I know you are busy but please post a little bit more often (once a month would be too much to ask?), we enjoy reading these a lot.

    Also please do not give up on the arbitrary placement idea, I think it will be a very innovative and fun feature for the game.

    Brad
    August 15, 2019 7:59 pm

    Knowing nothing about programming but loving the games you write has looking forward to these Dev Blogs and reading the entire thing. Keep it up, you have a day one buy here.

    Marcel
    August 16, 2019 4:34 am

    I found your entries very interesting even I haven’t writing any game related code. Looking forward your project crystalize to gameable/playable shape 😉

    Jimmy
    August 19, 2019 3:09 am

    I ran into very similar issues on a project of mine. My solution – which worked flawlessly – was to limit the precision you can place things at in the world. In my game, when you place an object, its position and rotation is rounded to the nearest 0.001 units. This is small enough that it’s not noticeable to the player, but large enough that the errors arising from floating point errors have totally disappeared. Everything is lined up on a small scale, so the math doesn’t need infinite precision.

    MZX
    August 20, 2019 12:49 am

    In my systems, as the precision is not that much required, I prefer to use fixed points instead of floating points; e.g., use int and assume it denotes 1/1000. I am not sure that may apply in geometry of games as well, though. It helps improve the performance, too.

    John (Dataremoved)
    August 25, 2019 2:18 am

    Love Banished and glad to see you’re still doing what you like doing 🙂
    Looking forward to whatever you have in store for us next regardless of when that will be 🙂
    Keep up the good work and stay healthy 😉

    Hakenden
    August 27, 2019 7:15 pm

    You do a great Job and we all wait for more Details what comes next.

    Xylax
    September 3, 2019 9:41 am

    I’m cheering you on so hard, thank you for the amazing dev updates. Banished is my favourite game of last 15 years, even going before it existed. Also, the layout of the generating algorithm reminds me of galaxy dispersal in the universe 10/10