[Random Map] Realistic Terrain Demo

[Spahbod]

OK, I fiddled with the code a bit. It seems that these lines in the end are the cause of the problem:

myReliefmap = getRescaledReliefmap(myReliefmap, heightRange.min, heightRange.max); // This is risky since it might bring players on another height!
setReliefmap(myReliefmap);

You basically lower the grounds where there are trees into the water area. Your placers and constraints are working properly.

I commented them out, deleted the extra "setReliefmap(myReliefmap);" in other parts of the code, and it worked. It seems that you should change the way you generate the map a bit to fix it.

[niektb]

Hehe, wrong topic .

[FeXoR]

I want to find the shortest "circular" path to connect all start positions.

I wrote a function for getting all permutations of player numbers:

function getOrders(elements){var orders = [];if (elements.length < 2)return [elements];else{for (var i = 0; i < elements.length; i++){var newElements = deepcopy(elements);newElements.splice(i, 1);var newOrders = getOrders(newElements);for (var k = 0; k < newOrders.length; k++)orders.push([elements[i]].concat(newOrders[k]));}}return orders;}// DEBUGvar elements = [];for (var i = 0; i < 8; i++){elements.push(i);log((i + 1) + ": " + uneval(getOrders(elements)));}

Sadly this is really REALLY slow!

In fact Atlas returns an OOM error if trying to run this for up to 10 players...

