A long time ago in a series of related threads (one, two, three), a discussion was held about Outrun style games. I came up with a brief engine demo that is still available on 23yrold3yrold's webpage. General criticism was that the corners were slightly unconvincing and at first it didn't support hills.

I've now taken the opportunity to revisit my ideas from back then and have produced a severely improved version. It properly cues its corners and supports different heights of terrain (although in a straight edged fashion familiar to anyone who knows what a polygon is), but remains a smoke and mirrors pseudo-3d "fake" extension of a 2d world.

What I still haven't been able to figure out are the rolling hills common to the older games. In some, such as Outrun itself, it is obvious that the trick is something simple like a sinal distortion (with scaling) of scanlines to produce something the player can see is meant to be a hill but with terribly unconvincing perspective. In others, such as Road Rash, the perspective seems to be quite good. I am wondering if anybody else has figured hills out?

I know it would be perfectly possible to ray cast onto a parabola or something, but I can't think of a way of avoiding possibly hundreds of square roots per frame with that, so am persuaded this is not the true path of racing games gone by. I am hoping some other people have some other smart suggestions.

Anyway, onto what I have managed so far. You'll see that source + a single .pcx (recycled from last time, a 23yrold3yrold original) is attached. It's a .cpp file but only so that I can not worry about where I'm declaring my variables and because new is a tiny bit neater than malloc. Anyone who knows C should have no problem with any of the syntax. It's all still a bit "first hack"y, filled with stupid variable names, direct calls to math.h functions where speed concerns would normally stop such free abandon and probably even a few variables that I don't even use. Keys are cursors + Q, A, W, S. Although Q/A are possibly confusing. They rotate the view around the x axis, a control that would almost certainly not be present in a finished product due to the hassle of adding objects to the scene.

It also doesn't properly check its return results. Particularly if it can't find its texture, it'll crash and if it can't get a 32bpp mode it'll irrationally refuse to run.

The algorithm is based on connected patchs of floor. Each patch has a curvature coefficient, used to fake the corners, a slope and a length. The improvements from the previous version come in each patch being allowed a unique gradient (in ordinary road user jargon) and curvature, and the use of that information to produce corners that properly approach and properly tail off.

The principle is simply that the patches are used for ray casting sequentially from front to back. If they have a curvature, then their scanlines are skewed by a function of sine, their position on their patch and the curvature coefficient for the patch. When the viewer enters the patch, the function is adjusted to start from the camera rather than the start of the patch.

Offsets in space and "forward direction" are accumulated as patches are walked. So, for example, a curve with a straight attached to the end causes the straight to "rotate" into view as best the pseudo-rotation in these games allows.

If there is any interest, I will continue posting to this thread, hopefully clearing up the code as I go. In the meantime, if anyone has some smart ideas for non-flat edged hills, I'd love to hear them.

EDIT: A screenshot for the interested (camera up high, rotated quite a way forwards):
http://img146.imageshack.us/img146/2068/picture29er.th.png
(click for a larger version)

EDIT2: demo with an actual bump in it attached!

I'm interested in this too, so please keeping post updates....

"Interestingly" my return to this sort of stuff is partly inspired by playing the Mega Drive Lotus Turbo Challenge (albeit on a real machine), which I believe is a straight port of no. 2 from the 16bits. Certainly it includes other cars as obstacles rather than competitors and no 2 on the Mega Drive includes RECS, which I think only came to the Amiga in no 3?

Anyway, enough of that and lets talk curved surfaces. I still cannot come up with a solution that doesn't involve either a square root or subdivision. Although a square root can be approximated on a 6800 in something like 2-300 cycles, and the machines will likely have had more than 1000 cycles to complete each scanline of the floor I note that the SNES has a piddly little CPU that almost certainly couldn't sqrt. Similarly, ports of Lotus Turbo Challenge (which has pretty decent hills) exist for the Amstrad CPC and ZX Spectrum, both of which have mildly slower CPUs than the SNES but also must do all their own pixel work. Even the Master System and NES can cheat by essentially having a pre-drawn perspective road and then just tweaking the scrolling registers on a scanline by scanline basis.

