Yet another random map generator

[elexis]

• TWO_PI -> 2 * Math.PI
• paintMap() -> The map should decide what textures should be painted. There may be no references to globals in the library (tWater, tCliff, ...)
• Names like "fillWith" are a bit common, other libraries might want to add a function with that name too. So we should probably move all of that into a prototype. (I can do that if it's difficult, but it's not really hard, just look at the constraints prototypes for example)

[elexis]

I've created a ticket so that we don't forget this patch #4952.

[Pyrophorus]

22 hours ago, elexis said:

• TWO_PI -> 2 * Math.PI
• paintMap() -> The map should decide what textures should be painted. There may be no references to globals in the library (tWater, tCliff, ...)
• Names like "fillWith" are a bit common, other libraries might want to add a function with that name too. So we should probably move all of that into a prototype. (I can do that if it's difficult, but it's not really hard, just look at the constraints prototypes for example)

OK... That's easy to do. I'll try to add some little (useful, I hope) things, and I will post a new version very soon.

Friendly,

[Pyrophorus]

Hi everyone (and happy new year !)

Here come the code changes asked by @elexis Please note there is no new functionality and this library version works not with previous posted scripts. This is not an update !!!

So, I created two new object definitions: one dedicated to the height map creation, another one for map decoration, each one can be used independently. There are no more simple functions in the library (except a private one), only members functions. Similarly, I removed all global variable uses in the function and replaced them with parameters. I think the code is now fully encapsulated, but it is not final yet: I have to set default parameters and rework fully the comments.

Please tell me if this fits your requirements...

Friendly,

yamg.zip

[elexis]

• alpha 22 rmgen code was changed for alpha 23, but that can be changed quickly when we're done with that
• HeightArray.prototype.createAltitudes has some duplication, that should be unified with a for-loop (or array-function)
• (Math.random() * off) besides the unneeded parentheses, we usually use the random helper functions from random.js, it could be randFloat(0, off)
• TileObjectMap.prototype.paintMap receiving arguments is much better than before, but it still hardcodes meaning and limits what random map scripts can do. Is it true that this function does what paintTerrainBasedOnHeight does? then it could just be moved to each random map script.
• this fills an area with 'terrain' adding actors from 'actorList'. This sounds a lot like what the Terrain prototype in rmgen does. Take a look at how forests are created on most maps, for instance on mainland.js: const pForest1 = [tForestFloor2 + TERRAIN_SEPARATOR + oTree1, tForestFloor2 + TERRAIN_SEPARATOR + oTree2, tForestFloor2]; https://code.wildfiregames.com/source/0ad/browse/ps/trunk/binaries/data/mods/public/maps/random/rmgen/gaia_entities.js

This means that one of the array items is picked at random in each tile of the given area. Some of the items are only a ground texture, other tiles additionally contain a tree entity.

If that Terrain is passed to a LayeredPainter, one can create forests where the outer 2-3 tiles are only forest-border-like ground texture and all the inner part this semi-randomized forest.

This way stuff could be deleted from your library while gaining more features :-) The magic key to placing anything is the createArea and createAreas call. You should really look into the SVN code, it had been cleaned for the past 5 months. I suggest to read the few prototype names and descriptions linked here, to find the capabilities and limitations of rmgen. Basically there are createArea calls which create exactly one area at fixed coordinates passed to a non-centered placer, painted by a painter in areas that meet the given constraint. createAreas creates multiple areas with randomized coordinates. By being able to combine these things arbitrarily, one has a very powerful tool at hand to create entities.

https://code.wildfiregames.com/source/0ad/browse/ps/trunk/binaries/data/mods/public/maps/random/rmgen/placer_centered.js

https://code.wildfiregames.com/source/0ad/browse/ps/trunk/binaries/data/mods/public/maps/random/rmgen/placer_noncentered.js

https://code.wildfiregames.com/source/0ad/browse/ps/trunk/binaries/data/mods/public/maps/random/rmgen/painter.js

https://code.wildfiregames.com/source/0ad/browse/ps/trunk/binaries/data/mods/public/maps/random/rmgen/constraint.js

