Voxel Space: Comanche's terrain rendering in less than 20 lines of code (2020)

It is actually X lines of code, not 10*X lines of code condensed into X lines with code golfing techniques. :)

That game was amazing. Still is, really. The particle effects hold up incredibly well even now.

Great to have an Outcast developer right here on Hacker News! Outcast was a great game with awesome graphics. Unfortunately, Voxel Space died soon after.

Of course, this demo is just a starting point. I could optimize it even further, also in JavaScript or WebAssembly. But that's not the goal of the project. It is more a fan site for the technique.

Also https://news.ycombinator.com/item?id=21944573

The lines are always drawn vertically from the point of view of the viewport, so they're always aligned to pixels.

This does limit the rotation allowed before the user starts to notice!

Adding the tilting is a tiny tweak: https://news.ycombinator.com/item?id=21945633

Clearly time travel is involved. "Restart" actually means "go back in time".

:)

He mentions the front to back optimization, keeping track of the max height.

> I don't think in Comanche they painted back to front, or at least I hope they didn't. It's best to render front to back, tracking the highest (in screen space) pixel you have drawn, and as you move further back, only drawing lines from that height. That "max height" is a zbuffer of sorts for each ray.

Discussed here <https://github.com/s-macke/VoxelSpace#more-performance>

> Also, you want to render each ray/vertical screen line one at a time, rather than running each single step of the ray for all rays/vertical lines.

This may require more performance. Remember, this algorithm was used for an early Nineties game.

The advantage of drawing along a line of same-distance (i.e. constant z) is that per pixel, there are no divisions, only additions and one multiplication (which could perhaps be optimized away?). Drawing vertical screen lines, you get the z-division for each step.

(Then again, perhaps the division could be removed with a look-up-table)

> It's best to render front to back, tracking the highest (in screen space) pixel you have drawn

As mentioned in the README of the linked repo:

Instead of drawing from back to the front we can draw from front to back. The advantage is, the we don't have to draw lines to the bottom of the screen every time because of occlusion. However, to guarantee occlusion we need an additional y-buffer. For every column, the highest y position is stored. Because we are drawing from the front to back, the visible part of the next line can only be larger then the highest line previously drawn.

Could run on a 200mhz pentium ... but these days runs with barely 60 fps on my 10th gen Core i7 and makes my laptop fans go crazy ;-)

It could be hybrid rendering with voxels for near details then polygons or parallax backgrounds. That would be cool.

IIRC every novalogic voxel game after comanche mixed polygons and voxels. Delta Force definitely did.

> But I can't understand how transformations other than rotation on the vertical axis can be performed.

Roll is visible in the game clip. I think it's not a true roll but just each column of pixels raised up or down so that the horizon is tilted appropriately. Given the fast movement and the nature of the scene, the user doesn't notice that vertical features in the scene are not rotated. It's neat.

Correct, modern browsers limit features when you just open a file.

You can launch a simple webserver to publish a directory to localhost port 8000 with `python -m SimpleHTTPServer`, and this should work.

The height map alone is enough for you to approximate a signed distance field, so you can do raymarching - which can give you pretty efficient light transport, volumetric fog, ambient occlusion, reflective water...

Yeah, that's how the optimization is done in the link I think.

From the article:

>More performance

>There are of course a lot of tricks to achieve higher performance.

>Instead of drawing from back to the front we can draw from front to back. The advantage is, the we don't have to draw lines to the bottom of the screen every time because of occlusion. However, to guarantee occlusion we need an additional y-buffer. For every column, the highest y position is stored. Because we are drawing from the front to back, the visible part of the next line can only be larger then the highest line previously drawn. Level of Detail. Render more details in front but less details far away.

Yup. A.k.a. depth testing†. TFA illustrates it under ‘More performance’: https://github.com/s-macke/VoxelSpace#more-performance

Edit: Originally, I had said: “Though in a highly constrained scenario such as this, with the right approach you could get away with a 1-bit depth buffer.” That would be true if you had one depth value per pixel, which is of course so common nowadays that no one even needs to think about it. Except in this case I should have thought about it, because this algorithm requires only one depth (or, alternatively, as TFA and parent comment explain, Y) value per column of pixels.

