PDA

View Full Version : Random Map Generator (Work in Progress)



jesuisbenjamin
10-01-2012, 04:24 PM
Hello,

I've been working on a random map generator for the last past days. Yes there are plenty of them already available. Yet it's been in my mind to make one and it's a good programming exercise too.

I've read as little as possible on what has been done prior so I could think afresh. I've come up with two core engines as of now, and neither are really satisfying, although progress is rapid.

The two core engines are based on elevation and seeding respectively. The first one consists in browsing the map and raising each tile depending on its neighbours' elevation. The second consists in seeding random dots around which land is spreading or mountains elevated.

Each have their own pro's'n'con's but the first is my favourite, because it has a much more organic result. Its drawback is that right now I have worked on a top-down, left-right pattern, which shows in the map (because everytime the map has less constraint on the sides it is growing towards, and thus patterns tends to repeat more in those directions). This could be remedied adding some randomness to the direction in which tiles are processed. Also because the way this model works it will be possible to increase the range of elevation details (i.e. from 5 levels to 10 levels or more), which you can flatten (or seemingly flatten) by merging those levels, for instance you can raise water level from level 0 to 3 to increase oceanic surface.


Elevation Model
48660

The second allows for much more customisation, but the seeding makes the map look like a bunch of big splotches as land tends to concentrate around the seeds. This one can be fixed too by adding clustering into the seeding. The best way to cluster is to seed a cluster center in a portion of the map (the more clusters, the more portions) and to divide the amount of seeds to be spread around the clusters randomly, yet within the portion. Once the seed are seeded, the spreading takes place, which also has some degree of randomness into it. If the resulting map looks better to you now it's probably because I have worked on it much more, and there are several more effects applied, like cleaning up and smoothing down. These effects can be implemented in the first model too. But if you look at the way this one is designed, you can see there is a repeating splotchy pattern, which I greatly dislike. I would like to see mountain ranges as in the model above. That's perhaps to be fixed with the clustering.


Seeding Model
48661


If you have any ideas, comments, questions. Let me know.
B.

jesuisbenjamin
10-04-2012, 02:19 PM
OK, so I've been working on this but made very little progress. Also my programming skills are very poor, which doesn't help.

I went seeking some information and in so doing I came across one of the best random map generators I have seen. It's so good it's getting ridiculous. So I decided to share it with you, who will most probably enjoy it.

There is an article explaining how Red Blob created a random map generator based on polygons (http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/) and there is an interactive demo (http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/mapgen2.swf) accompanying this. Enjoy!

HBrown
10-04-2012, 03:54 PM
The problem with growing land out from a central seed is that the high areas tend to concentrate in the center of your land masses. On a continental scale, that just ain't necessarily the case, at least on earth. This is a typical flaw in most generated map. Another problem I see is that coastlines all have the same fractal dimension (the same amount of wiggliness). A glance at any atlas will show that, except for fairly small sections of the planet, this isn't true either.

That said, remember the old engineering maxim, "First make it work, then make it work well."

One way you might remove the directional bias in your elevation model is to use two frames. The previous iteration is used as the basis for the next, but its values are not changed. That way the new values can't bias subsequent new values. I tried this once on a project I worked on longer ago than I care to admit, and it worked out pretty well.

The seed model might be improved by encompassing a directional bias, so that one direction is more likely to be raised than another. To avoid ending up with stripes, the directional bias should probably vary from seed to seed, and change slightly from iteration to iteration. I have not tried this, so I can't promise good results.

--Hugh

jesuisbenjamin
10-06-2012, 04:42 PM
Thanks Hugh, you are right. Actually in my seeding model I layed out mountain seeds randomly on land so they are not concentrated at the center of the landmass, but also on shore for instance. I haven't found a way to grow the landmass or the mountain ranges in a non centrifugal way, so I can get ranges rather than splotches. You are right about the fractal issue too, a good way around this would be to create various layers, some with extra smoothe.
As to the elevation model, I am not sure to understand what you suggest. Can you explain in more details? I have thought of a solution for the elevation model, which would be to take random rows and switch from LTR / RTL. To work this would require a non-miopic elevation procedure, by looking in a range around the current tile that would be far enough to ensure the slope can cope with the distance. (This relies on the premise the slope has to go through all increments, without skipping any, which is rather unnatural in fact).

I've tried the commonly used (and probably for good reasons) Perlin Noise model. It works pretty well, but I find the mountains again to be too much centered in the middle of the landmass. This is what it yields:


Perlin Model
48897

One other issue with this model is that I cannot easily create the illusion of a continuous landmass. It's mathematically tedious, there are examples online, but I really dislike using something I don't understand. I am thinking of simply overlaying the continuation of the map that would be on the right side, to the left. I haven't thought of how yet. The code is available on github (https://github.com/jesuisbenjamin/mappout).

Another model I have been thinking of is a seeding and slope on a hex-tiled map. Few peak seeds are sown and around them a random slope index from which the surrounding elevation is calculated. This would avoid a regular, centrifugal slope.

What's important is too consider what is the final mode of representation of the map. If it will be a 3D map, then the slope is hardly a problem, dots are linked to one another, and Pythagore does the job for us. What I want to do however is a flat model with hex-tiles. The elevation will not be rendered with 3D, but with the isometric hex tiles. So much of the elevation issue is already worked around.

jesuisbenjamin
10-09-2012, 11:38 AM
I worked on alternative models again. One I like, but which is a bit CPU heavy, is the trace model (which consists in drawing random squiggles within a certain scope and spreading them out a little). With the right proportions it renders quite credible continents, yet not really perfect:


Trace Model
48977 48978
48979 48980

Here the smoothness of the coastlines are all the same, I could randomise them a little to create diversity. Based on this model I could elevate mountain ranges using the same trace method. I am still not too happy about the continent shapes. A good idea perhaps is to work from tectonics. Perhaps I could guide the squiggles to break the plane into large chunks, elevate some of those breaks to make mountain ranges and dig other to create oceans.

Tectonics could work out well with Voronoi polygons (http://en.wikipedia.org/wiki/Voronoi_diagram) perhaps, but my math is poor and I don't know if I can do that.

Another try I did, is to erode the map with a lot of those random squiggles. This erosion model is not too bad, but I have a hard time guiding the erosion to create continental shapes. Also there is something buggy about this model because the sea is always on the right hand side and overlapping a little on the left side of the frame.


Erosion Model
48981