Map Database  •  FAQ  •  RSS  •  Register  •  Login

Random Map Generator

<<

Toxic

Rogue

Posts: 50

Joined: 22 Feb 2017, 19:04

Post 10 Jun 2017, 15:58

Random Map Generator

Random Map Generator (RMG)


There were people who wanted to see my progress with RMG so here is my algorithm which converts one single number (it is called Seed) into totally new map. I chose this section because RMG isn't part of Dynamics scripting anymore - native code is ~100x faster than script code so RMG procedure is approximately shortened to hundreds of milliseconds now (6) .

The parts of the algorithm are following:
  1. Random number generator
  2. Shape generator
  3. Terrain generator
  4. Generator of resources and non-walk textures (mountains, water, etc.)
  5. Functions correcting shapes to secure smooth transitions of textures
  6. Texture generator
  7. Height generator
  8. Objects generator


1. Random number generator
RMG have it's own random number generator. This secures that scripts which use random numbers will be independent on the Seed. There is used simple modification of xorshift32 which generates only positive numbers (RMG doesn't need a good correlation).


2. Shape generator
RMG uses two types of shape generators:
  1. Linear interpolation of grid with random values - from those values are chosen highest and lowest values and it makes the shape of specific texture.
    Example of shapes made by linear interpolation:
    Image
  2. Voronoi diagram - for non-walk textures and resources.
    Example of shapes made by Voronoi diagram:
    Image

3. Terrain generator
Terrain generator uses shapes from linear interpolation to construct various biomes. RMG works with multiple layers (with different size of grid) of this procedure to create nice terrain.
Example of multiple layers which makes various terrain:
Image


4. Generator of resources and non-walk textures (work in progress)
Balanced resources, mountains or water are created from Voronoi diagram. I use this method because it prevents overwriting already existing tiles and gives quite nice shapes.
Example of generated resources from Voronoi diagram:
Image
Example of multiple sets of resources with different Seed:
Image


5. Functions correcting shapes to secure smooth transitions of textures
This is probably the hardest part. Textures in KaM have max 2 transitions (for example water <-> grass). However, in real case is possible to meet 4 different biomes in 1 tile. Even in maps made by best map makers you can find some bugs (non-smooth transitions). RMG must scan the neighborhood of each tile and check for smooth transition.
One of possible problems with transitions of textures (left side = generated shape, right side = created "smooth" transition):
Image

I made for this special cellular automaton (CA). Basicaly it kills separated tiles and replaces them by surrounding neighbors. If you want check all rules of CA you have to visit my code (trust me ... you DON'T want to read it :wink: ).
Map before (top image) and after (down image) CA:
Image


Another problem is the fact that there are not transitions for everything. Actually, the most of biomes have just 2-3 types of transitions textures. This fact is partly fixed in the Terrain generator which doesn't allow to connect 2 biomes without existing transitions textures. Another fix is called 2 shape transitions. It creates transitions on booth sides of the shape in relation to "common" texture. This feature significantly improves possibilities of RMG.
Example of 2 sides transition - map editor will never draw smooth transition here ... RMG does:
Image


Last problem are 3 and 4 tiles transitons (CA will not fix it because it throws too monotonic maps). For those purposes there are special decompositions which will split each texture into 4 segments which are dependent only on the surrounding tiles. In casual (max 2 transitions) case, it will throw a standard smooth texture. In 3 or 4 tiles transition, there is applied another loghic (again ... it is better to live in blissful ignorance :wink: ).

The example of tile decomposition with smooth transition:
Image
The example of tile decomposition with 3 tile transition:
Image


6. Texture generator
This function converts numbers which represent biomes into tiles with right direction and with nice variation.
Image


7. Height generator
Height generator use linear interpolation to calculate the height of each tile. The formula is following:
  Code:
height = value of linear interpolation array (sum of 2-3 layers of LI)
         + minimal height of specific biome (mountains have more, water less etc.)
         + variance of specific biome (random number in specific interval - mountains have huge, water nothing etc.)
         - smooth tile coefficient (if there are 3-4 different tiles in neighborhood then decrease height and hide ugly transition)


Image


8. Objects generator
There are 2 ways how to create objects:
  1. Clumped objects - for example forests -> group of trees around randomly generated point. The type of tree corresponds with the type of biome (you will not find a conifer in a desert and a palm in a snow).
  2. Random objects - each x. tile is random object which is picked by biome where he is (each biome have it's own set of objects which can be used)

Image



More examples of completed maps (note: there was not used mountain fix to secure that all resources can be mined)
Image
Image
Image
Image


Please remember: non-accesible biomes are still in progress...
<<

Toxic

Rogue

Posts: 50

Joined: 22 Feb 2017, 19:04

Post 10 Jun 2017, 15:58

Re: Random Map Generator

Examples of settings
There are basic examples of settings - other items are quite intuitive.

Menu (Work in progress)
Image


Small / Big step of layers (walk textures)
Image
Image


Small / Big step of non-walk textures
Image
Image


Small / Big density of objects
Image
Image


Small / Big Loc-protection area
Image
Image



Players' positions


  • Rectangle
    Image

  • Vertical
    Image

  • Horizontal
    Image

  • Random
    Image

  • Center Screen
    Image
    Image

Note: all of those maps were generated by 1 Seed.
Last edited by Toxic on 16 Aug 2017, 13:39, edited 3 times in total.
<<

Krom

User avatar

KaM Remake Developer

Posts: 3233

Joined: 09 May 2006, 22:00

Location: Russia

KaM Skill Level: Fair

Post 10 Jun 2017, 18:16

Re: Random Map Generator

Awesome!
Keep up the good work )
Knights Province at: http://www.knightsprovince.com
KaM Remake at: http://www.kamremake.com
Original MBWR/WR2/AFC/FVR tools at: http://krom.reveur.de
<<

RandomLyrics

User avatar

Sword Fighter

Posts: 293

Joined: 21 Jul 2013, 02:15

KaM Skill Level: Fair

Post 11 Jun 2017, 09:34

Re: Random Map Generator

Great work :)
<<

