Random map generator


#101

I played only random maps in WOG/Hmm3. And I waited for HOTA to implement random map generator. And two my friends also preferred random map in single play. (One of reasons is that human created maps often lack quality and have few map elements per square cm.

Random generator is the most wanted feature I wait except spells modding system.

PS I dreamed today about realizing XXL maps (or even bigger) in VCMI. And about several levels of map. Like not only earth and dungeon, but to 3-10 levels at least, also in multiplayer.
Like it was in Age Of Wonders. So game can became not rush and trying to kill enemy heroes spreaded on map. But real long-term exploration. With a lot of monsters, artefacts and difficult battles for adventure enjoing.
This will require change of current Earth/Dungeon button behavior. I think it’s better be cyclically changing buttons 1/2/… depending on number of layers chosen.
It was one of requested HOTA features in early years, but they still didn’t implement additional levels yet.
Just imagine making map with 8 layers about 7 levels of Dante’s Inferno:-). Or sky level (with terrain like clouds and some celestial beeyings. Or some deeper dungeons with stalagmites. Or submarine level with some only sea beeings and underwater objects and town like Abyss.


#102

one thing you could use to generate the maps is order 1 makov chain

if you dont know what map generated order 1 makov chain is:
you would basically create a good map(s)
then you would split it into a square grid.
then you would get the statistics of map (what is the % of quares that have water…)
then you also get neighbour statistics (what are the things usually adjacent to a water tile???)

to generate the map you generate a random tile at random based on how likely it is to a tile be of a specific type.
Then you generate adjacent tiles at random based on how likely it is to a tile be adjacent to a tile of that type.

Important thing 1:
A square tile is adjacent to 4 tiles (up down, left and right [or 8 if you count diagonals]), a important thing is to create a generation pattern that most of the time you will be generating square tiles with alot of already generated adjacent square tiles.
As some example if you generate square tiles of the first row from left to right, then of the second row from left to right, then the third… you will generate a X pattern.
A way that could fix that, is generate a random square and then generate a random square between the ones with the most amount of already generated adjacent squares, then again generate a random square between the ones with most amount of already generated squares.

Important thing 2:
As you see this could generate maps with less than the amount of towns wanted or with different towns than the wanted ones. There are 2 ways to solve the problem

More literal one and one that takes more time:
Generate map until one dont come with this problem.

Faster one:
Before generating the map put the cities at random places. And then you continue to generate the map from this.
:->


#103

How’s the work is going for RMG?

I thought about possibility to make “sea” default terrain for some towns. Is it possible? It’s complex thing, so faction heroes must act as boats on water altrough (WATER_WALK is not sufficient - it requires to end on land).

And second - long ago was talk to allow placing creatures on water when random map generation/week of monster. It requires some non-needed for most other creatures flag like “seaCreature”:true (or better variant “terrain”: “sea” (or any other terrain). By default terrain for creature must be taken from faction, if it is not set in creature itself.
Sea creatures can be placed to guard sea visitable objects or on whirlpools for example (hero exits whirlpool and gets attacked).


#104

Okay, I finally merged jfhs’s patch. Managed to compile it and match to changes over last months.

However, RMG crashes at attempt to launch map, showing something in the depths of engine.
So I tried to launch old RMG with latest develop branch. However, it doesn’t work correctly either.
Map loads, at least, but it shows that the tile closest to hero is guarded (sword arrow). I need to attack that tile to ever move, but then game crashes :frowning:


#105

RMG works more or less now, time to make it actually worthwhile.

I’m going to start first with zone placement. Will give up Voronoi partitioning and go for non-euclidean distance function. Here are example results from Matlab (with script, if you can use it):

i118.photobucket.com/albums/o102/DjFaust/VCMI/RMGzonesExample_zps691fb83b.png

It seems to generate somewhat smooth and balanced zones. In original RMG sometimes they used to be bent beyond playability.
RMGmatlab.rar (668 Bytes)


#106

Yay, progress!

Just wondering - have you tried to create a rectangular map? Engine should support such but so far there was no way to create such map.

36x36 example isn’t far from it while 144x144 zones are just too smooth. Perhaps scale parameters so any map size will create zones like on 72x72 example?


#107

I just tried, template size limits are the issue now. Well, maybe another time :wink:

For that reason I suggest to specify template size in absolute value and not fixed letter.


#108

I noticed that your “distance” (strictly speaking , it’s not, but it looks good and organic!) is not symmetric under x <-> y exchange (hence it creates oblong regions). Is it intentional?


#109

This is just how this algorithm works, there is nothing more in it :P. I’ll try scaling parameters as Ivan suggests to create more rounded zones with every map size.

BTW, the idea of non-euclidean distance was suggested by Tapani who made custom RMG for Heroes 5.


#110

I don’t mean the pseudo-distance being non-Euclidian (in fact, it’s not a “non-Euclidian distance” at all, a non-Euclidian metric is bilinear and symmetric, that is, it can contain dx^2, dxdy, dydx and dy^2 only, your version is neither bilinear nor symmetric —but again, this pseudo-distance generates organic-looking zones).
What I mean is more related to aesthetics than mathematics: do you prefer to have wide-and-short areas rather than rectangular ones? Your “metric” is non-symmetric.

Edit: I checked Heroes 5 RMG page, apparently he only used a different p-norm only (with p=1/log2(1.5), Euclidian norm is p=2).


#111

I believe regular zones are better, as long and narrow ones tend to be cluttered, blocked and in general irritating.

And yes, this metric must be non-symetric to generate complex shapes.


#112

?
These two statements contradict each other given that “long and narrow” happens for “non-symmetric” distance. Am I making some mistake?

If you want to have complex shapes, you might want to do this instead: using position-dependent coefficients in front of each f(dx,dy) (currently they are constant factors like 1, 0.03. etc.). In doing so, you can also include a decaying damping factor for each term such that fancy irregularities do not dominate (but still contribute) as you move towards the characteristic length (that is, the Euclidian distance between the town and it’s border), and the fancy irregularity function should have a low gradient in this regime (such that you won’t get rapidly oscillating/zig-zaggy borders) (an inverse power-law should do).
Also, each term can contain random-constant factors, however it’s probably keep these random number close to each other to avoid balance issues.


#113

But metric should not depend on position, just on distance betwen points A and B.

The only issue I see now is that on very small or very large maps x or y dimensions dominate the metric. The solution is to scale coefficients proportionally to map size (or use relative values instead of absolute coordinates).

I would like to have randomized center positions of zones, but constant (thus reliable) metric.


#114

Tricky distance calculation is cool - this may make border randomization steep from original non needed.
Can this be somehow used for roads/rivers? (draw shortest road with non euclidean metric)


#115

I don’t understand the reasoning here or what you mean by a “reliable metric” here, but to avoid confusion, let me summarize some properties of a metric:
[ul]
] bilinear (not satisfied by the current implementation)/:m]
] symmetric (not satisfied by the current implementation)/:m]
] can be position dependent (see this for example) (current implementation is coordinate-independent)/:m][/ul]