What we really want is your core heightmap generation algorithm I believe. Maybe it could implement a Placer or Constraint and then the map could use createArea calls with fully arbitrary terrain modification and constraints. If it totally can't fit into that scheme, we might think about adding it to that heightmap library, which is about the diamond-square algorithm.

[Pyrophorus]

Hi !

Thanks for your quick reply.
Except your first three points which are not problematic, I would say maybe I wasn't clear enough about the painting (textures and objects) used in the library. I'm conscious they could be greatly improved using the rmgen library. Actually, I didn't pay much attention to them and the way I use them is only a proof of concept to illustrate height based area creation.

In other words, what is good and new (hopefully) in my filling algorithms is the area definition. The painting and actors placement are a quick and dirty hack and you're right to direct me to improve it. I'm not quite sure I have fully understood the rmgen code yet, but AFAICS, createArea rely on placer objects of various kinds. Maybe a way to achieve a better integration could be to create new placer classes which could be used like the existing ones.

I already had the idea to supply some functions which would return a tile class using the data created in the library (slope, terrain kind and so on). Maybe it could be placers too, and so I could remove from the library all this painting and placing code which lacks generality.

Friendly,

[elexis]

Totally :-)

Well if you just want to paint terrain or place entities on things between minHeight and maxHeight, that is already trivially possible with paintTileClassBasedOnHeight and paintTerrainBasedOnHeight.

One can do things in a split up process as well: 1. mark areas with a tileclass 2. do something unrelated 3. place things in the tileclass (stayClasses)

So for instance a createAreas(new HeightPlacer(minHeight, maxHeight), new TerrainPainter(tForests), [stayClasses(clLand, 2), avoidClasses(clMountain, 2)]) or whatever floats your boat :-)

The HeightPlacer is new in a23.

Pyrenean Sierra and Corsica also do have slope based terrain painting and I'm looking into making a SlopePlacer for that, so that one can paint cliff textures depending on height easily.

I'll take a look at your heightmap generation code to see what it should become. To me it sounds like it could become a Painter. But even if it's just a helper function or prototype would likely be sufficient too. I just don't want this opportunity to go to waste :-)

 

[Pyrophorus]

Hi,

Still a work in progress, but there are significant changes which can be seen in the 'aRandomMap.js':

- I have embedded a rather complex map creation into a 'fullMap' method of HeightArray object. More control is still available anyway as before.

*** Edit: I made a painter object to apply the height creation algorithm to a defined area in the map. See some results here:

The area is created with a ChainPlacer, colored in black and modified with the painter. Here we have some chaotic terrain created  on a flat field. More interesting maybe is the contrary: smoothing a rough area:

 

- All the ground painting and trees setting is now done with createArea  calls, using two new placers objects. The ground painting is not very interesting and probably duplicates other things in rmgen, but it takes into account the tiles slope. The YFillerPlacer is more original and despite elexis opinion, is not another kind of HeightPlacer. It allows to define areas which crawl along the relief, and has much more in common with the ChainPlacer.

This way, I think the library can now nicely melt into rmgen.
Now, my next step is to provide a road Placer (I know, there is already one in rmgen, but mine is a very different algorithm and will not give the same result).

Friendly,

 

 

yamg.zip

Edited January 26, 2018 by Pyrophorus
New features

[FeXoR]

I just noticed that we actually don't have a way to smooth a specific area of terrain yet (there is rectangularSmoothToHeight but this is not exactly the same and the smoothing effect es stronger near the center than the edges). So a painter for that is definitely welcome!

I also find getting and painting areas by slope very useful and think maps could become much more natural looking with much less work when utilized.

Nicely done!

(The terrain still shows artifacts in the direction of the coordinate axis and in a 45° angle to them. It would be nice if those could be removed but otherwise we then have multiple smooth tools now )

[elexis]

The SlopeConstraint is definitely on my TODO list, some maps (see above somewhere) already use it indirectly.

And yep, I missed some smoothing functions too.

[Pyrophorus]

Thanks for your replies,

I have just got an idea to remove the artifacts. Not sure it will work, but I'll test it today.

Now I have still no idea of what you will do with my code. Actually, there are three parts in the library, each of them being independent.

