Feb 2013

There are several building games that are offering non-grid building, including the upcoming SimCity 5. Although I love grids, I’m also happy to see these non-grid building games.

Cities in Motion

What would I do if I needed to draw curved roads in a game? I’d use Bezier curves and splines. They’re the standard solution for curves. The math is straightforward. They’re rather flexible. But they have some disadvantages, and you should also consider circular arcs as a primitive. Here’s a comparison:

Arc vs Bezier curvesBezierArc

Why circular arcs? When using bezier curves and splines for road drawing, you usually have to turn the spline into a series of short line segments. This is fine in practice but also unsatisfying, and can lead to visual artifacts in some games. I had wondered if there was something else I could use instead. After trying some things out, I mentioned this problem to my friend Dominic, who suggested I look at circular arcs; Steffen Itterhelm’s blog post also suggested arcs; and this thread on StackExchange also suggests using arcs. The more I played with arcs, the better they looked to me.

#Properties

Consider a road segment:

Line segment

What do we need to draw and use roads in a game?

  1. Offsets. Given an offset and the center of the road, we need to be able to draw a path at a given offset away from the road. Why?
    • The left and right edges of the road are offsets.
    • The lane markers in a multilane road are offsets.
    • The boundary between the road and the regions adjacent to the road are offsets. Games such as SimCity and Cities XL divide these regions into “lots” where houses, factories, stores, etc. are placed.
    • Intersections between roads are calculated with offsets.
  2. Distances. Given a position on a road segment, we need to figure out how far along the road it is. Given a distance along the road, we need to figure out the position. Why?
    • Converting positions to distances lets us calculate the lengths of road segments, which are used for pathfinding and movement.
    • To animate a vehicle along a road, we need to convert distances to positions.
    • It may also be useful to convert mouse clicks to distances.

#Building block: line segments

Let’s start with simple road sections between two points. The simplest connection is a line segment.

Offsets

To offset a line, calculate the normal  N = rotateLeft(normalize(P2 - P1)), multiply by the offset amount, and add that vector to the endpoints.

Line segment, offsetsN

Notice that the offset can be negative to go in the other direction. The offsets allow us to draw the road edges and stripes. With curved paths, we’ll want to offset using a normal from every point along the path.

Distances

To convert a distance into a position (interpolation), calculate the tangent  T = normalize(P2 - P1), multiply by the distance, and add that vector to the first endpoint.

Line segment, offsetsT

This allows us to move a vehicle along a road. It will be more complicated for curved paths.

To convert a position to a distance (measurement), we follow the steps in reverse: subtract the first endpoint, then take the dot product with the tangent T.

We can get the total length of the road by converting the second endpoint to a distance, length = (P2 - P1) ⋅ T. Note that this simplifies to ‖P2 - P1‖, because T = normalize(P2 - P1) = (P2 - P1) / ‖P2 - P1‖, and (P2 - P1) ⋅ (P2 - P1) = ‖P2 - P1‖².

#Building block: bezier curves

The first thing I think of when I want to draw a curved road is a Bezier curve. In addition to the two endpoints of the curve, a Bezier curve has additional “control points” that control the shape. The two most common forms are quadratic, with one control point, and cubic, with two control points. Here’s a road drawn along a quadratic Bezier curve. Move the endpoints and control point around to see how it works:

Bezier road segment(length)

Offsets

It turns out the offset of a Bezier curve is not itself a Bezier curve. If you offset the end and control points, you end up with a road that’s not constant width; it won’t look right. Or if you try to keep constant width, and the left/right sides of the road aren’t Bezier curves, or any easily describable curve. A workaround is to turn your curve into a series of short line segments, then calculate the offsets from each of them. This diagram moves the control points without using the workaround, and you can see it doesn’t quite have a constant width:

Bezier offsetsN

Distances

It turns out the length of a Bezier curve is not exactly computable. A workaround is to use an approximation, or to turn the curve into a series of short line segments.

It also turns out the interpolations aren’t exactly computable. The same workaround, turning the curve into short line segments, can also be used for interpolations. There are also other approaches but they’re not as simple.

Bezier distancesT

Workaround: a series of lines

