"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 open area like a park and cutting corners through the grass rather than follow 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.

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 (I haven't explicitly examined how large of an impact fixing this will really have compared to before--it might not be very noticeable, especially after other coming changes?)

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.

Each type of point has its own level of importance, and the paths linking with 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.

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

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!
• There's still more value and path tweaking to do, but it's in a workable state now so I've put that on pause to work on some other elements of this and related features.

Problems

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 from there, but when you mix in all that handmade content, that calls for... you guessed it... handmade points of interest xD

So, um, yeah, looks like we'll need to expand this yet further if we're going to add it at all. For this purpose I've added an additional range of point types that can be manually placed inside prefabs to link up with other points as usual.

As an example, here's the Exiles lab in REXPaint, with my test points placed using pink 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

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, racing through Cogmind's many hundreds of prefabs to assign these! (Some special procedural maps will also likely need their own rules for additional points.) In the bigger picture it's not so bad since honestly this whole feature and all the related stuff I'm working on is pretty complex and taking a while. I think the results are going to be worth it, though ;)

Other Notes

• Do we want to let desire paths be somewhat influence 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'm theming it such as that's not going to be too relevant or necessary anyway.
• No, I'm not yet actually talking about the utility itself yet--that's for later because it ties into some other mechanics yet to come ;)
• Altogether the desire pathfinding (and associated fuzzing process) does indeed slow down map generation, though it's currently within acceptable limits, adding about half a second on the largest/slowest worst case maps (e.g. Access). 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, so we could easily defer these calculations until after the map has been loaded and do it bit by bit then over the first handful of frames. No need to go there unless it becomes an issue, though. Also so far my profiling was only done on the debug version, which is of course slower with all its extra low-level checks, so my guess is that in reality it's adding a good bit less than half a second ;)