Saturday, March 20, 2010

Transportation Simulation Games

When SimCity 4 was released, I was very disappointed by the broken transportation model, the assumptions built into underlying economic model that resulted in all cities looking like California, and the weird game design that assumed I was more interested in building stories about Sims than about building stories about the city itself. Since then, I became interested in figuring out how the simulations in these games work, but I always got hung up on a small mathematical detail. I finally figured out the problem a couple of weeks ago. Some simple grade 11 math is all you need, but I just couldn't see it until now.

The most intuitive scale to model these simulations at is at the level of individual people. So for each "person" in the city, you code up a model for the person's preferences and behaviour, and you then "run" this model and record what happens. So if a person wants to drive along a road from one building to another, you then increment the traffic on that road segment to account for the person's car. If you simulate enough people, you can figure out the traffic along each street, resulting in a simulation for the entire city.

The problem is that the city is constantly changing and the people being simulated will change their behaviours, so you want to have the simulation running constantly to take these changes into account. This makes the simulation complicated. If your simulator decides that a person will take an alternate route to get to a destination, the simulator needs to reduce the traffic along the old route of the person (since the person no longer drives on those roads) and increase the traffic along the new route. Keeping track of the routes of all these people is complicated, memory-intensive, and slow. If you don't remove the person's traffic from the old route though, then the traffic along the old route will keep on increasing (since there's no way for the traffic to go down to reflect the fact that fewer people are using it).

One solution is to divide your simulation into rounds. In each round, you simulate the actions of all the people in the city once, record the result, and update the UI with these results. Then you start a new round by discarding all the results (i.e. set the traffic of all roads to zero) and running a complete cycle of the simulation again. This approach isn't satisfactory because one cycle of the simulator might take several minutes to complete. So if you change something in the city, it might take several minutes to see the effect of these changes in the simulator because the UI won't be updated until the next simulation cycle.

We want to constantly update the traffic values, but this results in traffic growing without bounds. Resetting the traffic to zero is not practical because we want to be able to display the simulation values as they are updated. What we need is some way to "decay" the traffic along road segments over time. As a result, the traffic along each road segment will constantly decrease, but as you simulate the actions of different people, the traffic along each road segment will increase again. For this to work though, the speed of the decay must be balanced out the speed at which you add new traffic, so that the simulation converges to reflect the correct traffic along a certain road. But I could never figure out the math for this problem. If traffic decays too quickly, then the traffic will be close to zero in most places, but will spike up randomly in places where the new routes of people are being simulated. If traffic decays too slowly, then the total traffic along each road will increase without bound.

Simulating transportation always results in new traffic being accumulated in an additive fashion. i.e. As you simulate the route of one person, the traffic along the route will be incremented by a constant to reflect the traffic of this one person. But the decay must be in the form of a rate. The traffic along a route cannot be decreased by a constant all the time, but by a percentage of its existing traffic (because heavily trafficked routes should have their traffic decreased by a larger amount than lightly-trafficked routes--otherwise the traffic on light routes will fall to zero while the traffic on the heavier routes will increase without bound). Previously, I tried to think of things as being like a physics simulator where the simulator would try to balance things out so that the amount of traffic added by the simulator will be counter-balanced by removing an equivalent amount of traffic due to decay or something like that, but this isn't quite the right thing to do.

In fact, the solution is the geometric series. For example, assume that you don't change your city at all, so that the simulation should converge to a steady-state. So if you simulate all the people in the city, the same amount of traffic will be added will be added to a particular road segment (say, a). If you decay the traffic on any particular road segment by a rate r (let's assume you apply the decay once every time you do a complete simulation cycle of all the people in the city), then over time, this results in a geometric series. Geometric series will converge to a/(1-r). This is exactly what we need! We don't have to fiddle with balancing the rate of new traffic with old traffic or whatever--the geometric series shows that the simulation will converge to nice stable values. And we can then scale a and r to get the convergence rate and overall stability that we want. It all becomes nicely straight-forward.