Random map : Alpine Mountains

[Feldfeld]

Hey guys, here is my try at making mountains in 0 A.D. with the new random map "Alpine Mountains", inspired by the skirmish map of the same name :

However, sometimes the generation can make a player separated from the rest due to forest blocking the path, this should be fixed sometimes later.
The recommanded map sizes to put in the settings is one size larger than what you would typically do for mainland type maps. It would be something like Medium for 2-3 players, Normal for 4-5 players, Large for 6-8 players .
Hope you will enjoy it.

Download here :
feldmap.zip

Edited June 22, 2020 by Feldfeld

[fatherbushido]

@Feldfeld it's more like the "vosges" than the "alpes" :D

I would say it looks better than a "try"!

 

[Feldfeld]

Thanks, that could make for a better name indeed, "Alpine Mountains" feels kinda generic

[niektb]

Only Vosges Mountains don't have any snow and are much more forested IIRC (been on holidays there for a couple of times but looooong ago)

[badosu]

You can make passages to ensure at least some pathway is free: https://github.com/0ad/0ad/blob/master/binaries/data/mods/public/maps/random/rmgen-common/gaia_terrain.js#L537

E.g. you make all players have a passage to the center or to other players. I'll check this map out!!

Edited June 20, 2020 by badosu

[Feldfeld]

46 minutes ago, niektb said:

Only Vosges Mountains don't have any snow and are much more forested IIRC (been on holidays there for a couple of times but looooong ago)

Yeah, also they are not very tall. I think my map ressembles more the feel of the alps except the shape of the mountains isn't quite there yet, too round/regular overall.

43 minutes ago, badosu said:

You can make passages to ensure at least some pathway is free: https://github.com/0ad/0ad/blob/master/binaries/data/mods/public/maps/random/rmgen-common/gaia_terrain.js#L537

E.g. you make all players have a passage to the center or to other players. I'll check this map out!!

I know, but the result would probably look ugly in my case I think.
My dream would have been to somehow be able to use the pathfinder to :
- reject non valid generations
- enlarge existing but small path (for better gameplay)
- possibly paint some roads

[badosu]

Instead of making an obvious passage you can use the smooth painter for elevation, so the path is at least trespassable. You can also make hills avoid other hills, or use a special class for other non-trespassable obstacles

Edited June 20, 2020 by badosu

[smiley]

53 minutes ago, Feldfeld said:

My dream would have been to somehow be able to use the pathfinder to :
- reject non valid generations
- enlarge existing but small path (for better gameplay)
- possibly paint some roads

You don't really need the pathfinder to do that. You just need to flood fill for non mountain tileclasses and see if your two points are connected. But you have to use the underlying storage of tileclasses for optimal performance. But this should not be that slow since the N in O(N^2) would remain in acceptable values.

For nicer mountains, I suggest using fractal generation. More specifically, subdivision generation. The concept is rather simple. Split into half, add height, repeat. The only issue might be that there just aren't enough vertices in 0ad terrain.

 

I might have some code to throw your way which I used to generate some screenshot worthy maps with regards to more natural looking forests.Will post if I managed to find it.

[Feldfeld]

27 minutes ago, badosu said:

Instead of making an obvious passage you can use the smooth painter for elevation, so the path is at least trespassable.

Yeah, but wouldn't it be weird being able to climb in some mountains but not others (or even being able to climb mountains at all, in this case) ? Also it would make the shape of the mountains less random (I think)

27 minutes ago, badosu said:

You can also make hills avoid other hills,

At first glance it looks incompatible with the way I generate mountains, however there could indeed be a way to do that by sophisticating a bit my algorithm. With the way I imagine now it would still make the mountains look a bit less natural however (and would still not guarrantee a valid map). 

I can always bruteforce a way to make this map reliable for multiplayer, but whether i want to do that is another question xd

[Feldfeld]

2 minutes ago, smiley said:

You don't really need the pathfinder to do that. You just need to flood fill for non mountain tileclasses and see if your two points are connected. But you have to use the underlying storage of tileclasses for optimal performance. But this should not be that slow since the N in O(N^2) would remain in acceptable values.

Oh yeah, that's true, it's a good solution. (still the 2 other benefits the pathfinder can bring could be nice but far from crucial)

5 minutes ago, smiley said:

For nicer mountains, I suggest using fractal generation. More specifically, subdivision generation. The concept is rather simple. Split into half, add height, repeat. The only issue might be that there just aren't enough vertices in 0ad terrain.

That looks interesting, I'll search that when i have some time.

[smiley]

density_placer.js

Submit it to upstream if you think that's worth having there. I am not sure I have much use for that now.

[FeXoR]

You could also just place path tiles (no changes to the map, just add an area) and then avoid those tiles while generating mountains.

As @smiley proposed the mountains could be more beautiful using different methods. An alternative would e.g. a diamond square method (setBaseTerrainDiamondSquare in heihgtmap.js) like used in Caledonian Meadown. There is no painter for that yet though.

