Hacker News new | past | comments | ask | show | jobs | submit login
Terrain rendering in fewer than 20 lines of code (github.com/s-macke)
793 points by blaze33 on Nov 24, 2017 | hide | past | favorite | 93 comments

I stumbled upon this very good explanation (and demo) of the Comanche Voxel 2.5D engine reimplemented in JS and thought it might interest some HNers. I did not had the pleasure to play Comanche though I have fond memories of playing Apache in 1996.

I've been investigating the terrain generation / rendering quite a bit for the past ten days and have started to play with https://threejs.org/, webgl and shaders, the current result (https://twitter.com/maxmre/status/933860624773283842) is quite humbling when I see how nicely the Comanche engine works :)

Pretty neat, but I'm confused. You say it's in JS, and the demo certainly is, but the repo is in Python plus some extractors written in C, a few shell scripts, and Markdown docs. No JS in sight. At the same time, Github claims the project is 100% HTML ... I don't know what or who to believe!

The project is originally a fan page about the game Comanche and the Voxel Space engine. The web demo is just one part and contains mainly JavaScript. The tools directory contain the code which was used to generate the gif animations and the tools to extract the maps from the Comanche games. So you can ignore the python and shell scripts.

Well, the magic of this algorithm lies in the prerendered color map. Use the height maps and color maps from this engine and your result will also look much better.

Thanks, the gifs displayed in the 'Basic algorithm' section are really good.

I'm gonna try this out for myself. I love graphics projects like these and the algorithm is straightforward to implement. Most of the additional work is boilerplate, setting up canvas and resource management of images.

Yeah, but imagine doing fractal landscapes on an 8-bit 6502 in 1984:


is this going to be 'rescue on fractalus'?

EDIT: It is! Had the commodore version - fun memories :)

c64: https://www.youtube.com/watch?v=fjR33K_wuD8

One of my all time favorite games, without a doubt. I used to play it on the Atari 800XL, but it had a different name, I believe. "Behind Jaggi Lines", I want to say.

Edit: fixed game name

Behind Jaggi Lines! was actually a development version that was pirated heavily amongst Atari owners. I played it on my Atari 800. It was the first game that actually made me jump out of my chair, scaring me. I can remember the moment vividly. Great game!

That is not 20 lines, that's 300+! Here is terrain rendered in 30 lines, with no textures either. https://www.shadertoy.com/view/lslBz7

Author here

The main algorithm fits easily in 20 lines. However, the JavaScript code is optimized and contains also the initializing routines and input device logic.

It is also a little bit unfair to compare this with shadertoy. He doesn't have to include the render algorithm but relies on a GPU. The Voxel Space engine just draws vertical lines and doesn't need a GPU.

Shadertoy shaders _do_ include the render algorithm. That shader is completely ray-traced, so the only real input that is used for that shader is the x, y coordinates and time. It's not using any of the GPU's polygon rasterization. It's stateless and is generating the terrain while it ray-traces it.

Firstly - this is really nice. I don't want to derogate the work itself in any way (and I don't think the gp did either) - I'm just really quite curious about what exactly the post title is referring to.

If I extract the code and delete what I can see might be extraneous setup boilerplate (event handling, camera navigation, init function, image download helper utility, various config object initialisations), it still comes in at around 150-200 lines. The render function alone is 38 lines, not including the external dependencies of that function (DrawVerticalLine, screen, camera).

Again, not a criticism of the work, just querying the title.

Shadertoys' authors never fail to amaze me.

To be fair that seems to originally be a piece of the 4k demo elevated.

Next challenge, code golfing, to render a golf course :D

Just a few years after Comanche was released I was sitting in a high school C++ class, content to explore the language with text adventures and RPGs. 3D graphics seemed vaguely mystical to me.

Next to me, however, was someone who seemed light years ahead of me. He had programmed his own voxel terrain rendering just like this. I had no earthly idea at the time how that was even possible.

In retrospect, he was not so much farther along, but he was passionate enough about game development to read books about these techniques and work out the details. I've always wondered what happened to him, and if he ever followed his passion to become a game developer...

