next »

[azagthoth]

I am building a world generator that I plan to eventually use as a basis for a game.  I am using this thread as well as my blog (http://www.dungeonleague.com/) to track progress and hopefully discuss some of the algorithms involved.

The goal is to have the all the data required to define discrete terrain types based on elevation, weather, humidity, etc. and render that data to tile graphics.

[nihilocrat]

That algorithm gives some pretty awesome results! The locations of the mountains still seem a bit strange, though it's much better than the earlier screenshots. maybe I just don't know enough about geology and how continents are formed, but there always seems to be a single major mountain range on each island that may or may not hug right up against the coast.

I'm interested to see what comes next, I like how you outline in your blog the precise algorithm you used to generate what you see in the screenshots.

[azagthoth]

I am not completely happy with the mountains yet either.  With the mountains what I am trying to avoid is an algorithm that just pretty much makes each continent into a big hill with the mountains in the middle.  Another goal is to have the mountains create meaningful barriers between regions.  I don't really know much about geology either, I think I am trying to get something "reasonable but interesting" vs an accurate representation of earth.  It should also be flexible enough to generate wild looking stuff nothing like earth as well, which could have interesting consequences game play wise.

So far I have only described the process for creating the drainage basins themselves on the blog.  I am planning to add a detailed post for how rivers are run and elevation is created.

[Fork and Beard]

Many, many moons ago I wrote a simple world generator in MS Excel using VBA.

In fact I wouldn't be surprised if the official evolution of a programmer isn't something like:

• Text Adventure
• Pong
• Continent Builder

Stands to reason I'd have one in my closet.





In a nutshell I tried to use the same method for creating mountains as I did for the land (as you'll spot in the video). Same for the forests and deserts. Not sure if it's a good approach or not but it's there if you're interested and I was always fond of it.

[Blaster]

Wow, this is really neat. There is something inherently fascinating about procedural world generation. Once I have the programming chops I'm definitely going to try this myself.

A simple change that might improve readability would be reverse the way you are displaying elevation. My eye gets really confused trying to understand the darker areas as higher.

I don't have any actual meaningful advice since I'm a complete newbie to programming, but wish you well regardless. 

[azagthoth]

Stands to reason I'd have one in my closet.

Thanks for the video.  I should work on something like that to better explain the process I am using.  Did you use brownian motion to create the islands in that ?

[Fork and Beard]

Did you use brownian motion to create the islands in that ?

In the words of Edward Woodward: "Jesus Christ no."

I just used trial and error.

[azagthoth]

I have now pretty much finished the rivers and water for this scale.

Current sample (New palette one color for elevation, Dark->Light == Low->High) :
http://www.dungeonleague.com/wp-content/gallery/lakes/1269130715925.gif

Loose ends to tie up before moving to the next stage are:
- Fix performance for lake placement code.  Right now it is really slow.
- Re-factor drainage basin package.  This collection of classes is poorly designed from an OO perspective, just a mess of code thrown together to achieve the result.
- More tweaks to elevation code that works based off of drainage basins and rivers.  It needs to take into account the lakes now.

Once those are taken care of I will move onto:
- Wind patterns
- Humidity/Rainfall
- Temperature

[AndyKorth]

Hey azagthoth, that looks fantastic! Your rivers are very impressive. I have done a bit of world generation stuff for a project of mine, mostly using Perlin noise.

I first created a pretty standard height map, and then created a temperature and rainfall map as well. From there I evaluated each point and assigned a biome based on height, rainfall, and temperature. These biomes would be grassland, marsh, desert, foothills, mountain, coniferous forest, and deciduous forest. This resulted in a biome map:

http://kortham.net/temp/ReclaimedBiomeMap.png

(light green is deciduous forest, greenish-tan is marsh, the dark brown is coniferous, etc.)

From there I calculated individual regions (this map is similar, but I cut out the ocean... my screenshot archive is not well organized)

http://kortham.net/temp/RegionsOfThatMap.png

So each color is a differently named region, such as the Cartographer's Foothills, The Long Plains, and other similarly silly names. I think it made for a pretty good feeling of an interesting world as you walked around it.

Then set loose some players for a month or two and they ended up building this:

http://kortham.net/temp/ReclaimedMap32.png

Rivers were definitely on my todo list, and yours look great. I was thinking about a cellular automata approach to generating river paths- by dropping a bunch of rain droplets on the heightmap and seeing where they flowed to define bodies of water. However, it looks like your basin approach worked really well and the rivers seem to flow downhill nicely, and not loop back into the ocean).

I'm guessing they flow so well because of your RidgedMultifractal. Inverted so drainage basin lines follow the local maximums of hills and mountains. I'm interested in hearing more about how you make rivers within a basin.

[azagthoth]

I'm guessing they flow so well because of your RidgedMultifractal. Inverted so drainage basin lines follow the local maximums of hills and mountains. I'm interested in hearing more about how you make rivers within a basin.

I actually create the elevation based on the rivers and water instead of flowing water based on the elevation.  I'll run through a set of images I created and hopefully it will explain it.  I left out lakes and endorheic basins from this example to focus on the rivers and elevation.

Drainage Basin Step
First I take an island and split it into basins (See: Drainage Basins. A few minor changes since then but it is pretty much current)
This creates the following:
1) Identifies drainage basins
http://www.dungeonleague.com/wp-content/gallery/drainage-basin-steps/01_drainagebasins.gif

