Opened 3 years ago

Closed 3 years ago

Last modified 3 years ago

#4845 closed defect (fixed)

Simplify rmgen code with vector algebra

Reported by: elexis Owned by:
Priority: Should Have Milestone: Alpha 23
Component: Maps Keywords:
Cc: Patch:

Description (last modified by elexis)

In a number of locations in the rmgen library we have equations that are duplicated for each dimension and equations that are the result of vector algebra, but written in an obfuscated way.

By using the Vector2D operations, these functions can become both much shorter and have their geometric meaning expressed instead of the way these are computed.

Thus making it easier for new readers to comprehend and extend the given piece of code.

We should consider switching from X/Y Vectors to X/Z ones: #4834.

Change History (32)

comment:1 by elexis, 3 years ago

Description: modified (diff)

In r20428:
Add Vector3D crossproduct and Vector2D perpendicular function.
Describe geometric features of the two cross- and dot-product functions.

In r20429:

Extend the random map river algorithm (r20185) to allow arbitrary start and end points.

Reverse engineer and cleanup obfuscated Rivers map code, refs r11137.
Use vector algebra to replace magic equations and express geometric intend.
Fix seed typo by removing river curve duplicate.

On the Rivers map, use areAllies directly instead of copying the diplomacies to a 2D array called isRiver.
Use modulo operator instead of an if-statement with duplication to determine the neighbor of the last player, refs r11174.

In r20435:
Further clarify geometric meaning of the river painting in r11137 and r20429.
Refer to the normalized river vector instead of the river vector divided by the length of the river.
Rename mag to magnitude.

comment:2 by elexis, 3 years ago

A really awesome property of the cross product is that it allows computation of things that in other ways do require division by zero checks (for instance the if-statements in checkIfIntersect).