† https://en.wikipedia.org/wiki/Z-buffering

It was written in assembly and required a boot disk to squeeze every available kilobyte out of the 640 a computer was guaranteed to have back then.

You could try PCem with a period-accurate configuration instead of Dosbox.

This is true of a lot of DOS simulator style games from this era, where they often let the game systems run at uncapped rates. They were typically just targeting a specific 386 or 486 CPU etc, so performance was pretty predictable on the customer's end hardware at the time. Wing Commander 3 is another example that is famously bad for this. When faster CPUs inevitably came along, these games basically broke or played differently due to the speed change. Back in early 90s many 486 systems had a button on the case marked "turbo" so you could slow down your 486 to play games optimized for earlier chips at the correct speed.

Dosbox offers ability to adjust CPU "speed" to help with this today, but it's often hard to get emulation speed right on early DOS games that ran uncapped.

> https://en.wikipedia.org/wiki/Turbo_button

I don't know, but based on a gameplay video it looks more like vector graphics to me. The terrain silhouette seems to have straight lines.

I don't know how they pulled that terrain rendering off with 1994 hardware. The limited rendering distance probably helps.

I don't have a source to back me up here, but IIRC, Magic Carpet used texture-mapped polygons.

Maybe fun trivia: James Schmalz trying to replicate Magic Carpet in pure assembly language and showing it to Tim Sweeney resulted in the embryo of UnrealEd and what later became the Unreal engine.

No, it's a polygon renderer of some sort. But it is quite restricted. Each "world" is a sphere, and checking again in a youtube video, it looks to me like the sphere has a regular tessellation. It's dynamic though: some of the game mechanics raise or level hills. I'd guess they found a way to special case a lot of the rasterization given the spherical restriction. Kinda like how Descent based everything off intersections of a unit cube.

I was pondering on that solution as well, not entirely sure how cache would behave but in 91 memory was relatively fast compared to CPU so lookup tables were useful still (my thinking is that perspective could be calculated per row if rendering per row but if one would be using lookup tables for that division it wouldn't matter much by flipping to vertical), also if they were running modeX then doing vertical rendering would've been a benefit.

modeX memory layout has a write-enable bit for every 4th (or was it 8th?)column but the addresses was the same so you often would want to write every 4th pixel if doing something "exact" and then change the IO registers so it'd be every 4th again but offset by one, then repeating for offset 2 and 3 and then be done. Unless you were doing flat-shading where this write-enabling could be useful for writing 16 pixels in one 32bit word write with 4 writes enabled (this could also be useful for doing a half-resolution rendering by having 2 offsets enabled and then doing every other column).

(I really loved writing software-rendering code back in those days, glad to be getting much of that power back with shaders these days)

Indeed, the Javascript code is much larger. But the description tells you.

"Terrain rendering algorithm in less than 20 lines of code"

So, it just means, that a clean implementation of the terrain rendering algorithm takes 20 lines.

With initialization, keyboard handling, map selection, collision detection, fps display and some JavaScript optimizations it needs much more lines of code.

It’s not a lie at all, since it is specifically talking about the rendering algorithm, not the entire program.

386 protected mode was not tied to 'boot from floppy'. It was more of a do these set of instructions and you can flip the cpu in the 386 mode. Many of us had an extra boot floppy that would not load xms or ems which would conflict with protected mode (as it wanted the same memory as those extenders). I personally used a 4dos script that would turn things on and off with a set of prompts if needed. Special boot floppies were pretty much the norm for other systems though as they used it as a form of copy protection. Many of the later origin games would flip themselves into protected mode so that special path was needed. It may have been one of the first as that was right around the time many games started using protected mode (ultima 7 was another if I remember correctly). As memory prices has started to fall a bit and and it was 'only 150 dollars per MB'

Many commercial games in the 80s were booted from floppy. That wasn’t unusual. What sucked about this game was it used DOS but in a weird way, incompatible with every other DOS hack, so you had to set up your boot menus specifically for this game.

Winter games by EPYX booted directly to the game, ignoring DOS.