2) Elevation hierarchy.  This map is used to assign weights when I create the elevation.  The darkest (non-black) line is the primary continental divide it has the greatest weight, as the lines get lighter they have less weight on the final elevation.  I'll explain more about this in the elevation step.
http://www.dungeonleague.com/wp-content/gallery/drainage-basin-steps/04_elevationhierarchy.gif

Rivers Step
I didn't describe this on the blog so here are the steps.
1) Create a cost map for pathfinding.  I will use an inverted multifractal again:
http://www.dungeonleague.com/wp-content/gallery/drainage-basin-steps/02_rivercostmap.jpg

For each drainage basin that is big enough to support a river I do the following:
2) Select a random point that is part of its coast and then using the Dijkstra's algorithm with the cost map to determine the furthest away point and create a path between the two.

3) Depending on the size of the basin I select a random number of points within it.  For each of these points Dijkstra's algorithm is used again to create a path to the nearest river point.  Here is an animated gif of the process:
http://www.dungeonleague.com/wp-content/gallery/drainage-basin-steps/03_rivers.gif

Elevation Step
I also didn't explain this on the blog.  It was changing too much at the time.  Here are the steps:
1) Using the rivers and the ocean as source points I use a Voronoi operation to calculate the distance of each cell to its nearest water.  That value is added to a value from a FBM noise pattern to create the initial river valleys.

2) Now I use the elevation hierarchy from the drainage basin step.  For each level in the hierarchy I create a map which is a combination of a Voronoi operation with the divide points as a source combined with a layer of FBM noise.  This map is then multiplied by a weight and added to the previous map.

The final elevation is the sum of the valleys from the rivers and a set of decreasingly weighted maps based on the elevation hierarchy.

Here is an animated gif, the first frame is the valleys from the rivers, each one after that is a weighted layer being added (Warning ~1MB):
http://www.dungeonleague.com/wp-content/gallery/drainage-basin-steps/05_elevation.gif

Here is the final result:
http://www.dungeonleague.com/wp-content/gallery/drainage-basin-steps/06_final.gif

[azagthoth]

Added a method to generate wind direction information, more detailed description on the blog.  Here is a sample:

Wind Direction Legend
Blue = East
Green = North
Red = West
Yellow = South

http://www.dungeonleague.com/wp-content/gallery/wind-direction/1269766202808.jpg

Next Up: Wind Magnitude

[azagthoth]

Added wind speed and temperature generation.  Details on the blog.

Samples:

Elevation map the wind and temperature are generated for:
http://www.dungeonleague.com/wp-content/gallery/wind-speed-amp-temperature/1270358202044.jpg

Wind Speed (Dark -> Light = Low -> High Winds):
http://www.dungeonleague.com/wp-content/gallery/wind-speed-amp-temperature/1270358207924.jpg

Temperature (Red -> Green -> Blue = Hot -> Moderate -> Cold):
http://www.dungeonleague.com/wp-content/gallery/wind-speed-amp-temperature/1270358208604.jpg

Next Up: Rainfall & Rain Shadow

[Alex May]

Very nice, lovely stuff.

[azagthoth]

Finished the rain shadow generator.  Details on the blog.

Source Elevation:
http://www.dungeonleague.com/wp-content/gallery/rain-shadow/1270999201973.jpg

Resulting Rain Shadow (Black = Rain shadowed -> White = Normal):
http://www.dungeonleague.com/wp-content/gallery/rain-shadow/1270999256208.jpg

The next thing I am working on is generating the final rain fall map.  The rain shadow map is one component of that but I haven't figured out what I am going to do for the rest of it yet.

[oyog]

Those are some delicious fractals.

[azagthoth]

I finished most of what I consider to be the first phase of this world generator.  Today I added rainfall and biomes.  Details here.

