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.
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.
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!
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!