Map Database  •  FAQ  •  RSS  •  Register  •  Login

Random Map Generator

<<

Toxic

Rogue

Posts: 50

Joined: 22 Feb 2017, 19:04

Post 27 Feb 2017, 19:05

Random Map Generator

This script converts 1 number (it is called Seed) into totally new map. You can specify it in parameter INIT_SEED in the script file or let script to generate Seed randomly.

Download from
RMG Test version 1.zip


How it works?
Short version: Seed -> random number generator (modification of xorshift32 - provide 2^31 original maps (6) ) -> the modification of Diamond-square algorithm (initial grid of points instead of 4 points, works without noise) -> 1 cycle of cellular automata with specific rules (fixing shapes to secure smooth transition) -> shape detection and creation of biomes (secure balanced distribution of resources in map) -> tile and height assignment (huge performance impact) -> object creation.

Note: generated trees cannot be cutted down by woodcutters because of bug in command actions.ObjectSet (KaM version r6720). If you dont want generate initial forests change constant FORESTS to FALSE.
You do not have the required permissions to view the files attached to this post.
Last edited by Toxic on 10 Jun 2017, 16:08, edited 1 time in total.
<<

Lewin

User avatar

KaM Remake Developer

Posts: 3821

Joined: 16 Sep 2007, 22:00

Location: Australia

KaM Skill Level: Skilled

Post 27 Feb 2017, 23:31

Re: Random Map Generator

That's awesome!! :)

For a seed you can use States.KaMRandomI. That gives you access to the engine's RNG, which is given a random seed each time a mission is started (the random seed is synced in multiplayer obviously). In fact you can use it as your random number generator if you like, it should be fast.

Yes the terrain modification functions are slow because they recompute pathfinding stuff every single time. As Krom said it would be much better to implement it in the game code since it will be fast (you can do pathfinding stuff once after making all the modifications). You'll also have access to useful things like our terrain painting functions from the map editor which take care of setting transition tiles.

If your generator ends up sufficiently advanced we could discuss adding it to the game.

Our source code is on Github:
https://github.com/Kromster80/kam_remake/
There's some documentation about getting it compiling here:
https://github.com/Kromster80/kam_remak ... ompilation
<<

Krom

User avatar

Knights Province Developer

Posts: 3237

Joined: 09 May 2006, 22:00

Location: Russia

KaM Skill Level: Fair

Post 28 Feb 2017, 15:12

Re: Random Map Generator

This is awesome!

For illustrative purposes - this is the map I've got:

kam_rmg.jpg


The algorithm took just 3.79sec to make it. Not too long in my opinion :)
You do not have the required permissions to view the files attached to this post.
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
<<

Rey

User avatar

KaM Remake Developer

Posts: 209

Joined: 12 Oct 2016, 07:41

Location: Moscow

KaM Skill Level: Fair

Post 28 Feb 2017, 17:09

Re: Random Map Generator

Yeah, this script is great!

I am very impressed with it. Not so many lines of code, and working pretty fast.

To check Lewin's suggestion about recomputing pathfinding every time you modify map tile I added new method for bunch update of array of tiles and recompute pathfinding once after all tiles are modified.

Here is the results:
GenerateMapOld 10 runs. Average execution time = 5772 (with passability updates on every tile change, MapTileSet function)
GenerateMapNew 10 runs. Average execution time = 2730 (with new bunch of tiles update function)

But I have to say, that for some reason GenerateMapOld are executed slower and slower on run tests. But anyway the first run of GenerateTiles (old version) was about 2 sec, while the last was about 4.5 sec.
New GenerateTiles function executes less then for a second. So at least 1 sec out of ~4 (on my pretty ok PC) that can be saved.

So its about 25% faster, good result anyway. I will add this function soon.

Are you planing to develop it further on ? Its great now, but to make it more "playable" in real life you need to adjust resources (gold/coal/iron). May be some mountain chains could be great, so locs could be more closed one from another. And all that you can configure ... Not sure if it easy or not to do that though.

Also it would be nice to have similar generator function in MapEditor... Just for fun at least ... :)
<<

Rey

User avatar

KaM Remake Developer

Posts: 209

Joined: 12 Oct 2016, 07:41

Location: Moscow

KaM Skill Level: Fair

Post 28 Feb 2017, 18:08

Re: Random Map Generator

_
<<

vovets1

User avatar

Sword Fighter

Posts: 357

Joined: 20 May 2012, 08:59

Location: Russia

KaM Skill Level: Veteran

Post 28 Feb 2017, 18:09

Re: Random Map Generator

Just couldn't resist of doing a meme for it. Great job!
You do not have the required permissions to view the files attached to this post.
<<

Toxic

Rogue

Posts: 50

Joined: 22 Feb 2017, 19:04

Post 28 Feb 2017, 20:08

Re: Random Map Generator

Lewin wrote:For a seed you can use States.KaMRandomI...

This is how it already works. Until the seed cannot be set in the game interface, it is better to use my own RNG (xorshift should be one of the fastest algorithm). I need max 200 000 randomly generated numbers for each map so it is not the issue. An implementation in the game makes sence only if there will be interface which allows players to set parameters of generated map - size, resources, composition of biomes etc. All of those can be set right now from the script file.