Legend:


Biome Sample:
http://www.dungeonleague.com/wp-content/gallery/biome/1272339879623.gif

I was thinking next I would add a user interface to try different parameters out that would guide the world generation process and export a set of images at the end.  This would be something I would release as a java web start app.  Would anyone be interested in playing with something like that ?

Other things that are coming up next:

• Code cleanup and performance optimization.  Thinking about restructuring the whole library to make better use of dependency injection...
• Visualization.  I am tired of looking at pixels to represent the terrain, I am not sure whether I want to do ascii, tile some pixel programmer graphics, or something else.  Ideas ?
• Add more detail.  There is still lots of detail to be added.  Many of the biomes generated right now are quite large and could use some more diversity (Different types of vegetation/forests).  Adding terrain features for things like swamps, marshes, flood plains, glaciers...

[nihilocrat]

I can think of tons of uses for this thing, particularly if you could have some kind of "export" function that would export the terrain data to JSON, XML, or whatever you please. It's probably good enough to export pictures, though, and anyone that uses them can just write code to analyze the pixel data.

[azagthoth]

Been a while since I posted.  I added the ability to write a Tiled map.  Currently the tiles are dwarf fortress style.

If you have Tiled you can download these two files to the same directory and open the .tmx file with Tiled to see the world: (I used the Qt version, didn't test it with the Java one)
http://dungeonleague.com/downloads/01.tmx
http://dungeonleague.com/downloads/Terrain.png

Otherwise you can check out this gigantic image ! (Warning: 5.73 MB 16384×16384 Pixels)
http://dungeonleague.com/downloads/01.png

Since last time I posted I did a lot of code cleanup and some performance optimization.  Biggest performance fix was to make the rain shadow calculation not take forever.  On average it is taking about 1 minute to generate 1 entire world.  I guess the tiled export covers most of my visualization needs for the time being. Still planning to add more detail, there needs to be lots more special land features to make the map more interesting.

I tried plugging away at making a GUI for this thing but there are a ton of parameters resulting in many screens of forms.  Coding a GUI is not exactly how I like to spend my spare time so it hasn't resulted in anything useful yet.  I tried out thinlet which seemed to speed development up a bit but not enough to make me want to do that over working on other cool stuff.  I am leaning towards just making a command line processor to take an XML config file.  Of course I won't be really doing that until I run out of more fun things to code like more land features and civilization generation...

[baconman]

Your methodology is rather incredible so far.

•Define Latitudes and wind directions to go with them. All directions are in radians. I defined the following latitudes:
◦North Pole = Southeast
◦North Circle = East
◦North Tropic = Southwest
◦Equator = North/South
◦South Tropic = Northwest
◦South Circle = East
◦South Pole = Northeast

That's all I would change, as it gives a general sense of flow; along with a few minute distortive regions, kind of like + and - magnets, that attract or repel the wind, and move in accordance with feedback from it. Attracting more eastbound wind (or repelling more westbound) will move it east, for example.

What's really going to be interesting is to see how the underwater development will go, if you choose to voyage there; though I'd imagine it's simply a matter of reduplicating the process, with the completely-shaped continents and then redefining the climate/biome data accordingly. (And changing "lakes" into "air pockets.")

You could also use such an approach, with an aquatic medium, to create a mirrorized "light" and "dark" world.

[azagthoth]

That's all I would change, as it gives a general sense of flow; along with a few minute distortive regions, kind of like + and - magnets, that attract or repel the wind, and move in accordance with feedback from it. Attracting more eastbound wind (or repelling more westbound) will move it east, for example.

I am not sure I understand what the desired outcome is with the change in wind direction you have described.  Could you please describe the desired outcome ?  It is easy enough to change the wind directions to any direction at any given latitude as they are just parameters into the wind direction function.

The effect on the final map of the wind direction is to determine rain shadow which then determines rainfall.  The wind direction interacts with the elevation during the rain shadow step.  In the end the result is fairly random since if you have mountain ranges that run parallel to the winds there isn't much rain shadow but if the mountain ranges run perpendicular there is a lot more.

What's really going to be interesting is to see how the underwater development will go, if you choose to voyage there; though I'd imagine it's simply a matter of reduplicating the process, with the completely-shaped continents and then redefining the climate/biome data accordingly. (And changing "lakes" into "air pockets.")

You could also use such an approach, with an aquatic medium, to create a mirrorized "light" and "dark" world.

Currently I don't have any plans to develop details underwater other than simple features to add variety to the map, such as reefs, ridges and trenches.  Possibly I will add these while I am adding the other land features.