Although Bezier curves are common, supported in lots of graphics libraries, and easy to use, they don’t have nice properties for road drawing. For offsets, distances, and interpolations, you can use a series of line segments to approximate the curve, and get the properties that aren’t computable exactly with Bezier curves.

How many line segments do you need? There’s a tradeoff here. Using fewer but longer line segments makes the approximation visible to the player, but polygons for adjacent regions will be simpler, and that will make intersection and other calculations faster. Cities XL and SimCity 5 support regions adjacent to roads (for farms and buildings), and both of these games use longer line segments. Here’s a screenshot from Cities XL:

Cities XL

If you tell players that they can build “curved roads”, a series of short straight roads is probably not what they expect to get. If you make the segment short enough though, most players won’t care. I don’t yet have a screenshot from SimCity 5 but from previews it looks like their roads are a bit smoother than the ones in Cities XL. The shorter the segments, the more curved the roads will look. However, if you need to perform calculations on regions and intersections, those calculations will likely be slower. Tropico 3 and 4 roads look much more curved than those in Cities XL or SimCity 5. Here’s a screenshot from Tropico 4:

Tropico 4

Cities in Motion 2 has beautiful roads. I’m not yet sure if they use Bezier curves or circular arcs. If they use Bezier curves they must create lots of line segments so that players can’t tell. Whatever they’re doing, it looks incredibly good. Click through for the full size:

Cities in Motion 2

#Building block: circular arcs

An alternative to quadratic Bezier curves is circular arcs. Neither is a superset of the other — Bezier curves cannot produce circular arcs and circular arcs cannot produce Bezier curves.

Circular arc segment(length)

Notice that the symmetry of the arc adds to its pleasing shape, but it also constraints the control point. The main reason to consider circular arcs is that they don’t require the “series of line segments” workaround of Bezier curves. Note that you still have to convert them to polygons to render them on a GPU, but you can reason about them in their native form.

Offsets

To form an offset curve, at every point we add the offset multiplied by the normal N. With a circular arc, the normal is the radius vector, so the offset curve is simply a change in radius, resulting in another circular arc.

Arc offsetsN

One tricky thing we need to deal with is very large radii. A straight line is an arc with infinite radius; zero radius is something you’d never want. But we would like to perform operations like adding or subtracting from the radius, and with large radii, we might have issues with numerical precision. One idea would be to use curvature (1/radius) or signed curvature instead of radius. A straight line can be represented as a circular arc with zero curvature; infinite curvature is something you’d never want. Another option would be to detect large radii and switch to line segments.

Distances

The length of a circular arc is derived from the length of the circle. It’s the radius multiplied by the angle of the span (in radians).

To interpolate along a circular arc we convert the position to an angle (divide by the radius), interpolate angles, and then convert back to position (multiply by the radius)

Arc distancesT

Here too we can have problems with an infinite radius, because we’re dividing by the radius and then multiplying by the radius. Is there a better representation that avoids these issues? I don’t know.

#Biarcs: two arcs glued together

A downside of arcs is that they aren’t as flexible as Bezier curves, especially cubic Beziers. One way to increase the flexibility of arcs is to join two of them together into a biarc. Constructing a biarc requires two endpoints and their tangents, but it also has one additional degree of freedom.

A key question for biarcs is where to join the two arcs. We want a point where the tangents of the two arcs will match. The places where they match all lie on a circle. In this diagram, move the endpoints and tangents, then move the control point to somewhere on the colored circle:

Arc connection

Notice that control points not on the colored circle lead to the two arcs not connecting smoothly. Also look at the colors on the circle: they show how long the resulting biarc will be. Shorter biarcs are usually better but you also want to take into account curvature and connectivity with adjacent roads.

The biarc UI above demonstrates how biarcs work but it’s not a great UI for players to build roads. A better UI would constrain the control point to lie on the circle, or automatically choose a control point based on some heuristics. In the biarc literature there’s no one best heuristic that everyone agrees on, so you might want to try several and see which is best for your game. Also, my guess is that you wouldn’t even want to give players a control over the tangents. You can easily choose tangents that lead to gigantic arcs. In a game it’s likely you’re connecting the road to an existing road, so the tangent is already determined.

#Conclusions