The Dark Lord

User avatar

King Karolus Servant

Posts: 2152

Joined: 29 Aug 2007, 22:00

Location: In his dark thunderstormy castle

KaM Skill Level: Veteran

Post 11 Jun 2017, 20:46

Re: Random Map Generator

Wow, that's better than most human-made maps. :lol:
What I find particularly interesting is the (seemingly flawless) transition between two mountain types. That requires quite specific elevation!
<<

grayter

Barbarian

Posts: 102

Joined: 18 Aug 2014, 12:06

Location: Poland

KaM Skill Level: Skilled

Post 26 Jun 2017, 07:30

Re: Random Map Generator

This is really awesome :)

Toxic wrote: I chose this section because RMG isn't part of Dynamics scripting anymore - native code is ~100x faster than script code so RMG procedure is approximately shortened to hundreds of milliseconds now (6) .



This project is now official part of kam remake? It will be included in upcoming release?
<<

Rey

User avatar

KaM Remake Developer

Posts: 206

Joined: 12 Oct 2016, 07:41

Location: Moscow

KaM Skill Level: Fair

Post 30 Jun 2017, 21:44

Re: Random Map Generator

This project is now official part of kam remake? It will be included in upcoming release?

Yes, if
1) this feature will be finished:
Its very unique and in perfect world it could add new great game mode. But its not easy to make really playable - it should be balanced RMG map.
2) if release will come at some day:
Number of small improvement are already finished. But mostly they are not about gameplay/balance - some cosmetic/convience stuff/bug fixes/map editor features etc. Full list you can check here (done features marked with '+')
<<

Toxic

Rogue

Posts: 50

Joined: 22 Feb 2017, 19:04

Post 03 Jul 2017, 13:33

Re: Random Map Generator

grayter wrote:This project is now official part of kam remake? It will be included in upcoming release?


Right now is RMG implemented like a feature of the Map Editor. Before it will be done I want to add support of dynamic scripts, saved configuration etc. Here you can see possible settings. I am trying to reduce the amount of free parameters to minimum (there is over 50 different parameters which have huge impact on final map).

Image

Rey wrote:But its not easy to make really playable - it should be balanced RMG map.

I think that RMG map can be more balanced than human-made maps. Here is proof:

Image

Rey wrote:if release will come at some day


:O :mad: :O Noooo way... In this case I will realease my own "version". :wink:
<<

thunder

User avatar

Moorbach's Guard

Posts: 1020

Joined: 15 Apr 2012, 12:11

Location: In the Market

KaM Skill Level: Fair

Post 03 Jul 2017, 21:08

Re: Random Map Generator

I think that RMG map can be more balanced than human-made maps. Here is proof:


Well, the balance depends from lots of things.
Anyway There are few very balanced maps.

My opinion is the random mapgenerator is really good to make the basements (sketch) of a new maps. I'm sure I would use it for one-one project to see how much time to save it for a mapmaker :wink:
Keep up the good work!

PS: I hope you will decrease the irinmining time with 30% in your Remake edition!;P :mrgreen: ofc just joking. :P
<<

zombie01

User avatar

Pikeman

Posts: 152

Joined: 21 Jul 2014, 13:04

KaM Skill Level: Fair

Post 07 Jul 2017, 20:48

Re: Random Map Generator

Toxic wrote:
grayter wrote:This project is now official part of kam remake? It will be included in upcoming release?