At first it looked like there are only few functions that would benefit from using Vectors (by using vector operations), however it seems the entire rmgen code should use Vectors to address x/z coordinates. (Rewriting everything again will be quick after #4805, #4804, #4831)

comment:3 by elexis, 3 years ago

In 20468:

Add rotateAround Vector2D function.
Remove the rmgen rotateCoordinates helper function from rP20295 and clean the implementation of that commit, refs #4845, #4804.
Deepfreeze mapCenter vector from rP20463 used here to prevent accidental overwrites with the mutating Vector2D functions, refs #4854.

comment:4 by elexis, 3 years ago

In 20469:

Unify the other axis of the 8 remaining playerPlacementRiver calls following rP20151, refs #4805.
Use the rotateAround function from rP20468, refs #4845.
Freely randomize the river angle on Corinthian Isthmus following rP20295 and rP20468, refs #4855.

comment:5 by elexis, 3 years ago

Milestone: Alpha 23Backlog
Status: assignednew

comment:6 by elexis, 3 years ago

In 20723:

Allow Vectors to be rounded.

For instance useful when working with location vectors on arrays, such as terrain generation in random map scripts, refs #4845.

comment:7 by elexis, 3 years ago

In 20732:

Deobfuscate, deduplicate and fix Corsica vs. Sardinia and Pyrenean Sierra, refs rP11266, rP12248.

Use vector algebra instead of adding one equation for each dimension everywhere, refs #4845.
Add common createPassage terrain helper function to unify straightPassageMaker and the modified copy PassMaker, refs #4805.

On Corsica vs Sardinia:

Comfort island shaping by
not hardcoding and not hiding magic numbers behind magic equations,
not specifying areas and deriving the radius from the disk area,
but always refer to newly introduced radius globals and compute the area using diskArea from rP20332.

Don't give some players 10% more map area and place all circular island parts at the same center location in the map corner.
Don't place trees and mines into passages.
Simplify and order numbers, increase fail fractions from 4 to 10.
Use mapCenter getter from refs #4854.

comment:8 by elexis, 3 years ago

In 20758:

Simplify rmgen distanceOfPointFromLine and checkIfIntersect a lot by using vector algebra, refs #4845, #4805, rP13605, rP13613, rP20429.
First createRamp cleanup, rP13618.

comment:9 by elexis, 3 years ago

In 20761:

Delete createRamp which is the same as createPassage, refs #4805, rP13618, rP11266, rP12248.
Use vector algebra to compute the ramp position, refs #4845.

comment:10 by elexis, 3 years ago

In 20775:

Rename getTIPIADBON (The Intended Point In A Direction Based On Height) from rP12110 to findLocationInDirectionBasedOnHeight.

Use vector algebra to simplify it and the according maps, refs #4845.
Remove stepSize parameter as long as the non-interpolated heightmap grid is tested.

comment:11 by elexis, 3 years ago

In 20780:

Delete createShallowsPassage / passageMaker from rP11152 and use the unified createPassage function from rP20732 (rP11266, rP12248) to achieve the same shallows generation, refs #4805.

Place shallows at every tributary river rather than leaving out the last 35 percent of the mapsize.
Use vector algebra to do the horizontal/vertical rotation, refs #4845.

comment:12 by elexis, 3 years ago

In 20787:

Return an array of Vector2D instead of an array of X coordinates and an array of Z coordinates from distributePointsOnCircle, so that one can iterate over the result, refs #4845.
Use map center getter for Rivers and the Unknown maps, refs #4854.

comment:13 by elexis, 3 years ago

In 20806:

Use createPassage from rP20732 to connect islands on Snowflake Searocks to remove weird math, just like rP20780 and rP20761, refs #4805.
Use vector algebra to simplify and mapCenter getter, refs #4845, #4854.

comment:14 by elexis, 3 years ago

In 20815:

Implement random map script playerbase function.
Unifies 54 variants of the rmgen playerbase code, fixes #4805.

Add retry loops to prevent collisions of starting resources, fixes #4600 and
resources placed outside of the map area, fixes #4796.

Lays the foundation to test for collisions with Iberian walls, refs #2192 and
allows to rearrange the starting resources on all random maps without being confronted with code.

Delete remains of misc.js, leaving the rmgen files sorted by logic, fixes #4804.
Concludes what was started in rP18816, rP19282, specifically the 82 rmgen commits starting rP20115, rP20301.
Uses vector algebra, refs #4845.
Removes many Math proxy calls, refs #4933.
Removes 35 unused elevation and 24 unused cliffRadius variables, demonstrating the copy&paste antipattern.
Reduce iberian-wall hardcoding to one line, refs #4940.

comment:15 by elexis, 3 years ago

In 20856:

Use vector algebra for the unconventional playerbase resources on Belgian Uplands, refs #4845.
Add an extra scope since that block will become conditional on nomad maps, refs #3591.

comment:16 by elexis, 3 years ago

In 20858:

Fix unreachable trees on Oasis, fixes #4937.

Use constants instead of convoluting magic numbers
Use vector algebra and distributePointsOnCircle to determine the locations of animals in the oasis, refs #4845.

comment:17 by elexis, 3 years ago

In 20871:

paintRiver cleanup.

Pass vectors, refs #4845.
Pass tile sizes rather than percent numbers of the map, refs #4939.
Replace some water- and land-functions with more common createArea+RectPlacer and paintTerrainBasedOnHeight calls.

Implement getMapBounds to make references easier to read, refs #4854 (and thus less error-prone, refs rP20465).
Move height constants to the top of the files.

Fix Aegean Sea, English Channel and Danubius fadeWidth off by factor of 2 in rP20185.
Fix forgotton clWater in unknown_common of rP20866 and move that createUnknownObjects call to common.

comment:18 by elexis, 3 years ago

In 20879:

Extract a RandomPathPlacer prototype from Deep Forest (rP11444) and Schwarzwald (rP15327) duplication, refs #4805, #4804.

This allows creation of paths that are not linear nor sine-shaped like the PathPlacer, refs #892.
To mimic the per-tile path elevation randomization on Deep Forest, use a SmoothElevationPainter and it's randomization argument from rP20354.
Use vector algebra and the mapCenter getter, refs #4845, #4854.

comment:19 by elexis, 3 years ago

In 20882:

Merge all playerX and playerZ arrays into one array of Vector2D items.

This way random map scripts can do vector math and pass the result to library functions that do further vector math on them and leave shorter code, refs #4845.
Pass tilegrid coordinates rather than percent numbers to the playerbase functions too, refs #4939.
Some more mapCenter calls, refs #4854.

comment:20 by elexis, 3 years ago

In 20891:

Cleanup Island Stronghold starting resources code using vector algebra, mapcenter getter, distributePointsOnCircle, refs #4845, #4854.
Since it is the only map with stronghold placement where the mines are placed facing away from the team center, this code should be moved to a library eventually, refs #3851.

comment:21 by elexis, 3 years ago

In 20892:

Don't call it centerOfMap, center, mid, centerX, centerZ, fractionToTiles(0.5), Math.round(fractionToTiles(0.5)), mapSize / 2, mapSize * 0.5, but just mapCenter everywhere and get it from the library.
Fixes #4854, refs #4845.

comment:22 by elexis, 3 years ago

Milestone: BacklogAlpha 23
Resolution: fixed
Status: newclosed

Marking this as fixed since most of rmgen code uses vectors as of a23.

comment:23 by elexis, 3 years ago

In 20910:

Randomize map orientation on most river maps, Gulf Of Bothnia and Migration to remove hardcoded magic numbers and add more variation for the player.
Refs #4855, #4845.

comment:24 by elexis, 3 years ago

In 20914:

Pyrenean Sierra sigmoid-based Mountainrange cleanup, refs rP12248.

Use vector algebra and remove duplication, refs #4845, #4805.
Unify the first createTerrain call with InitMap.
Move mountain constants and the information which height receives which texture to the top.

comment:25 by elexis, 3 years ago

In 20933:

Randomize map angle on random maps with linear playerposition pattern, refs #4855, #4845.

comment:26 by elexis, 3 years ago

In 20970:

Pass position vectors to the PathPlacer rather than each component individually, refs #4992.

Every PathPlacer constructor already has the two vectors in place, refs #4845.
The code becomes shorter (operations not copied once per dimension) and more readable (normalize, perpendicular).
Performance can improve even.

comment:27 by elexis, 3 years ago

In 20971:

Pass a vector to the ClumpPlacer instead of the vector components individually, refs #4992.
Support non-integer values and remove some unneeded floor / rounds.
Use more vector math in Caledonian Meadows, Oasis and Wild Lake, refs #4845.

comment:28 by elexis, 3 years ago

In 20974:

Pass vectors to the ChainPlacer instead of the components individually, refs #4992, #4845.
Support non-integer numbers.

comment:29 by elexis, 3 years ago

In 20977:

Return vectors instead of objects with x and z property for all Placers and Painters, refs #4992, #4845.

Create the vectors sooner, so that the conditions can use them eventually too and since the loops might be replaced with vector getters.
Fix missing comma in Deep Forest rP20971.
No measurable performance decline was noticed.

comment:30 by elexis, 3 years ago

In 20988:

Use vectors for setTexture, refs #4992.

Simplify duplicate Caledonian Meadows and Wild Lake height-based texture painting by using for-of loops, texture setter and vectors, refs #4845, #4998.
Allow setTexture to write to impassable tiles as reported by FeXoR some time ago, refs #4245.

comment:31 by elexis, 3 years ago

In 21021:

Change placeObject, placeStartingWalls, wall builder library and wall demo to use vectors, refs #4845, #4992.

comment:32 by elexis, 3 years ago

In 21069:

rmgen random placement and Entity instantiation refactoring, fixes #4992.

ChainPlacer, ClumpPlacer, SimpleObject receive the vectors that are in place everywhere already, refs #4845.
Add public setCenterPosition to CenteredPlacer and Group rather than writing private properties of the prototypes.
ChainPlacer and ClumpPlacer simplifications, deduplication and renames, refs #4805.

Replace placeObject global with RandomMap placeEntity members, refs #4804.
Split to placeEntityPassable / placeEntityAnywhere, as well as validTilePassable / validTileAnywhere to more cleanly distinguish actor and casual entity placement.
No more does SimpleObject create Entity instances and register entityIDs if they are never placed.
Removes the map global reference from the Entity constructor, refs #4964.
By definition of what is passed to the engine, an Entity has an ID and position, so keep it impossible to create Entities without IDs.

Implement randomPositionOnTile so that there aren't different implementations thereof, including unintented ones as in ardennes_forest.js in rP21021.
On Caledonian Meadows, remove unused pathplacing code, to be superseded by #4368.
On Schwarzwald, delete unused startLocations following rP20864.
On Latium, replace complicated duplicated hardcoded fish location computation with a simple HeightConstraint, refs #4960.

Note: See TracTickets for help on using tickets.