Island Generator(exupero.org)
exupero.org
Island Generator
http://exupero.org/hazard/post/islands/
14 comments
Final angle? If it's gonna close the path for you, just stop at n-1. No extra side.
Floating point math is hard. I recommend this interview of William Kahan, creator of the IEEE-754 standard, and the associated HN discussion (esp. the comment by user russell)
https://news.ycombinator.com/item?id=7769303
https://news.ycombinator.com/item?id=7769303
It wouldn't have been a problem if it instead used an index variable i ranging from 0 to the number of sides, computing 2pii/sides along the way.
If you're going to rely on repeated addition of irrational numbers to come out to some exact value, then you've misunderstood the abilities of finite decimal representations. It is something easy to overlook, but shouldn't be too surprising to someone who has computed anything by hand (for instance, try long dividing 1/7 out to some number of decimal places, and then adding the result to itself seven times --- if it's a problem there it's not simply a tooling issue, assuming of course the problem isn't with decimals!).
Though, if we want to fix our tools, perhaps instead of the promise of a "cos" or "sin" functions, we could have (ngon-point i n) which returns [(cos (/ i n)) (sin (/ i n))]. Then you wouldn't be tempted to use floating-point numbers to represent the index of a polygon vertex.
If you're going to rely on repeated addition of irrational numbers to come out to some exact value, then you've misunderstood the abilities of finite decimal representations. It is something easy to overlook, but shouldn't be too surprising to someone who has computed anything by hand (for instance, try long dividing 1/7 out to some number of decimal places, and then adding the result to itself seven times --- if it's a problem there it's not simply a tooling issue, assuming of course the problem isn't with decimals!).
Though, if we want to fix our tools, perhaps instead of the promise of a "cos" or "sin" functions, we could have (ngon-point i n) which returns [(cos (/ i n)) (sin (/ i n))]. Then you wouldn't be tempted to use floating-point numbers to represent the index of a polygon vertex.
I fully agree.
As a more general strategy, just use integers (preferably unsigned integers) for all critical stuff such as state handling and looping over. Then, perform floating point operations only on top of that, as a last step. Sometime you don't even need that and use fixed point arithmetics instead (i.e. change your unit to some fixed fraction, e.g. in accounting calculate with integer cents instead of floating point euros/dollars).
As a more general strategy, just use integers (preferably unsigned integers) for all critical stuff such as state handling and looping over. Then, perform floating point operations only on top of that, as a last step. Sometime you don't even need that and use fixed point arithmetics instead (i.e. change your unit to some fixed fraction, e.g. in accounting calculate with integer cents instead of floating point euros/dollars).
> Then, perform floating point operations only on top of that, as a last step.
Right. "Once you go float, you never go back."
Any time you need discrete operations like counting and equality, do it in integer space. Avoid going from integer space back to floating point space.
Right. "Once you go float, you never go back."
Any time you need discrete operations like counting and equality, do it in integer space. Avoid going from integer space back to floating point space.
We can do better. It's true that decimal representation doesn't work:
Maybe better tooling could infer that if the limited math produces an angle indistinguishably close to 2pi, we probably meant for it to be equal to 2pi. Maybe it could do fractional addition, instead of converting to a decimal representation and truncating the number of digits.
Maybe it would write the outputs of the function in the initial triangle example, instead of as
0.999999 = 0.142857 + 0.142857 + 0.142857 + 0.142857 + 0.142857 + 0.142857 + 0.142857
1 = (1 + 1 + 1 + 1 + 1 + 1 + 1) / 7
1 1 1 1 1 1 1
1 = — + — + — + — + — + — + —
7 7 7 7 7 7 7
Maybe better tooling could infer that if the limited math produces an angle indistinguishably close to 2pi, we probably meant for it to be equal to 2pi. Maybe it could do fractional addition, instead of converting to a decimal representation and truncating the number of digits.
Maybe it would write the outputs of the function in the initial triangle example, instead of as
([50 0]
[-24.99999999999999 43.30127018922194]
[-25.00000000000002 -43.301270189221924])
([50 0]
[-25 25*sqrt(3)]
[-25 -25*sqrt(3)])
See also the venerable xmountains (possibly already installed on your workstation).
Screenshot: https://osde8info.files.wordpress.com/2007/02/6a00d4141b9517...
There's a writeup on how it works:
http://www2.epcc.ed.ac.uk/~spb/xmountains/about_xmountains.h...
I don't know how old it is, but the timestamp at the bottom of the HTML file above is 1997.
Screenshot: https://osde8info.files.wordpress.com/2007/02/6a00d4141b9517...
There's a writeup on how it works:
http://www2.epcc.ed.ac.uk/~spb/xmountains/about_xmountains.h...
I don't know how old it is, but the timestamp at the bottom of the HTML file above is 1997.
Nice. For those interested in the topic Amit Patel has a great article on polygonal map generation. Also discusses features like elevation, moisture, rivers etc:
http://www-cs-students.stanford.edu/~amitp/game-programming/...
http://www-cs-students.stanford.edu/~amitp/game-programming/...
Really cool! beyond the generation, I learned about https://github.com/viebel/klipse which looks pretty cool. The whole post also makes me want to look more into clojure.
Aside: Is it OK to not have a <head> element?
Aside: Is it OK to not have a <head> element?
Yep, you don't need a head — browsers will handle that just fine, and the spec generally allows for it. For an example of some HTML that leans quite heavily on the ability to omit tags, see here: http://www.colorglare.com/2014/11/24/stateless-html.html
And you should get into Clojure(Script). It's a joyful language.
And you should get into Clojure(Script). It's a joyful language.
Neat! I got a very marshy one on my third generation: http://imgur.com/doRJskF
If you like this stuff, check https://github.com/Mindwerks/worldengine
Crashes safari on iPad Air 2
Considering the JS file is 7 megs minified! It sometimes crashes even on my Macbook Pro. Other than that pretty impressive work.
That should be 783 kb, right?
The crash window says it's coming from this script when you click "New Island" http://app.klipse.tech/plugin/js/klipse_plugin.js which is 6948118 bytes.
iPhone also.
This is cool, thanks for posting. I especially like how there are several styles of coastlines.
I'm really interested in algorithmic generation of topography, probably by first creating fractal stream networks (either from the coast/ low elevation boundary or from watersheds/drainage divides). I'm a geologist so most game-oriented topography generators look super unrealistic to me, but making stream networks and working from there would be helpful with quantitative landscape analysis and simulations. Anyone heard of anything like this? If nothing else, then some way of filling in a polygon with branch-like fractals?
I'm really interested in algorithmic generation of topography, probably by first creating fractal stream networks (either from the coast/ low elevation boundary or from watersheds/drainage divides). I'm a geologist so most game-oriented topography generators look super unrealistic to me, but making stream networks and working from there would be helpful with quantitative landscape analysis and simulations. Anyone heard of anything like this? If nothing else, then some way of filling in a polygon with branch-like fractals?
Yes, this is one of the main approaches when I was looking at this. Sorry, don't have references at hand, but recall comng across a few when searching for "hydraulic" erosion and river formation.
IIRC, it took a little while to find the favoured search terms. I was using http://citeseerx.ist.psu.edu/ and http://scholar.google.com.au/
There's an interesting review paper by Musgrave (decades after he was lead author on the most cited paper on fractal-landscapes, erosion and rendering) where he notes what you do: fractal landscapes look uncannily realistic to most people but they really aren't very realistic. https://www.classes.cs.uchicago.edu/archive/2015/fall/23700-...
BTW Can I ask you something please? I may rave on a bit, sorry... I'm interested in stream formation by erosion, instead of your more feasible stream-first approach, but I'm concerned that I end up with canyon-filled mountains, and silted up seas. I need a countervailing process, for mountain-formation and sea-emptying, which is surely plate tectonics: squashing mountains up, and subducting seas. Do you have any thoughts/references on modelling this? From my research, the cause of plate movement is not quite well-understood, with tentative theories of roiling magma rising, and somehow also point sources (for island chains like Hawaii).
Wikipedia says the crust is thinner under oceans, because land is a better insulator and the sea cools it faster (but shouldn't that make it thicker?); and the weight of the sea pushes it down (but shouldn't land -- ie rocks -- be heavier than water, being denser, since they sink?)
Thanks for your thoughts!
IIRC, it took a little while to find the favoured search terms. I was using http://citeseerx.ist.psu.edu/ and http://scholar.google.com.au/
There's an interesting review paper by Musgrave (decades after he was lead author on the most cited paper on fractal-landscapes, erosion and rendering) where he notes what you do: fractal landscapes look uncannily realistic to most people but they really aren't very realistic. https://www.classes.cs.uchicago.edu/archive/2015/fall/23700-...
BTW Can I ask you something please? I may rave on a bit, sorry... I'm interested in stream formation by erosion, instead of your more feasible stream-first approach, but I'm concerned that I end up with canyon-filled mountains, and silted up seas. I need a countervailing process, for mountain-formation and sea-emptying, which is surely plate tectonics: squashing mountains up, and subducting seas. Do you have any thoughts/references on modelling this? From my research, the cause of plate movement is not quite well-understood, with tentative theories of roiling magma rising, and somehow also point sources (for island chains like Hawaii).
Wikipedia says the crust is thinner under oceans, because land is a better insulator and the sea cools it faster (but shouldn't that make it thicker?); and the weight of the sea pushes it down (but shouldn't land -- ie rocks -- be heavier than water, being denser, since they sink?)
Thanks for your thoughts!
Thanks for the Musgrave reference, I'll check it out.
As far as your geological questions:
1) Silted up seas and canyon-filled mountains aren't actually that inaccurate. Mountains as we think of them are highly eroded, basically just the remnants of much larger volumes of rock that were uplifted. I'd ballpark a 'typical' mountain range (Rocky Mountain front range, Appalachians, Alps, NZ Southern Alps) at having 10-20% of the uplifted volume of rock remaining. Say the mean elevation of a mountain range is 1 km above the surrounding land, the peaks may be ~2 km above. The rocks that make up those peaks (granite, gneiss, schist) might easily have formed at 10 km depth, so ~9 km of rock was removed through erosion.
Note most of this erosion happens during rock uplift, not after! So it's not like the mountains were super high and then got whittled down. I mean that happens but it's less dramatic than you may think. So the 'stream first' approach is not wrong--the two processes are simultaneous.
2) Ocean basins are huge, and very deep, but there are very large accumulations of sediments there. The oceans are so deep not simply because the crust is thinner, but because it's more dense. Tectonic plates are basically rafts of rock floating on a more dense mantle, and ocean plates are ~10% more dense than continental plates, so they sit lower (Archimedes' principle). However there giant 'fans' of sediment where big rivers, especially those draining actively rising mountains, hit the sea. The Bengal fan, where the Ganges empties into the Indian ocean, is a good example. But the fans are tiny compared to the ocean basins.
In subuction zones, as you've mentioned, the sediment does get squeezed and thickened. Though the oceanic plate in a subduction zone may be 8 km below sea level, in some cases erosion of the plate, sedimentation in the 'trench' and tectonic thickening of the sediment may be enough that it fills the trench in completely and comes above sea level. Barbados is an example of this.
The sediments in subduction zones trenches (called 'accretionary prisms') do eventually get compacted and heated enough to become rock again and pasted onto the sides of the continent. Often after enough ocean plate is subducted, there will be some islands or microcontinents on the oceanic plate that are too thick and buoyant to get subducted and they will smash into the continent, and all the sediment in between becomes incorporated in between, and melted and metamorphosed enough to look a lot like the continents in between. This is how continents grow.
3) The causes of plate tectonics are very well understood--The mantle is convecting because it's much hotter near the core than at the surface. Oceanic plates are more or less the surface of those convection cells, and continents are light by-products that don't get subducted back around but get moved around and smashed into each other and pulled apart by the convection below.
There are also things called 'mantle plumes' that are less well understood but seem to be places at the core-mantle boundary that are much hotter and send up very localized batches of magma to the surface. These are small, relatively stationary, and independent of mantle convection, and so they basically perforate the plates as the plates slide by. Like a machine that spurts frosting onto cookies on a conveyor belt, except upside down. Or something. This is what Hawaii is.
4) I had a 4 but I'm cooking dinner and forgot what it was.
As far as your geological questions:
1) Silted up seas and canyon-filled mountains aren't actually that inaccurate. Mountains as we think of them are highly eroded, basically just the remnants of much larger volumes of rock that were uplifted. I'd ballpark a 'typical' mountain range (Rocky Mountain front range, Appalachians, Alps, NZ Southern Alps) at having 10-20% of the uplifted volume of rock remaining. Say the mean elevation of a mountain range is 1 km above the surrounding land, the peaks may be ~2 km above. The rocks that make up those peaks (granite, gneiss, schist) might easily have formed at 10 km depth, so ~9 km of rock was removed through erosion.
Note most of this erosion happens during rock uplift, not after! So it's not like the mountains were super high and then got whittled down. I mean that happens but it's less dramatic than you may think. So the 'stream first' approach is not wrong--the two processes are simultaneous.
2) Ocean basins are huge, and very deep, but there are very large accumulations of sediments there. The oceans are so deep not simply because the crust is thinner, but because it's more dense. Tectonic plates are basically rafts of rock floating on a more dense mantle, and ocean plates are ~10% more dense than continental plates, so they sit lower (Archimedes' principle). However there giant 'fans' of sediment where big rivers, especially those draining actively rising mountains, hit the sea. The Bengal fan, where the Ganges empties into the Indian ocean, is a good example. But the fans are tiny compared to the ocean basins.
In subuction zones, as you've mentioned, the sediment does get squeezed and thickened. Though the oceanic plate in a subduction zone may be 8 km below sea level, in some cases erosion of the plate, sedimentation in the 'trench' and tectonic thickening of the sediment may be enough that it fills the trench in completely and comes above sea level. Barbados is an example of this.
The sediments in subduction zones trenches (called 'accretionary prisms') do eventually get compacted and heated enough to become rock again and pasted onto the sides of the continent. Often after enough ocean plate is subducted, there will be some islands or microcontinents on the oceanic plate that are too thick and buoyant to get subducted and they will smash into the continent, and all the sediment in between becomes incorporated in between, and melted and metamorphosed enough to look a lot like the continents in between. This is how continents grow.
3) The causes of plate tectonics are very well understood--The mantle is convecting because it's much hotter near the core than at the surface. Oceanic plates are more or less the surface of those convection cells, and continents are light by-products that don't get subducted back around but get moved around and smashed into each other and pulled apart by the convection below.
There are also things called 'mantle plumes' that are less well understood but seem to be places at the core-mantle boundary that are much hotter and send up very localized batches of magma to the surface. These are small, relatively stationary, and independent of mantle convection, and so they basically perforate the plates as the plates slide by. Like a machine that spurts frosting onto cookies on a conveyor belt, except upside down. Or something. This is what Hawaii is.
4) I had a 4 but I'm cooking dinner and forgot what it was.
Thanks for taking the time to explain some geology/plate tectonics in an accessible way. HN is great for the random educational diversions away from plain old tech.
This might be up your alley:
http://mewo2.com/notes/terrain/
http://mewo2.com/notes/terrain/
This is a good reference, thanks.
I recall a most amazing screen saver that was installed on a mid 90s mac which would build mountains one layer at a time. Pretty far off topic but I have often tried to find that screensaver and this wonderful writeup triggered a memory. I would stare at that screensaver for hours as a child.
Very cool! I'm a keen surfer, and the imagination runs wild seeing each newly generated island.
This really great, brings me back to my childhood - I used to love to draw islands.
This is so awesome! I now am a lover of islands :D
A somewhat obscure piece of trivia.
There's code similar to this seen on a computer screen in digimon. http://i.imgur.com/gh3dK.jpg
A translation from the Basic dialect into Javascript http://fingswotidun.com/code/index.php/Digimon
Press the play button to get it trying a series of random seeds.
There's code similar to this seen on a computer screen in digimon. http://i.imgur.com/gh3dK.jpg
A translation from the Basic dialect into Javascript http://fingswotidun.com/code/index.php/Digimon
Press the play button to get it trying a series of random seeds.
Some islands look a bit unrealistic.
With swamp areas sticking out i the sea.
Waves would remove such things in a short timespan.
With swamp areas sticking out i the sea.
Waves would remove such things in a short timespan.
I disagree. We know nothing about the height at this point. It could be anything between a big, flat beach (http://hd.wallpaperswide.com/thumbs/beach_island-t2.jpg) and crazy cliffs sticking out into the sea (https://upload.wikimedia.org/wikipedia/commons/d/d1/Cliffs-O...)
Without a scale and a height map, almost no shape is unrealistic.
Without a scale and a height map, almost no shape is unrealistic.
It's broken. I just used it, and it randomly generated Australia (https://www.dropbox.com/s/3aa5mr7gvbbmpc5/australia.png?dl=0).
Notice that range stops just shy of 2π. Floating point math sometimes produces a final angle indistinguishably close to 2π, adding one extra vertex to our n-gon. To see for yourself, change (- tau 0.000001) to tau and set the number of sides to 6. You’ll see an extra point in the output very close to the starting point.
This is a "trick" that you find everywhere in graphics programming, and I can't believe we've been programming for over half a century and still have to deal with crap like that in our tooling. It leads to code that, while readable to the initiated programmer, is not what it should be.