Fit An Entire Planet In 90k 122
missingmatterboy points out this "interview with Dr. Ken "Doc Mojo" Musgrave, a computer graphics pioneer who worked with Benoit Mandelbrot generating fractal landscapes and who's designed custom shaders for Hollywood movies. His latest project is called MojoWorld and it uses the power of math to generate infinite-resolution fractal landscapes? one entire planet at a time. It's going to have an open SDK and, to top it all off, a Linux version is also in the works." This is a fascinating project.
/.ed already! (Score:5, Informative)
If you have to see the images, BryceWorld got a beta release and posted a gallery [cyberjournies.com] of images online.
And if you want to download it immediately to start playing with it, you can do it by filling out this questionairre [pandromeda.com]
Re:/.ed already! (Score:2)
Re:/.ed already! (Score:1)
Rebuild Planet Earth (Score:2, Interesting)
Old news... (Score:5, Interesting)
I've seen some with complete weather and day/night cycles. Some really inspiring stuff.
Re:Old news... (Score:2)
Re:Old news... (Score:1)
Re:Old news... (Score:5, Informative)
Well the thing is Ken Musgrave is one of the pioneers, if anything a lot of people that have posted code like this out there are based on Ken's numerous papers. He was a researcher with Mandelbrot, kinda developed "multifractals", given SIGGRAPH courses about terrain and procedural modeling, and has written several chapters for a great book "Texturing and Modeling: A Procedural; Approach". He also worked for a time for or at Digital Domain, doing code a for the moon on Apollo 13, and procedural smoke for Dante's Peak (not used) and Titanic.
Here is his webpage:
Ken Musgrave's website [wizardnet.com]Saw Mojoworld briefly at SIGGRAPH and it looked neat.
Wowee (Score:1)
Whatch Yuo Want Miss,Betelguese?
Marginal (Score:5, Interesting)
Planets would move, trees would grow, forests and deserts would change shape, oceans would rise and recede, etc. (Taking into account that the planet is of the type to support something like forests and oceans). The variables that define a "place" as a human looking onto the universe were coordinates and time, and a perspective (direction/angle) from which to project back information. Yet the visual perspective was only minor compared to the actual number of calculable variables, like temperature, and the like. Of course, strange things like density has to be accounted for with Newtonian physics, but that was ironically easy. Choosing what was the cause (is temperature random, ie. fractalish, or a product of Newtonian; really it's a combination; random in a Newtonian'ish thermodynamic space, but random only because we wouldn't actually want to calculate that sort of thing) and what was an effect was the hard part.
It is an interesting premise, isn't it? Taking a mathematical curiosity (the fractal) and doing something useful with it like creating a universe, or planet in this case. Somewhat matrix'ish.
Re:Marginal (Score:1)
Re:Marginal (Score:1)
Re:Marginal (Score:1)
Isn't that Shadowbane [ubisoft.com]? I heard they were doing something similar, being able to add continents in real time over a modem connection, no more massive "EQ-like" downloads. Curious if thats the game you talking about, I havent played it.
Re:Marginal (Score:2)
Thanks to chaos, one could insert minor changes into the variables, so a line of a lorenz equation could be completely changed down the road by adding small (read: negligable) attractors. Lorenz isn't a good choice, IMHO, but it's an example of a simple, obvious case where small attractors would change things invariably. People adding attractors to a game universe fractal is a much niftier idea; just much more complex.
Re:Marginal (Score:1)
We're aiming for something along these lines at www.legacy-ovwp.org. The goal for now is a single-player story-driven game, however we make every part as reusable as possible and introducing MMORPG to the engine shouldn't be a problem once it's done as we're very aware of the game probably evolving there sometime.
The site looks somewhat dead and messy because we mostly communicate on IRC and mail these days, it's by no means as dead as it looks! (We have many mails between us a day in laying this out and a well developed source tree). If anyone wants to help us out then simply mail one of us (find mine or JPNotADragon's email address there) and you'll probably have a response the same day.
Re:Marginal (Score:2)
--
Evan
Re:The galaxy in the palm of your hand (Score:2)
The earth is in somebody hands for sure (Score:1)
"The Galaxy is on Orion's Belt" (Score:2)
:-)
Don't tell Slartibartfast.... (Score:5, Funny)
Re:Don't tell Slartibartfast.... (Score:1)
Re:Don't tell Slartibartfast.... (Score:1)
Re:Don't tell Slartibartfast.... (Score:2)
Excellent! (Score:1)
Re:Excellent! (Score:4, Informative)
What about, for example, Frontier: Elite2 which pretty much pioneered planet wide fractal terrain gen in a commercial game and ran on a 386.
Or, its sequel, Frontier: First Encounters which added texturing to make everything look a million times more ugle.
Or any of the recent fan-made clones, Millenium3 http:://m3fe.com or even The Eternal Project http://compsoc.net/~flend/tep/.
Frontier (Score:2)
This was one of the most amazing games I'd ever seen at the time, becuase the player is completely free to go anywhere in the "universe" and do anything. I think the discovery of "wormholes" (from a 16-bit overflow bug) also added quite an interesting element to it as well (That's not a bug, it's a feature!).
Don't forget the fractal-nature of the Frontier universe as well. I doubt they could have fit all of that data in the game! It was quite interesting how whole solar systems were created around each star, with different planet types and numbers, different political situations, random natural and manufactured satellites, different star configurations (double and triple systems). I suppose this was all seeded from the same value, or it would have been different every time.
I wish there were an upgraded game like Frontier, which took advantage of modern computer systems, but still contained all of the elements of the original. I'd love to see such a game as a massive-multiplayer-online sort of game. I'll check those links you provided and see what those are like...
Re:Frontier (Score:1)
Re:Excellent! (Score:2, Funny)
The Eternal Project - what an ironically true to form name
Re:Excellent! (Score:1)
On a personal note, that game probably did more to get me hooked on PC gaming than any other.
Re:Excellent! (Score:2)
Each world is a coordinate in a matrix of worlds (Score:2, Informative)
Since the product doesn't store individual worlds, but rather parameters for a procedural system... or a point in parametric hyperspace... the data file for a single world isn't large. Each individual world only needs to be defined with a set of n-dimensional coordinates. I don't do much playing with things like bryce or whatever (can't afford it) but if I'm not mistaken that is a significantly different paradigm. What I didn't see is how large the executable was that generated the worlds dynamically from the n-dimensional parameter vector or hyperspatial coordinates. Technically the program wouldn't have to be large either, but I'm curious...
90K! (Score:2, Troll)
I bet a 'make world' will go a lot faster then
volumetric pixels (Score:4, Interesting)
fractals are good for storeing large amounts of information but decompression is hard and how do you then represent the information useing standard methods or volumetric pixels type approach ?
seems nice but I would like more details before makeing any jugment
anyone have details ?
regards
john jones
p.s. I am sure a game used this type of thing before
Re:volumetric pixels (Score:1)
Yep.
I remember "Strike Commander" built its terrain maps this way. (Fractals + smoothing + texture + objects)
(back in '92 ? '93 ? )
... ten 1.44 Mb disquettes, 1hr of fractal stuff on my good ole 386...
Re:volumetric pixels (Score:1)
You have it backwards, if you want an exact or even a lossy representation of an image using fractals then compression is a very difficult problem. Decompression on the other hand is simply iterating a usually simple function, or a small set of functions. Since you can estimate the costs of calculating the function and the number off times you iterate is related to the level of detail you present you can calculate the level of detail you can represent given available compute power and time constraints.
The information is entirely parametric, you specify what region you are interested in and level of detail, then you get a texture back.
I'm a little lazy so I'm not going to give links, but a simplwe query (like "fractals" or "fractal compression") on Google should provide plenty of jumping off points.
Looks quite cool, but not photorealistic (Score:5, Interesting)
I have been working on terraform [sourceforge.net] (which is aimed more at the generation and manipulation of digial terrain rather than the rendering of it) for a while now and in the course of doing so have learned a few things about fractal terrain generation. The fact that you can regenerate the terrain from a few seed parameters is not that special (dimension, scale factor, random seed, etc); these are the kind of parameters that are typically passed to these functions anyways. The more interesting thing (to me) is that they have apparently found a compact representation of all the data needed to create a (semi)realistic scene from it. All in all, I think this is quite cool. Hopefully they (at some point) will write a white paper detailing some of the algorithms used by the (closed source) generator.
Re:Looks quite cool, but not photorealistic (Score:1)
ok... (Score:1)
"640K ought to be enough for anyone"
--donabal
Anyone successfully downloaded yet? (Score:1)
Mirrors anyone?
Very nice screenshots though. Wasn't First Encounters supposed to allow you to fly over planet vistas though?
Just have to wonder... (Score:5, Insightful)
Smooth may be defined as:
If this were true, then one could theoretically evolve (using GA techniques) a planet that is a reasonable facsimile of earth, or any other feature set. Want a detailed map of San Francisco Bay? Let me squirt my survey through my Genetic Algorithm MojoWorld Compression Algorithm. Oh good, it's done. Use these five numbers to recreate the map...
Hmmm... sounds like it's plausible, but I don't think that small changes in the genotype necessarily result in small changes in the phenotype.
Re:Just have to wonder... (Score:2)
The big question is, is the representation "smooth" enough to encapsulate arbitrary real-life examples?
Check out these related articles (Score:3, Informative)
http://www.gamasutra.com/features/20010302/oneil_
http://www.gamasutra.com/features/20010810/oneil_
There is a nifty demo available for download. The same code is used in the glElite [sourceforge.net] project.
Sing it... (Score:2, Funny)
"I have the whole world, in my floppy"
Does anyone remember Captain Blood? (Score:1, Informative)
But for some reason the computer industry seems to belive that if there has been a lapse for 10 years, the next sucessor is suddelny 'new'.
http://www.mobygames.com/game/sheet/gameId,134/ [mobygames.com]
www.oldskool.org/shrines/captainblood/capblood.ht
http://argnet.fatal-design.com/bluddian.htm [fatal-design.com]
A More Practical Application (Score:2, Funny)
Where would one find information? (Score:1)
It's a little grandiose (Score:1)
Sierpinksi Gadgets (Score:4, Interesting)
To make it look even better, you can choose a color for each vertex. I also found you can do similar things with other shapes (pentagons, squares, etc.) Perhaps this algorithm is a well known way to generate the Sierpinksi Gadget. The amazing thing is how *small* the code is!
pseudocode (possibly with mistakes...its been a while)
Sierpinski
Choose 3 equidistant points on the screen: {x[0],y[0]},{x[1],y[1]},{x[2],y[2]}
Choose random coordinate on screen (x,y)
while no user input
choose random number n from {0,1,2}
plot ((x+x[n]/2), (y+y[n])/2))
loop
Cheers,
jw
Re:Sierpinksi Gadgets (Score:3, Informative)
Choose 3 equidistant points on the screen: {x[0],y[0]},{x[1],y[1]},{x[2],y[2]}
Choose random coordinate on screen (x,y)
while no user input
choose random number n from {0,1,2}
x = (x + x[n])/2
y = (y + y[n])/2
plot (x,y)
loop
and the points don't actually have to be equidistant, any three points will work. You'll just get a warped triangle, which can look kind of cool.
Re:Sierpinksi Gadgets (Score:2)
There was a great chapter in the book, "Programming Tricks of Computer Graphics Gurus" about the subject. Basically, lay out regions on your screen that represent the various parts of the fractal. Make a translation / rotation / scale matrix describing each one. You can make an IDE that applies the matrix to the entire screen (resulting in morphed rectangles at each vertex).
Then, assign a probability to each row of the matrix that is the area of the transformation compared to the total area. Use your random number algorithm to pick out which one to apply, and apply it to your point.
Most of the time this is an arbitrary process, such as "Do it 100 times without plotting to stabilize the jumping point, then do it 1000 times to get a good estimate of the final figure." A lot of people coding it take it one step further and basically end tracing when a certain percent of the last x points drawn were already present...
Re:Sierpinksi Gadgets (Score:1)
Seriously, I need to get back to work now..
Cheers,
jw
Re:Sierpinksi Gadgets (Score:4, Informative)
Iterated function system. Compression by this method is covered by US patent 4,941,193 [delphion.com] issued 1990. This is a clearcut example of how a potentially useful mathematical technique has been largely ignored because of its patent encumbrance. Just one more example of how patents are good for lawyers and bad for everybody else. I seriously doubt Barnsley has made any money from the patent, I suspect the book produced more revenue. In any event, whatever usefulness the technique might have is lost to us until the patent runs out in another 8 years or so.
The word "asshole" comes to mind.
Re:Sierpinksi Gadgets (Score:2)
As I remember, one of the major advantages, besides cheap decoding, was hardware encoding could be used relatively easily...
Re:Sierpinksi Gadgets (Score:1)
%!
%%Title: Sierpinski Gasket
%%CreationDate: 6-21-92
%%Creator: Seth Leichter
%%BoundingBox: 0 0 612 792
%%EndComments
%%BeginProlog
/R {rand 3 mod} def
/plot {
x y moveto
x y lineto
stroke
x y moveto
}def
/midpoint {
x2 x1 add 2 div
y2 y1 add 2 div
}def
%%EndProlog
/A {306 661}def
/B {0 131}def
/C {612 131}def
/gasket
{R dup
0 eq
{A currentpoint midpoint plot pop}
{1 eq
{B currentpoint midpoint plot}
{C currentpoint midpoint plot}ifelse
}ifelse
}def
1 setlinewidth
0 setgray
A moveto
100000 {gasket} repeat
showpage
Far out (Score:3, Insightful)
Very cool for video game development (Score:1)
I've expiremented with various algorithms to try creating landscapes, some of which have relied upon fractal and Mandelbrot math, but often with mixed results. I'll follow this with interest.
Name taken? (Score:2)
I hope that Mojo Nixon doesn't decide to sue, seeing as how he's already written songs about it [tripod.com], and all.
Re:Name taken? (Score:1)
Elite: Frontier and First Encounters (Score:2)
Reminds me of old ideas... (Score:1)
Just this seems to be the other way around - make a formula and find the universe it creates.
One word: Starflight (Score:1, Funny)
Rolf Harris tells a joke about a lawyer from a long-established firm. Over the decades that he and his family had practiced law in the same building, the constant foot traffic over their doorstep had worn a big depression into the solid granite. So the lawyer had a stonemason come in and give him an estimate on a new doorstep. It came out to a lot of money. So our boy thought his best lawyerish money-saving thoughts, and came up with an idea. He said to the stonemason, "Well, how much would it be to not replace the stone but just flip it over? It's just a solid rectangular block, so nobody would be any the wiser if we got some wear out of the bottom as well as the top." And as it happened, that would cost rather less money. So that was what the lawyer decided to have the stonemason do.
So the stonemason goes to work, hammering and chiselling and doing all the usual activities of his trade, and then after about an hour the lawyer hears a knock on his door. He hurries to open it and there's the stonemason with a cheeky grin on his face, saying, "Yer grandfather thought of that fifty years ago!"
Fractal planet generators are indeed a good idea, but they're not so new as all that. Starflight, people, starflight.
This really isn't that impressive... (Score:4, Interesting)
Musgrave is also extremely annoying in the way he dismisses enhancements as trivia and gives the impression that he's done the hard work. He hasn't - he's done the easy bit. For example placing vegetation on his landscapes is a very, very hard problem. Lets see him place a forest of oak trees besides a river, with realistic rendering of sunlight through the leaves, the roots in the soil, and the shadows of the leaves on the ground then I'll be impressed.
There are packages that are attempting to do this - World Construction Set, WorldBuilder and GenesisII come to mind - there are many more (including the granddaddy of them all Vistapro). None look as realistic as Terragen though - again something that can probably be ascribed to the fact that terragen, like Mojoworld, chooses a particular type of landscape in which to work. Unlike Mojoworld though, Terragen is photorealistic.
Creating a general-purpose photorealistic terrain renderer is probably on of the hardest problems still available in computer graphics. And while Musgrave deserves respect for what he has achieved over the years, sadly he's one of those people who simply isn't as good as he thinks he is.
Re:This really isn't that impressive... (Score:1, Interesting)
In any case, TerraGen is pretty fucking far from photorealistic. Get the right camera angle and it looks great; get the wrong angle and you're in polygon hell.
I'm not impressed with any of this shit.
Realtime vs. non-realtime arguments aside... (Score:2)
Want to know what is more impressive about it?
It is written mostly in Visual Basic (don't believe me? Email the author. I found out after having a conversation with him about using VB for 3D stuff like this a few years ago, because I noticed it installing the VB runtime during setup).
Re:Realtime vs. non-realtime arguments aside... (Score:2)
I stopped playing with it a couple of years back. The things I keep waiting for is:
Trees
Sunlight thru clouds
One other thing I would love to see (any possibility of?) is a Linux/X port. Basically, since you have the C++ stuff taken care of, most of it would be a UI interface, right (using GTK or some similar lib for that would work)?
Ihara-grub algorithms, anyone? (Score:1, Redundant)
Fractal Planets... Literally. (Score:1)
My Fractal Planet Gallery [buran.org] might interest some people...
(The most recent one uses another plugin, developed by the same people [flamingpear.com] -- to add a nebula background. Yes, I know the planet should drown the stars and nebula out. It looks cool, and I created that pic to be my desktop background image!) :-)
Impacts for Non-computer gaming and other things.. (Score:1)
It also brings to mind some of the Illustrated Guide to XYZ fantasy universe books that so many fans crave. With software like this becoming more common, could we begin to see CDs o' Fractal images with such publications? Or (again with file sizes of 90k), will we see printed URLs with a "Go here do DL the complete wold..."
Still, while thier limited viewer is free, and the professional viewer (with unlimited resolution) is only $30, I think the $250 SRP (even the $200 intro price)the hobbyist may stay off this platform for a while.
Power of math (Score:1)
Is the power of math something like the power of Oxyclean?
Sorry if I'm skeptical (Score:2)
I can see it now... (Score:1)
Kirk: Spock, is the Genesis planet demo ready?
Spock: I am in the process of building the last piece of the rendering software now, Admiral. It will be completed in 7.182 seconds...
Kirk: (smirking) Could you be a little more specific, Spock?
Spock: (cock's an eyebrow at something on his display)
Kirk: Problem, Spock?
Spock: Yes, Admiral. The rendering software requires an ancient version of something called "GTK". This is not logical... "GTK" fell out of disuse in the early 21st century following the advent of the Quantum Display...
Hmph (proprietaryware seller!) (Score:3, Informative)
What you're seeing in the mpeg videos behind that link is flyover scenes that generate a terrain grid with dynamic level of detail concentrated near the camera, overlaid onto an entirely synthetic and repeatable world which is derived from multiple pointer math on a large (16M) data file. That means FAST- it was only implemented in REALbasic and still runs reasonably fast, and is a natural for C.
I also spent some time producing universe distributions- one stumbling block that I ran into that I hadn't got around to solving was what I was keeping world space in, as the universe is very big and at the same time the actual planets would go down to roughly 1/8" level of detail using some approaches for data synthesis. In particular, one of the techniques for positioning stuff would go down to 1/8" level of detail with four pointer-like operations using no kind of higher math. The difficulty is that you don't get a list of objects- instead if you wanted to synthesise, say, blades of grass, you'd go over a ten mile view by scanning across your view grid and every eighth of an inch, would do the fairly quick lookup of whether there was a blade of grass or some similar object on that eighth-inch spot. On the bright side, it would at least be repeatable, being entirely procedural.
The thing about these projects, and I can see that many people have done them, is that you can get grandiose about them but the bottom line is: this is not a game. This is not inherently fun, or interesting. One thing I'd thought of for _my_ approach is to apply some Warcraft-like game (scaled to MMORG, of course ;) I think that's a rule for all people coding virtual worlds) and make use of the fact that you can have a world-sized area with (perpetual) resources laid out irregularly and down to an extraordinary level of detail. So you could be in a game, and have to dig for gold or iron or something, and go by people's reports of where that resource could be found- including "There's this planet out by Alpha Centauri that's loaded with it". I also had a procedural planet and location name generator that wasn't entirely horrible ;)
Like I said- you get into this sort of thing and totally forget that it's NOT FUN for anybody else, unless there's a plot. I'd suggest that the author of this more recent work, if he seriously expects to earn money off it, should treat it very much like selling an art object: 'here's a viewer through which you can explore millions of worlds much like Bryce, only with less interaction', and not be too haughty about the price, either. This isn't a set of libs that will be useful for anyone creating a game, period. For one thing, you can get the same thing cheaper from elsewhere- it's NOT a unique idea.
Re:Hmph (proprietaryware seller!) (Score:1)
But such a universe is empty and dead. As you say, not fun for anybody else.
So now I'm thinking about aspects of alien civilizations that could be mapped to various math functions. Color schemes and habitation layouts seem like an obvious mapping. Entire classes of names and gibberish seem like another (as you've done already). Certain game-dependant things, like types and levels of technology, could work too.
But the biggest problem with the whole scheme, is how to keep it realistic when someone decides to play Captain Kirk and goes galavanting to hell and gone, pissess off a few civilizations, destroys a bunch of bases and ships.. then returns a month later to find out it all reset. No good. Gotta find a resonable way to store events, or more properly, to instantiate a given set of fractal points as persistant, malleble data, without occupying terrabytes.
Re:Hmph (proprietaryware seller!) (Score:2)
Here's what I'd gotten to, in case it's useful in any way: I figured, the universe was divided neatly into 8 quadrants. Center of the universe is too hot with radiation to survive in, so you're going around the edges. Two corners are occupied by opposite races: one, a race of pacifist avian creatures, and two, a race of basically Daleks ;) robot things that only want to take over everything else and exterminate everyone. That is an immediate overriding plotline: these bad guys, with a home turf, making attacks. You could also have certain resources only exist within the baddies' territory. It's all about forcing mechanisms- you don't give a player a choice. If you play chess it's not to perform interpretive dance with knight movements, it's to take pieces and win and beat the other player. In a vast universe game like we're talking about there has to be a vast universe-sized plot-line, and the most direct one is an attacker.
That said, look to Star Wars for an object lesson in the scale of conflict. In theory it's about the decline and return of the Jedi etc etc, but in practice, in the film, it's Luke in hand to hand combat with his father Darth Vader. In 'A New Hope', even the cinematography is more upfront and immediate- things are in your face, whizzing through the frame, it's not about pulling back and getting a broad view. (PM does that sometimes, and it sucks ;) )
So, in making your massive universe, in what ways can it be made so that a player's IMMEDIATE location is compellingly interesting? Then there can be billions of such locations- but people will be interested in just the one they're in.
90k worlds? Pah! Elite had 8 galaxies in 48 bytes! (Score:4, Interesting)
Elite used Fibonacci Numbers [surrey.ac.uk] with a eight 6-byte seeds, plus a few dozen bytes of look-up tables, to achive this. The principle was very similar to MojoWorld's use of fractals, but Fibonacci series are considerably quicker to process, particularly on an early 80's home computer.
Check out 'The Science of Fractal Images' (Score:1)
The Science of Fractal Images, edited by Heinz Otto Peitgen.
This book can be considered 'Fractals 101', and when I was doing a fractal related final year university project about 8 years ago, it came it VERY handy
However, the images on Musgrave's website don't look much better than the colour plates in that book, so other peoples comments, like 'Big Deal' etc, do hold. I was expecting him to have at least produced better looking images than my team at Uni did
But whatever, the guy still gets major respect from me, he is a true computing pioneer.
Andy
Multi-user interactive worlds (Score:1)
I wish I had known about this interview before hand so I could pose this problem to Dr. Musgrave himself, since he seems eager to use this in multi-user worlds.
Starflight (Score:2)
Starflight was magnificent... (Score:1)
Great Advertising Campaign (Score:1)
If they can just get that guy from the cheese comercial, I think it'll really sell.
Bah! (Score:1)
Re:Bah! (Score:1)
101010b = 42d
powerMATH (Score:2)
POWERmath is a system of high performance
algorithms engineered to meet your
planet creation and design
needs head on. Want to know more?
Follow the equals [powerade.com]...
This is old news. (Score:1)
Not if they want to make the big money... (Score:3, Interesting)
Not if they want to do well in the adult entertainment business. And don't think I'm kidding: the sex-starved portion of the population is willing to pay billions to see something like this developed.
Generating fractal landscapes... (Score:4, Interesting)
It is possible to implement a fractal landscape generation system on using only 2D graphics, which produce an image that looks amazingly 3D in scope, but isn't. Of course, it is possible to do the same algorithm in a 3D coordinate system.
I came across the 2D method first in an old Creative Computing article from around 1983 (the issue was the "graphics" issue, and in addition to the fractal mountain code done in BASIC for a couple of systems, there was an article that detailed making photo masks and combining computer graphics and real photo techniques to produce cool effects for the time - today, photoshop works wonders). The BASIC code was for a PCjr (IIRC) and an Apple IIe, but I converted it to my TRS-80 Color Computer - and it ran fine (though very slowly).
Essentially, the process is:
1. Select three random (X,Y) points on the screen - these form the "base" triangle.
2. Find the midpoints of each side of the base triangle. Split each side in half (subdivide it), and move the midpoint up/down by a small random amount (in the Y direction on screen), and join the points - the deformed triangle should now be composed of 4 sub-triangles.
3. Repeat the process on each of the resulting sub-triangles n-times.
Of course, n tends to be a small number - around 7-10, depending on the resolution of your output device. There is also a way to add "water" by deciding on an certain "Y" level to disallow drawing of "land", instead showing "water" (where "land" is green, brown, or grey, and "water" is blue).
That's the basic algorithm, and the hard part is keeping all the sub-triangle's vertices joined, so that when one is shifted up, the adjoining triangle's vertex shifts up as well. In the Creative Computing article, this was accomplished with arrays and really complex code that wasn't explained too well. Today, you would probably use a combination of linked-lists of objects (where each object represents a vertex), and of course a recursive function system. It would end up being more of a memory hog, but it would be easier to code as well.
Taking the algorithm into the 3rd dimension would be easy, since you would plot the base triangle on the X/Z (or X/Y) plane, then as you went through the subdivision process, you would simply change the height of each vertex in the Y (or Z) plane respectively.
Re:Generating fractal landscapes... (Score:1)
...in fact the 3D version is simpler to implement than the 2D version - you just plot your triangles on a 2D grid, with the value at each grid position being the terrain height. Because the X,Y positions of your points are intrinsic in the 2D grid, you don't have to faff around trying to keep linked-list objects or anything.
e.g.5 0 0 0 3
0 0 0 0
0 0 0
0 0
1
=>
5 0 7 0 3
0 0 0 0
2 0 2
0 0
1
=>
5 5 7 4 3
3 2 6 3
2 1 2
1 3
1
(of course, for efficiency, you actually do it in squares, two triangles at a time.
Re:Generating fractal landscapes... (Score:2)