Track + point line stops editor

In May the code was ready for track + point line stops, but the UI was not. This was added in early June:

It works as described in May: you can click on any point in any track to create a line stop, and then on the second click you choose the facing direction for the stop. The footprint of the line reference train is also displayed, so you can pick a position which fits the train. If you click in a station, the stop is setup as a pax stop with stop time. If you click outside of a station, it is setup as a waypoint with no stop time. As always you can change these defaults after creating the stop.

New track system?

The theme of both 1.7 and 1.8 was one of reviewing very old decisions in the game design and code, some of which dated back to the pre 1.1 prototype era, finding a better idea for them, and implementing it. 1.9 continues this trend by making pax capable of boarding (some) late trains and with multi node stations. But working on this last feature made me think of one of the final bosses of the game rewrite ideas: the tracks themselves.

At the most basic level, a track is a single point. This single point is the object the user can manipulate at will, and it is connected to one or two other points. That’s all. From this very simple structure the game then traces a track. Nearly four years old code which has only received bugfixes. Since it dates to the prototype era the original motivation for this code was “make it work and move on”. Back then I didn’t want to spend nearly an entire month researching and testing ways to trace railways tracks over a set of points, like I did during this month of June. But the game has matured, and some big features loom in the horizon, so its foundations need to be as solid as possible.

But what’s wrong with the original track system?

There’s nothing very wrong with the original track system (OTS from now). It works and it’s robust, within its limits. But the way it works and the price it pays to be robust directly result in some specific UX limitations which would be good to lift. Plus, from a development point of view, it is composed of very old code which is full of special cases and exceptions. For example, if I ever wanted to do pixel perfect drawing of curved tracks it would be a challenge.

The OTS is based on the idea that the track points determine the tangents of a circle. They are the P point in the power of a point theorem. OTS finds the largest possible circle it can fit in the corners formed by interpreting a sequence of track points as a polyline, then it finds the tangent points and draws circle arcs in between. Not all circles have the same radius, so it fills the gaps with straight segments which follow the common tangent lines. This results in a track trace exclusively composed of circle arcs and lines, which is 2/3 of the way civil engineering curves are designed (the missing 1/3 is using clothoids for the transitions between the other two).

I decided to devote most of June to experiment and try to find a new track system for the game, with a set of goals:

1. The node points should be part of the track, not an external point
2. It should be possible to add curvature to dead end tracks
3. (A consequence of 2) Branch tips should not force a straight section of track
4. Impact on existing saves is unavoidable, but at least try to make sure it’s around the same level of impact the Mercator fix had, or less
5. (Nice to have but not mandatory) No more piecewise construction. The curve should be G2 continuous and ideally possible to calculate in the GPU in the future, and also to have some way for arc-len evaluation for exact train movement (spoiler: the picked system is G2 continuous but the other stuff is not in game)
6. (Ideally but willing to compromise) Curves which both can approximate a clothoid and also produce reasonably circle arc-like curves without having to spam too many points

I listed it last, so it looks like it’s the least important, but the OTS is dear to be due to how super easy it is to create perfect circle arcs (even if then just glues it to a straight tangent segment). Splines are notorious for producing all kinds of curves which are very much not a circle unless the user puts specific effort into it. For point 6 I’m happy if the curve can do up to 90 degree circle-looking arcs with just two points.

Prototyping continuous splines

Suspecting it is easier to make a spline behave than to hit all the goals with piecewise construction (either by evolving the OTS or finding a new one), I decided to start my experiments with splines. More specifically, with splines whose curve passes on the points. Out of the bat I discarded the usual suspects: cubic Hermite and Catmull-Rom. These splines do not attempt to approximate a circle or a clothoid at all, rather being just a specific way to interpolate the start and ending input points. They lack the extra input required to, for example, independent control of tangents on the input points.

Circle spline? Maybe?

So I decided to try a radically different curve and implement something called the circle spline. This spline, which to be honest I only ever read descriptions about and never seen a piece of code implementing it, is based on the concept of the start and end points of the curve also being points belonging to a circle. So the input is two points, and each point has associated a circle center and a radius. The literature I found on this spline is like:

1. The description I just made
2. ???
3. Profit!

No code at all (admittedly I could have looked harder). So I made my own circle spline. I interpolate using slerp between the start and end circle, expressing the start and end points as angles in the circles. Then blend between the results to get the final point. I have no idea if my implementation is an actual circle spline or not, but it did look good to me. And as expected it absolutely aces approximating circle arcs:

The input circles are found by taking the circumcenter of the point and its two siblings. This spline produced very good results for wide angle curves like in the screenshot, but it was quite bad at inflection points and transitions into straight segments. Since most actual gameplay is small angle transitions I decided to keep looking.

Taming cubic Bézier splines: Raph Levien PhD thesis

Cubic Bézier splines are omnipresent due to combining being are very powerful and also very fast to compute. But directly manipulating them is not so nice. Anybody who has ever played with, or professionally used a vector drawing program, knows about how fiddly cubic Bézier splines are.

