28 ms·
Terrain rendering algorithm in less than 20 lines of code
- rcarmo 7y agoThis is _really_ nice. Captures that Comanche feel I had playing the original game many, many years ago on my first VGA card. :)
- netgusto 7y agoSame. 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.
- baq 7y agoi've had major Magic Carpet vibes.
- pjmlp 7y agoMe too, I spent countless hours playing flight sims since the 48K days, including Comanche.
- Abishek_Muthian 7y agoComanche 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!
- newzombie 7y agoThis 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 7y agoIt 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 7y agoProps 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 7y agoCouldn't agree more with you.
- aliveupstairs 7y agoI 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 7y agoI believe asking and could even warrant openning an issue with said repo!
- overcast 7y agoAlways amazes me this is overlooked, especially for graphical projects. Why leave it out, do they not want to show off what they made??
- richard_shelton 7y agoHere is my simple port of VoxelSpace (74 sloc). Written in Python 3, no additional libraries required. https://github.com/true-grue/terrain 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 7y agoThe 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 7y agoSure, 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!
- ArmandGrillet 7y agoReally cool project! If you like artsy and short code snippets https://twitter.com/hashtag/tweetcart https://twitter.com/hashtag/tweetcart is also a great source of awe.
- jpxw 7y agoAlso dwitter.net
- hydgv 7y agoIf you use Brave you have to enable device recognition attempts or you won't see anything. https://i.imgur.com/QYIBFVO.png https://i.imgur.com/QYIBFVO.png
- somesortofsystm 7y agoThis 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 https://www.lexaloffle.com/voxatron.php
- Twirrim 7y agoAlso 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.
- cr0sh 7y agoI 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)...
- somesortofsystm 7y agoDo it. Mars awaits! :)
- feiss 7y agoAh, memories! Sooo many hours playing with Vista pro and Mars.. :_)
- cottenio 7y agoThis 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.
- bni 7y agoI 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 7y agoEver 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.
- rejschaap 7y agoBrings 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 7y agoUsed a Logitech Wingman 3D... Win10 doesn't even recognize it as a device. Low priority to find a current flight stick.
- mikepurvis 7y agoIs 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.
- deleted 7y ago[deleted]
- pjtr 7y agoThere 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 7y agoIndeed, 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.
- pjtr 7y agoSame 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 :)
- s-macke 7y agoCool, that works!
- cr0sh 7y ago> 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!)
- qubex 7y agoAll 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.
- pickledish 7y agoI 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 7y agoIt’s probably not so much a spectrum as it is a pair of orthogonal axes.
- sweetheart 7y agoI 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.
- nkrisc 7y ago> 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?
- dragonwriter 7y ago> 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.
- scoopr 7y agoI 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 7y ago> 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?
- magoghm 7y agoAfter 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/UzpfSTY3NzQ3ODczNDpWSzoxMDE1MzgxOTk2ODEwODczNQ/ https://www.facebook.com/magoghm/videos/10153819968108735/Uz...
- marcusjt 7y agoI get "The link you followed may be broken, or the page may have been removed." - likely you've not made the content "public"
- magoghm 7y agoI 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.
- notkaiho 7y agoThe 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 7y agoTerragen 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 7y agoI 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.
- soulofmischief 7y agoThis repo helped me when I was implementing my own 2.5D voxel engine. I definitely recommend tearing through it for anyone interested.
- Abishek_Muthian 7y agoThis 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 https://github.com/dafarry/python-fractal-landscape
- sebastianconcpt 7y agoI still remember the Comanche feelings :D It was glorious
- dahart 7y ago@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 7y ago> 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 7y agoOh 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.
- pjtr 7y agoEven 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.
- 7y ago
- derefr 7y agoHow 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 7y agoSim 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.
- hcarvalhoalves 7y agoIngenious! The terrain looks realistic for such a simple technique, specially w/ well chosen colours (check the C13 and C16 maps on the live demo).
- m3kw9 7y agoLove the readme, maybe that is the star of the show
- gavanwoolery 7y agoA 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 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 7y agoAha, I've been following your main account but didn't know this one existed. Definitely impressive!
- gavanwoolery 7y agoHaha, yep, because this account retweets gavanw and not the other way around. But the links are cleverly "hidden" in my profile. :)
- Drakim 7y agoVery 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?
- amelius 7y agoIt seems that stuff randomly appears/disappears between the horizon and some line that substitutes for the real horizon.
- lostgame 7y agoIs there a practical way to achieve better draw distance? The horizon seems superficially low.
- Jare 7y agoDraw distance can be as high as you want, you just need a big enough map.
- emilfihlman 7y agoKeyboard controls not working for anyone else?
- krossitalk 7y agoSame here. Does this only work with firefox? Edit - nope doesn't work at all. Same with the 'distance' slider.
- swashbuck1r 7y agoI 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 https://github.com/s-macke/VoxelSpace/pull/13. The distance rendering works once you move and force a redraw.
- tomduncalf 7y agoFantastic 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!
- ben7799 7y agoGreat 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 7y agoI imagine it would be very sad, when you then realise how many wasted cycles our CPUs are doing versus those days.
- gibolt 7y agoThose cycles enable much higher level operations. Still tons of wasted effort, but hopefully development time for the same complexity is significantly reduced.
- pjmlp 7y agoYeah like Electron based apps, sigh.
- soylentgraham 7y agoI think you just proved the point. If we didn't have this high level, easy-to-produce abstraction... you wouldn't have even heard of slack and electron. Yet it enabled people to create something a lot of people use :)
- everyone 7y agoI was just wondering what other metrics are there for code other than 'lines of code' Cus I could write some stuff in one line of code. But that one line would be horrendously unmaintainable. What metrics are there for maintainability (the most important aspect of code imo) If there was a hard measure you could put on granularity for example.. Instead of saying hey I wrote this in 10 lines, you'd say hey I wrote this with 90 fleeborps of granularity! its super-maintainable! ps. Not meant as a sly criticism of this. I have not even looked at the code. Just the 'lines of code' in the title sparked that thought. This thing is awesome! Just a few days ago I was chcking out Commanche Maximum overkill videos.. in 1992 that was mindblowing!
- floki999 7y agoVery cool. Reminds me of reading the now-defunct Game Developer magazine years ago.
- technomalogical 7y agoI'll have to check out some of the old issues, I thought it was more of an industry magazine and not covering algorithms or coding. Archive.org has most (all?) issues in a collection: https://archive.org/details/game_developer_magazine https://archive.org/details/game_developer_magazine
- kvark 7y agoI recently implemented the painters algorithm in a modern-ish way: using atomic ops in a compute shader. That's one of the rendering techniques for the terrain in https://github.com/kvark/vange-rs https://github.com/kvark/vange-rs