## Saturday, 2 November 2013

### Car tracks

After tracks, the next step is obviously to have some cars on them, carrying paying guests of course!
In the real world, you just put the car on the track, and it will follow them. In the digital world of make-believe, car graphics don't care about track graphics, and you have to explicitly tell them how to move through the world.

If you remember the original Rollercoaster Tycoon programs, you'll know tracks came in all kinds of bendy shapes, so how to do that?

One answer that should work (we think), is segmented cubic bezier splines. Basically, you define a start and end point in 3D space, and two intermediate control points (also in 3D), and the bezier algorithm computes a smooth line from the start to the end point. For the more bendy shapes, one such spline is not sufficient, you either need a higher order bezier curve (but it's math becomes complicated), or you chain a number of cubic splines after each other. If you do that careful, the cross-over from the end of one spline to the start of the next spline is also smooth.

So far so good, bezier splines gives a line of rope through 3D space for the car to follow. But what about the orientation of the car? (Keep in mind, the car ignores the track graphics!)

Just a line doesn't tell whether the car is up-right or upside-down (or anything in-between). To solve this problem, a track also needs a roll orientation for every point at the line. A smooth path from a starting roll value to an ending roll value (in degrees).... Another segmented cubic bezier spline to express the roll orientation in degrees!

From the direction of the 3D line (for the mathematically inclined, its derivative) and the roll, the pitch and yaw can be computed (hopefully, I haven't actually tried that yet).

For the test rollercoaster track graphics, roll is simply 0 (upright orientation), so that's easy. The path involved a bit more experimenting. I made a small Python program that plotted the path curve onto the existing track graphics, and tuned the start, end, and control points until it all looked ok. You can see the result above.

For example, the path of the level-to-going-down-track in negative x direction (bottom-right sprite) is defined  as

car_xpos: splines { cubic { a: 255; b: 150; c: 100; d: 0;   length: 1000; } }car_ypos: splines { cubic { a: 128; b: 128; c: 128; d: 128; length: 1000; } }
car_zpos: splines { cubic { a: 80;  b: 78;  c:  50; d: 15;  length: 1000; } }
car_roll: 0;

The roll is 0, as expected. The x position runs from 255 (point a) to 0 (point d), with intermediate control points at 150 and 100. The y position is 128 all the time. The z position starts at 80, and ends at 15 (points a and d). Point b at 78 is almost the same height as point a, so near the start the path is almost level. Point c is much higher than point d, so it goes down more steeply.

So far, it all looks good, but getting to the point of a car following the track on the screen will be quite some work. Then we will see whether the above math actually works :)

1. I like to see that there's some work going on!

2. In original RCT car images were (supposedly) made by rotating in 3D a single car (rotating around a point between the rails on which it currently was), until it just fitted to the rails (I think it was 8 images per track piece, with car each 1/8th of a track piece further in every image. Make images of all the needed angles and work with them further.
Then you would save the angles and just apply them to every rollercoaster`s car.

But that`s an old and tiring method, your idea of using bezier splines seems nice.

I gotta tell you one thing I LOVED about RCT - it`s how smooth rollercoasters rolled on the track while still OBVIOUSLY being just a slide show of images. It still amazes me, how real it looks. Certainly more realistic than 3D animation.
I would even risk the statement, that this particular part of RCT graphics was what gave it this amazing uncomparable FEEL. It was a pleasure just to watch.

1. so I truly hope the method you wrote about will be a way to make dozens of shots of the car to be put together later

2. I didn't talk about the cars, but there already exists a sprite sheet of 1024x16384 (1MB png) with exactly those 4096 rotated car positions. (Yep, not dozens, but thousands :p )

That's just empty cars, so if you add 2 rows of passengers, you have another 8192 sprites (theoretically, as in many orientations, the passengers are not visible).

The bezier splines are mostly a nifty way to fill the angle tables. If it works, it saves a lot of effort. If it fails, well, we can always fall back to manually filling those tables :p

3. This is not for rendering graphics correct? Your still using a sprite based system for the track pieces and vehicles?

Is this to determine vehicle acceleration, as well as pathfinding and potentially determining the g-forces for rating?

Is there risk of the processing overhead due to floating point maths with the beizer calculations?

There seems to a fixed number of arrangements for track pieces from what I've seen, some which are disabled for track based rides.

Wouldn't it be easier to divide each track pieces into say a fixed number of parts (ie. a 9 plot wide angle turn is the largest piece of track- analyse how many car frame changes occur by watching a frame by frame replay of RCT) . This is the upper limit of frame changes that can occur within any one piece. Capture the x,y,z and the vehicle frame applicable for this on a neutral rotation (and offset it with the world rotation). Now just use some simple integer maths to represent x,y,z, comparing it to the previous transition, and doing a simple physics calculation to determine push, pull on the 3 axis's for vertical/horizontal forces and acceleration.

Thoughts?

1. It is for rendering graphics, in the sense that a roller coaster is a one dimensional track, and for each position, you need to decide which graphics to render at what 3D position (which is then again mapped to a 2D screen position).

Vehicle acceleration looks like a good candidate too, to derive from the curve. The other ratings look like a good candidate too, although at this time I have no idea how to compute them.

As for processing overhead, it's possible, but I'd like to see that happen first. With modern processors, memory access and if statements in the computation may be more damaging to the processing pipeline than a few floating point operations, in particular since the entire program relies on integer calculations, leaving the floating point processing circuits unused.

I am not sure how reverse engineering of behavior of the Rollercoaster Tycoon program would help here. Obviously you can do that, but who says my track graphics match? Also, what if someone invents a new track? I need a simple way to define the path, no matter what track you have.

I do agree you can do a lot of pre-computations to simplify the runtime calculations. The beauty of using the splines directly is their compactness, and ease of implementation. If that fails on runtime overhead however, I see no obstacles in doing these pre-computations based on the splines.

god this is getting better and better all the time.

i can't express how bad i want this and want it now. the first 2 rct are my favorite pc games i ever played. the only reason i don't continue to play the crap out of them is because i cant window the game.

all i can say is that i cant wait for it to be released, and when you get to hedge mazes and mini gulf, you have to make some way for people who stop caring to be culled out, it was a problem when i made an excessively large maze that people just stopped trying to move and would get stuck, or someone who stopped caring played gulf but also just got stuck.

3. I feel like you are making the rendering much more complicated then necessary. I get it that we want the old feel, but regarding the performance, i feel that you are over doing way to much pre-mature optimization. I mean come on the game is really old now, to require it to be able to run on the same hardware feels just plain dumb to me. I understand that you might want to challenge your self, however, people just want this to be playable as fast as possible. I don't think the majority cares whether they can do that on their grandmas rig or not.

I don't see why you just don't stick to 3d models which are rendered to a 2d sprite at run-time. The rotation could then be aligned to a certain threshold to still get that jacking feeling. And if you want to crank it up a notch you could use voxel models since the sprites will be quite low res anyway, this is what Red Alert 2 did and that's quite an old game.

I have stared at that sample sprite-sheet of a cart now for so long and i am still having a hard time to figure out some sort of meta-pattern that relates the sprites to relative rotation.

4. @alidan:
Yes, we are, already from the start. Currently, even the base set is just a bunch of RCD files that get loaded, which thus could be replaced by your own files. I haven't really thought about the extension eco system, but eventually that should be done as well.

@feelnerdy:
If I understand you correctly, you want me to throw away the already created sprites, and add a 3D model and renderer that produces the same set of sprites at run-time? Maybe that's a good idea, but I know absolutely nothing about 3D models and rendering, so in terms of finishing earlier, it'd mean a step back. On the other hand, I do like to get my hands dirty with it some time, but not likely to happen until this is running on its own feet.
As for the sprite sheet, the top-left image is straight-horizontal, in perspective. To the right, the car gets rotated in yaw, in 16 steps. One row down means a 1/16 rotation in pitch, and 16 rows down is one 1/16 rotation in roll (thus leading to 16x16 rows of 16 columns).

4. To reduce some pain i would recommend you to use two separate 2d graphs instead of a 3d one. One for height change and one for turns. Since the roll is going to be computed by the "roll" of the track anyway.

If you want to pre-compute you can instead of storing these graphs and calculate their derivatives all the time, you can store graphs of the derivatives instead. However i think both are necessary for the "statistics" tab of the coaster.

5. It is really helpful for me. Thank you for sharing it. I am very thankful for your hard and innovative work. Dear Keep it Up.

6. Thank you for sharing. I really appreciate your hard work. Your site is really helpful for me.