The default choice for curved paths is Bezier curves/splines. It’s a reasonable choice. They’re well understood and easy to work with. However, you need to convert them to piecewise linear curves to work with them. Cities XL, Tropico 4, and SimCity 5 all use Bezier curves.

For roads and railroad tracks though, I think circular arcs are an interesting alternative. They have some nice properties when it comes to representation and simulation, with a possible issue with very large radii. Railroad Tycoon 3 and Sid Meier’s Railroads use them. Racing games use them. I think Train Fever uses them. Are there other building games that use circular arcs?

Does it really matter which you use? Most players probably won’t care. Some will though. When I played Cities XL I was greatly annoyed by the roads not being curved, and the buildings not fitting into the spaces left by the weirdly shaped roads. I do think arcs are worth considering.

For my own games, I think I will stick with grids.

Also see the discussion on reddit/r/gamedev; there are lots of good comments and alternative approaches there.

Further reading

Connecting primitives together

It’s fine to look at the primitives in isolation but in a game you’ll want to chain them together into road networks.

  • We can connect line segments together into piecewise linear curves, which have G0 continuity.
  • We can connect Bezier curves together into Bezier splines. With cubic Beziers we can get G2  continuity.
  • We can connect circular arcs into piecewise circular curves, which have G1 continuity.

I made a demo that produced piecewise circular curves by chaining together biarcs, but I’m not quite happy with the UI. I picked the control points automatically; it may be better to allow the player to choose them.

Also watch a video of the track building UI in A-Train 9.

Biarc chain

In practice, we have to convert Bezier curves into piecewise linear curves. This produces polygons, which are well understood and easy to work with. I found these pages to be useful for learning about Bezier curves:

Piecewise circular curves are used in manufacturing, robotics, and highway engineering, but I haven’t found many online references for them. As with circular arcs, piecewise circular curves can handle offsets, distances, and interpolation. Here are some papers I used to learn about circular arcs, biarcs, and piecewise circular curves:

Intersections

How can we calculate intersections? I believe we can intersect the left/right offset curves of two roads to find four points for a quadrilateral. For Bezier curves we’d need to convert to a piecewise linear form; for circular arcs we can calculate the intersections directly. However I haven’t tried implementing intersections for curved roads, and there are probably many corner cases to work out (no pun intended!).

In the real world

In real life, roads and railroad tracks use circular arcs, not Bezier curves. However arcs are not G2 continuous. This means you have to abruptly shift your steering wheel when transitioning from a straight segment to a curved segment. To solve this, they use clothoid connectors. (Clothoids are also called “Euler spirals” or “Cornu spirals”.) However, clothoids have complicated distances/interpolations and unlikely to have clean offset curves. They might be useful in racing games but I wouldn’t use them in a city-building game. (See the next section for some references.)

Other curves

Elliptical arcs give you more flexibility than circular arcs, and are supported by many graphics libraries. However, Paul Bourke says elliptical arcs don’t have closed form lengths, and I think they aren’t closed on offsetting either. This gives them the same disadvantages as Bezier curves.

Rational Bezier Curves add weights to the control points. This allows them to represent circular arcs and other paths that regular Bezier curves can’t. However, these aren’t widely supported in graphics libraries, and still don’t have all the nice properties we want.

Catmull-Rom splines produce paths that go through all the points, unlike Bezier curves which go through only the endpoints. However, I’m fairly certain (not 100% sure!) that Catmull-Rom splines do not have the nice properties we want — they likely have the same disadvantages as Bezier curves.

Clothoid curves act as transitions between circular arcs, to provide G2 continuity. Here are two great resources for clothoid curves:

AbouBenAdhem on Reddit suggests computing offsets of Bezier curves using Hermite curves, as they’d take far fewer segments than a piecewise linear approximation.

Geometric Algebra

For a few weeks I got distracted by geometric algebra, which seemed like it might be a nice way to represent lines and curves. There are a lot of cool ideas in there, and it explained things that really bothered me about the usual vector representation in 3D graphics. However, I didn’t learn enough of it to be able to say whether I could use it in my 2D setting. I should’ve probably tried implementing circular arcs with geometric algebra; that would’ve made me learn it faster.