Rey wrote:I added new method for bunch update of array of tiles and recompute pathfinding once after all tiles are modified.

Thank you. Just consider that the highest performance consumption takes command actions.MapTileHeightSet(...) - my script changes height significantly only at non-walking tiles (water, mountains) anywhere else it is just white noise +-5 from original height. For example, if you try to make sine wave (amplitude 0<->100) in a grass texture via script, the game will propably crash (loading time takes over 10 minutes in my Pc). I guess that it will totaly break a pathfinding function due to sharp transition between updated and original tile. Sometimes happens: "EAssertionFailed: UpdateWalkConnect failed due too many unconnected areas" in file KaM Remake\Trunk\src\KM_TerrainWalkConnect.pas, line 294.

Rey wrote:... to make it more "playable" in real life you need to adjust resources (gold/coal/iron).

Right now, the resources are computed using a function (consideration: distance, size, shape and ratings) which parameters were choosen experimentally and without testing. However I think that it should be at least playable.
Rey wrote:May be some mountain chains could be great, so locs could be more closed one from another.

Basicaly, all tiles which are not clear grass can be potentionaly mountains or other non-walking texture - I personaly prefer water over mountains and also prefer smaller shapes with more roads between them over huge mountains and camp tactics. This is why locs are divided especially by water biomes. Hoewer, it can be easily changed.
<<

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 28 Feb 2017, 21:07

Re: Random Map Generator

Very impressive! A slap in the face to all who said a random map generator wouldn't work. :) Love it!
<<

Esthlos

User avatar

Knight

Posts: 676

Joined: 23 Jun 2013, 16:02

KaM Skill Level: Beginner

Post 28 Feb 2017, 23:50

Re: Random Map Generator

Awesome, good job!
I vote for adding it as an actual feature in the main KaM Remake release. :mrgreen:
Just when you think you know something, you have to look at it in another way, even though it may seem silly or wrong. You must try! - John Keating, "Dead Poets Society"
<<

sado1

User avatar

Council Member

Posts: 1396

Joined: 21 May 2012, 19:13

KaM Skill Level: Skilled

Post 01 Mar 2017, 10:37

Re: Random Map Generator

O.o

Amazing proof of concept. A slap in the face indeed, for wannabe scripters like myself, and for wannabe mapmakers (koczis would say "like sado" xD). This still looks better than countless CR "remakes" :D (if this ever gets implemented in game, we need a "CR mode" for the generator)