What I meant by random-constant factors is something like this: in 2+1 space-time, imagine you’re putting some extra mass around the center of the zone (=where town is), the masses and their distribution is random, but the range of the random number is small, that is, these masses are distributed close to the town. This will give some little randomization while retaining the balance between zones.


#116

The reasoning is that we are making reliable and playable random map generator, not solving Einstein’s equation from the link you provided.

Proposed metric is symmetric, at least, in a sense that the distance from point A to B is equal to distance from B to A.

I didn’t choose this algorithm because it’s the best one possible, just because it’s simple and straightforward.


#117

That’s not what a symmetric metric is though (in fact, and again, there is no metric-whatsoever there either, see my previous post --what you have is some made up function of dx and dy that has nothing to do with metric or differential geometry); distances are symmetric by definition on the other hand, if the distances from/to point A to/from B are not equal, it’s not a distance at all. Well, sure, it looks organic and OK for your test cases, I hope pathological cases won’t appear often. Not that anything I say or how mathematically broken the model you’re using is likely to change your mind anyway.


#118

There is no model here at all, since there is no phenomenon we could model. I’m not trying to model anything, but to solve a problem of zone shaping.

Anyway, much more interesting thing was recently implemented gravity (electromagnetism?) based algorithm for zone placement:
We treat each zone as a sphere. Zones that are connected are attracted, zones that overlap each other or map boundaries are pushed away. At each step vector sum of all these forces is calculated and zones are moved around.
Additionally, efter each iteration the gravity constant (previously “temperature”) is reduced - be it good or bad. Either way, this gives really balanced zone placement on pair with Voronoi partitioning.

i118.photobucket.com/albums/o102/DjFaust/VCMI/RMG03_zps12667666.png


#119

Looks good. Now I think its time to make zone border blocking and zone connections. This this also show how good gravity works.


#120

Why top-left corner looks like that? I mean huge swamp area with tiny snow area. Is this because of zone sizes defined in template? Or this is due to function used?

Apart from that looks good :slight_smile: