Eureka? (Feb 28 '17)

After describing the difficulties I'm facing while trying to come up with a microeconomy model for Citybound in the last update, I got a lot of very interesting responses, probably since this topic is both at the heart of what Citybound will be and very interesting in general to everyone from smart layperson to expert.

Sometimes it seems like there is only one thing missing for everything to fall into place and in my lucky case it was a hint from a friend, encouraging me to look at "planning graphs" from AI research. Since that wasn't directly applicable, my conscious mind initially rejected this idea, but my ever smarter subconsciousness kept cooking it and not much later presented to me a most delicious idea:

The Activity Network

There is already a road network in Citybound and pathfinding is done on it to find the best way from point A to point B. Direct connections (a.k.a. graph edges) between points (a.k.a. graph vertices) have a cost associated with it: the travel time along the connecting piece of road. An optimal path between A and B is thus composed of road pieces / graph edges with the minimum total travel time.

Now, what if roads weren't the only kind of graph edges, but if there also were activity edges? These would usually form a small loop, simply connecting a place (like a bakery) — using an activity (like "buy a pretzel") — back to itself again (since you are still at the bakery after the purchase). The interesting part is now the more complicated benefit + cost of such an activity edge, which would cover several resources: (-0.4 money, -0.5 time, +1.0 pretzel), describing how the carried resources of an agent using this edge are affected.

Making a trip to the bakery to get a pretzel would thus mean traversing the normal road network edges to get to the bakery, doing the pretzel-buying-loop, say, five times, and traverse the road network edges again to get back home.

Now imagine the whole network of a city like this (and at this point I'd love to already have a detailed example picture, but just imagine) and all road and activity edges having a time cost associated with them. In a way, the road edges are also just activity edges using and giving different kind of resources (using time, fuel, giving scenery, ...), they just happen to bring you to places instead of being loops.

The problem of planning your daily life then just becomes the problem of finding the optimal path through this activity network — in particular the path that, by travelling and using activity edges, accumulates exactly the benefits you need to cover your household's needs, while minimizing negative factors such as fuel consumption, unhealthyness of traveled paths (because why not give the road edges more complicated costs as well!), the tiring effect of some activities, ... while also fitting all of the summed time cost into, for example, 16 waking hours.

This alone potentially allows for complex and diverse behaviours like walking through a park after work to a supermarket and finally going home by subway, not only making reasonable use of the closeness of these facilities, but even making it possible for the supermarket owner to understand the benefit of putting his supermarket inbetween a business center and a subway station (for example by simulating the improvement of "daily path" of a couple representative sample people already travelling there).


The straightforward way to introduce new agents to the city would just be to try finding self-sustaining paths from all currently vacant living space.

Unfortunately pathfinding on huge networks (think all the road segments plus all the activities at each place in the network, keeping in mind that there can be hundreds of households in a single high-rise building) is already difficult enough — but once you start to optimize for not just one cost metrics but several, things get really interesting and complicated (there is not really strictly "one optimal path" anymore but a potentially large set of paths that are hard to compare or tradeoff and each just "don't definitely suck more than another path").

Luckliy, like I a lot of my previous post was about, more humanity saves us again. Almost no one starts off as a blank slate, most of us have an existing life which we might try to incrementally improve from time to time and that should be feasible and intuitively implementable on the Activity Network, even in such a detailed setting.

In the context of a citybuilder, the most obvious way to start everything off is with a couple of agents who just spend their whole day in the "neighboring city" point, which offers all the activities they need to survive, but from time to time they check out if they can use some of the activities offered only (or better) in your new small city to improve their lives, and eventually it will make sense for them to move there altogether.

More complicated details

To actually make the picture more complete at least all of the following need to be added to the model (off the top of my head):

  • distinguishing who is the recipient/supplier of which resource benefits/costs during an activity (person buying a pretzel pays with household money to the bakery business, uses personal time, receives one pretzel from bakery storage, ...)
  • having resource preconditions on activity edges (you can only traverse this edge if you "have a car with you" / if you are an adult / if you have at least 0.5 management education / ...)
  • having time of day preconditions on activity edges (work hours, opening hours, public transport schedules)
  • distinguishing between predicted costs while planning (based on estimates, historical traffic data, ...) versus actual costs while doing an activity (slowdown due to concrete cars on a road, waiting for a cashier to have time, ...)

In conclusion, I have a really good feeling about this idea, to the point where I want to start implementing it right away and see how to best optimize it to millions of agents along the way — since it really contains so many challenges combined in novel ways (if I look at current research) that it seems very hard to predict what will actually be slow.

What really convinces me is how easy it is to imagine both problems and their solutions in terms of the Activity Network, that it ties together transport and activities in this amazing way and that it lends itself not only for planning, but also for running the simulation of what happens at each moment and visualising that in many different ways and even debugging everything!

It's scary but super cool and exciting. Let's do this!

Discussion on Reddit

Support Citybound on: