random map script performance improvements

[elexis]

Some map generations are inacceptably slow and consume up to 3 minutes, whereas most maps are done within 15 seconds.

With #4950 we have log message entries measuring the time for each step in all maps. Here the biggest hits with normal mapsize:

Alpine valleys 
	Creating mountainrange with 500 possible edges... 133.229s.

english channel
	Creating tributary rivers... 183.528s.

danubius
	Creating spawn points for ships... 7.621s.
	Creating patrol points for ships... 4.989s.
	Creating ungarrison points for ships... 11.109s.

deep forest 
	Painting paths... 6.879s.

extinct volcano
	Creating hills... 6.028s.
	Creating forests... 5.960s.
	Creating hill patches... 12.319s.

frontier
	Creating plateaus... 20.481s.

hells pass
	Creating lakes... 15.883s.
	Creating bluffs... 30.356s.

islands
	Creating big islands... 6.262s.
	Creating small islands... 6.127s.

kerala
	Creating hills... 9.072s.

migration
	Creating shore jaggedness... 26.056s.

pyrenean sierra
	Creating forests... 20.743s.

rhine marshlands
	Creating bumps... 13.460s.

sahel
	Creating big patches... 5.457s.

sahel watering holes
	Creating rivers... 6.017s.
	Creating bumps... 6.743s.
	Creating hills... 4.524s.
	Creating forests... 0.001s.
	Creating dirt patches... 7.111s.

Stronghold
	Creating valleys... 7.431s.
	Creating plateaus... 20.617s.
	Creating forests... 8.884s.

Syria
	Creating bumps... 11.347s.

As reported in #4695, the 25 seconds on danubius are needless and can be cut down by not using the deprecated group placement functions.

[elexis]

In 21082:

Implement a ConvexPolygonPlacer that returns all points in the convex hull of some given points.
Implements the Gift-Wrapping algorithm to compute the convex hull.

Replace the latter half of the pathplacer with this new placer, refs #892.
Improves the performance a bit, refs #5011.

Use the new placer on Kerala and Hyrcanian Shores to replace the workaround from rP20933, refs #4855
(the area is not supposed to be parallel to the meandering river).

[elexis]

• I suspect getAngle might be faster by using the cross product.
• #4957

[elexis]

Often rmgen is slow when we need to do many retries to place entities that have a low likelihood of being placed by chance in a position that meets all constraints.

For instance on Danubius it is unlikely to get a random coordinate that is on an island to place a tower there. Then we need a high amount of retries to compensate and it consumes up to 10 seconds. Should use createObjectGroupsByAreas.

[elexis]

6 player normal-sized Danubius before improvement:

Generating Danubius of size 320 and 6 players.
Creating gallic villages... 0.259s.
Creating playerbases... 0.109s.
Creating river... 0.215s.
Creating shores... 0.057s.
Creating bumps... 2.794s.
Creating hills... 0.924s.
Creating forests... 3.752s.
Creating grass patches... 0.838s.
Creating islands... 0.836s.
Creating bumps... 0.361s.
Painting seabed... 0.042s.
Creating island metal mines... 0.543s.
Creating island stone mines... 0.582s.
Creating island towers... 0.859s.
Creating island outposts... 0.957s.
Creating metal mines... 0.629s.
Creating stone mines... 0.887s.
Creating stone ruins... 0.860s.
Creating decoratives... 0.000s.
Creating decoration... 0.207s.
Creating decoration... 0.098s.
Creating fish... 0.000s.
Creating food... 0.170s.
Creating huntable animals... 0.000s.
Creating food... 0.043s.
Creating violent animals... 0.000s.
Creating food... 0.040s.
Creating fruits... 0.000s.
Creating food... 0.021s.
Creating straggler trees... 0.312s.
Creating straggler trees... 0.915s.
Creating animals on islands... 0.000s.
Creating food... 0.318s.
Creating treasures... 0.006s.
Creating gallic decoratives... 0.001s.
Creating decoration... 0.027s.
Creating spawn points for ships... 7.456s.
Creating patrol points for ships... 4.959s.
Creating ungarrison points for ships... 10.847s.
Creating riverdirection triggerpoint... 0.005s.
Creating patrol points for land attackers... 44.786s.
Creating water logs... 0.021s.
Setting day theme... 0.002s.
Total map generation time: 85.806s.

Same replay after improvement:

Generating Danubius of size 320 and 6 players.
Creating gallic villages... 0.267s.
Creating playerbases... 0.111s.
Creating river... 0.479s.
Creating shores... 0.074s.
Creating bumps... 2.791s.
Creating hills... 0.927s.
Creating forests... 3.746s.
Creating grass patches... 0.824s.
Creating islands... 0.822s.
Creating bumps... 0.345s.
Painting seabed... 0.032s.
Creating island metal mines... 0.087s.
Creating island stone mines... 0.128s.
Creating island towers... 0.086s.
Creating island outposts... 0.201s.
Creating metal mines... 0.047s.
Creating stone mines... 0.220s.
Creating stone ruins... 0.012s.
Creating decoratives... 0.000s.
Creating decoration... 0.192s.
Creating decoration... 0.101s.
Creating fish... 0.000s.
Creating food... 0.166s.
Creating huntable animals... 0.000s.
Creating food... 0.052s.
Creating violent animals... 0.000s.
Creating food... 0.039s.
Creating fruits... 0.000s.
Creating food... 0.017s.
Creating straggler trees... 0.289s.
Creating straggler trees... 0.934s.
Creating animals on islands... 0.000s.
Creating food... 0.311s.
Creating treasures... 0.000s.
Creating gallic decoratives... 0.000s.
Creating decoration... 0.019s.
Creating spawn points for ships... 0.261s.
Creating patrol points for ships... 0.319s.
Creating ungarrison points for ships... 1.566s.
Creating riverdirection triggerpoint... 0.000s.
Creating patrol points for siege engines... 0.467s.
Creating patrol points for soldiers... 0.167s.
Creating water logs... 0.008s.
Setting night theme... 0.000s.
Total map generation time: 16.174s.
Total entities: 4646.

[elexis]

In 21088:

Accelerate Danubius map generation performance, from 90 seconds to 15 seconds, refs #5011.

Use the non-deprecated createObjectGroups variants, so that one doesn't have to do 10 million placement attempts...
Mark the area (land, water, island) and only chose random locations from these areas using createObjectGroupsByAreas.
Don't ignore the map border for siege engine patrol points, because AvoidClassesConstraint is very slow for large radiuses.

[elexis]

In 21092:

Performance improvement on Kerala, refs #5011.

[elexis]

I suspect we could use a StaticConstraint, or pass two constraints (static and mutable) to createAreas.

For instance when placing animals, we have avoidClasses(clForest, 1, clMetal, 4, clRock 4, ..., clFood 2). In createAreas we pick a random coordinate of the map or given areas and then throw that away if it's too close to mines, trees or food. But the tree and mine tileclasses never change when placing, only the clFood tileclass. So only the clFood has to be reevaluated, while the other classes can be evaluated at the beginning of a call.

This is similar to the createAreasByAreas function, but we likely want to avoid creating the area for the performance improvement in every single call, hence the StaticConstraint idea, in case that is achievable.

[elexis]

avoidClasses becomes slow with numbers of 10 and greater. One could improve the performance by marking more of the area with the tileclass and avoiding that are a less.

For example clMetal is only placed at the center tile of the mine afaik, but a 4x4 square (which covers the current obstruction size) would be better for performance.

[elexis]

In 21134:

Arbitrarily constrain the random playerbase location function.

Decrease the minimum distance between players progressively to find suitable locations.
Assume that constraint to be constant and compute possible locations in advance, improving performance drastically, refs #5011.

[elexis]

In 21175:

Implement SmoothingPainter for random maps, fixes #5027.

This allows only specific regions of the map to be smoothened, especially important on imported digital elevation models.
It uses the Inverse Distance Weighting / Shepard's method as mentioned by Imarok and formerly implemented in the Pyrenean Sierra map by wraitii in rP12248.

Supersedes the globalSmoothHeightmap function in FeXoRs heightmap library, refs #3764.
Drop the heightmap argument to be consistent with the other painters.
If painting on arbitrary heightmaps is wished, the createArea mechanism, all Placers, Painters, Constraints and Areas can and should support that.

Update the HeightmapPainter from rP21133 to not break if TILE_CENTERED_HEIGHT_MAP is enabled (i.e. numVertices = numTiles), refs #5018.
Use that mode on Mediterranean and Red Sea.
Drop the disabling of bicubic interpolation in the HeightmapPainter instead of extending it to this feature.

Inevitable smoothing performance improvement for Belgian Uplands (from 45 to 15 seconds per call), even if it implies a somewhat different outcome, refs #5011.

[elexis]

In 21300:

Ambush bluffs rework.
Remove ugly large circle patterns around the playerbase on Ambush, fixes #4993.
To ensure passability, create ramps from the playerbase to the bluffs.

Change the circular player avoidance to a ChainPlacer generating more heterogenous pattern.
Use vectors in rmgen2 bluffs creation and simplify equations, refs #4992.
Don't turn inaccessible bluffs to plateaus but don't place them until it is certain they are passable.

Increase minimum distance from the playerbase to the mapcenter by picking different distance values per playerbase pattern in g_PlayerbaseTypes.
Attempt to improve bluffs performance by avoiding bluffIgnore by 0 instead of bluff by 12, refs #5011.
Implement AdjacentToAreaConstraint and deleteTerrainEntity.
Delete createBoundingBox and use getBoundingBox, refs #4947, #4805.
Delete fadeToGround and nextToFeature and use conventional createArea calls with the SmoothingPainter of rP21175, refs #5027.
Paint bluff cliffs slightly more accurately using the SlopeConstraint from rP21085, refs #5004.

[elexis]

In 21401:

Implement StaticConstraint, refs #5011.

This allows random map scripts to evaluate a set of slow constraints once and then only access a cache of the results later,
rather than reevaluating the constraints for every randomized coordinate.
Remove an unused comment following rP21356.

[elexis]

In 21414:

Add "has" helper function to TileClass, so that one can find out if the given tile is marked with that class or not without having to fallback to Constraints.
Performance improvement for Ambush, refs #5011.

[elexis]

In 21418:

Performance improvement for the StaticConstraint by not initializing the cache upon construction but filling it just-in-time, refs #5011.

[elexis]

In 21419:

Always use the StaticConstraint for createPassage nomad player placement to improve the performance on some random maps slightly, refs #5011.

[elexis]

In 21425:

Improve random map script performance by using squared distance where possible, refs #5011.

RandomPathPlacer.js diff proposed and reviewed by FeXoR

[elexis]

In 21440:

Fix trees on hills on Survival Of The Fittest following rP19358 / D145.
Use the StaticConstraint to reduce map generation time by 50%, refs #5011.

[elexis]

NearTileClassConstraint can return true early if the first match has been found, doesn't have to compute all matches.

[elexis]

If avoidClasses receives multiple classes, it will iterate the affected area once per tileclass. Instead it could iterate only once over the largest area and test the affected classes from the center to the border. But that might also be slower because usually the tileclasses shold be ordered to have the most likely one to avoid first (for performance reasons).

[elexis]

problem: One can often not estimate well how many entities should be placed for every mapsize and how many retries are necessary to place as many entities as one wants to. So one overshoots and then the code runs hundreds of retries that can never succeed and cost lot of time.

mapscript solution: first compute the area, then place entities inside there. Disadvantage: scales badly with larger mapsizes, more code complexity, repetitive.

rmgen solution: createObjectGruops could have a new option to keep track of locations already tested and not test that location again, thence return early before all retries are performed.

[elexis]

avoidClasses precomputation optimization:

The performance of an avoidClasses(tileclass, distance) constraint can be optimized by computing the grid differently after the last tile was marked with tileclass. The tileclass can remember the points that were marked. Then when the last tileclass was marked, it can do breadth-first-search outwards from the given points and remember the closest distance to the tileclass. The BFS can be stopped after the largest distance to be searched was processed.

This would be faster in situations where the constraint is performed on many tiles.

Anti-use-case: For example if an area that makes up 10% of the map is marked with that tileclass and with the avoidClasses distance it would extend to 20% of the maparea, then the BFS will take a lot longer to be performed than the current "test-on-demand" approach if the latter would succeed after only a handful of calls (for example only 5 entities placed with that constraint and the constraint is true with 80% probability in our example, so almost no retries).

Use-case: Sometimes many dozens of areas and objectgroup calls must avoid the playerbase, but with different distances (for example 15 for resources and actors, 25 for animals, water and hills, 60 for fortresses). Here we can assume that the order of magnitude of the map area is tested (the constraint tested multiple times per tile).

Precomputing the constraint with createArea is wasteful, because the area is processed once per constraint and because it doesn't consume the benefit of skipping the computation of avoidClasses calls that are known to return false, while the proposed algorithm does. The StaticConstraint doesn't help either, so the proposal maybe worth to be implemented if we carefully observe enough use cases that can't be solved more elegantly.

[elexis]

RangeOp optimization:

In 'tileclass.js` we find:

if (radius >= 27) // Switchover point before RangeOp actually performs better than a straight algorithm

To me it's always faster, cutting mapgen time from 60s to 30s on one map! It does change mapgen, so it either influences RNG or has a bug somewhere.

We should have a performance test that figures out the best value for the given test, computer, SpiderMonkey version, providing an indicator for easy maintenance by a developer and testing that the two algorithms compute the same result.

[elexis]

Test to visualize the difference between RangeOp and the default algorithm. They ought to compute the same result.

[elexis]

refs ​Phab:D1640 ​Phab:D1641 ​Phab:D1587

[phosit]

More ideas how to improve performance: #5305