Right now is RMG implemented like a feature of the Map Editor. Before it will be done I want to add support of dynamic scripts, saved configuration etc. Here you can see possible settings. I am trying to reduce the amount of free parameters to minimum (there is over 50 different parameters which have huge impact on final map).

Image

Rey wrote:But its not easy to make really playable - it should be balanced RMG map.

I think that RMG map can be more balanced than human-made maps. Here is proof:

Image

Rey wrote:if release will come at some day


:O :mad: :O Noooo way... In this case I will realease my own "version". :wink:


only if you make sure that the starting places of everyone is +- the same amount away.
<<

Michalpl

Sword Fighter

Posts: 318

Joined: 10 May 2014, 21:46

KaM Skill Level: Fair

Post 10 Jul 2017, 10:48

Re: Random Map Generator

This could be nice for testing AI behaviour without needing to switch over so many maps and bug test the AI
<<

Lewin

User avatar

KaM Remake Developer

Posts: 3821

Joined: 16 Sep 2007, 22:00

Location: Australia

KaM Skill Level: Skilled

Post 07 Aug 2017, 02:53

Re: Random Map Generator

I know this is a late reply, but this is really impressive stuff Toxic!

The dream goal for this would be to have a "random map" mode where you select some parameters like map size and a number of AI opponents, then click play and it generates a different random map for you to play on every time.
<<

Toxic

Rogue

Posts: 50

Joined: 22 Feb 2017, 19:04

Post 09 Aug 2017, 18:37

Re: Random Map Generator

thunder wrote:Well, the balance depends from lots of things.

Sure but basically, it depends on balanced resources and a similar area (for a program there are only resources, accessible and inaccessible tiles). I can easily create something like "Mirror version" where you will have 2 totally identical sides of a map (tile by tile). This must be totally balanced map but I think that it will looks ugly. Generally, the RMG works with random numbers and random numbers do unpredictable things.


zombie01 wrote:only if you make sure that the starting places of everyone is +- the same amount away.

I created examples of different players' locs in the second post. I will add another setting where you can change locs manualy by the "Center screen" option in the map editor. So if you have an interesting idea about players' positions but you do not want to create map, you can use RMG :wink: .


Lewin wrote:The dream goal for this would be to have a "random map" mode where you select some parameters like map size and a number of AI opponents, then click play and it generates a different random map for you to play on every time.

I have a problem with this realisation in the single-player. Everytime when I run KaM Remake, the game throws identical random numbers so I cannot randomly set my Seed. I will propably have to create something like a seed-creator from the system time to secure that generated map (RMG + random parameters) will be always different. It should work in the multiplayer.
<<

Krom

User avatar

KaM Remake Developer

Posts: 3233

Joined: 09 May 2006, 22:00

Location: Russia

KaM Skill Level: Fair

Post 11 Aug 2017, 05:42

Re: Random Map Generator

Toxic wrote:I have a problem with this realisation in the single-player. Everytime when I run KaM Remake, the game throws identical random numbers so I cannot randomly set my Seed. I will propably have to create something like a seed-creator from the system time to secure that generated map (RMG + random parameters) will be always different. It should work in the multiplayer.


I'm not sure to what are you referring to:
- RNG in the dynamic scripts - those are indeed have to be identical across all players in multiplayer and for replays.
- RNG between plays are reshuffled (see the https://github.com/Kromster80/kam_remak ... e.pas#L458)

There's no need to invent a seed-creator - using Random() will work just fine. Just keep in mind that it can not be used for gameplay applications - random sequences MUST match between players and between plays/replays.
Knights Province at: http://www.knightsprovince.com
KaM Remake at: http://www.kamremake.com
Original MBWR/WR2/AFC/FVR tools at: http://krom.reveur.de
<<

Toxic

Rogue

Posts: 50

Joined: 22 Feb 2017, 19:04

Post 11 Aug 2017, 06:45

Re: Random Map Generator

Krom wrote:There's no need to invent a seed-creator - using Random() will work just fine. Just keep in mind that it can not be used for gameplay applications - random sequences MUST match between players and between plays/replays.


This is it (line 223+):
  Code:
//Here comes terrain/mission init
  SetKaMSeed(4); //Every time the game will be the same as previous. Good for debug.


And here is real game (line 457+):
  Code:
//Random after StartGame and ViewReplay should match
  if IsMultiplayer then
    SetKaMSeed(fNetworking.NetGameOptions.RandomSeed)
  else
    SetKaMSeed(RandomRange(1, 2147483646));


Right now are random maps generated in the map editor so Seed is always 4. Maybe you should change it and add a condition for debug mode. I just need different Seed and RandomRange does it well.
Next

Return to Map Design

Who is online

Users browsing this forum: No registered users and 2 guests

cron