“Desire Paths” for a Robot World

desire path (n.) -- a planning term referring to a path made by walkers or cyclists, as opposed to one that is officially planned

For years I’ve always been interested in making some kind of utility that allows you to see paths that were traveled by robots, partially because it just seems like a neat thing to do, something which would also probably look cool :)

Of course if the player is just entering a map and the entire population has literally just been “spawned in” as well, then they haven’t actually done anything yet and this utility wouldn’t even have any real information to display at the time, making the environment seem pretty artificial. What we want is a way to basically fake the data to reflect actions that might’ve happened before.

At the same time, with a theoretical utility function such as this there’s also the concern that where actual robots have been moving in the past hundreds or even thousand turns probably isn’t really very useful information for the player. To be useful, it’s less about where these actual robots have moved, but the areas we imagine they might’ve been more likely to visit over a longer duration, thereby highlighting potential “points of interest” on the map, points that the player probably finds interesting as well…

Time to fake some traffic data!

Basically we need to:

1. Identify points of interest
2. Assign them relative levels of importance
3. Plot paths between them to generate a reference map for visualization purposes

I also needed something to call this feature internally, so I looked up the term to describe natural paths gradually created over time by people taking routes that don’t perfectly align with available pathways. They’re apparently called “desire paths” (among other names).

Now obviously 0b10 is mostly straight corridors with fewer open areas that work differently than people walking through an area like a park and cutting corners through the grass rather than following walkways. Robots are still essentially confined to these corridors and we don’t see them blasting through walls just to make a shortcut (unless you’re a Behemoth? :P), but they’re also not always moving in cardinal directions and taking perfect right angle turns (even if in the world of Cogmind doing so would technically not affect travel time!). Instead we see them frequently cut across areas in what looks like more natural movement, or taking a shortcut through a room where it’s convenient, or slipping between several machines in an array rather than going around the edge of the array, and so on.

A very early implementation of the desire path system.

Those big squares filled with numbers are junctions, one of the “points of interest,” where the number represents their respective rating. Junctions are rated based on their size and number of corridors and rooms they link to.

Aside: In working on this feature I discovered that in all prior versions junction ratings have been incorrect due to forgetting to initialize their value before a different part of the code actually did the calculations, meaning that junction Sentries have been misplaced this whole time. I always kinda wondered why they seemed to be in random junctions rather than the important ones, but it was never all that important so I didn’t look into it. Now we know xD (Junctions are now properly rated, though this may not have a huge impact on Sentries going forward anyway since the most important junctions are going to be repurposed for another defensive purpose coming soon…)

Clearly the first thing we need to do here is identify exactly what types of locations count as points of interest for our purposes:

• Exits: Duh
• Machines: The interactive ones, yup
• Junctions: Mainly to help connect everything and also make the path map seem more realistic
• Chutes: Technically count as exits of a sort, and also for realism since as we know there is some 0b10 activity centered around these

And that’s pretty much it? Really that covers most of the relevant core environmental features, and although I had some other ideas, if there are too many points and a dense web of paths connecting them all, then the entire map is filled and the information becomes mostly useless anyway, or at least really difficult to parse.

Each type of point has its own level of importance, and the links between more important points will appear more prominently in the desire path visualization. Point types are also broken down further where appropriate, since not all exits are created equal, plus we can assign different values to different types of machines, and junctions can use their calculated rating as their importance (which is how I discovered that bug since I needed the actual number here and something was seriously off at first :P).

The general idea for the process is to plot a path between every point and every other point, assigning the average of each endpoint’s importance (“desire path value”) along the entire pathway.

Now it’s not realistic or useful to literally connect every point on the map--we don’t want some tiny Terminal in one corner of Factory pathing its way over to a caves exit on the opposite side, so we’re going to need more variables in order to limit these connections in a realistic manner. Each point type and subtype also define a maximum connection range and maximum path distance. The former requires that endpoints be within a certain direct range from one another (also nice because this value can limit our number of pathfinding calculations by not even calculating those which are clearly too far away), and the latter path distance limit will be some larger value to allow a path to snake over to its destination if necessary, but still stop it if the direct range check found it was simply on the other side of a wall but actually reaching it requires an excessively circuitous route.