Disregarding a heightmap, I'm therefore stuck at the conclusion that subdivision is the answer. There is no need for this to be expensive because it can be precalculated quite efficiently due to the limited depth of field and the fact that the hill will only ever be approached from one direction.

That said, I think possibly a heightmap is in use in the older games. My guess is that the camera remains a constant height from the floor and a number of hill positions are pre-cast, i.e. approaching a crest, levelling off from a crest, approaching a dip, levelling off in a dip. It's perfectly possible that some sort of tweening is used to transform between key frames, as this can be done in two multiplies and one add per scanline if things are set up correctly beforehand. I don't want to use this approach because I want the camera to be moveable and to properly "rotate" across the landscape, even if it can only ever do so subtley to prevent the various sprite objects from looking stupid. That means that as you cross the crest of a hill, the valley comes into view as you would expect.

In the meantime, I've discovered some sort of error that causes a slight jump in the scenery where patches with curvature of a different tilt meet. My guess is that I've used the distance along the patch synonymously with distance along the z axis somewhere without really thinking about it, or else that I'm clipping curves in a slightly incorrect fashion. That said, my clipping is the two lines that read:

if(PlayerZ > 0) BaseOffset = -PlayerZ;
else BaseOffset = 0;

So if the error is related to that, it probably isn't huge!

The aim is to fix that, then see what can be done concerning subdivision. I'm guessing that it'll be as simple as branching between sections of the patch list depending on distance.

It'd be really cool to make a game based on this stuff (although probably in OpenGL in order to use hardware scaling & translucency) but I just don't think I can source the art - that was certainly a problem last time.

I have to admit I'm not 100% following what you mean by height lines. Are you talking about something slightly voxely (i.e. the program knows or calculates what z on the floor should come at each scanline if the floor were flat, then draws something in the shape of a rectangle to produce floor, albeit from front to back with clipping for zero overdraw)?

The problem is in the main function, where I determine "StartPlane" by z-depth rather than plane relative depth. It is therefore only a problem when the player is high above the floor, because when they are close the correct moment of moving on a StartPlane more or less synchronises with when the player crosses the depth threshold. In pure drawing terms either way would do but because of the way curves are accumulated using pseudo math the main way needs to be changed or else the game can just keep the player "close" to the floor so that the problem doesn't occur.

I've also added a coloured sky and "side bars" to the road, i.e. those two tone stripes that are common to these games covering the untextured area. I suppose if I will insist on 32bpp, I could use a proper gradient! The camera "rotates" and moves/up down with the floor automatically and is shifted to the left/right when on a curve increasing the illusion of real 3d movement. I've come up with an ingenious little modification that allows real time subdivision effectively via lookup, although it's only two extra members to the Plane struct and one extra if statement to the caster. I have no doubt that a real 8/16bit racing game could use the algorithms I am implementing.

That would make sense. You could also create small hills (more like bumps, I guess) by adding pre-stored alterations to the correctly scanned floor in a fashion analogous to 1d sprite drawing, allowing several to be added in sequence.

Anyway, I'm going out for the night so I'm attaching my work to the end of today. One thing I especially like about the non-"voxel" approach is the way that a future slope can approach as at the start of this version. The camera jumps from one orientation to the next when you leave the slope, but that will be fixed if my little subdivision idea comes together. I think the main problem is going to be obtaining the data set, so I probably need to throw together a little track editor.

Thanks for taking the time!

So we are talking about a 1d heightfield? So in C you could reproduce it as a 1d array of height values which is indexed by depth into the screen?

So you saw sticks modelled as "1 pixel deep"? It isn't that flat sections of terrain were constructed over the sticks as if they were a heightfield you'd communicate as vertices to OpenGL, for example?

This is how I did my last engine (give or take height changes), and the problem I had was that the approach and exit of corners looked wrong. I know plenty of games that are clearly doing just what you suggest, but it looked a little too fake for me.

What I've come up with is quite different, having taken Road Rash 2 as the thing from which I tried to determine behaviour rather than Lotus Turbo Challenge. Road Rash 2, by the way, has aged horribly and although I don't remember it having any such problem appears to have a framerate of 10-12fps. That's probably about half of Lotus Turbo Challenge, so it is believable that a more complicated algorithm is in use.

