[HN Gopher] Terrain rendering algorithm in less than 20 lines of...
___________________________________________________________________
Terrain rendering algorithm in less than 20 lines of code
Author : netgusto
Score : 534 points
Date : 2020-01-03 09:48 UTC (13 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| soulofmischief wrote:
| This repo helped me when I was implementing my own 2.5D voxel
| engine. I definitely recommend tearing through it for anyone
| interested.
| richard_shelton wrote:
| Here is my simple port of VoxelSpace (74 sloc). Written in Python
| 3, no additional libraries required.
|
| 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 :)
| s-macke wrote:
| 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.
| richard_shelton wrote:
| 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!
| hcarvalhoalves wrote:
| Ingenious! The terrain looks realistic for such a simple
| technique, specially w/ well chosen colours (check the C13 and
| C16 maps on the live demo).
| somesortofsystm wrote:
| 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
| Twirrim wrote:
| 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.
| cottenio wrote:
| 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.
| feiss wrote:
| Ah, memories! Sooo many hours playing with Vista pro and
| Mars.. :_)
| cr0sh wrote:
| 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)...
| sebastianconcpt wrote:
| I still remember the Comanche feelings :D It was glorious
| tomduncalf wrote:
| Fantastic description of how voxel rendering works with a really
| great illustration, I had no idea it was that "simple". I
| remember the Comanche game mentioned in the README, it was
| amzaing graphically for the time!
| m3kw9 wrote:
| Love the readme, maybe that is the star of the show
| gavanwoolery wrote:
| 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).
| mysterydip wrote:
| Aha, I've been following your main account but didn't know this
| one existed. Definitely impressive!
| gavanwoolery wrote:
| Haha, yep, because this account retweets gavanw and not the
| other way around. But the links are cleverly "hidden" in my
| profile. :)
| emilfihlman wrote:
| Keyboard controls not working for anyone else?
| swashbuck1r wrote:
| I was confused by this too. Clicking and dragging with the
| mouse (or at least touchpad) works for navigation. The HTML
| canvas element key events aren't working (maybe they worked .
| in older browsers). There is an open PR that hooks window
| events instead (I made similar edits locally that make it
| work). https://github.com/s-macke/VoxelSpace/pull/13. The
| distance rendering works once you move and force a redraw.
| krossitalk wrote:
| Same here. Does this only work with firefox? Edit - nope
| doesn't work at all. Same with the 'distance' slider.
| bni wrote:
| I find the 2D color maps beautiful for some reason, despite their
| simplicity.
|
| Was these hand drawn by an artist or generated in some way? Any
| info about it exists?
| s-macke wrote:
| 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.
| scoopr wrote:
| 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.
| netgusto wrote:
| > 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?
| spitfire wrote:
| 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.
| JackRabbitSlim wrote:
| http://www.pouet.net/prod.php?which=4662
| magoghm wrote:
| After seeing 'mars.com' I decided to write write a game using
| that terrain algorithm. I never finished the game, but here is
| a video of one of my tests:
| https://www.facebook.com/magoghm/videos/10153819968108735/Uz...
| marcusjt wrote:
| I get "The link you followed may be broken, or the page may
| have been removed." - likely you've not made the content
| "public"
| magoghm wrote:
| 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.
| squarefoot wrote:
| I can confirm it works here. Very low resolution, but
| watchable.
| marcusjt wrote:
| Here's a video of it in action, for those unfamiliar, the
| poster had also included a link to its location at Pouet
| https://youtu.be/_zSjpIyMt0k
| s-macke wrote:
| 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.
| ben7799 wrote:
| Great article.
|
| I wonder at the speed of this on a modern machine vs an assembly
| version running in dos on a 1992 machine. A benchmark of
| interpreted code on a modern OS + machine vs bare metal native
| code written in the 1992 style on an old machine would be
| interesting.
|
| I remember when Comanche came out... the 1990s were like the
| Heyday of flight sim games and Comanche was mind-blowing at the
| time as a teen. They were my favorite by far type of game. At
| some point it feels like they really died out. There were a lot
| of games that had a happy medium of fun vs realistic/complex back
| then.
|
| At some point the # of flight sim type games plummeted and the
| ones that stuck around bifurcated into hyper-realistic to the
| point they are a time suck (cause you could be using an actual
| real flight sim for real flight training) or they are hopelessly
| unrealistic and no fun compared to the old stuff.
|
| Not sure but I might disagree with the author about Comanche
| being 3 years ahead of it's time. It might have been closer to 5
| years ahead of it's time. You didn't get stuff that really blew
| it away till hardware acceleration became prevalent, but by that
| time 3D FPS games were demolishing the flight sim market.
| pjmlp wrote:
| I imagine it would be very sad, when you then realise how many
| wasted cycles our CPUs are doing versus those days.
| gibolt wrote:
| Those cycles enable much higher level operations. Still tons
| of wasted effort, but hopefully development time for the same
| complexity is significantly reduced.
| pjmlp wrote:
| Yeah like Electron based apps, sigh.
| Abishek_Muthian wrote:
| This was nice, here is a code[1] for Python Fractal Mountain
| Landscape in 20 lines i.e. if you ignore the Mayavi import.
|
| 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
| derefr wrote:
| 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...
| ant6n wrote:
| 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.
| dahart wrote:
| @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?
| pcwalton wrote:
| > 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.)
| dahart wrote:
| 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.
| s-macke wrote:
| 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.
| esrauch wrote:
| I wonder if you could nearly as efficiently draw to fixed
| distance arcs instead of perpendicular to viewing area lines
| to avoid that effect?
| s-macke wrote:
| 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.
| pjtr wrote:
| Even drawing front-to-back you don't need the y-buffer, if you
| switch the loops: for x ... for y ...
|
| Another trick I now remember was to interpolate the color
| values on such a y-segment, to reduce the pixelated look.
| dahart wrote:
| 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!
| s-macke wrote:
| 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.
| rejschaap wrote:
| 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.
| zentiggr wrote:
| Used a Logitech Wingman 3D... Win10 doesn't even recognize it
| as a device.
|
| Low priority to find a current flight stick.
| mikepurvis wrote:
| 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.
| Drakim wrote:
| Very cool. I've ported it and played around a bit now. Anybody
| got any pointers on how I might add arbitrary flat sprites like
| trees to the mix?
| [deleted]
| ArmandGrillet wrote:
| Really cool project! If you like artsy and short code snippets
| https://twitter.com/hashtag/tweetcart is also a great source of
| awe.
| jpxw wrote:
| Also dwitter.net
| qubex wrote:
| 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.
| dahart wrote:
| 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'.
| nkrisc wrote:
| > 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?
| qubex wrote:
| Judging by the downvotes I've really rubbed a lot of people up
| the wrong way.
| dahart wrote:
| 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.
|
| 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.
| qubex wrote:
| Thank you for your kind words.
|
| 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.
| pjc50 wrote:
| > I just hope I didn't come across as dismissive,
|
| You did, at the point where you said "misguided".
| username90 wrote:
| 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.
| qubex wrote:
| 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).
|
| Anyway, I'll leave it at that. Have a good day.
| username90 wrote:
| 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!".
| dragonwriter wrote:
| > 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.
| pickledish wrote:
| 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.
| qubex wrote:
| It's probably not so much a spectrum as it is a pair of
| orthogonal axes.
| sweetheart wrote:
| 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.
| rcarmo wrote:
| This is _really_ nice. Captures that Comanche feel I had playing
| the original game many, many years ago on my first VGA card. :)
| baq wrote:
| i've had major Magic Carpet vibes.
| pjmlp wrote:
| Me too, I spent countless hours playing flight sims since the
| 48K days, including Comanche.
| Abishek_Muthian wrote:
| 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!
| netgusto wrote:
| 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.
| hydgv wrote:
| If you use Brave you have to enable device recognition attempts
| or you won't see anything. https://i.imgur.com/QYIBFVO.png
| pjtr wrote:
| 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.
| s-macke wrote:
| 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 +-20deg, but will lead to perspective
| distortions for higher angles.
| pjtr wrote:
| Same with leaning. Add one more line of code and tweak the
| draw call: var ylean =
| (input.leftright*(i/screenwidth-0.5) + 0.5) *
| screendata.canvas.height / 4; DrawVerticalLine(i,
| heightonscreen+ylean, hiddeny[i]+ylean,
| map.color[mapoffset]);
|
| It adds a lot to the "feeling" IMO :)
| cr0sh wrote:
| > 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!)
| pjtr wrote:
| The one I remember was "voxel.pas by Steven H Don". A Delphi
| port survived here:
| http://tothpaul.free.fr/sources.php?dprgrp.voxel
|
| Searching for "voxel" in
| https://github.com/nickelsworth/swag/ also finds some very
| similar tiny Turbo Pascal programs.
| pjtr wrote:
| 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/ggn
| kua/Atari_ST_Sources/blob/master/Docs/...
| lostgame wrote:
| Is there a practical way to achieve better draw distance? The
| horizon seems superficially low.
| Jare wrote:
| Draw distance can be as high as you want, you just need a big
| enough map.
| amelius wrote:
| It seems that stuff randomly appears/disappears between the
| horizon and some line that substitutes for the real horizon.
| notkaiho wrote:
| 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.
| CrazyStat wrote:
| Terragen is still going strong but it's been about 15 years
| since I played with it.
|
| 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.
| cr0sh wrote:
| 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.
| newzombie wrote:
| 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.
| cr0sh wrote:
| 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!
| SteveSmith16384 wrote:
| Props for a great readme as well. I wish more open source
| included at least a screenshot so you can see what it actually
| is.
| kburman wrote:
| Couldn't agree more with you.
| overcast wrote:
| Always amazes me this is overlooked, especially for graphical
| projects. Why leave it out, do they not want to show off what
| they made??
| aliveupstairs wrote:
| 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.
| idclip wrote:
| I believe asking and could even warrant openning an issue
| with said repo!
___________________________________________________________________
(page generated 2020-01-03 23:00 UTC)