Under the Influence (of Euclidean Distance Mapping)

First off, an announcement: customarily, we release new builds of CE (major ones) at the fifteenth of the month, or as close as we can get to that. This month’s build will be pushed back until next week, owing to the fact that we lost a week and a bit of development time in December due to the Fishmas Holidays; experimental builds will, of course, continue.

That said: Technical Talk Day.

Loosely speaking, this month’s patch is focused on doing spit and polish, maintenance on existing issues, and busting some bugs rather than new gameplay features (although we’ve done a bit of that). In terms of character behavior, you may have noticed that characters occasionally do things that are counter-intuitive; we are narrowing this down as development continues (Daniel has a huge and terrifying spreadsheet). We have received a number of bug reports of the following varieties:

“people wander off into the woods and die”

And, well, that’s about it, really.

Here's a tantalizing sneak peak at the promo illustration for this month's update.

Tangentially, here’s a tantalizing sneak peak at the promo illustration for this month’s update.

The solution to this is that people should calculate when they are, or are not, in the user’s colony. We previously did this with a notion of “civilization”, which computed (for each tile) the closest distance between the tile and any civilization in range. The problem is that the way this calculation was done was a) buggy (if a building was not within some radius of the square being tested, which was quite a small radius, we wouldn’t pick it up), and b) slow (using more than one square root per grid tile, which adds up on a 512×512 map.) I finally got sick and tired of this this week, and decided to look up the right way to compute distances.

It goes a little something like this.

It goes a little something like this.

The solution I settled on comes from an academic paper, “Euclidean Distance Mapping”, published in 1980 by PE Danielsson. Originally designed for robotic motion planning and computer vision processing, it treats the world as “foreground” and “background” (in our nomenclature, “civilization” and “not civilization”) and then does two scans to propagate distance from civilization across the map in a very clever way. The first scan propagates top-to-bottom then left to right; the second scan then propagates bottom-to-top, then left-to-right. It’s very fast, operating in linear time on the number of elements in the civilization map, and because we now store and use square distances everywhere, we get rid of those pesky square roots. Even better: people can now return to civilization effectively using the Brushfire algorithm to compute the nearest path to civilization: starting at the player’s source location, keep moving in the direction of highest civilization until you find an area that actually is in civilization, and that’s the closest path to safety!

Book it, it's Her Majesty's Anti-Paranormal Investigators and/or the constabulary!

Book it! It’s Her Majesty’s Anti-Paranormal Investigators and/or the local constabulary!

Because this is fast and easy to update, we can now compute the influence of arbitrary buildings quickly and effectively, provided we know the maximum value that we care for. This will be affecting a number of things, as we proceed: barracks and chapels can now spread influence throughout the map; the office of Her Majesty’s Anti-Paranormal Investigation Squad will, once it’s in, have designated areas of Finding Problems and Neutralizing Them; and areas full of specific areas can be marked as having influence such as “don’t go here, it’s full of danger.” We can now also update these maps quickly and efficiently as the game changes, which eliminates the stutter you may have observed when creating a new building. (We still get a stutter when placing modules, because this updates the connected component map; embarrassingly, we discovered we broke this back in *June*, so now characters correctly see if they can pull items for building jobs and the like before selecting them as requirements. This should fix the bug where “characters lock up, forever, trying to gather building materials”; we also hard wired it so they only consider the closest usable building material or workshop commodity, which should hopefully prevent people wandering off into the woods to get some log that they feel particularly happy about but which is swarming with bandits and then dying.)

You may also have noticed a chain of events of the form “bandits steal your stuff, characters go off to use the stuff that was stolen, and die” (also: “characters die at the hands of fishperson, other characters go off to butcher their corpses and die at the hands of the fishpeople; cannibalism tango ensues”) As part of our long-awaited networking overhaul, we need to have the notion of “Player A’s Logs” versus “Player B’s Logs”; we have extended this to include a general model of object ownership, so that your characters will only use logs that they think they can own. Once a bandit picks up logs or steals them, these resources will be marked as no longer being your logs; instead, they will become the bandit’s logs (until you defeat the bandits and claim them) Retrofitting the entire jobs system with this is time-consuming, but we’re working on it.

In conclusion, fixing things and ironing them out! Progress! Game development! Woo!



Posted in Clockwork Empires | Tagged , , , , , , , , , ,

15 Responses to “Under the Influence (of Euclidean Distance Mapping)”

  1. kikito says:

    Ah, pathfinding. I don’t know if this will help you, but I found Rimworld’s Technology video about Regions quite fascinating. It seems it has helped ironing out lots of tricky pathfinding issues in that game, improving speed at the same time.

    { reply }
  2. MailersMate says:

    I can confirm that all codebases are terrifying mounds of comments

    { reply }
    • Mike says:

      A codebase that is a terrifying mound of comments is infinitely preferable to it being a terrifying mound of no comments.

      { reply }
      • Yeol says:

        That’s rather dependent on whether you trust the people who wrote the comments or not, though. If you do, you’re likely to end up wasting time and screaming at code that doesn’t do what it’s supposed to do, only to realize the code has changed since the comments were written. If you don’t trust the people who wrote the comments, then you’re probably fine since you’ll be pointed in the right direction, but otherwise won’t put too much faith in the comments’ accuracy.

        tl;dr: assume every programmer is a liar

        { reply }
    • MailersMate says:

      @MIike This is true
      @Yeol That seems a little hash – but then I almost exclusively work in 2/3 man projects

      { reply }
  3. Puzzlemaker says:

    I don’t understand how that distance mapping works. Is there a link anywhere to a simple explanation or the exact paper you used?

    { reply }
    • http://www.prism.gatech.edu/~aclegg3/Papers/Danielsson_Distance_Mapping.pdf

      In a nutshell: you set everything that isn’t in civilization to INFINITE DISTANCE from civilization. You then do a top-down pass in which you check each pixel against its neighbour below, to see if your neighbour’s distance to civilization plus one in the Y direction is smaller than your current distance to civilization. If so, you update. You then do a left-to-right pass, then a right to left pass. You then repeat, going bottom up. The key innovation here is that you store the X and Y distance from civilization as two components per tile, measured as red and yellow in the animated GIF.

      The only gotcha is that when it says “min” they want you to work out the squared distance to civilization and use that for the comparison. Took me a day of guessing to figure that one out.

      { reply }
  4. Jabberwok says:

    My favorite programming stories are the ones about why characters wander off to die.

    { reply }
  5. Sapphire Crook says:

    When a Colonist reaches a certain, ripe age or feels the onset of nature, all they can do is wander off into the woods and die.
    Why are you getting in the way of nature, developers? You’re ruining the cycle that Eldritch Horror #45 dreamed of years ago!

    { reply }
  6. Alephred says:

    I find the refinement of pathfinding and the concept of ownership terribly engrossing, from a game mechanics standpoint, and yet I feel this will not translate well into the form of Youtube videos, which makes me sad.

    { reply }
  7. Coaldust says:

    I hope you will take a page from Dwarf Fortress and preserve some of your amusing bugs as gameplay features.

    Remember back when the buildings rendered incorrectly? Maybe that was just a cultist building non-euclidean housing!

    Perhaps particularly powerful hell and hellfire sermons could cause sinners to explode!

    { reply }

Leave a Reply

Your email address will not be published. Required fields are marked *