There are several building games that are offering non-grid building, including the upcoming SimCity 5. Although I love grids[1], I’m also happy to see these non-grid building games.
What would I do if I needed to draw curved roads in a game? I’d use Bezier curves and splines[2]. 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:
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. There are also side problems like representing lots, and subdividing lots[3], where Bezier curves aren’t great. 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[4], who suggested I look at circular arcs; Steffen Itterhelm’s blog post[5] also suggested arcs; and this thread on StackExchange[6] also suggests using arcs. The more I played with arcs, the better they looked to me.
Properties#
Consider a road segment:
What do we need to draw and use roads in a game?
- 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.
- 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.
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.
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[7]. 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:
Offsets#
It turns out the offset of a Bezier curve is not itself a Bezier curve[8]. If you offset the end and control points, you end up with a road that’s not constant width; it won’t look right[9]. 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:
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[10] but they’re not as simple.
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:
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:
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:
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.
Notice that the symmetry of the arc adds to its pleasing shape, but it also constrains 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 a change in radius, resulting in another circular arc.
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[11] (1/radius) or signed curvature[12] 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)
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[13]. 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:
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[14] uses them. Are there other building games that use circular arcs?
It’s not just games. Apple Maps and Google Maps use line segments, whereas the Transit app[15] uses 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[16].
Also see the discussion on reddit/r/gamedev[17]; 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[18], which have G0 continuity.
- We can connect Bezier curves together into Bezier splines[19]. With cubic Beziers we can get G2 continuity[20].
- 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[21].
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:
- The Beauty of Bezier Curves[22], a great video from Freya Holmer
- Math for Bezier curves[23]
- Bezier curves from Paul Bourke[24]
- Bezier curves[25] reference, with interactive diagrams, and a javascript library for working with Bezier curves[26] (including distance and offset approximations).
- This article[27] shows how to construct an approximate offset curve and also has a browser demo. (2015)
- Raph Levien’s blog post[28] about how to convert a quadratic Bezier curve into line segments without using recursive subdivision. (2019)
- Also from Raph Levien, how to compute Parallel curves for cubic Beziers[29], where he presents a fast, accurate, and numerically robust way to compute offset curves. (2022)
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:
- Biarc interpolation for games[30] - highly recommended if you are going to implement biarcs. This article goes into a lot more detail than my page.
- Optimal Single Biarc Fitting and its Applications [PDF][31] (by Park) explains how to represent and use biarcs, and also goes into curve-fitting, which could be useful for designing a UI for road building. However I didn’t explore curve fitting, and probably won’t unless I actually use these ideas for a game.
- Planar Biarc Curves - a Geometric View [PDF][32] (by Chandrupatla and Osler) was helpful for me to understand more about the geometry of biarcs and how to find the circle of valid control points.
- Approximating Curves and Their Offsets using Biarcs and Pythagorean Hodograph Quintics[33] (by Sir, Feichtinger, Juttler) helped me understand how to represent biarcs, how to calculate and use the circle of valid control points, and also helped correct a misunderstanding I had — a misunderstanding that had led me astray when writing my code. It also goes into curve fitting, which could be useful but something I didn’t explore.
- On the geometry of piecewise circular curves [PDF][34] (by Giblin) has an overview piecewise circular curves but I didn’t use much from this paper.
- The use of Piecewise Circular Curves in Geometric Modeling[35] (by Khudayarov) (mirror on scribd[36]) had some very helpful explanations of how to represent curves, as well as biarc math.
- [2019] Oleksandr Kaleniuk[37] explores picking biarcs or line-and-arc based on the tangents. This avoids the bad biarc cases and also the bad line-and-arc cases. Demonstrated with interactive diagrams!
- Jacob Rus’s notebook[38] shows how to interpolate along a circular arc defined by the endpoints and a midpoint.
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!).
Cities in Motion (Cities Skylines) and Transport Fever 2 both have very impressive intersection handling. I don’t know how they do it. A-B-Street[39] and Citybound[40] are also worth a look.
In the real world
In real life, roads and railroad tracks use circular arcs[41], 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[42]. (Clothoids are also called “Euler spirals[43]” 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
Kevin Yin demonstrates some problems with Bezier curves[44] and proposes a set of properties he wants for curves, such as having direct control over curvature, but also says that no curve can satisfy all of the desired properties. I recommend trying the first two interactive diagrams to get a feel for the problem.
Elliptical arcs give you more flexibility than circular arcs, and are supported by many graphics libraries. However, Paul Bourke[45] 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[46] 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[47] 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.
Dubins paths[48] put a straight line segment in between two circular arcs.
Clothoid curves[49] act as transitions between circular arcs, to provide G2 continuity. Here are two great resources for clothoid curves:
- Raph Levien’s thesis[50] covers clothoid curves (Euler spirals) and properties of splines that you might want in your application.
- Sketching Piecewise Clothoid Curves[51] (by McCrae and Singh) is about clothoid curves in road design for games, including curve fitting, and also includes a video showing a UI in which players can draw a curved line and the system will figure out how to turn it into a piecewise circular curve, then render a road. Be sure to watch the video! I didn’t play with any of this on this page; I focused on circular arcs, not clothoids, and I haven’t explored the UI aspects. They also include a Windows demo and source code.
- Citybound[52] (a city-building game) also has a video showing a UI for building curved roads.
Hobby Curves[53] are a way to generate pleasant looking Bezier control points to form a spline that goes through all the input points.
AbouBenAdhem[54] on Reddit suggests computing offsets of Bezier curves using Hermite curves[55], as they’d take far fewer segments than a piecewise linear approximation. I’ve also gotten a suggestion to look at trigonometric splines[56].
Freya Holmer’s talk about geometry[57] shows that geometric algebra can be used to get a cleaner calculation of radius of curvature[58]. When I wrote this page back in 2013, it got me to look at geometric algebra, but I didn’t try implementing the curved paths with it.