Space Filling Curves in Simulated Cities

I’ve been playing around with Cities: Skylines recently, the super-popular SimCity knock-off.  Dealing with traffic is a core theme of the game (as it should be).  Traffic tends to accumulate at intersections, and it’s well known that one-way streets have higher traffic flow.  The logical conclusion, then, is to try to build a city with a single extremely long one-way street…  Unfortunately we have to compromise on this perfect vision, because people want to get back home after work and so on.

hilbertville4
Hilbertville: The space-filling city.

A Quick Intro to Space Filling Curves

Meanwhile, a space-filling curve is an mathematical invention of the 19th century, and one of the earlier examples of a fractal.  The basic idea is to define a path that passes through every point of a square, while also being continuous.  This is accomplished by defining a sequence of increasingly twisty paths (H1, H2, H3, …) in such a way that H∞ is well-defined and continuous.  Of course, we don’t want a infinitely twisty road, but the model of the space filling curve will still be useful to us.

There are a few important ideas in the space filling curve.  The first is a notion that by getting certain properties right in the sequence of curves H1, H2, H3, …, we’ll be able to carry those properties on to the limit curve H∞.

moore-curve-stages-0-through-5
The Moore curve is an example of a (continuous!) space-filling curve.  The color changes keep track of time as you move along the path; notice that in the very twisty sixth path, a small change in time still keeps you in the same (blocky) neighborhood.

The second main idea is how to get continuity.  Thinking of the curve as a function where you’re at the start at time 0 , and you always get to the end at time 1, we want an H∞ where small changes in time produce small changes in position.  The tricky part here is that the path itself gets longer and longer as we try to fill the square, potentially making continuity hard to satisfy…  When the length of the path doubles, you’re moving twice as fast.

In fact, because of continuity, you can also “go backwards:” Given a point in the square, you can approximate what time you would have passed through the point on the limit curve H∞, with arbitrary precision.  This gives direct proof that the curve actually covers the whole square.

Here’s an example of a space filling curve which is not continuous. Define Bk as the curve you get from following these instructions:

  1. Start in the lower-left corner.
  2. Go to the top of the square, and then move right by 1/k.
  3. Move to the bottom of the square, and move right by 1/k.
  4. Repeat steps 2 and 3 until you get to the right side of the square.

The problem here is that a very small change in time might take us all the way from the top of the square to the bottom of the square.  We need to be twistier to make sure that we don’t jump around in the square.  The Moore curve, illustrated above, does his nicely: small changes in time (color) don’t move you from one side of the square to the other.

Actual Simulated Cities

What happens if we try to use space filling curves to build a city in Cities: Skylines?

My first attempt at building ‘Hilbertville’ was to make large blocks, with a single, winding one-way road for access, using the design of a (second-order) Hilbert Curve.  In addition to the roads, though, I placed a number of pedestrian walkways, which allow people on foot to get in and out of these neighborhoods directly.  I like to think that this strongly encourages pedestrian transit, though it’s hard to tell what people’s actual overall commuting choices are from the in-game statistics.

hilbertville2
Hilbertville, two blocks. The lower view highlights where the roads are, and are color-coded for the amount of congestion along each segment of roadway. There’s a bit of congestion at the output of each block, as cars wait at the intersections.

Skylines only allows building directly facing a road; corners tend to lead to empty space.  You can see a large empty square in the middle of the two blocks pictured above.  There are also two smaller rectangles and two small empty squares inside of each of these two blocks.  Making the top ‘loop’ a little bit longer removed most of the internal empty space.  This internal space is bad from the game perspective; ideally we would still be able to put a park in the empty spaces to allow people to extra space, but even parks require road access.

Intersections with the main connecting roads end up as ‘sinks’ for all of the traffic congestion.  So we should try to reduce the number of such intersections…  The Moore curve is a slight variation on the Hilbert curve which puts the ‘start’ and ‘finish’ of the path next to one another.  If we merge the start and finish into a wide two-way road, we get this:

hilbertville3
A space-filling road based on the Moore curve.

We still get the wasted square between neighborhoods, but somewhat reduce the amount of empty interior space.  Potentially, we could develop a slightly different pattern and alternate between blocks to eliminate the lost space between blocks.  Also, because the entrance and exit to the block coincide, we get to halve the number of intersections with the main road, which is a big win for traffic congestion.

Here’s a view of the full city; it’s still not super big, with a population of about 25k.  We still get pretty heavy congestion on the main ring road, though the congestion is much less bad than in some earlier cities I built.  In particular, the industrial areas (with lots of truck traffic) do much better with these long and twisty one-way streets.

hilbertville4
Full view of Hilbertville, population 25k. There are fourteen blocks here; note the two Moore curve blocks at the bottom, and the slightly modified Hilbert curve block in the lower left, which reduces empty space at the expense of a slightly longer road.

The empty space is actually caused by all of the turns in the road; fewer corners implies fewer wasted patches of land.  The easiest way to deal with this is to just use a ‘back-and-forth’ one-way road, without all of the fancy twists.

The other major issue with this style of road design is access to services.  Fire trucks in particular have a long way to go to get to the end of a block; the ‘fire danger’ indicators seem to think this is a bad idea.  I’m not sure if it’s actually a problem, though, as the amount of traffic within a block is next to none, allowing pretty quick emergency response in spite of the distance.

Overall, I would say it’s a mixed success.  There’s not a strong reason to favor the twisty space-filling curves over simpler back-and-forth one-way streets, and in either case the access for fire and trash trucks seems to be an issue.  The twistiness of the space-filling curve is mainly used for getting the right amount of locality to ensure continuity in the limit curve; this doesn’t serve a clear purpose in the design of cities, though, and the many turns end up creating difficult-to-access corner spaces.  On the bright side, though, traffic is reduced and pedestrian transit is strongly encouraged by the design of the city.

Advertisements