Never get tired of writing this but people probably get tired of reading it - I played Gunship on the C64 when it came out, and about 20 years later I worked with one of the guys who helped write it, and he was IIRC 16 years old at the time he worked on Gunship (which humbling enough was my age when I was playing it).

Ha I was waiting for you to say that guys name was 'John Carmack'

Could probably search for him on LinkedIn maybe it is ha

Ha! Carmack and I both grew up in Kansas, but I'm not quite that old yet. ;-)

I don't remember my classmate's name, unfortunately.

You might be able to find it by calling the school maybe, or yearbooks? If you did care to find out and didn't consider it too creepy that is.

Here's the credits for Gunship. Any of those look familiar? http://www.mobygames.com/game/c64/gunship/credits

C++ in high school in the 90s? We had Turing taught by our gym teacher ;(

We had Turbo Pascal taught by a math teacher, who read to us straight from a course binder and admitted to literally drawing the short straw in the teacher's lounge when they were figuring out who had to teach the computer class..

+1 TP by math teacher. Without him, I'd never have become a real programmer.

I only had TP7 back in the 90s. No math teacher needed. The help file teaches itself.

Hah.. our guy barely knew the material... My friend and I ended up teaching the recursion module to the rest of the class because he couldn't wrap his head around it.

Turbo Pascal had a great graphics library, though. Perfect for experimentation with 2D graphics for games and such.

I did c++ in high school in the late 90s. No teacher, just a textbook. The "teacher" for the computer lab just handed each of us a book and told us to show him something cool every day.

So I ended up doing bits of QBasic, Visual Basic, and C++ (since all three books were in the room, and QB was easier to generate flashy visuals with, as a beginner).

Our school actually had a pretty good programming curriculum for the time: Basic, Pascal, and C++. Unfortunately the instructor for all three progressed through the topics at an utterly glacial pace. As a result I would finish the assignment in the first 10 minutes and alternate between helping others and surreptitiously playing Master of Orion from my homework diskette.

Had a similar experience. VB class in HS was my first programming experience, but me and another guy finished the end of course project in the first month. It was a playable tic-tac-toe game. Instructor said if we made the computer actually play a side, we'd get 100s for the class. Took me a day or two to write an algorithm for it combining identical game states, the other guy spent a few days making an absurd mess of nested if statements to cover every possibility. Spent the rest of the year alternating between making more games (a clone of Space Invaders and then the beginnings of a clone of Legend of Zelda) and playing an NES emulator, which the instructor overlooked. Probably wouldn't have approved if she'd noticed we had it saved locally in the school machine and the emulator was called NESticle, complete with an icon depicting a hairy sack...

My high school had a single programming class led by our Physics teacher. UCSD Pascal running on ancient IBM PCs. Having already taught myself Pascal 1+ year prior, it was kind of a waste, but I thought it would be a better elective than metal shop. I did all the exercises and the exam after the first week, so the teacher agreed to let me do whatever I wanted to on the computers the rest of the term as long as I wasn't disruptive.

On a side note, fast forward to today, I've taken up metal working as a hobby and kind of wished I had taken metal shop instead. Except for the fact that the highlight of metal shop in my year was when a bunch of knuckleheads ground another kid's teeth down in the grinder while the teacher wasn't looking. So, actually, yea I'm glad I opted for computer lab.

We had the art teacher teaching us how to fill a form on a Thomson MO5. He screamed when I entered some random data instead of the ones he told us to write because it could brick the computer. :(

Flashbacks to playing Delta Force in the 1990s as a kid. Looking through the binoculars at a long open distance (say 3500 metres), only to realise that the same hill repeats 3 times :-)

Delta Force 2, released in 1999, still used a voxel engine which could already be hardware-accelerated, supporting "stretched voxels" which were able to simulate high grass.

Came to say the same thing. DF and DF 2 are still some of the best multiplayer experiences I've had.

Oh, the memories! Delta Force 2 over multiplayer, with, I think, 30 players or more, on 56K was surprisingly fun! Advanced voxel engines are quite impressive.

I played both (1 and 2) almost exclusively in single player, completing every mission. SP missions in DF2 were much, much harder by comparison. Unlike the helicopters in DF1, the MIL Mi-24 Hind helicopters in DF2 were able to shoot at you and you were only able to eliminate them either with an anti-tank missile or with the grenade launcher. No matter how many magazines you emptied at a vehicle, it stayed there and didn't explode :-(

Oh I so loved delta force. We had some russian version where whole menu was cyrillic and I had no idea what it means but it was still great.

Reminds me of this classic 4k demo which blew my mind back in 1993



The demoscene is still pumping out amazing stuff. Check out this ~5 minute 64K demo (2016): https://www.youtube.com/watch?v=gX7ESVZ7T6Y.

IMHO not very many 64Ks have reached the amazingness of this 11 minute one from 2000: https://www.youtube.com/watch?v=Y3n3c_8Nn2Y

...and for 4K, this one from 2009:


These dudes doin' mountains and oceans and music in 4K and yet it takes LinkedIn and the like like 9MB worth of assets to show me a bit of text.

This is probably the most impressive 64K I've seen: https://www.youtube.com/watch?v=rWwNgVwQG1A

'elevated' is an absolute marvel of a demo...

There was a superb demo I can't seem to find again, one of the scenes was a giant spaceship floating in the distance above a desert, and some silhouette people were walking atop a dune along with goats or some other animal. I seem to remember there was some article from the author about the implementation. If anyone can throw some link in my general direction then I'll throw back some <3 in theirs :)