[fatherbushido]

6 hours ago, Feldfeld said:

more the feel of the alps except the shape of the mountains isn't quite there yet, too round/regular overall.

yes that's what I meant ;-)

(for the alps you also forgot the purple cow!)

[Feldfeld]

I updated the map using flood fill. I saw @FeXoR put a todo for that. My implementation could probably be generalized. The forests can still block the passage, though, so i'll have to modify the map later to fix that. There's also the nomad case.
I also modified the map a bit. It now can generate 4v4 Tiny maps with a few internal retries :

Overall, the map is much more reliable now.

 

Quote

You could also just place path tiles (no changes to the map, just add an area) and then avoid those tiles while generating mountains.

As @smiley proposed the mountains could be more beautiful using different methods. An alternative would e.g. a diamond square method (setBaseTerrainDiamondSquare in heihgtmap.js) like used in Caledonian Meadown. There is no painter for that yet though.

Thanks for the suggestions. I'll look into that diamond square method sometimes later.

Edited June 20, 2020 by Feldfeld

[smiley]

General comment on the flood fill algorithm.

When testing reachability, there is no reason to not stop once a connection has been established.

Edit: disregard the comments below. You are already using a stack it seems.

~~Keeping that in mind, for most cases, using a stack (the data structure) might lead to a connection being found faster than if you were using a queue.

If you visualise your algorithm, you would see the fill expanding like a diamond (actually a square oriented diagonally). If you were using a stack, the fill would be expanding line by line. Vertical lines going across the whole area. The probability of hitting the target is much higher. Especially if the target is an area rather than a point.

Basically, last in first out instead of first in fast out. But implementing a stack is more complex than a queue.~~

Edited June 20, 2020 by smiley

[Feldfeld]

7 hours ago, smiley said:

General comment on the flood fill algorithm.

When testing reachability, there is no reason to not stop once a connection has been established.

Edit: disregard the comments below. You are already using a stack it seems.

~~Keeping that in mind, for most cases, using a stack (the data structure) might lead to a connection being found faster than if you were using a queue.

If you visualise your algorithm, you would see the fill expanding like a diamond (actually a square oriented diagonally). If you were using a stack, the fill would be expanding line by line. Vertical lines going across the whole area. The probability of hitting the target is much higher. Especially if the target is an area rather than a point.

Basically, last in first out instead of first in fast out. But implementing a stack is more complex than a queue.~~

Thanks for the comment. Yeah, I didn't do the early stop as it would imply some more checks during the algorithm but guess it's faster after all. Will change for next version.

[fatherbushido]

@Feldfeld@smiley

You can talk about that at another interesting place :p

https://webchat.freenode.net/#forkad

[smiley]

4 hours ago, Feldfeld said:

Yeah, I didn't do the early stop as it would imply some more checks during the algorithm but guess it's faster after all. Will change for next version.

Can you abstract it a bit and make it part of rmgen/math.js?

And submit a patch of course. (code.wildfiregames.com is fine by me). It can be reviewed more easily and committed (at least to the one I commit to).

[Feldfeld]

Alright, so upon testing with other players we discovered that there is a problem with post processing. If you see something like this :

You need to disable post processing in options.
I'm don't know about graphisms so I don't know why this bug happens.

2 hours ago, smiley said:

Can you abstract it a bit and make it part of rmgen/math.js?

And submit a patch of course. (code.wildfiregames.com is fine by me). It can be reviewed more easily and committed (at least to the one I commit to).

Yeah, I'll submit a patch for flood fill, along with the map in my next update, except if the graphic issues turn out to be too much of a problem.

[Stan`]

Can you give us reproduction steps ?

[nani]

34 minutes ago, Feldfeld said:

Alright, so upon testing with other players we discovered that there is a problem with post processing. If you see something like this :

You need to disable post processing in options.
I'm don't know about graphisms so I don't know why this bug happens.

Yeah, I'll submit a patch for flood fill, along with the map in my next update, except if the graphic issues turn out to be too much of a problem.

You have probably changed the contrast or the hdi strength with in the code, usually those are at the end of the map script code, check that.

[Feldfeld]

Yeah, problem fixed, I had put the line 

setPPEffect("hdr");

as I copied the graphic settings from a skirmish map.

[badosu]

Oh, I thought that was  a lava-themed map :-)

[Feldfeld]

New update, the most notable change is that can't be separated by forests now. A patch has also been submited on Phabricator.

Edited June 22, 2020 by Feldfeld

[badosu]

I tested it, the mountains and ranges look pretty good!

I found two issues:

- Players can spawn side by side or too close often, you might want to make them avoid with a bigger radius. For this reason, and mountains occupying a big amount of territory i think normal might be the best format atm
- In one occasion the chickens could not be placed for a players, maybe it's an issue with elevation, or additional straggler wood. But I couldn't pinpoint the issue.