Using Markov chains for Random Maps beautification

[wraitii]

This is an idea I've had from reading /r/SubredditSimulator, a subreddit where bots post content using Markov chains. I've been giving it some thinking and I thought I'd share it.
I don't have yet anything to show for it as I'm unable to code at the moment, but might try it later.

The idea is quite simple: let's use some sort of markov Chains to make our random maps nicer. The biggest problems in our random maps, in terms of niceness, is not so much the larger elements (such as continent shape, ...) but the finer details. It just looks too random quite often, compared to scenarios.

My idea is simply to use markov chains to replicate those scenario achievements in random maps.
I won't go into details on markov chains (google it), but basically the idea would be to analyze scenarios of a similar biome (or may only one map, if it's good enough. Fiddling with the data would be needed.), and then use this as a database in a "beautification" pass for random maps.

So RM would still create the maps as we do know, put terrains as we do know, then add basic "necessary" entities, such as trees, player entities, and could also add some larger beautification elements.
Then we'd go into a beautification pass. I see a few ways this could work:

• For each "important" entity, check what "decoration" entities are usually placed around (from the markov chains) and place those.
• For each terrain type, check which decoration entities can be found around

Possibly this would require us to "pre-sort" important entities by checking how many important entities they have around (as you might place different stuff around a lone tree than in a forest), but this would have to be checked.

It might be extended to actual terrains too, to make it easier to have nice transitions, but I'm not entirely sure it'd work so well.

Just an idea, anyways.

[vladislavbelov]

Markov chains are very good for generate recognizable details of landscapes and it works very well, but it needs a lot of data.

Do we have so number of scenarios map?

Else we will get generating rules, which don't depend on map type (hot, island and etc).

Edited June 24, 2015 by vladislavbelov

[shokodemon]

registered for this!

this sounds like a good idea. my exams will be done around the end of july - i will read up about markov chains then and we can take a look at it.

let's study the random gen code together and see what we can come up with. as to training, we'll see. maybe a half -trained markov is better than a non-trained random gen - and if the maps it makes are good, they can be fed to it in return.

[wraitii]

Created a Githbub repo for a simple python script that sort of implements this.

For now it's very naive and only uses entities as a source.

https://github.com/wraitii/0-AD-RM-beautifier/

 

Sample output: http://pastebin.com/11MLkwTZ

[niektb]

Now what does it do and how do I use it?

[wraitii]

Added a mod to simply see the effects: https://github.com/wraitii/0-AD-RM-beautifier

Just use the beautifier mod.

Basically this automatically adds beautification elements around entities. The mod overdoes it so you can see the changes.

[FeXoR]

Works fine, well done!

The main thing missing are the "terrain objects" (see map.js line 292 ++). Most trees are terrain objects as huntable/domesticated animals on many maps.

Distribution is not circular but will do as a start.

I think both the analysis and placement distances should be increased to at least 3 tiles (12m) though the analysis might take quite long with higher distances.

Many actors are placed "under" the entity because of the low distance. Using the squareroot (beautifier.js line 18: randFloat(-1,1) -> Math.pow(randFloat(-1,1), 0.5) ) will reduce such cases.

I didn't print a screenshot because I didn't find a good before/after example, sry.

EDIT: This will definitely become a feature used by most maps!

[FeXoR]

I added the terrain objects to be beautified and woila:

Only the trees are placed by the map script itself, the rest is beautification!

beautifier2016-6-4.zip

[niektb]

I think the amount of actors added is too big (it reminds me of the maps I made in the beginning that ran with ~2 fps because of the amount of actors  ) Are those deers placed as well? (that might not be wanted from gameplay perspective, as a RMS scripter you want to be sure about the amount of animals added and not rely on some random beautifier placement) 

[wraitii]

FYI, the mod runs the beautification 4 times when it should really just be run one time, to overdo it.

Here are some screenshots from a modded Kerala with no beautification. I added a flag for all added props. As you can see it adds a lot of props, particularly under dense amount of trees.

 

I've also updated the github repo with the latest version of the script and mod. It now takes basic distances into account so the result is overall better.

 

[FeXoR]

26 minutes ago, niektb said:

Are those deers placed as well?

Ah, no. Those are placed by the map script. Only actors are placed by that beautification function AFAIK.

[wraitii]

Yes, the script currently loops over entities (and only entities) to add actors (and only actors).

Ultimately I think it should also run over actors to add actors. I don't see adding entities working very well overall.

[wraitii]

New comparison screenshot over SVN RM Syria. I'll let you guess which is with and without.

[elexis]

The output looks really nice, but I feel this should be done by the map generation in the first place

[wraitii]

I don't think a beautification pass like that is really easy to do during the map generation. It might be helped by better integration with the random map generator though.

I've kept the work up, now working on adding more "meta" info. I've also added a function to add a given amount of actors, so you can easily set your density. Results at "2","10" and "100".

[wraitii]

I've been adding more stuff. First thing is I now open the PMP files, which allowed me to sort which actors go over water and which go under (or both), to avoid weirdness.

I also added the possibility of adding "rules", for example a map might decide to not add entities around a certain fauna/flora element, or forbid some actors from appearing (useful on volcanic lands for example).

Finally I've added a beautifier based on the terrain texture, but it only works on some textures (check out Oasis) so it's not as useful as I'd hoped. It could probably be modified slightly to become a more uniform way of placing actors around a map though.

At this point I'm not entirely sure what to add next, so I invite everyone to play a bit with it and see if they like it. Generally speaking I think it looks good, needs a few tweaks.

 

Just download the mod at https://github.com/wraitii/0-AD-RM-beautifier

 

[Lion.Kanzen]

1. the beatification are only with natural element or you introduce some kind human interaction?
2. when will near to have a svn version? because I can share with my friends to publicity...

[wraitii]

1. Only actors, not sure what you mean exactly otherwise

2.It's for SVN (and should also work for alpha 20)

[Lion.Kanzen]

ruins, huts, eyecandy stuff, roads textures, wells, abandoned buildings(ruins but not destroyed).

[FeXoR]

To be a real marcov chain it would  need to have entities and actors in the (square) matrix IMO.

The advantage would be that objects could then be placed continously over any size of area without entities to start with (or only one entity to start with).

The disadvantage would be that also placing entities means less controll of the map designer about resource distribution and ammount

 

So maybe let's just sick with only placing actors and maybe do a full map generation script with real marcov chains (best if also including terrain texture) later.

[niektb]

Actually it would be really fun to use this on hand-made skirmish maps. Saves tons of detailling work...

[wraitii]

Should be somewhat trivial to adapt to use in skirmish maps as the "script" part, then you could load it up, open the map on Atlas, save it, remove the script. I agree it would be a nifty Atlas tool also, but I don't think Atlas supports running arbitrary JS, so it'd have to be C++, and that would make it much more complicated to implement.

 

As for creating a more complete map using real markov chains, it sounds possible but I think it'd require a different, more "top down" approach.