1-  The full map creation.
2- The FractalPainter (standalone)
3- The TileObjectMap on which rely some placers (the fillerPlacer and the road placer in the future, and maybe more) and constraints (BTW, there is already a slope constaint in the library ! ).

Actually, the third object duplicates and enhances the g_Map object, but thanks to Javascript, those members could be added directly to g_Map. My design should not be used as is, but I think it would be nice to add the slope to g_Map for instance. The tile slope is useful in many contexts, and computing it each time one needs it is not very efficient. The slope constraints are trivial to write when you have the slope in g_Map . Same with the iterator which provides the tiles connected to any tile (checking map boundaries), and maybe other members.

Friendly,

[elexis]

I'd take the unique terrain generation + sample map packet without the redundancy.

I assume you're working with alpha 22 code, but that was rewritten for 5 months. I can rebase it, but I expect the TileObjectMap to be dropped and or merged.

Caching the slope might be an idea, but should be measured if really needed (it's better to keep g_Map state minimal).

[FeXoR]

IMO

• Base terrain generation should go to /heightmap (maybe separate in different files but it's not that big yet).
• Painters, placers and constraints should go to /rmgen . Functions they depend on should also go to the same file.
• The g_Map object should IMO only contain stuff that is needed to be exported. Anything else should go into another object (e.g. map_extensions or something). This includes the slope/incline map (vector/scalar) as well as the planned collision map and abstract water height/speed maps (to simulate water driven erosion).

Recomputing those maps over and over again is indeed insanely inefficient. I have the same problem with the collision map (updating whenever an entity is placed is fast but means to hook in the collision system in even if it's not needed - though no performance impact than with a collision.enabled flag. Updating whenever needed means "number of uses" more calculations of the entire map). I think the way to go is "update manually when needed" for those heightmap related maps - though this is prone to induce bugs by oversight. Updating whenever used and update needed might be appropriate in some cases - a copy of the underlying object could be stored and - on change - update the derived thing if used (this is somehow against the "direct access" policy I usually prefer though).

[Pyrophorus]

21 hours ago, elexis said:

I'd take the unique terrain generation + sample map packet without the redundancy.

The parts 1 and 2, if I understand correctly.

 

21 hours ago, elexis said:

I assume you're working with alpha 22 code, but that was rewritten for 5 months. I can rebase it, but I expect the TileObjectMap to be dropped and or merged.

Actually, there is no call to rmgen in those parts, only access to g_Map.height. It should work as is.

I agree with what you and Fexor say about the TileObjectMap (or whatever name we call it). It's seems to me the design is not mature enough to syntheses all those features in a single object.

21 hours ago, FeXoR said:

Recomputing those maps over and over again is indeed insanely inefficient. I have the same problem with the collision map (updating whenever an entity is placed is fast but means to hook in the collision system in even if it's not needed - though no performance impact than with a collision.enabled flag. Updating whenever needed means "number of uses" more calculations of the entire map). I think the way to go is "update manually when needed" for those heightmap related maps - though this is prone to induce bugs by oversight. Updating whenever used and update needed might be appropriate in some cases - a copy of the underlying object could be stored and - on change - update the derived thing if used (this is somehow against the "direct access" policy I usually prefer though).

Yes, I'm aware of this too. The slope member, for instance, remains accurate while you avoid modifying the height map after computing the slope, and reading the various random map scripts, one can see height map manipulation can occur anywhere, not only at the beginning.

I'm aware of efficiency too: javascript is Ok, but... really slow. This is the reason why I added a 'lock' member to my tile object, because I think testing a bitfield with a mask is much faster than fetching one or more arrays to enforce constraints. It's not difficult to create a tile class from a bit pattern or set a lock bit from a tile class, but it must be done 'manually' which is error prone.

BTW, I'm rather surprised rmgen don't provide set operations on tile classes. Maybe, I didn't dig enough

Friendly,

P.S. The idea I had to remove artifacts don't work, or more accurately, removes them but introduces new ones ! too bad !

Edited January 28, 2018 by Pyrophorus

[elexis]

Ambush is one of my favorite maps due to those bluffs / hills, but the perfect circle around the playerbases is so ugly. Correcting an error (artifact) after it has occured is not really good, better prevent introducing that artifact. For bluffs I suspect we just need to set the failfraction to a much lower value than the current 50%, so that the ChainPlacer fails entirely if it runs into a playerbase, rather than returning all points around a circle of the playerbase. Same approach might work for your problem I suppose.

[elexis]

As of #4950 we also have a logger showing how long each operation of the map takes. This way we can identify bottlenecks. How much faster is that bitmask invention? I fear the increased complexity might just make things harder to read and maintain. It's easier if all maps use the same style and all maps can use all features and benefit from the same improvements. Which arrays are we talking about actually? I never timed the RangeOp code used by tileclasses.js.

[Pyrophorus]

Hi,

The artifacts problem in my generation code comes from the the algorithm working on squares, and the height map itself being squares. I think this is why may various attempts to blur the map introduce new artifacts of another kind. Our eyes are trained to detect any geometric shapes even in complex pictures and it's very difficult to fool them.

That said, it's possible to improve the result, for instance using 'globalSmoothHeightmap(1);', which is probably highly advisable: it doesn't change the map too much and improves certainly regions accessibility. But I guess map decoration should be enough to solve the problem. Here is a map, not painted at all, showing clearly some artifacts:

And npw the same, painted in a very plain way:

The artifacts are less noticeable I think, and will probably even less if more decorations are added.

18 hours ago, elexis said:

As of #4950 we also have a logger showing how long each operation of the map takes. This way we can identify bottlenecks. How much faster is that bitmask invention? I fear the increased complexity might just make things harder to read and maintain. It's easier if all maps use the same style and all maps can use all features and benefit from the same improvements. Which arrays are we talking about actually? I never timed the RangeOp code used by tileclasses.js.

Actually, I didn't notice the TileClass object had an inclusion map which is in fact similar to the "bitmask invention", at least in performance  (it costs much more memory, but this is not a problem). And of course, increasing complexity must be avoided if only little benefits are expected.

I made some quick tests on giant maps to identify where some bottlenecks could be.

- First of all, creating a flat map with no painting at all, already takes a few seconds: just  loading the libraries and executing InitMap() and ExportMap(). It certainly could be sped up loading only what is needed.
- Creating a height map, smoothing it, is very fast and don't increase significantly execution time. Adding textures on terrain may add a second. Not a big deal.
- The real problem I found is with placing objects. In the giant map below, I created forests, painting only forest floor, omitting only to place  the trees (with placeObject() ). Costs one second or two even if there are large forests (28 994 trees and a lot more tiles to scan):

Trying to place the 28 994 trees on the snowy areas lead to disaster: Atlas hangs during a minute or so and finally crashes (I have an i7 processor and a lot of RAM).

Friendly,

 

[elexis]

We also have the bicubic interpolation function in rmgen2/ somewhere in case that helps.

Yes, giant maps are totally out of reach currently. The number of entities itself especially. The pathfinder struggles if there are more than 8 * 150 player entities on a normal sized random map.

Given that you speak of InitMap, you must still be developing with alpha 22. That is reasonable on one hand because the library in alpha 23 changes every day. But judging from the screenshots, your project matures and we should start to think about committing something to our codebase.

What matters most to me would be to throw out all redundant code. For instance I assume there is no invention in entiy placement, is there?

The SlopeConstraint was implemented in rP21085 and one can do a createAreas or createObjectGroups on mapBounds using HeightConstraint + SlopeConstraint + avoidClasses to distribute as intended.

About performance, I have replaced the log() entries with a call to g_Map.log() which measures and prints the time between two log calls. This way we can identify performance bottlenecks immediately: #5011. It seems the most of the time (up to multiple minutes) are wasted in pointless loops: Picking a random coordinate on the map and hoping to find a lucky position that isn't in water or a forest. Instead we can compute all locations that aren't water nor forests and then pick a random coordinate within that location and test against the variable constraints.

The biggest refactoring in alpha 23 is that all x / z coordinate pairs were merged into a Vector2D object so that we can utilize the vector operations; replaced all cos/sin operations with one rotate() function; especially the cross products, normalization and perpendicular functions are now much more transparent. This is expected to have a some performance cost attached (creating new objects), but in my tests it had actually improved the performance.

Can you upload a more recent version of your code (so that we can pick it up later in case you get bored)? In case you intend to work longer on that, you could also create a github branch. In case you can clean that library to the essence, rebase it for the alpha 23 codebase (BuildInstructions)  and add one good playable map within the next 2 weeks (maybe little longer, we don't know yet), we might add it to alpha 23. But don't rush things, take the time you need :-)

[Pyrophorus]

On 2/1/2018 at 3:46 PM, elexis said:

Given that you speak of InitMap, you must still be developing with alpha 22. That is reasonable on one hand because the library in alpha 23 changes every day. But judging from the screenshots, your project matures and we should start to think about committing something to our codebase.

What matters most to me would be to throw out all redundant code. For instance I assume there is no invention in entiy placement, is there?

Not yet, at least, given the two weeks delay, I shall not have new things stable enough to get into your codebase. I have made some progresses with the  player base setting, but I have still some way to go before publishing a "good playable map".

Now, I can give you the map creation code and the FractalPainter at once. This code don't rely on rmgen at all. The only point is in the FractalPainter. It uses the "points" member of an area to get coordinates points.x and points.z. I don't know if switching to Vector2D impact this or not. I think it's better to let you choose exactly where to insert the code, and even rename objects if you want. You can either choose to incorporate the fullMap method of the HeightArray object or not. It's more or less a template to use the fractal map creation and you may find it's not the place for this in a library.

Along with alpha23, I agree with you, but I think I have not enough time left to install the dev version whole shebang AND finalizing something of a "good playable map". So, unless you disagree, I will focus on this last goal. Maybe the script shall be more alpha22 than alpha23, but I imagine you maintain some ascending compatibility

Friendly,

 

 

[Pyrophorus]

Hi !

Here are some news:

-- The YAMG library with only the fractal generation program.

-- A first version of a random map script named "Egyptian oasis". Mountains, pools, and of course camels and crocodiles. Here is a preview:

and a more general view:

If I understood correctly, this script is a candidate to enter alpha23 OAD version. I certainly would be glad it would be so, but I doubt because it should be seriously tested before, and time is very short ! That's why I post it today. I know there are still some problems and improvements needed, but I need help to test the main features. Let explain a little:

The script is self sufficient. There is no need to install a library as I inserted all the needed code into. It needs only the standard rmgen and Heightmap libraries. The map creation is done with merging two height maps: a chaotic one for the mountains and a rather soft to install players bases and battlefield. This allow to control rather exactly how much mountains and water are on the map. The real problem with this approach is finding reasonable places for players bases. Most scripts (and maybe all of them), set the bases first and create terrain and relief around. I do the contrary, and my attempt works rather well, I think, but within some limits. Every base has the same starting resources, but the map can advantage neatly some players. Is it playable as is ? I hope some people will get the script and create some maps to give their opinions and criticisms. Suggestions about decorations and such are welcomed of course, but not so deadly wanted. If you find something really ugly, please try to report the seed, map size and players number settings.

The script works without error on any map size, but is not really designed to create tiny or small maps with a lot of players, just because there is not room enough. I think it works best on size within medium to giant.

Doing so, you may encounter some cases where some parts of the map are unreachable and even players probably cannot join, because mountains/water pools are on the way. I aware of this and will provide a solution.

One word about the code (for the braves who dare to put their nose into...). It is not very clean yet, of course. The map creation is not the fullMap() method of the YAMG library but a brand new one. New too is the swiss-knife placer I developed for this. It's a very versatile placer allowing to create quite any area you want, particularly if you want to avoid geometric shapes and patterns. Quite everything is placed with it, except the players starting units and resources which are set with rmgen standard procedures.

Waiting for you feedback...

Friendly yours,

YAMGLibrary.js

EgyptianOasis.zip

[Lion.Kanzen]

@Skhorn

[Skhorn]

Awesome, although i think it deserves more randomness on terrain textures

[Pyrophorus]

8 hours ago, Skhorn said:

Awesome, although i think it deserves more randomness on terrain textures

@Skhorn  I admit willingly the result is not fully satisfactory (I'm not very good at this terrain painting) but i can't see clearly what you mean. Terrains are already painted with four to five different textures chosen at random, but I imagine it is not exactly the randomness you have in mind. Could you make suggestions to improve this ?

Friendly,

[Stan`]

I guess you could try to connect terrain patches better. For now the transition is a bit harsh. 

I guess @elexis might have some more ideas.

[elexis]

On 2/2/2018 at 8:50 PM, Pyrophorus said:

FractalPainter

Gimme gimme gimme!

On 2/2/2018 at 8:50 PM, Pyrophorus said:

It uses the "points" member of an area to get coordinates points.x and points.z. I don't know if switching to Vector2D impact this or not.

Everything is a vector now, especially the points to be placed at. The first random map script commit had introduced both the Vector2D prototype and the Point prototype, but I really don't know why the latter one was done when both objects don't store anything besides the two coordinates. The only difference is that z is now y and we can simplify equations by using the vector operations.

16 hours ago, Pyrophorus said:

The script is self sufficient. There is no need to install a library as I inserted all the needed code into.

If it contains functions that ought to be in the library, then we'll put it in the library. Otherwise we're just adding work for later. But that's not too much work for now. I can transfer it.

16 hours ago, Pyrophorus said:

should be seriously tested

Agree, luckily that only means doing map generations on different sizes, playercounts and looking unreachable entities or blatantly unfairly placed players.

16 hours ago, Pyrophorus said:

Most scripts (and maybe all of them), set the bases first and create terrain and relief around. I do the contrary, and my attempt works rather well, I think, but within some limits

Indeed. FeXoR runs into that problem on Caledonian Meadows too, it often fails on tiny mapsizes. It's just more stable to first place players and then adapt the terrain accordingly. But I understand it's not always possible to achieve. (For instance on the geographic maps like Red Sea too).

16 hours ago, Pyrophorus said:

Every base has the same starting resources, but the map can advantage neatly some players.

That's the case with all maps unless resources are distributed very homogenously. On your screenshot that guy surrounded by mountains and 2 lakes has a really bad map compared to the others. We could try to do something with forest density, but those are details.

16 hours ago, Pyrophorus said:

Suggestions about decorations and such are welcomed of course, but not so deadly wanted

The saver of all boring flat maps: createBumps. Also createPatches / createLayeredPatches to randomize the textures a bit. The mountains should be painted according to Slope with the SlopeConstraint, I can look into it when adapting to a23. Another huge improvement are paths (consider the one on danubius for instance). Lorraine Plaine also shows how paths (here: rivers) can have a treeline parallel to them. It's just hard to try to find a path that doesn't break the terrain, so might need lots of retry loops which in turn can consume too much time. But there are remedies for that too (first computing placeable areas, then finding coordinates within that area, rather than picking random coordinates and testing against constraint that are highly likely to fail).

16 hours ago, Pyrophorus said:

tiny or small maps with a lot of players

Tiny maps with many players are a gimmick anyway. Most maps just place CCs and 10 trees.

16 hours ago, Pyrophorus said:

encounter some cases where some parts of the map are unreachable and even players probably cannot join, because mountains/water pools are on the way. I aware of this and will provide a solution.

That's more problematic. Eventually we will need some reachability test. I also ran into this problem bigtime when reducing the radius of the playerbase flattening on Ambush and had to add a ramp so that the players can reach a nearby bluff (so that they can't be surrounded by an impassable bluff) #4993. A nice solution would be to somehow detect the unreachable case and use createPassage (a23 function) or a PathPlacer + elevation setter to force a way to somewhere else. But tricky to achieve and likely messy (typically paths should be placed first too and terrain only placed around it).

16 hours ago, Pyrophorus said:

swiss-knife placer

Whut? Let me see. (I'm really missing a new centered placer, we only have the two ones, ClumpPlacer and ChainPlacer, which were iirc present when rmgen code was in C++ 12 years ago).

Thanks for the update!