That's it! The specific scene is at 1:14[0], and the article, is titled "How a 64k intro is made"[1].

<3 <3 <3

[0]: https://youtu.be/yei3mJm33SQ?t=1m14s

[1]: http://www.lofibucket.com/articles/64k_intro.html

That was mindblowing at the time. We thought we were being cool with our "Comanche engine using ripped Comanche terrain" on Heartquake https://youtu.be/LLsRBbFOa3k?t=1m39s but Mars was amazing.

p.s. yeah we edited the terrain to hide the signature pyramid :)

Yeah, the maps of Comanche were just run-length encoded and it took me an evening to reverse-engineer it. Nice to know, that I am not the only one who were able to extract them.

But even without the pyramid it is very obvious, that these maps in your demo were from the game Comanche.

Hehe you're going to laugh at me - I just played the game, exited back to DOS and dumped all RAM to a file. I had already written a relatively popular tool to explore files visually (dump every N bytes to a pixel, with W pixels per line and S stride), so it was trivial to find the raw maps. :)

This was also my first attempt. But I was too lazy to extract all maps that way.

I remember heartquake! I could probably play the credits part of the music by memory. I never realized the terrain was the actual comanche terrain.

So the editing worked hehe

Very cool, I remember this demo from that time! I even have a vague memory of trying to implement something similar.

Neat, great readme.

Everyone seems to be in flashback mode, so I'll add mine: I remember getting a good grade in my multiprocessing class by making a voxel terrain generator using mpi and with the same technique, but also with clouds (just think of upside down white mountains). But I just randomly generate them, without any lighting. The color of the voxels were determined by their height. Using (nice) color and height textures adds a lot indeed! It's a shame I didn't know that trick on that time, I remember playing with vistapro[1] or terragen[2].

[1] http://www.creative-3d.net/images/vistaprointerface.jpg (I had an older, ms-dos based version)

[2] http://planetside.co.uk/ (It's great to see that it's still alive after so many years..)

Here's my (old) take on a terrain renderer (more than 20 LOC, oh well):


For anyone who wants a refreshing/fun code project, strongly recommend implementing some kind of software renderer. A raytracer or raycasting engine like this one, or something more fundamental like a polygon renderer.

what would you say is the best resource for learning about building one from scratch in JS?

I followed Inigo Quilez's article on terrain marching:


Be sure to browse his other articles:


and his awesome video tutorials (which tend to be more about the math than the code):



The simplest techniques for 3D rendering without relying on a GPU and WebGL are indeed (2.5D) raycasting engines (such as this Voxel Space engine). A short google search reveals for example:


Also read the readme file of this Voxel Space engine. Maybe this is already enough to understand the principle.