Since I want to generate a circular road only (numberOfPlayers - 1)! / 2 different calculations has to be done (-1 because the start of the "circle" doesn't matter and /2 because the reverse order is the same).

Example for 4 players (always starting from player 1, the reverse orders are stroke):

[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2]

Sadly for 5 players it's not the first half starting with player 1...

So any idea how to make a function for that?

Making my example function faster (and then check for a valid sequence to start with 1 and otherwise check if the reverse sequence was already checked) would be OK too I guess...

Edited March 20, 2014 by FeXoR

[Spahbod]

I want to find the shortest "circular" path to connect all start positions.

I wrote a function for getting all permutations of player numbers:

function getOrders(elements){var orders = [];if (elements.length < 2)return [elements];else{for (var i = 0; i < elements.length; i++){var newElements = deepcopy(elements);newElements.splice(i, 1);var newOrders = getOrders(newElements);for (var k = 0; k < newOrders.length; k++)orders.push([elements[i]].concat(newOrders[k]));}}return orders;}// DEBUGvar elements = [];for (var i = 0; i < 8; i++){elements.push(i);log((i + 1) + ": " + uneval(getOrders(elements)));}

Sadly this is really REALLY slow!

In fact Atlas returns an OOM error if trying to run this for up to 10 players...

Since I want to generate a circular road only (numberOfPlayers - 1)! / 2 different calculations has to be done (-1 because the start of the "circle" doesn't matter and /2 because the reverse order is the same).

Example for 4 players (always starting from player 1, the reverse orders are stroke):

[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2]

Sadly for 5 players it's not the first half starting with player 1...

So any idea how to make a function for that?

Making my example function faster (and then check for a valid sequence to start with 1 and otherwise check if the reverse sequence was already checked) would be OK too I guess...

I'm pretty sure the problem itself is NP-complete (http://en.wikipedia.org/wiki/Np-complete), Which in short means any algorithm that returns the correct answer will be very slow even for small numbers.

Fortunately this particular problem is extensively studied and many good algorithms are devised for it: http://en.wikipedia.org/wiki/Travelling_salesman_problem

[FeXoR]

I'm pretty sure the problem itself is NP-complete (http://en.wikipedia.org/wiki/Np-complete), Which in short means any algorithm that returns the correct answer will be very slow even for small numbers.

Fortunately this particular problem is extensively studied and many good algorithms are devised for it: http://en.wikipedia.org/wiki/Travelling_salesman_problem

I guess you are right for the orders.

Luckily in the case of a closed road there is a much simpler solution (THX leper!) since the path will never cross itself in the optimal solution (I forgot that):

So we just start with 3 players in any order and calculate the path's length (3 distance checks).

Then we pick another player and calculate the difference of the path's length for putting him in any of the 3 possible positions (2 * 3 = 6 distance checks).

And so on.

For 8 players that leads to 3 + 2 * (3+4+5+6+7) = 53 distance checks (compared to 8 * (8 - 1)! / 2 = 20160 distance checks with my previous method ^^).

Edited March 20, 2014 by FeXoR

[FeXoR]

The "player connectivity" problem is solved.

Sadly it takes long ATM (the entire hightmap is passed back and forth throughout functions to often. I'll fix that shortly).

Here's an example:

Overview:

Valley:

Dam:

The terrain alteration is much to strong sometimes but I will fix this alongside the "hightmap passed to many times" issue.

realisticTerrainDemo2014-3-20.zip

Edited March 20, 2014 by FeXoR

[niektb]

Cool! Especially those valleys! They might come in handy in my Schwarzwald map.

[sanderd17]

The "player connectivity" problem is solved.

Sadly it takes long ATM (the entire hightmap is passed back and forth throughout functions to often. I'll fix that shortly).

Normally, passing around stuff (even if it's big) between JS function doesn't cause performance problems. That's because everything is passed by reference. Iterating over big arrays multiple times, or passing big objects through the Engine to other parts of the code (either C++ code or other scripts) does cause performance problems, as the Engine has to clone the JS values.

[FeXoR]

Normally, passing around stuff (even if it's big) between JS function doesn't cause performance problems. That's because everything is passed by reference. Iterating over big arrays multiple times, or passing big objects through the Engine to other parts of the code (either C++ code or other scripts) does cause performance problems, as the Engine has to clone the JS values.

Well, maybe I'm missing something.

If I use:

myHeightmap = getBasicHeightmap(bla, blub); function paths(heightmap, ...){...heightmap = getSmoothedHeightmap(heightmap);...} paths(myHeightmap, ...)

The heightmap is not altered at all.

So I return the hightmap in the path function and use it with myHeightmap = path(myHeightmap) and that works.

So what am I doing wrong?

(guess if I use deepcopy and return once in the process (here in getSmoothedHeightmap) I have to use it always (since the reference is broken then)?)

I just never know when it's better to set something directly in a function and when its better to return the result and leave the original untouched...

I guess for big objects like the heightmap direct manipulation is (most of the times) better than deepcopy and return. It's just getting to resource intense otherwise (?)

Edited March 20, 2014 by FeXoR

[sanderd17]

Because '=' sets the reference value. I don't know the GetSmoothedHeightmap function, but since you say the heightmap isn't edited, the GetSmoothedHeightmap function must make a new object in some way.

That means the heightmap variable will hold a different address after the assignment.

In JS (at least with the SpiderMonkey implementation), every new object causes a new "type" to be made in the background. That type holds the information of the available keys, and the types those keys can store. Creating of modifying such a type can cost some time. The bigger the type, the more time it costs. That's why deleting a key (with the delete keyword) is no good idea. Adding keys goes quite fast. Modifying the type a key can hold is somewhere between the two.

So when you can modify the existing heightmap into the smoothed heightmap without changing the type while doing that (so only assigning numbers to the keys that already had numbers assigned), it should go a bit faster.

But for smoothing, you probably have to access some neighbours that were already processed. To remember that, you either need to introduce new keys to solve the old value (which isn't good, as those keys become part of the type, while it isn't needed for further processing, and it causes more memory usage than needed), or you need to store it in a separate object, which isn't good either, as you're constantly cloning parts of the heightmap to separate objects. So I think, for smoothing the heightmap, creating a new object would be the best option. If you'd have to f.e. level up the heightmap with 1 meter. Then you don't need the old value of the neighbours, so you don't have to copy values in some way, which means it will be faster to edit the object directly.

[FeXoR]

Yes, I need 2 heightmaps for some functions.

In global heightmap manipulation functions (meaning every value might be change) it doesn't matter for it's speed if I manipulate the old object given to the function and generate a new one as a reference or use the given one as reference and return an entirely new one.

But for functions calling this function it makes a difference in usage (if I just call it or if I set something to it's output).

And the reference to the original object in the calling function will be broken if I use the original as reference returning a new object (which is bad in some cases)..

On the other hand returning an entirely new object enables the calling function to have both objects at hand easily (wich might be handy in other cases).

However, the getSmoothedHeightmap (in the map it's rectangularSmooth (line 502) since it was never meant to return a value) functions does only change local values in a small rectangle so in this case it's better to directly manipulate the heightmap and use the (much smaller) rectangular area as reference (and in the end throw it away) since the new object to generate is much smaller (?).

And other functions can use it by just calling it.

Well, understood a bit better but still not sure if I'll get which way to go in some cases.

Any other input welcome.

Edited March 20, 2014 by FeXoR

[sanderd17]

That seems correct. If you only want to edit a small part of the heightmap, it's better to modify it on the existing object. If you need access to parts of the old data, copying that to a new map before changing it would do the trick. As you don't have to copy everything, it would be a speed gain.

[Yves]

For heightmap data I suggest you have a look at typed arrays.

They should be the best data structure for compact single-typed array data.

That should allow the JS engine to pack the data very closely and should make copying of the whole array efficient. It should just be a single copy of a memory block.

If you use a normal object and the JIT compiler has to figure out that it can pack the data as a compact array, that might not work. If it has to fall back to a generic object structure that's much less efficient. That's the theory at least...

EDIT: We have some code using typed arrays, but they probably aren't fully supported by SpiderMonkey v1.8.5.

If everything goes well I'll commit the upgrade to v24 in a few days though.

[FeXoR]

Thanks much both of you, I'll try using typed arrays.

So...

Much faster and smoother now.

Still to slow for my taste (about 3 secs for the player order and the path's heightmap smoothing on a normal map with 8 players).

And the paths partially devastate the nice terrain but, well...

(Guess I'll try doing some terrain analysis to skip unneeded paths)

Example (Overview/Valley/Dam, seed 6200, medium, 5 players):

Map:

realisticTerrainDemo2014-3-20b.zip

Edited March 20, 2014 by FeXoR

[FeXoR]

I rewrote all functions so they now directly manipulate the heightmap (and use (deep)copies of it if they need a reference).

So now every manipulation should take place on float32arrays.

However, map generation now needs ~2 secs more though I also use deepcopy less often.

Code structure got straighter in the process though.

I also use the center of the diamond square generated heightmaps now so presets work much better now.

realisticTerrainDemo2014-3-21.zip

EDIT: Did some texture changes depending on the biome. Now I hope thinks look much less weird:

realisticTerrainDemo2014-3-21b.zip

I now did all I could think of so far (not very pleased with the textures but much better).

It's not good enough I'll abandon the random biome stuff and paint everything myself.

Oh, and forgot beautification of the secondary resource spots...

(OK some things still to do...)

Anyway, input on style and especially playtest would be helpfull.

Some more screenshots:

Edited March 21, 2014 by FeXoR

[Yves]

Wow some of these maps look gorgeous!

Too many Cypress trees can look a bit weird like in this example:

./pyrogenesis -autostart-random=6200 -autostart-size=384 -autostart-players=4 -autostart=realisticTerrainDemo

And there are some cases where there are so many trees that:

1. The spatial subdivision problem occurs. But that's an engine problem and not a problem of the random map.
2. It lags very bad.

Maybe you should still try to limit the density of forests with some sorts of trees a bit.

An example causing a lot of lag:

./pyrogenesis -autostart-random=600 -autostart-size=384 -autostart-players=4 -autostart=realisticTerrainDemo

Generally the maps are generated relatively quickly (less than 10 sec for this size), so I don't know if tuning even makes sense.

Why do you want faster map generation?

EDIT:

The winter maps with snow look the best IMO. Other biomes sometimes have a bit boring ground textures.

This map is my favourite so far (with some AI players, enjoy the battle!):

./pyrogenesis -autostart-random=7555 -autostart-size=256 -autostart-players=4 -autostart=realisticTerrainDemo -autostart-ai=1:aegis -autostart-ai=2:aegis -autostart-ai=3:aegis -autostart-ai=4:aegis -autostart-civ=1:gaul -autostart-civ=2:brit

[FeXoR]

Thx!

Yes, the generation time is not really a problem for me. Just thought the speed increase would be quite noticeable.

The speed depends much on the seed so I don't think it really became slower.

Tree density:

Lowered it.

Textures:

Well, I'll try by hand which pairs look well on a wide area and which single textures does.

Then I will see what biomes work well and set them up by hand.

Paths:

Actually draw some texture on the paths.

(Was a bit out of motivation when I wrote the last post but it's back now ^^)

Edited March 21, 2014 by FeXoR

[Radagast.]

This is stunning work!! The snow one really makes a good impression! The others are also very interesting. If I'm honest, I can hardly grasp it's all randomly generated. Wow.

I wonder if you use this information already for your paths: (I guess you do .. ah, just realised the rivers are missing. wanted to sell yourself under value? )

.. you could make the paths more clear with textures. When you start, it's not very clear how you can get off your hill, or if you can climb a certain mountian or not. In atlas, you can enable the passability overlay (in the terrain section). if you set it to "default", you'll see where every unit can pass. Then you can colour the passable bits of the hills with a different texture (something like gravel or similar).

Edited March 23, 2014 by Hephaestion

[FeXoR]

Thx!

Rivers (and lakes on different levels):

If you mean this I didn't use it because it's slow and I can't set different water levels so it would not look very nice.

I finished the Alpine biome and noticed some problems:

- Textures (placement):

Using a single texture leads to regularly repeated terrain. Using multiple textures leads to the loss of their beauty if randomly placed.

(Possible solution: Divide the map into irregular polygons (of target size) and place one texture per polygon. Some work and may be slow)

- The distance fog is brownish by default! IMO it should be gray... I didn't find how to change it in RMS (e.g. here).

- Textures (not fitting textures of one biome):

In the Alpine biome there are different types of grass (most looking awesome) but many don't fit to each other.

Some are bluish (In fact I never saw such grass though I was in the alps quite often) while others are (mainly) pure green. They don't fit to each other at all.

[My impression of the alpes was much more gray (rock with a little moss, some lichen and few but deep green grass/plant spots like alpine_mountainside) and rich dark green grass (mainly in wind covered areas below cliffs and in high valleys/hollows like alpine_grass or even greener/darker/richer).]

Any suggestions for texturing welcome!

realisticTerrainDemo2014-3-23_alpine.zip

Some screenshots:

Other things to do:

- Try to fasten base terrain generation by using splice()

- Add avoid class (or similar) support for terrain placement and paint the paths

- Reduce water murkiness, lighten water color (EDIT: Done. See last picture)

Edited March 23, 2014 by FeXoR

[Spahbod]

- The distance fog is brownish by default! IMO it should be gray... I didn't find how to change it in RMS (e.g. here).

setFogColor(r,g, b )

You can also use post proc graphics in your maps. Best to check an existing map to see how they work.

[FeXoR]

setFogColor(r,g, b )

You can also use post proc graphics in your maps. Best to check an existing map to see how they work.

Thx! Updated the RMGEN lib reference track pages environment section (removed setWaterShininess since I couldn't find it anywhere, is this correct?).

I'll bother about the general ambience later I think.

I couldn't find though why the fog was brownish before. It's set to 0.8/0.8/0.8 by default (environment.js) and that should be gray.

However, setting it to the same value in my map makes it gray (removing the line makes it browniish again ofc.)...

EDIT:

Hm, Atlas seams to reset it after rmgen libs are loaded:

log("g_Environment.Fog.FogColor = " + uneval(g_Environment.Fog.FogColor));

Output: g_Environment.Fog.FogColor = ({r:0.847059, g:0.737255, b:0.482353, a:0})

Edited March 24, 2014 by FeXoR

[niektb]

I quickly looked through your code and I think it's time to give Schwarzwald an update (especially giving the initial heightmap more usefulness is important to me)

But could you explain how the paths would flow through the map, around the edge or directly from player to player? And how do I avoid dams (since I don't want a dam running straight through my lake)?

And what are you doing with the textueByHeight array? Nothing as it looks to me.

[feneur]

As far as I can see from loading up Atlas and looking at the settings there the default fog is actually slightly bluish. Not sure how/where that interacts with environment.js/random maps though. Just tried in Atlas generating a random map, and at least from just looking it seemed as if the settings are the default. But again, I don't know the actual code or anything, just what I see when I try things

[FeXoR]

textueByHeight:

Yes, I don't use it any more and I'll remove it soon. It's just a relic from the randomBiome usage.

Paths:

Tailing from player to player (mainly straight). It's simple to make bend paths though so they would likely not go through the lake.

(see the path placement in Deep Forest e.g. use "- 0.5 * pathAngleOff, 1.5 * pathAngleOff" instead of "-pathAngleOff, pathAngleOff".

However, this should only be needed for 2 and maybe 3 players.)

BTW: My new code had a bug in the angle setting (x/y angles where independent). Thx for making me find it ^^.

EDIT: I just noticed that if you use a random player derivation it's not clear if the path will bend in or out...

(so you have to find out if the path is placed clockwise or counter clockwise first or even better place the start positions by angle, not by height so you know the order of them. This should work for your map since it's general shape is roughly rotation-symmetric.)

Fog color:

OK, found it. Atlas does nothing obviously wrong.

I roll the random biome multiple times to force the biome to be alpine (to test it). The alpine biome does not change the fog color but some biomes do.

(Biome savanah has the fog settings {r:0.847059, g:0.737255, b:0.482353, a:0} so this was rolled before hitting the apline biome)

Sorry for the confusion and thx feneur!

Edited March 24, 2014 by FeXoR

[niektb]

I guess you could make huge texturing improvements by adapting a combination of height-based texturing and slope-based texturing.