6 ms·

Island Generator

271 points by exupero 10y ago

tzakrajs 10y ago
Crashes safari on iPad Air 2
- kaizoku111 10y ago
  Considering the JS file is 7 megs minified! It sometimes crashes even on my Macbook Pro. Other than that pretty impressive work.
  - arkitaip 10y ago
    That should be 783 kb, right?
    - kaizoku111 10y ago
      The crash window says it's coming from this script when you click "New Island" http://app.klipse.tech/plugin/js/klipse_plugin.js http://app.klipse.tech/plugin/js/klipse_plugin.js which is 6948118 bytes.
- geuis 10y ago
  iPhone also.
cossatot 10y ago
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?
- roywiggins 10y ago
  This might be up your alley: http://mewo2.com/notes/terrain/ http://mewo2.com/notes/terrain/
  - cossatot 10y ago
    This is a good reference, thanks.
- hyperpallium 10y ago
  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/ http://citeseerx.ist.psu.edu/ and http://scholar.google.com.au/ 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-1/final-project/MusgraveTerrain00.pdf 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!
  - cossatot 10y ago
    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.
pmyjavec 10y ago
Very cool! I'm a keen surfer, and the imagination runs wild seeing each newly generated island.
niix 10y ago
This really great, brings me back to my childhood - I used to love to draw islands.
charlesetc 10y ago
This is so awesome! I now am a lover of islands :D
GuiA 10y ago
Great writeup! 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.
- delinka 10y ago
  Final angle? If it's gonna close the path for you, just stop at n-1. No extra side.
- AceJohnny2 10y ago
  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
- kmill 10y ago
  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.
  - 10y ago
Lerc 10y ago
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 http://i.imgur.com/gh3dK.jpg A translation from the Basic dialect into Javascript http://fingswotidun.com/code/index.php/Digimon http://fingswotidun.com/code/index.php/Digimon Press the play button to get it trying a series of random seeds.
callesgg 10y ago
Some islands look a bit unrealistic. With swamp areas sticking out i the sea. Waves would remove such things in a short timespan.
- viraptor 10y ago
  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 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-Of-Moher-OBriens-From-South.JPG https://upload.wikimedia.org/wikipedia/commons/d/d1/Cliffs-O...) Without a scale and a height map, almost no shape is unrealistic.
tunnuz 10y ago
It's broken. I just used it, and it randomly generated Australia (https://www.dropbox.com/s/3aa5mr7gvbbmpc5/australia.png?dl=0 https://www.dropbox.com/s/3aa5mr7gvbbmpc5/australia.png?dl=0).
beeswax 10y ago
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/polygon-map-generation/ http://www-cs-students.stanford.edu/~amitp/game-programming/...
david-given 10y ago
See also the venerable xmountains (possibly already installed on your workstation). Screenshot: https://osde8info.files.wordpress.com/2007/02/6a00d4141b9517685e00d09e56ce08be2b.jpg 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.html 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.
jimktrains2 10y ago
Really cool! beyond the generation, I learned about https://github.com/viebel/klipse 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?
- spiralganglion 10y ago
  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 http://www.colorglare.com/2014/11/24/stateless-html.html And you should get into Clojure(Script). It's a joyful language.
tuned 10y ago
If you like this stuff, check https://github.com/Mindwerks/worldengine https://github.com/Mindwerks/worldengine
pavel_lishin 10y ago
Neat! I got a very marshy one on my third generation: http://imgur.com/doRJskF http://imgur.com/doRJskF

Island Generator

271 points by exupero 10y ago

tzakrajs 10y ago

Crashes safari on iPad Air 2

kaizoku111 10y ago
Considering the JS file is 7 megs minified! It sometimes crashes even on my Macbook Pro. Other than that pretty impressive work.
- arkitaip 10y ago
  That should be 783 kb, right?
  - kaizoku111 10y ago
    The crash window says it's coming from this script when you click "New Island" http://app.klipse.tech/plugin/js/klipse_plugin.js http://app.klipse.tech/plugin/js/klipse_plugin.js which is 6948118 bytes.
geuis 10y ago
iPhone also.

cossatot 10y ago

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?

roywiggins 10y ago
This might be up your alley: http://mewo2.com/notes/terrain/ http://mewo2.com/notes/terrain/
- cossatot 10y ago
  This is a good reference, thanks.
hyperpallium 10y ago
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/ http://citeseerx.ist.psu.edu/ and http://scholar.google.com.au/ 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-1/final-project/MusgraveTerrain00.pdf 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!
- cossatot 10y ago
  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.

pmyjavec 10y ago

Very cool! I'm a keen surfer, and the imagination runs wild seeing each newly generated island.

niix 10y ago

This really great, brings me back to my childhood - I used to love to draw islands.

charlesetc 10y ago

This is so awesome! I now am a lover of islands :D

GuiA 10y ago

Great writeup! 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.

delinka 10y ago
Final angle? If it's gonna close the path for you, just stop at n-1. No extra side.
AceJohnny2 10y ago
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
kmill 10y ago
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.
- 10y ago

Lerc 10y ago

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 http://i.imgur.com/gh3dK.jpg A translation from the Basic dialect into Javascript http://fingswotidun.com/code/index.php/Digimon http://fingswotidun.com/code/index.php/Digimon Press the play button to get it trying a series of random seeds.

callesgg 10y ago

Some islands look a bit unrealistic. With swamp areas sticking out i the sea. Waves would remove such things in a short timespan.

viraptor 10y ago
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 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-Of-Moher-OBriens-From-South.JPG https://upload.wikimedia.org/wikipedia/commons/d/d1/Cliffs-O...) Without a scale and a height map, almost no shape is unrealistic.

tunnuz 10y ago

It's broken. I just used it, and it randomly generated Australia (https://www.dropbox.com/s/3aa5mr7gvbbmpc5/australia.png?dl=0 https://www.dropbox.com/s/3aa5mr7gvbbmpc5/australia.png?dl=0).

beeswax 10y ago

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/polygon-map-generation/ http://www-cs-students.stanford.edu/~amitp/game-programming/...

david-given 10y ago

See also the venerable xmountains (possibly already installed on your workstation). Screenshot: https://osde8info.files.wordpress.com/2007/02/6a00d4141b9517685e00d09e56ce08be2b.jpg 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.html 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.

jimktrains2 10y ago

Really cool! beyond the generation, I learned about https://github.com/viebel/klipse 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?

spiralganglion 10y ago
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 http://www.colorglare.com/2014/11/24/stateless-html.html And you should get into Clojure(Script). It's a joyful language.

tuned 10y ago

If you like this stuff, check https://github.com/Mindwerks/worldengine https://github.com/Mindwerks/worldengine

pavel_lishin 10y ago

Neat! I got a very marshy one on my third generation: http://imgur.com/doRJskF http://imgur.com/doRJskF