It’s not necessary to directly offer the user the full power of these splines if there is a UX/UI goal which makes them easier to use. Indeed these splines could be understood as a lower level primitive, like straight lines or arcs, rather than being the UI themselves. This is one of the reasonings in Raph Levien PhD thesis. Dr. Levien explores a collection of splines and curves, evaluating them for their ability of approximating a clothoid, which I’ve come to realize is kind of a holy grail in the subject of curve design.

In this vein Dr. Levien proposes using cubic Bézier splines whose control input points are found using a formula solving for a given set of tangents. Since Bézier control points are two set of 2 parameter (x, y), it is also possible to somehow encode the curvature in them, to approximate a straight-clothoid-circle transition. This approach is them complimented by a global optimization step which minimizes as much as possible the curvature of the whole curve.

The maths involved in this are way above my capabilities, plus the final global optimization step is a bad fit for the game, but I could use just the tangent-to-control-points formulas. These alone are a huge win over presenting just a tangent locked Bézier curve to the user.

For this experiment I used Dr. Levien newest formula from his github. The proposed tangents are just the average angle for the incoming and outgoing direction in each corner of the polyline.

Results were a mixed bag. While it can and does produce smooth results, it’s not very circular. It is also easy to trip with wider angles:

Wide angles like those are rare to use in-game, but they are allowed by the UI, and I would rather avoid glitching out. That being said it is very possible I made an error implementing the control point formula and it’s just my code. This is likely considering what happened afterwards.

Failing at the Hobby spline

Dr. Levien mentions another spline using a similar approach to his, namely using a formula which given tangent angles outputs control points for a cubic Bézier: the Hobby spline. It produces fantastic results as you can see from the linked blog post, so I implemented it following the formula in Dr. Levien thesis. Unfortunately I made a mistake with how I input the tangents into the formula, which I didn’t realize until two weeks later, long after I discarded it.

A false step: back to piecewise construction and Dubins path

My implementation of the Hobby control points was not working, and I decided to move on. Since I wasn’t having luck with splines, I decided to try again with piecewise construction. I was inspired by the Dubins path concept used in robotics to try to build piecewise legs out of arcs and segments again, like in the OTS, but this time from points belonging into the curve and with customizable tangents.

This was a failure, but thinking it was the only way, and that splines were not going to work and/or I was too dumb to use them, I kept pushing. The issue is that finding the correct arcs for piecewise construction is very hard. It’s a problem of finding the right radius, and then it’s full of tricky corner cases. I managed to get it working (for some definition of working) for half of the cases, but the other half needed a completely different algorithm. I did not keep any screenshots from this, I was too frustrated.

In order to fill the half of the cases not working, and not knowing what to do, I enabled again the spline traced, but just for the cases the piecewise constructor was unable to handle. It worked… fine? And it looked… very good? Then I realized something: the spline code I just uncommented was using the Hobby control points! It turns out that in my two week meandering into piecewise construction I managed to fix my tangents, and imputing them into the Hobby formula now made it just work, no more fixes needed.

The revenge of the Hobby spline

I immediately trashed the piecewise code and enabled the Hobby spline for all cases. And it worked just fine, and it looked glorious:

Dear reader, I don’t know how familiar you are with computer curve design, but that previous screenshot is, if you allow me, amazing looking. And this is the kicker: guess how many nodes are required?

You just click and the formula does its damndest hard to find a way to draw something as circular as possible, and then to blend it smoothly.

New track system!

In 1.9 the OTS has been replaced with this new track tracing system. It achieves all the goals I set forth:

1. Track nodes are always part of the track
2. It allows manual control of the node tangent by the user, so curvature can be added to dead end tracks
3. Branches inherit their parent tangent without needing to be half a straight segment
4. There is some impact on existing saves but it’s not too bad, in my opinion
5. No more piecewise construction, which could enable exact curve tracing in the future
6. Dr. Levien discusses how the Hobby spline approximates a clothoid at small angles, and by my visual verification (so no maths used to be fair), my code appears to achieve it

To elaborate on some points:

Manual control of the node tangent by the user

The default tangents give good results in general, but when you are doing direction changes in the middle of a curve, of transitions from straight to curve, it might be a good idea to manually edit the tangent of the track point:

This new control is also available at dead end tracks, so you can finish them at any curve you want.

Impact on existing saves

1.9 features an importer for old saves. Thanks to how good Hobby splines are at approximating circles it’s a simple one but it produces reasonable results:

No new track nodes are inserted. Everything is accomplished by just moving the existing track points a little. The small flaws can usually be fixed by retouching some tangents, so at least for 1.9 I am enabling the tangent control for built tracks, to make this process easier on old saves.

Of course, even if tracks are not too affected, all the subtle curvature changes affect track speeds, so line timings are changing again in 1.9. As I mentioned in the past, just assume line timings will change in every version until the game is out of Early Access.

Clothoids

An image is easier to understand than any words I could write (right image is from Track transition curve):

If you told me just a couple months ago that this game would get clothoid drawing from just two points, belonging to the track, I wouldn’t believe it.