Road representation

Playing Transport Tycoon, I've recently been setting up multimodal
transport, where a bus will transport passengers from the bus stop in
the middle of town to the train station outside of town (because once
the towns in Transport Tycoon get big, it's hard to buy up enough land
to build a train station or airport). The trains then take people to
the nearby airport, which is even farther away from town for noise and
space reasons. It would be fun to design those airports
yourself,
but Transport Tycoon gives you only a few rectangular predesigned
airports.

The real trouble with playing Transport Tycoon is that it makes me
want to write a transportation
game. I'm
too busy to work on a full game right now, but I want to experiment
with small pieces of games. I thought it'd be fun to design container
ports that mix truck, train, and ship traffic. While trying to break
that down into smaller problems, I decided to work on roads:
representing them, simulating vehicle movement, and drawing
them. Someone asked me: why use grids? I
love grids. I think a lot about
grids. Even
when I used splines for
roads,
the endpoints were on grid edges. I recently updated my A* pages
about non-grid
maps,
and it seems like this project would be a good fit for a non-grid representation.

As I mentioned in the last
post,
I'm trying things quickly and am happy to throw them away if they
don't work out. I'm now on the fourth design, which uses a two-level
graph structure. The first graph is used by the player to edit
the world. You'll place nodes and then connect them with edges. The
second graph is used by pathfinding for vehicles to move along
lanes. Each connection point generates one node per
lane. Intersections export edges corresponding to all the ways a truck
can go straight or turn, and roads export edges for going straight and
for changing lanes. The rough plan is to have three kinds of objects:

1. “Anchor” objects like intersections and truck stops export connection points. The anchors act like nodes in the first graph and generate edges in the second graph. For example, a 4-way intersection will export 4 connection points.
   

   
   
   




2. Connection points have a position, orientation, and lane configuration. They don't show up in the first graph but generate nodes in the second graph. The lane configuration is the number of lanes in each direction. For example, a connection point might specify 2 lanes going one way and 1 lane going the other way.
   

   
   
   




3. Roads are attached to existing connection points and can follow a spline curve. Roads do not export their own connection points, but only can attach to anchor objects. They act as edges in the first graph and generate edges in the second graph.
   

   
   
   

Unlike the previous three designs, in which I quickly ran into trouble, this design has held up for a few weeks, so that's a good sign. The subproblems are:

1. How do I represent connection points? I decided to keep the position, orientation, and the number of lanes going into and coming out of the anchor object. It's a very simple struct and it'll be easy to change.
   

   
   
   




2. How do I represent intersections? I've limited myself to 4-way straight intersections (90 degree turns). Each side can have its own in/out lane configuration.
   

   
   
   




3. How do I draw intersections? For roads, there's a double yellow line in the center, a dashed white line between lanes going the same direction, and a solid white line on the side. There's a stop line where vehicles come to a stop. If there are right-only and left-only turn lanes, then there will be solid white lines separating those (not implemented yet). There may be arrows drawn to show which ways a vehicle can turn (not implemented yet). The size of the intersection itself is a rectangle as small as possible (not implemented yet).
   

   
   

   
   (Try the demo!)

   
   
   
   
   




4. How do I represent roads? I'd normally say cubic splines. However, since Flash supports drawing quadratic Bezier curves, it'd be nice if I could draw the roads using Flash instead of implementing my own curve rendering, so I'm going to use a spline with quadratic Beziers. There are ways to approximate cubics with quadratics but I'll see how far I get with quadratics alone. The lane configuration at the ends of the roads is determine by the anchor points, and the road handles the change in configuration. It might even be useful to have a lane configuration at each spline handle.
   

   
   
   




5. How do I draw roads? The roads again have the same yellow and white stripes as in intersections. However, this is where I ran into some trouble. I want the lane stripes to be parallel. This is done by taking the original curve and constructing an “offset curve”. Unfortunately, offsets of Bezier curves are not Bezier!
   

   
   

   This could be a major problem. The more I dug into this problem, the more papers I found. It turns out that it affects various industries use Bezier curves (not only quadratic) for representing curves, and they use approximations for offset curves. I found papers mentioning circular arcs, Pythagorean hodograph curves, Hausdorff distance, and a few other things, but in the end I decided that what mattered was not whether the curve is exactly correct but whether it looks reasonable.
   

   
   

   

   
   
   
   

   I drew the Bezier curve and the constructed somewhat-parallel Bezier curves, and it turns out it looks okay at low curvatures but not high curvatures:
   

   
   

   
   (Try this demo.)

   
   
   
   

   I think it'll be reasonable to restrict the curvature of the road, and then I can use Flash for drawing the roads and lane markers. A new problem arose: although Flash 10 allows bitmap line drawing (this is how I draw the “dashed” lane divider lines), the bitmap orientation is fixed and does not curve as the line does. I'm not yet sure how much of a problem this will be.
   

   
   
   




6. How do I move along roads? With Bezier curves, the movement isn't uniform; I need to adjust for arc length. Most likely I'll turn each lane path into a series of points, and then move linearly between them. If that doesn't look good then I'll try something else.
   

   
   

   One thing I'm considering is using circular arcs instead of Bezier curves. Arcs are fairly easy to understand and have simple movement. Offset curves from circular arcs are also arcs. Also, arcs are commonly used in real roads. Arcs can be approximated with Bezier curves.
   

   
   
   




7. How do I handle collisions? Open Transport Tycoon's “path based signals” have vehicles reserve the path ahead of them. Grids make this easier because you can reserve grid spaces (although OTTD is a little smarter than this and can allocate half-grids). Without grids, I could either precompute all intersecting road segments and mark them all occupied whenever one of them is reserved, or I could use polygon intersection to watch for vehicles colliding. The first approach uses planning; the second is purely reactive. I think a reactive system would lead to traffic jams.
   

   
   
   

Road representation turns out to be a fun problem. As the code stabilizes, I'm pushing it out to github and I'll put demos into the wiki. It's all under the MIT license so feel free to use it for anything. My next step is to determine how the roads and anchors connect to each other. That problem may help me decide on Bezier curves vs. arcs.