How ambitious can this idea become in the future? I can already expect some people asking whether there's anything that could be done to improve the visual quality of such generated maps, but it doesn't look too bad for the start. Some loose ideas I'd have would be to:
-new constants for setting number of players, iron/goldmine spots, amount of coal per loc, etc.
-auto storehouse positions (I believe the locs should be generated starting from the storehouse point somehow), and constants to set stuff like, how far the basic resources will be, how much space per loc there should be, etc.
-style of locations layout: left vs right vertical (a'la The Final Frontier), L-shaped left vs right, etc...
-campiness of locs
...

Of course, this list is VERY optimistic about what can be done, and what you would be willing to do. Consider this more of a "if you're looking for directions on how to improve it in long term" than "I want this to replace human mapmakers". It's highly unlikely for now that I'll ever play a satisfying eco game on a randomly generated map, there'd have to be loads of work put into the generator before this can happen, so for now it's only a really interesting fun thing to play with.

If you're looking for a fun and not too hard thing to do... current code generates a potential good enough fighting map in my opinion. Adding some randomly placed random troops (same way like on Cross, random but same for everyone) and stuff for every player shouldn't be too hard, and it would be fun to show this around with something to do other than staring at the blank map.
<<

thunder

User avatar

Moorbach's Guard

Posts: 1024

Joined: 15 Apr 2012, 12:11

Location: In the Market

KaM Skill Level: Fair

Post 01 Mar 2017, 12:14

Re: Random Map Generator

WoWowo! Amaizing!
I got a map with medium quality which is far better than many of of the "clear style" maps. It's amaizing job! This script is a great start of this project.
Random map generator was idea a half decade ago also but then it would take many time to implement it. Seems dynamic scripts realy opened and gave solutions to mayn things.
good job!
<<

thunder

User avatar

Moorbach's Guard

Posts: 1024

Joined: 15 Apr 2012, 12:11

Location: In the Market

KaM Skill Level: Fair

Post 01 Mar 2017, 13:08

Re: Random Map Generator

Hi again!

It is the first test version of your script. I hope you will work more on it and will add some more feuteres. I would like to share with you something which can help to upgrade your script.
TXC_map average.xlsx

Here is a table with more than 40maps and more than 250locations. These values from the popular maps.
The average values could help to optimalizate your location generating. Added resources, resource distances from the storehouse etc... If the values are near to the average then a location is quite well playable. The very low or very high values can change the dificulties of course.

Size of a location is depending of how large is the PT. Larger PT->larger locations. For 60min PT the average is 2500tiles but over 1900tiles with lower amount of resources can be OK. Personaly I like to use ~2200tiles .
There is an interesting values also which could be important when generating fighting zones. An average map's fighting zone size is around 30% of the whole map with 7-8 well eliminated area.

Bests!
t


PS: I use to follow this method to editing maps because it saves lots of time to making maps manually.
Step by step:
Round 1-*Painting
1st - place storehouses- It will predict lot about the game already. and paint a 12-15tiles radius circle and place resources aroun this circle.
2nd -stonehill (with 1-2bigger parts)
3rd -goldmountain (2-3slots)
4th -ironmountain (2-3slots)
5th -coalfields (be enough to approximately 9-12coalmine near to gold mountain)
6th -placements of the forests balancing locations with placement. 2-3forests with 12-18trees.
7th -+1random little hill/lake in the location (~10-15tiles from the storehouse and be useless).
8th -'close' all locations- draw the entranaces of the locs
9th -filling out the space between the locations with the main objects of the fighting zones.Bridges, hills,passages and with the most important unwalkable areas etc...
10th - micro painting -shapes of the grasslands and forests, waterfalls and speciel objects.

Round 2- *elevations
Grass is level 0
brown tiles/murds goes to deeper level -1
sand grass and sandy tils +1
hills +1 +2 from grass
water, rivers, beaches the deepest

Round3-*final checks with sliders and settings.
You do not have the required permissions to view the files attached to this post.
<<

Toxic

Rogue

Posts: 50

Joined: 22 Feb 2017, 19:04

Post 01 Mar 2017, 19:55

Re: Random Map Generator

sado1 wrote:How ambitious can this idea become in the future?

This script is limited especialy by missing the textures of transitions. Right now, you have only grass-something transition. It will secure together with settings in Diamond-square algorithm that you are always able to get from position X to Y (mountains will not divide map to 2 inaccessible sectors). All this without testing. However, I think that every idea could be done ... if you dont mind that map will be loaded over 15-30 min :wink: .

sado1 wrote:...new constants for setting number of players, iron/goldmine spots, amount of coal per loc, etc.

It is already there ... just hidden inside a function. There should be an option to set it from the game. To make the new version of map isnt always good solution when you want just to edit parameters.

sado1 wrote:...auto storehouse positions

I like actual solution where players can choose initial position with protected (black) area around choosed location. There could be possibility to restict this position in 1/X of map for each team.

sado1 wrote:...style of locations layout: left vs right vertical (a'la The Final Frontier), L-shaped left vs right, etc...

Style makes from map generator something like map modificator ... I am 100% sure that if you tune up the right parameters you will get a result like you suggested (simply 2^31 maps provide good chance). The goal is that those styles are just piece of cake of all possible solutions which you can get it from. Obliviously, I do not expect that every generated map is good but I like the fact that it will make everytime something new.

thunder wrote:I use to follow this method to editing maps because it saves lots of time to making maps manually.

This is an exelent example how players should create map. However, it is something totaly different in the case of PC where you have just "couple random numbers". You can see that in my script players can place storehouse after everything is done => generating map by PC is completely different point of view. My procedure is described in the first comment.
<<

Rey

User avatar

KaM Remake Developer

Posts: 209

Joined: 12 Oct 2016, 07:41

Location: Moscow

KaM Skill Level: Fair

Post 01 Mar 2017, 20:57

Re: Random Map Generator

I almost finished new func developing. Some code refactoring was needed.

Unfortunally time was not reduced significally. Here are the results (where numbers are milliseconds):

Init time: 45
DiamondSquare: 699
Rules: 217
DetectShapes: 423
GenerateTiles: 1214 (your previous realisation was about ~1600-2000ms on my PC)
GenerateObjects: 173
MapTilesArraySet: 40

Where 'MapTilesArraySet' is an new function, which receives as input parameter array of all tiles with terrain type,rotation,height and object. It was executed very fast - only 40 milliseconds.
So all other time it was script execution. I believe problem is that execution in pascal script is significally (may be 100 times) slower then in main game code.

For example, if you try to make sine wave (amplitude 0<->100) in a grass texture via script, the game will propably crash (loading time takes over 10 minutes in my Pc)

With new function I easily make sine wave on terrain from script, it took just a few milliseconds:

Image

**Update**
I went even further... check it out (20mb short video): https://puu.sh/upOeh/faaab8e4f3.mp4
:lol:
<<

thibmo

User avatar

Council Member

Posts: 121

Joined: 03 Aug 2015, 09:12

Location: the Netherlands

KaM Skill Level: Skilled

Post 01 Mar 2017, 23:31

Re: Random Map Generator

What the.. xDD
+1

//EDIT: What was your FPS during that clip? Did the script have an impact or was it about the normal FPS?
It could open up some interesting ideas, like maps that change based upon the choices of the player(s)
~~ The magic wizard of PascalScriptus. ~~

KP-Wiki :
  • Information about Knights Province scripting ( unofficial )
  • Information about several hosting/server maintenance basics
  • Other random stuff
Next

Return to Dynamic Scripting

Who is online

Users browsing this forum: No registered users and 1 guest