I've essentially stuck to what I had of a segmented track where each segment has a curvature and an orientation, but I've created a brief hill editor and thrown Bezier data into a file to generate track heights. I've implemented something a lot like adaptive meshing to save ray casting costs. The trick is to remember that in my engine the segments are a linked list. All I've done is added two variables to each node, a "too far" distance and a second "next segment" link. If the segment is further from the player than its "too far" distance then the engine immediately moves on to the thing linked by the new "next segment" link. By pre-merging segments and exploiting linked lists by having the off shoots reconverge onto the main list the processing cost for adaptive meshing is very very little.

You'll probably be able to see the Road Rash influence in this shot:

As versus a wikipedia shot of the original:

{"name":"MD_Road_Rash.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/2\/0259adaf64d33815da50bf1927928f6a.png","w":320,"h":225,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/2\/0259adaf64d33815da50bf1927928f6a"} (click for article)

Note in particular that in mine a double peak is shown. The cool thing about the way I've settled on something that is pretty much "real maths" for the elevation is that the camera can genuinely rotate, no hacks. I've found a small bug in the code I already had while implementing this, which affects the SkewRatio value. That should be accumulated across segments and not reset (i.e. I wanted +=, not =).

Anyway, I want to make sure the adaptive stuff is actually working before I post source. I'll hopefully be back later!

EDIT: latest source attached. Note the new "track.dat" file, it's a list of depth and height references for the track, generated by a somewhat basic level editor I've thrown together. That editor doesn't know anything about or output curvature at present, so the code puts a fixed curvature on every single segment, producing one long leftward corner. I want to add curvature to the editor then I'll provide that too.

The number now in the top left of the screen is the number of patches/segments/planes (I should pick a name for them and stick with it!) considered for the current frame. It currently goes very high whenever a you approach a peak, which I believe is because it runs through all the downward faces realising they are facing away before finding something forward facing, casting a ray onto it and decidiing it is sufficiently far away that the casting can stop. I need to add a basic distance constraint in the ray caster when considering potentially visible faces.

There is one place where the adaptive meshing is visible, I'll leave the discovery of that as a treat! Note that I've switched to allocating Planes in blocks. Besides being better for the cache, this means that even with my adaptive meshing trick nothing gets deallocated twice.

The spirit of "getting things done" must, I think, now take a moment to give way to the spirit of "making readable code". I want to fix the problem described above, do a cleanup then have a look into the best way to add sprites. I'm imagining that on the forward pass, drawing the floor, a visible sprite list will be built along with correct clipping rectangles (since objects may be obscured by the floor), then it can be drawn from back to front. But we'll see.

I'll probably do an OpenGL switch at some point, especially as here in the OS X world there isn't any other conduit to hardware acceleration and Allegro is a non-optimised pure-C implementation.

That said, it doesn't really make any odds while it remains as inevitably true as it does for almost every other project I attempt that I have no artist and correspondingly no way of obtaining art!

EDIT: does my somewhat overenthusiastic use of hills in my previous post's attachment make anyone else feel a little nauseous?

With all due respect, you can only eliminate the polygon rendering/ray casting by doing the polygon rendering/ray casting in advance and prestoring the results! Otherwise you don't know where to map your sticks to on the screen. You can work it out with trigonometry, in which case you're reinventing the ray casting approach or with linear algebra meaning that you reinvent the polygon fill, but the result is the same!

I think the solution I implemented last time is very similar to what you suggest, except that the heights of sticks were not calculated but prestored. If you can run it, try the binary I posted in a previous thread. It may be DOS or it may be Windows, I don't recall and the source is long lost.

Yes, look at the elevation view from the burgeoning editor (EDIT: uploaded correct shot!):

Given the shortness of the curve when mapped according to the scale applied, it must be at least the 70 you state! Luckily any degree of hill is possible. I think I have suffered a hill mania, having been impressed with the fact that I finally feel I have a grip on hills in the same way that recent C++ converts usually immediately try and do everything with classes.

If you mean up/down style jumping then the way the camera adapts to the hills needs work. It should be easy enough, I just need to do it.

If you mean the texture jumping left/right (which occurs if you look for it, but to my eye doesn't jump out), then it is a result of the adaptive meshing. I've essentially implemented depth cueing much as you suggest ("adjusting the x' offset based on "into screen depth" in a similar way as with the y' offset with the heights, so several consecutive curves would also be shown correctly and all automagically?"), which has the effect due to the way things are split by the (somewhat dense) adaptive meshing of switching between a true evaluation of cos and a Euler approximation reached by evaluation of -sin, the derivative of cos. Nowhere is this explicitly written or anything, it's just a natural effect that I hadn't otherwise given any thought to.

EDIT: I hope that the jumpiness is now entirely fixed. I've switched to maintaining camera position relative to the track surface, and am interpolating viewing angles from surface to surface. The adaptive meshing isn't quite so violent as it was before, but is still a little bit too simple for its own good. The code has now definitely crossed the threshold into ugliness. So my next task is to clean up what I have, and possibly remove whatever math.h references remain as I do. Even though the full source is still under 400 lines, I expect I'll break it into a few files purely for easy organisation. Once it is clean I will add curves to the level editor, removing the eternal left hand corner, and then sprite objects. Ideally I want to comment and document most of what I do because there aren't enough psuedo-3d games like this any more!

You may want to wait for my tidy up - especially the bits concerning the camera movement are probably indecipherable at present.

In the meantime, I've made a first hack of curves into the level editor, and as a result have produced a level that features moderate hills and varied curves. It is attached, not because it significantly builds on code already posted but for the benefit of newcomers to the thread.

At present I have no idea why it does what it does when you approach the end of the level. Something somewhere obviously isn't terminated properly!

Admittedly I have been thinking more about the 16bit generation of titles than the 8bit. Although the algorithm I describe sounds complicated, it's does calculate the depths and texture offsets of around 90% of its scanlines with just 8 adds and 5 multiples each. And the others will normally be only around two or three times as expensive as that.

What the 8bit console racers probably do is load a single frame containing a single track slice scaled to 224 different possible widths. Through altering palette and scroll registers according to the hsync interrupt they can then display any combination of corner and slope they can calculate the correct values for virtually without drawing costs.

I would imagine that a fixed "width of road slice per scanline" table then produces a lookup for what scale of track slice should go where. Obviously with a display around 240 scanlines, this is a 240 byte table. Corners can be added quite cheaply in real time, probably using more tables with a few shifts and adds. This gives a flat display sufficiently cheaply for one of those consoles, and probably explains the proliferation of flat tracked racers.

To add hills, I'll bet they have a few precalculated hills. They can store these as how the 240 byte scaling table should look, say every 2 frames. For a 2 second hill animation, that's somewhere around 3,000 bytes of storage. You can further mix that up a bit by combining hill animations for small bumps.

Chances are, due to the resources available, that these hill animations were hand calculated by the programmers or else created by the artists rather than prebuilt by a computer so they should look pretty fake. If you still have access to Rad Racer, it's possibly worth booting it up and making a judgment on how realistic you think the hills appear and how similar they look to each other.

Pressing on with my implementation of an admittedly very 16bit type road racer, I've cleaned up what code I had and added a first stab at adding roadside objects - see the attachment for all of that. Predictably the editor doesn't do objects yet, so I've just hardcoded three in by hand. The final one seems to appear a pixel or so above the road when on the crest, but I'm not sure I can rule out Allegro's lack of subpixel accuracy as the culprit.

EDIT: I've also eliminated math.h functions from every per frame calculation. That costs less than 10kb in LUTs, so is probably worth it.

Hey, I'm not complaining at all

So, let me get this straight...you are not using ray casting anymore? How much different is this demo as compared to your earlier work? Do they have anything in common? I thought i was getting somewhere with the coding and theory, then you went and got all "professional" on me

Anyway, I'll just PM you with specific questions.

<-- Doesnt understand how to do cool graphics programming and its pissing him off.

Same here, all pitch black and it just shows:
Visible segments:1 Base angle:-4129245.25
The value for the angle seems a little 'strange'.
(MSVC6, Allegro 4.20rc2)

Nope, track file is found fine, still all black, same error message.
Maybe it is an ENDIAN issue with your track editor?!

The tree grows through the asphalt. "Were you stoned, when you coded that?" (voice in the off: "No he was asphalted.":P doh!)