Source code values describing how each point point of interest integrates with the web of paths.

With these three variables in action, our desire path map should start to look better.

A further refined implementation of the desire path system.

Additional notes about the above map:

• Unlike the earliest sample image I shared before, the paths have now been fuzzed to look a bit more reasonable and pleasant. This is accomplished by adding half of each path’s value to any adjacent positions not on the path itself, and can also represent bots moving around each other, or patrols checking out rooms via doorways, etc.
• Overlapping paths of course increase the value of a route even more, which is what the brighter lines represent. Having access to this information brings interesting implications for navigation… Is that bold line leading to an exit? Or a bunch of useful machines? Or… a Garrison!
• More path and value tweaking might still happen depending on the results of the current prerelease version patrons are testing, but it’s in a decent state for now so I put that on pause to see how that plays out.

Challenges

For the most part this system seems to work nicely in Complex 0b10 maps, which as you can see it’s been initially designed for, but what about caves? What about custom prefabs? Oh my…

Defining a list of points of interest is easy when our maps are procedurally generated and everything can be managed automagically with a simple set of data and algorithms, but when you mix in all that handmade content, that calls for… you guessed it… handmade points of interest xD

So yeah, looks like we’ll need to expand this yet further if we’re going to add it at all. For this purpose I added an additional range of point types that can be manually placed inside prefabs to link up with other points as usual. These are actually listed at the end of the POINT_OF_INTEREST_DATA I shared above.

As an example, here’s the Exiles lab in REXPaint, with my test points placed using pink numbered identifiers in one of the layers.

And here’s that same map with the resulting desire path visualization as generated in the game

Now I’ll be the first to admit this information won’t be particularly helpful when you visit the Exiles, but it’s a part of maintaining consistency and polishing a game, so what are you gonna do? :P (okay technically for now it’s even going to be impossible to get the ability to see these paths before reaching this very early map, so it’s totally unnecessary here, but I needed a big prefab test case, and one that wouldn’t require sharing spoiler locations!)

That’s the extent of what I’ve done so far in terms of prefabs, just to test it out, but this is going to be a fairly large amount of work, parsing through Cogmind’s many hundreds of handcrafted rooms and areas to assign these! (Some special types of procedural maps will also likely need their own rules for additional points.)

I’m waiting to see more playtest results before assigning all the manual values, since the amount of effort required means it had better get done right the first time!

Processing power is another concern when working with this many calculations at once. Altogether the desire pathfinding (and associated fuzzing process) does indeed slow down map generation, though it’s currently within acceptable limits. To make sure I wouldn’t need to optimize the algorithms yet I did a bit of profiling to see just how much time these desire paths adds to the map initialization process in various locations (“initialization” includes both generation and all post-generation steps, everything needed to get the map ready to start playing in):

Overall the cost shouldn’t be noticeable, especially given that some maps themselves may occasionally take up to 2~4 seconds to load due to throwing out a large number of invalid layouts.

A feature like this would be pretty easy to optimize since you aren’t going to need the data within the first split second of entering a map anyway, and nothing else is dependent on them, so we could easily defer these calculations until after the map has been loaded and distribute it over the first handful of frames. My first profiling results were actually noticeably slow, but that was during the implementation phase when I was using the slower debug version, so I eventually went on to compile the above data using the release version to make sure.

Other notes:

• Do we want to let desire paths be somewhat influenced by actual robots and their activities? Probably not, because again it’s not especially useful, and although it could be more realistic or interesting in other ways, I’ll be theming this data such that this factor won’t be too relevant or necessary.
• How does the player access this intel? That’s for next time ;)

Update 210802: Meet the Active Sensor Suite, the gateway to getting all this info and more!