Same. I find it amazing about how much can be achieved with so little. Even more so now that games require computing power that rivals the supercomputers humans had when these games were released.
Another World (Out Of This World) featured a couple of days ago hightlights this also, imho.
And fun, I had plenty while playing these games. Increasing computing power improves immersion and realism, which certainly improves the entertainment; but the fun? Not obvious to me.
Comanche 4 is one of the first games my dad bought me and I loved it a lot. After years of playing it, I was disappointed to learn then that the actual Comanche helicopter program was cancelled.
Anyways, it seems new Comanche game is on the way!
This is the kind of 3d engines I was making as a teen. The way it works is that you iterate over x screen-space, get a "ray"/"slice", then you iterate over z camera-space (goes inward) using that ray. From there, you have what it takes to sample a heightmap. Draw a vertical line. There is plenty of room for optimizations and it's very good for learning to code.
It seems like this code would be fairly easy to add to a simple 2.5D raycaster (either a cube variant like the old Wolfenstein, or something more advanced like Doom/Doom 2) to give some variation (or more "natural" stuff) for indoor/"outdoor" scenes.
It really isn't much different from floor/ceiling rendering code.
Something else I was thinking was if you flipped it upside down (and kept the current view), you could render "caves"; heck, it probably wouldn't take much effort to mod the current code to achieve this.
Somewhere I have code to a voxel rendering engine someone made in QBasic; they posted a demo of it on youtube, but never posted the code - I got in contact with them, and they sent me a copy of the code. The interesting thing they did, though, was add voxel rendering of "buildings" - you could easily go inside spaces and outside, all voxel rendered, and it was fast (for QB code).
Note - I know about Ken Silverman's voxel and other 3D engines he did in QB (and posted his old code), prior to Duke Nukem 3D - but this wasn't that code; it was completely original...
Anyhow - this is a great little "3D" engine; I'm glad it was posted!
I oftentimes don't know if asking for screenshots is appropriate as I have no idea what's the software is about; so, whenever there are screenshots, I get a sense of relief.
The 20 lines mentioned in the headline refer to the render algorithm itself, not including all the code for map loading, input handling, line drawing and html/css. Basically the lines 51 to 71 in your code.
Sure, my code is only a demonstration that you can fit everything in <100 lines. I remember that there were some sceptics in older HN discussions on this topic... :)
Again, thank you very much for all your education reverse engineering works!
This was a very pleasant read and brought back fond memories of the days of Novalogic Commanche and the followup Commanche 3D, which was one of my favoured network games back in the day - many a Friday afternoon spent blasting co-workers out of the sky ..
Voxels are a pretty neat graphics technology. For the fans of such style, Voxatron (from Lexaloffle, the PICO8 crew) is a pretty great environment for experimenting with the subject - its a fun game, but also a neat design/experimentation environment as well... https://www.lexaloffle.com/voxatron.php
Also brought to mind Vista and VistaPro scenery generation / terrain rendering programs. Used to play with them a lot to produce pictures. Terragen is the only program I know of in that space these days.
I had VistaPro with the Mars maps on my Amiga 2000 and 1200 back in the early 90s; I should dig those machines out someday (no idea if the floppies still work, tho - I have tons of Fred Fish stuff, too)...
This is the first thing that came to mind for me too! I loved VistaPro so much. I got a copy in one of those old programming books you used to buy with the CDs. It also came with PolyRay and some old-school VRML tutorials.
Ever since I played Comanche, I've been asking myself the same thing. I guess they had some real elevation maps and pictures as a base and then made manual changes to add periodicity and color. A half-manual and half-algorithmic approach.
Brings back memories of playing Novalogic Comanche with a Logitech WingMan Extreme. It was an amazing experience at the time. That game was really far ahead of its time.
I really like the animations that illustrate how the algorithms render the final result.
Is that a gameport or USB device? Looks like there are a bunch of adapters out there which will allow legacy gameport sticks/pads to represent themselves as modern xinput controllers.
There were also tricks to extend this simple rendering algorithm to allow limited rotations around the other two axes, to look up / down slightly (just move everything up / down; also implemented in the demo here) and to "lean" when steering left / right (just move everything up / down proportional to the distance from the center of the screen; not implemented in the demo here, but visible in the 1992 NovaLogic Comanche example GIF).
There were Turbo Pascal versions of this on websites in the 90s I think, but it seems they were lost.
Indeed, look up / down is very simple implemented. Just alter the horizon line position. This works for the human eye for small deviations such as ±20°, but will lead to perspective distortions for higher angles.
> There were Turbo Pascal versions of this on websites in the 90s I think, but it seems they were lost.
You can still find a lot of this old code if you dig for it; lot's of it can be found on various SIMTEL MS-DOS ftp archive sites, for instance. I also think the textfiles site has some of it. Also archive.org might have some of it.
Take a look around using google and such: "ftp msdos source code" etc - you'll find plenty to be sure (and even if you don't find what you're looking for, you're sure to find stuff you weren't expecting!)
A short article titled "Voxel Landscapes 2D and 3D By Scout/C-Lous" described most of the tricks, but I can't find the text anywhere. A similar article by the same author on another topic I found here https://github.com/ggnkua/Atari_ST_Sources/blob/master/Docs/...
All these “X in less than Y lines of code” efforts strike me as fundamentally misguided because they seem to confuse succinct notation (short code) with efficient computation. To whit: there’s absolutely nothing preventing anybody whipping together a de facto DSL wherein one can call a single render_terrain( ) function and get the task done with a single token, particularly in today’s environment of dime-a-dozen new programming languages.
I think any piece of code falls on a spectrum, somewhere between "software engineering" (efficient, well documented, etc) and "art" (interesting to look at in some way, someone had fun making it, etc).
The two ends of the spectrum serve completely different purposes but I think both deserve to be appreciated! Just for different reasons. This post (IMO) veers pretty close to the "art" side of the spectrum, so it doesn't make much sense to talk about its efficiency.
I don’t think anyone is saying they are particularly computationally efficient. It’s just an extra limitation to make the process of writing the code more fun. It’s just for entertainment.
> To whit: there’s absolutely nothing preventing anybody whipping together a de facto DSL wherein one can call a single render_terrain( ) function and get the task done with a single token
Yeah they could. But it's not a competition and would anybody care if they did?
> All these “X in less than Y lines of code” efforts strike me as fundamentally misguided because they seem to confuse succinct notation (short code) with efficient computation.
I've never seen any comment about any of them which confused the brevity for computational efficiency, so I don't think that's an issue at all, and don't know where you got that idea.
> To whit: there’s absolutely nothing preventing anybody whipping together a de facto DSL wherein one can call a single render_terrain( ) function and get the task done with a single token
Sure, but they don't, because that's usually not interesting. Leveraging and demonstrating ways to do a task with small amounts of code using tools that are available but flexible enough that they can be applied to other tasks or variations of the task that are not identical, OTOH, is interesting and useful, and tends to be what people do in these things.
Since the article is written in a generic programming language, not a DSL, and has the math derivation and notes on performance, maybe you got confused about what this is? It’s not code golf, it’s demonstrating that this algorithm for terrain rendering is fundamentally expressable in a small amount of code.
> To whit: there’s absolutely nothing preventing anybody whipping together a de facto DSL
That’s true, but that’s not what happened here, the author did not write a DSL, so this is not a valid example of your first sentence. As such, your phrase ‘to whit’ is misused, the phrase is synonymous with ‘specifically’. Also just FYI it’s spelled ‘to wit’.
Downvotes always feel pretty harsh, but it helped me a lot to realize that downvotes are usually impersonal. Think about downvotes as symmetric with upvotes; upvotes don’t need justification, and they are given for a wide variety of reasons. Same with downvotes.
In any case, I find it best to start by assuming not that people are getting rubbed the wrong way, but that I actually wrote something incorrect and didn’t know it. The primary reason downvotes are given is for information that is either incorrect or irrelevant to the thread. Without passing judgement or being upset, it is safe to say your top comment is incorrect about this article, and thus irrelevant here.
I realize that justifying downvotes or continuing to talk on a thread that’s gone south doesn’t necessarily make you feel any better, but I honestly hope that helps. These things have helped me in the past.
I didn’t mean to come across as ‘complaing’ about downvotes, just as I didn’t mean to offend anybody with my comment (which admittedly was rather generic and probably not a specific response to the posted article, rather something I’d been meaning to get off my chest for a while).
I just hope I didn’t come across as dismissive, because that wasn’t my intention.
People weren't offended by your comment, it was just ignorant. 8 of these 20 lines are comments, so it is not code golf, just a very simple algorithm that anyone can read and understand. If you wish to not get down voted in the future you should probably try to read and understand things before commenting.
Thanks for your feedback, I think my comment history can stand as testament to the fact that broadly speaking I generally know what I’m talking about.
As for your charge of ignorance, that’s your call to make, but you seem to be missing the point I was trying to make (and which I obviously articulated very poorly), namely that code length and complexity is an interaction between both the algorithm being encoded and the formalism into which it is being encoded (programming language).
Code length correlates with complexity if you don't go out of your way to game it, so it is still a valid way to say "this renderer is really simple and cool!".
No it isn't. Are you counting the total lines of library code you're calling also? Total number of machine instructions generated? This attitude you have, that only the Y lines of code in your high level language floating way up in the clouds is the only thing that matters, is one of the key reasons why bloated, shit code is being constantly written and shoveled upon the masses. You don't know about the underlying complexity, and apparently don't care to know.
I also remember 'mars.com', that I guess I found on some bbs, which was basically just the terrain renderer you could roam about in a very basic heightmap that was coloured to resemble mars. I think I saw that before comanche, and it was fast on fairly mediocre pc back then.
I don't know if it is just me and the appeal to the stuff I grew up with, but I find the style of the visual artefacts a lot more appealing than in many more modern rendering techniques. Perhaps it is just the simplicity of it.
> I find the style of the visual artefacts a lot more appealing than in many more modern rendering techniques. Perhaps it is just the simplicity of it
Looking at the visual artefacts in question, it appears that the big chunks of pixels (the ones closer to the POV) are not regularly aligned on screen, but rather disseminated around, which I guess improves the render quite a bit by giving it a somewhat "fuzzier", more organic look.
Maybe this irregularity is a side effect of the algorithm itself, and not something done on purpose?
I don't know why you get that message. The content is set to 'public'. I just tested it on another computer, without login into Facebook, and it worked fine.
mars.exe has only a size of 5.6kB. When you disassemble the code you realize that most of the code consists of just massive loop unrolling. It would have fitted in 2kB easily.
For anyone wondering what he means by /fast/. mars.com ran at 30+ fps on a 12MHZ 286 with a slow VGA video card. I still remember being impressed by how smooth it was. It was fast fast fast.
The way the slices render in the image examples reminded me of TerraGen and setting my computer to render a simple animation overnight while I slept, and hoping it didn't crash.
I remember playing with TerraGen back when the original programmer of it was coding it in VB5 and 6 - it was so amazing to see back then, it's too bad the VB source code wasn't ever released.
@s-macke very cool article, it brings me back. :) Thanks for the write up.
Regarding speeding it up & drawing front-to-back, didn’t some games do a back-to-front with some kind of bounds on how far down they draw? That way you get speed up without needing the y-buffer memory. I remember that in some games you could sometimes see cracks in the terrain, and I’m guessing from my faded memory that it was bounding the vertical draw. Not entirely sure if I’m remembering seeing cracks in sprite-drawn terrain though.
I was also wondering about the “Rotation” animated gif example, some extra mountains show up on the right side in the 360 spin for a couple of frames while the camera is passing the far end of the river, just before the pyramid comes into view. Is that just a bug, or is it something about the algorithm that’s tricky to fix?
> That way you get speed up without needing the y-buffer memory.
I mean, the "Y-buffer" memory is just one integer per column, pretty trivial even for a software rasterizer on an early 90s machine with a limited cache hierarchy. Pretty much any algorithm that has overdraw will lose to that. That's why this technique was so popular in the nineties—what Doom did was just a generalization of this idea to allow multiple sparse pixel spans per column instead of just one. (For comparison, Z-buffer bandwidth is expensive because it's an extra 16/24/32 bits per pixel, which can double your fill rate requirements.)
Oh yeah, you’re totally right, please chalk that up to pre-coffee brain fart, I wasn’t thinking about the size and stupidly assumed it was on the same order as z-buffer.
Such good points and so obvious (now that you said them) that first I really want to retract my comment and second now I feel like coding up a terrain generator today. Duh, Doom did (famously) switch the loops for similar reasons!
Indeed, switching the loops is valid and might or might not give you an additional speedup. I had hoped, that someone figures this out :-).
However I think in order to understand the basic algorithm the way in the readme is the better one.
Do you know of referenceable pseudocode (or real code) for that somewhere? I've tried modifying your code to switch the loops, but it always comes out garbled; clearly I'm messing up somewhere in the refactoring process, but I don't have enough experience with this algorithm to figure out where!
The rotation artifacts you see are a result of the very simple algorithm and the property of the viewing triangle. It renders objects that are farther away when they are near the border of the viewing screen.
In the pseudo code in the readme just calculate the (square) distance between pleft and p and don't draw the line if the distance is larger than a given threshold. But this is not very efficient.
When you switch the loops this will be easier because this check can be done in the outer loop.
But I would suggest to experiment with some fog effect first.
Turns out it can be made quite efficient with a little effort put into arithmetic power reduction. In the outer loop, it is possible to calculate a `dr` value from the existing `dx` and `dy`. Then you just increment the radius traveled at the same time as `px` and `py`, and replace the inner loop condition that puts a bound on `z` with a new condition that puts a bound on the radius.
That fixes the rotation artifacts, and then makes it really easy to add a distance-based fog effect to hide the cut-off where new terrain comes into view as well.
How many more lines do you need if you want to capture the natural “roughness”, but you also want to guarantee some plateaus, such a for building on in a simulation game?
Or, to put that another way: what does the code in Sim City 2000’s terrain generator look like? Because it’s almost just doing this, but then it has that one extra thing...
Sim City is 2000 is isometric, it doesn't have perspective. You just need to overlay 2d bitmaps of the prerendered tiles and assets on top, drawn back to front, bottom to top.
A bit of self-promo, but for those interested I also am using a variation of this algorithm powered by compute shaders. See https://twitter.com/voxelquest. If you scroll down a bit, you can even see versions using the maps from Comanche shown in this demo. :)
(Also, thank you @s-macke, your github page taught me the fundamentals of the algorithm - previously I had only seen Ken Silverman's post on wave surfing, which was not nearly as clear).
119 comments
[ 4.5 ms ] story [ 74.5 ms ] threadAnother World (Out Of This World) featured a couple of days ago hightlights this also, imho.
And fun, I had plenty while playing these games. Increasing computing power improves immersion and realism, which certainly improves the entertainment; but the fun? Not obvious to me.
Anyways, it seems new Comanche game is on the way!
It really isn't much different from floor/ceiling rendering code.
Something else I was thinking was if you flipped it upside down (and kept the current view), you could render "caves"; heck, it probably wouldn't take much effort to mod the current code to achieve this.
Somewhere I have code to a voxel rendering engine someone made in QBasic; they posted a demo of it on youtube, but never posted the code - I got in contact with them, and they sent me a copy of the code. The interesting thing they did, though, was add voxel rendering of "buildings" - you could easily go inside spaces and outside, all voxel rendered, and it was fast (for QB code).
Note - I know about Ken Silverman's voxel and other 3D engines he did in QB (and posted his old code), prior to Duke Nukem 3D - but this wasn't that code; it was completely original...
Anyhow - this is a great little "3D" engine; I'm glad it was posted!
https://github.com/true-grue/terrain
Looks like Python+Tkinter is a good demoscene platform where you have performance of graphics close to 286/EGA :)
Again, thank you very much for all your education reverse engineering works!
Voxels are a pretty neat graphics technology. For the fans of such style, Voxatron (from Lexaloffle, the PICO8 crew) is a pretty great environment for experimenting with the subject - its a fun game, but also a neat design/experimentation environment as well... https://www.lexaloffle.com/voxatron.php
Was these hand drawn by an artist or generated in some way? Any info about it exists?
I really like the animations that illustrate how the algorithms render the final result.
Low priority to find a current flight stick.
There were Turbo Pascal versions of this on websites in the 90s I think, but it seems they were lost.
You can still find a lot of this old code if you dig for it; lot's of it can be found on various SIMTEL MS-DOS ftp archive sites, for instance. I also think the textfiles site has some of it. Also archive.org might have some of it.
Take a look around using google and such: "ftp msdos source code" etc - you'll find plenty to be sure (and even if you don't find what you're looking for, you're sure to find stuff you weren't expecting!)
Searching for "voxel" in https://github.com/nickelsworth/swag/ also finds some very similar tiny Turbo Pascal programs.
The two ends of the spectrum serve completely different purposes but I think both deserve to be appreciated! Just for different reasons. This post (IMO) veers pretty close to the "art" side of the spectrum, so it doesn't make much sense to talk about its efficiency.
Yeah they could. But it's not a competition and would anybody care if they did?
I've never seen any comment about any of them which confused the brevity for computational efficiency, so I don't think that's an issue at all, and don't know where you got that idea.
> To whit: there’s absolutely nothing preventing anybody whipping together a de facto DSL wherein one can call a single render_terrain( ) function and get the task done with a single token
Sure, but they don't, because that's usually not interesting. Leveraging and demonstrating ways to do a task with small amounts of code using tools that are available but flexible enough that they can be applied to other tasks or variations of the task that are not identical, OTOH, is interesting and useful, and tends to be what people do in these things.
> To whit: there’s absolutely nothing preventing anybody whipping together a de facto DSL
That’s true, but that’s not what happened here, the author did not write a DSL, so this is not a valid example of your first sentence. As such, your phrase ‘to whit’ is misused, the phrase is synonymous with ‘specifically’. Also just FYI it’s spelled ‘to wit’.
In any case, I find it best to start by assuming not that people are getting rubbed the wrong way, but that I actually wrote something incorrect and didn’t know it. The primary reason downvotes are given is for information that is either incorrect or irrelevant to the thread. Without passing judgement or being upset, it is safe to say your top comment is incorrect about this article, and thus irrelevant here.
Also, note the guidelines ask to not complain about downvotes, which is why the immediate comment above is getting them. See “In comments” https://news.ycombinator.com/newsguidelines.html
I realize that justifying downvotes or continuing to talk on a thread that’s gone south doesn’t necessarily make you feel any better, but I honestly hope that helps. These things have helped me in the past.
I didn’t mean to come across as ‘complaing’ about downvotes, just as I didn’t mean to offend anybody with my comment (which admittedly was rather generic and probably not a specific response to the posted article, rather something I’d been meaning to get off my chest for a while).
I just hope I didn’t come across as dismissive, because that wasn’t my intention.
As for your charge of ignorance, that’s your call to make, but you seem to be missing the point I was trying to make (and which I obviously articulated very poorly), namely that code length and complexity is an interaction between both the algorithm being encoded and the formalism into which it is being encoded (programming language).
Anyway, I’ll leave it at that. Have a good day.
You did, at the point where you said "misguided".
I don't know if it is just me and the appeal to the stuff I grew up with, but I find the style of the visual artefacts a lot more appealing than in many more modern rendering techniques. Perhaps it is just the simplicity of it.
Looking at the visual artefacts in question, it appears that the big chunks of pixels (the ones closer to the POV) are not regularly aligned on screen, but rather disseminated around, which I guess improves the render quite a bit by giving it a somewhat "fuzzier", more organic look.
Maybe this irregularity is a side effect of the algorithm itself, and not something done on purpose?
I remember it taking about an hour per 800x600 frame, and then we got a new computer and it only took 3-4 minutes per frame.
P.S. This code is not mine, the author has made an effort after seeing the documentary on fractals.
[1]https://github.com/dafarry/python-fractal-landscape
Regarding speeding it up & drawing front-to-back, didn’t some games do a back-to-front with some kind of bounds on how far down they draw? That way you get speed up without needing the y-buffer memory. I remember that in some games you could sometimes see cracks in the terrain, and I’m guessing from my faded memory that it was bounding the vertical draw. Not entirely sure if I’m remembering seeing cracks in sprite-drawn terrain though.
I was also wondering about the “Rotation” animated gif example, some extra mountains show up on the right side in the 360 spin for a couple of frames while the camera is passing the far end of the river, just before the pyramid comes into view. Is that just a bug, or is it something about the algorithm that’s tricky to fix?
I mean, the "Y-buffer" memory is just one integer per column, pretty trivial even for a software rasterizer on an early 90s machine with a limited cache hierarchy. Pretty much any algorithm that has overdraw will lose to that. That's why this technique was so popular in the nineties—what Doom did was just a generalization of this idea to allow multiple sparse pixel spans per column instead of just one. (For comparison, Z-buffer bandwidth is expensive because it's an extra 16/24/32 bits per pixel, which can double your fill rate requirements.)
Another trick I now remember was to interpolate the color values on such a y-segment, to reduce the pixelated look.
https://www.pastiebin.com/5e10d48ac6595
Just exchange the Render() method in my VoxelSpace.html file with the pastie.
That fixes the rotation artifacts, and then makes it really easy to add a distance-based fog effect to hide the cut-off where new terrain comes into view as well.
Or, to put that another way: what does the code in Sim City 2000’s terrain generator look like? Because it’s almost just doing this, but then it has that one extra thing...
(Also, thank you @s-macke, your github page taught me the fundamentals of the algorithm - previously I had only seen Ken Silverman's post on wave surfing, which was not nearly as clear).