Loading .obj files is pretty easy, and basic triangle rasterization isn't too hard either. Still probably a bit harder than height maps.

Firefox Quantum gives me better FPS than Chrome for the provided demo :)

And Safari seems to give me better FPS than both Chrome or Firefox Q.

Edge didn't work for me :)

I love it!

How's the rolling in comanche done? The lines are no longer vertical then, so seems trickier.

Roll means the horizon is no longer horizontal by the way, what is labeled roll in the demo is actually pitch :)

In Comanche rolling is a skew, not a rotation. You never tilt too much so it's ok.

Two skews can also make a rotation in a 2D plane.

Yeah but the vertical skew came practically for free (just an offset before you start working on each column), which was very important for performance.

You can't look up and down using this technique. However, you can move the horizon line up and down. You don't recognize the difference for small angles.

This is fantastic! I really enjoyed playing with the web demo. Thanks for open-sourcing it, and for the excellent explanation!

I have a bit of a fetish for old-school 3D tricks, I'm currently working on a 3D project for the Sega Saturn using jo-engine.

Reminds me of Tim Clarke's Mars demo: https://www.pouet.net/prod.php?which=4662

When I saw the demo decades ago I was also totally amazed by it. And only 4k. I reverse engineered it with the Turbo Debugger under DOS. Found that most of the code was repetitive to prevent a slow loop construct. So it would have fitted easily into a 1k executable .

Hasn't Outcast (1999) used the same/similar techniques for terrain rendering.

The re-released it on GOG last year, and remade it this year with a Unity engine (all polygons now).

We had interpolation to "blur" the rendering + some other optimizations (mostly stemming from the fact that the engine inner loops where super heavily optimized (think VTune level optimizations)) (note that I didn't work on the voxel engine, it was a colleague; I just worked on optimizing the 3D triangle pipeline)

(edited for more clarity and info)

Indeed, Outcast used the same technique. However, not as simple as this algorithm. They included interpolation for the terrain and polygon rendering for the parts, which are not terrain.

Spent so many hours playing this game on my 386....


Would love to see a C++ implementation of this of this code, whether it's a test project or an example already available in open source.

This would also be a cool thing to give an example of across programming languages. Sort of like how https://github.com/drujensen/fib does it.

Very well and concisely explained, kind of an eyeopener for someone who has never done any game/3D programming.

Where's the 20 lines of code? The code base is small, but looks like hundreds of lines, not dozens.

I counted 20 in the body of the README's Render function. I count it as one line if the block is a single line that uses a simple test to execute conditionally (for/if).

Once you understand the algorithm, it's conceptually even simpler than 20 lines.

What you look at, is the whole engine and not just the rendering part. This contains, HTML, CSS, loading and initialization of the maps, clear and flip screen code and especially input device logic. The rendering part in the JavaScript is still rather small. However, the code is optimized and therefore larger. For example the drawing of the vertical line is done manually.

Read the explanation of this algorithm and you will see how the 20 lines are meant.

The difference between Comanche and Game Gunship 2000 is remarkable. Very good write-up of the techniques.

My only problem with this demo is that it is almost too realistic. It makes me uncomfortable to view something like this and not be able to decide if I'm looking at a computer render or if I'm actually in an airplane flying over real terrain.

It wouldn't load Map Comanche 3 - it's trying to load a non-existent image for it - https://s-macke.github.io/VoxelSpace/maps/undefined.png

Sorry, this in an error. The Comanche 3 map is not part of the Github archive. Try the outdated website if you want to see how a Comanche 3 map looks:


I removed the map in the dropdown menu.

Perfect for an easter egg. I'm having higher-definition Excel 97 flashbacks... https://www.youtube.com/watch?v=-gYb5GUs0dM

traslate to :r4 in 95 lines of code (all)


Wow, great demo. Even works on mobile!

there are literally thousands of lines of code in this repo. This is bull shit.

The 20 lines refer to the pure rendering algorithm. Please read the description of the algorithm.

The repo contains also the scripts, to generate the GIF animations on the start page and the tools to extract the maps from the Comanche computer games.

looks well

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact