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:
“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.
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.
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:
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.
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.
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!)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.
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.
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.
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.
Labels: project
Nice project, I dream of working on a vehicle-simulation on my own. And the first problem I've found was the movement of the cars on splines. But after searching the net I've found a neat solution to the problem: you sample the spline and generate a polynom for uniform movement... the idea is not from me, but you can find my code here: http://www.unseen-academy.de/timeconstSpline.html
Thanks Anonymous! Yes, that's along the lines I was thinking. However, circular arcs are even simpler because there's a direct mapping from the length to the curve position. I'm going to experiment a bit before deciding which approach to use.
This is quite cool, and along the lines of a project I've been working on too. I'm using bezier curves to draw railroad graphics. It's possible to construct offsets using vectors and the normal to the curve (which is generated as a side effect of drawing the curve, by taking the tangent at each point generated). This can give you very nice approximations of a parallel bezier curve. By iterating over the length of the curve (calculated as a series of vectors) you can draw things at regular interval, e.g. railway ties or road markings.
Here's a quick screenshot, it can also draw free-form bezier curves (and I'm planning on producing an engine built around these, I think it'd be possible to make an entirely free-form track drawing system by combining functions to split/join bezier curves, the tile-based approach is also quite interesting and the basis of this demo).
http://entropy.me.uk/pytile/bezier_demo.png
There are a couple of old demos up there too.
Let me know if you'd like to take a look at the source code, or drop me an email: tb[at]entropy{dot}me(dot)uk.
Thanks Timothy — that looks neat!
If I were generating points for Bezier curves, then generating their offsets would be easy. What I'm hoping to do is use Flash's curveTo() library routine to draw the Bezier curve, but the downside is that I won't get the points or normals back. So instead I'm trying to construct a Bezier curve that's approximately parallel to the original.
I just realized I can't generate proper railway ties if I use Flash's library routine. Even with the road markings, it might be tricky. So I may end up having to draw the curve myself.
The more I look at circular arcs, the more appealing they get. The next step for me is to create a road editor (somewhat like the demo here: http://wiki.github.com/amitp/containerport). Figuring out the continuity constraints on adjacent Bezier curves (or circular arcs) may help me decide on the representation.
Circular arcs seem much more predictable, but of course some experiments are needed :)
About the continuity constraints: you can fit a circle perfectly to 3 points (see link at end). If your only constraints are the endpoints of the arc, you have one additional degree of freedom that controls the circle's radius (a free variable). But if you want to control the arc's slope at the endpoints, you're over-constraining your circle - in most conditions it's impossible!
However, you can set both endpoints and the slope at *one* end, and get a perfect fit. IMO this would be acceptable for road-building; you always start by placing the road at one end, and that previous piece of road constrains the slope of the next piece.
I was going to try to figure out the formula, but then realized that it's much easier to use one of the existing formulas for 3 points fitting, with 2 of them being the desired endpoints and the 3rd inducing the desired slope - by placing it right in front of one of the endpoints, in the direction of the slope. (ie, if one endpoint is A and the direction/slope is D, the 3rd point C is A+D*delta, where delta is a small scalar.)
A picture is worth a thousand works and with geometry this is even more true, so if there's any interest I'll try to illustrate what I mean with an image...
(see formula 2) http://www.geocities.com/kiranisingh/center.html
Yes, with arcs I'm overconstrained. However, if the basic component is a straight line next to an arc, then it works out pretty well, I think. The change in angle between start and end points determines the arc angle, and the remaining slop goes into the straight line. I'll make some diagrams once I work out the math.
The other nice thing about arc+line is that all components have the same form; I don't need the player to choose between lines and arcs. However, some configurations are impossible so that part is not so nice.
I assumed alternating lines and arcs but got carried away and forgot to mention it! Anyway, I hope I'm not taking any of the fun from you - but I figured out the geometry, which is really simple in retrospect! 3-points fitting is not necessary. The circle's center is given by the intersection (V) of the two dashed lines here:
http://img191.imageshack.us/img191/2901/arcfit.png
The segment A to B is the existing straight road. C is the new point that the user is selecting, and the relevant arc of that circle is the fitted arc. I tried not to botch up the image but I hope you can see it works pretty well, as the arc continues from the previous segment seamlessly. M is the midpoint between B and C. The dashed lines are simply the existing lines (A-B and B-C) rotated 90ยบ. Their intersection yields V, the circle's center, and its distance to either B or C yields the radius. So if you have some line intersection code available, you can easily get playable results just by shifting some vectors around :)
Jotaf, thanks! That's a good diagram. I've come up with a different approach but haven't worked out the details. The basic idea is to make straight lines between the control points and insert very small circular arcs as “turns”. The remaining control will be to make the small arc into a larger one, “consuming” parts of the straight line. I'll put up a diagram once I make one.
Jotaf, here's a diagram of what I've been thinking about. The player would draw lines between points, which will create a joint (purple shaded area) and then drag another control to change the radius of the curve. For example, if you drag along the dashed line, you'd end up with the green shaded area.
Ah, I see! Much more intuitive from a UI perspective, I like it better. So the center of the circle must lie within the dashed line in the middle. For any of the possible centers the distance to both of the original lines must be the same, so there's a definition to work with... Haven't really given much thought to it, but fun stuff :)
Here's a demo. The road on the left uses Bezier curves; the road on the right uses circular arcs. I'll eventually add a drag handle on the road itself to control the arc size but for now you can use the slider above the road.
Really cool. I agree with what you wrote about the handles. Are you gonna use the Bezier approximation in the final version or are you planning on changing it? A cheap way out of it would be to disallow sharp angles. I think this warrants a proper blog post don't you? :)
I'll still use the Bezier approximation, but it's very easy to break up a circular arc into small segments, so I won't have to burden the player with a restriction on angles.
Yes, there will be a blog post once I have more of this worked out :)
I just discovered that Cities XL will have curved roads too. Neat! Here's a video.
Post a Comment