Opened 8 years ago

Closed 8 years ago

Last modified 6 years ago

#3764 closed enhancement (fixed)

[PATCH] Add heightmap manipulation library for random maps

Reported by: FeXoR Owned by: FeXoR
Priority: Should Have Milestone: Alpha 21
Component: Maps Keywords:
Cc: FeXoR Patch:

Description

I collected the functions used for heightmap generation and manipulations in a library heightmap_manipulation.js.

Some where already use by maps and thus needed to be changed: Belgian Uplands and Schwarzwald.

Also some Global variables for heightmaps are now in library.js.

Some basic terrain "painting" function is also preasent now in misk.js.

A demo map is also added: Realistic Terrain Demo

Attachments (14)

realistic_terrain_demo2016-1-31.diff (118.6 KB ) - added by FeXoR 8 years ago.
realistic_terrain_demo2016-1-31b.diff (117.6 KB ) - added by FeXoR 8 years ago.
realistic_terrain_demo2016-1-31c.diff (114.8 KB ) - added by FeXoR 8 years ago.
Inserted a continue, removed commented out code
realistic_terrain_demo2016-1-31c-noStyle.diff (61.7 KB ) - added by FeXoR 8 years ago.
Stile-only sections removed
add_hm_lib.patch (36.8 KB ) - added by FeXoR 8 years ago.
Minimal patch that only gathers functions/constants in libs
add_hm_lib-2016_5_1.patch (36.8 KB ) - added by FeXoR 8 years ago.
Added an early return
add_hm_lib-2016_5_1b.patch (36.8 KB ) - added by FeXoR 8 years ago.
Added spaces before stars for comments
add_hm_lib-2016_5_1c.patch (36.8 KB ) - added by FeXoR 8 years ago.
Replaced tabs in comments with spaces, added some spaces in schwarzwald
add_hm_lib-2016_5_1d.patch (36.8 KB ) - added by FeXoR 8 years ago.
Changed the spaces in schwarzwald
add_hm_lib-2016_5_1e.patch (37.5 KB ) - added by FeXoR 8 years ago.
Added @return doxygen comments to heightmap.js, removed some more comments
add_hm_lib-2016_5_1f.patch (37.3 KB ) - added by FeXoR 8 years ago.
Added @todo and @warning, made a parameter optional, removed some dots "20."->"20", fixed an "use out of scope"
add_hm_lib-2016_5_8.patch (37.0 KB ) - added by FeXoR 8 years ago.
Fixed an out of scope, changed var to let, shortened lib description, added comments for circular maps
add_hm_lib-2016_5_8_circular.patch (37.4 KB ) - added by FeXoR 8 years ago.
Optional patch with circular map support
add_hm_lib-2016_5_8_circular_b.patch (37.5 KB ) - added by FeXoR 8 years ago.
Fixed typo hight, fixed a fail by one, used getDistance

Download all attachments as: .zip

Change History (31)

by FeXoR, 8 years ago

Inserted a continue, removed commented out code

by FeXoR, 8 years ago

Stile-only sections removed

comment:1 by FeXoR, 8 years ago

Summary: [PATCH] [REVIEW] Add heightmap manipulation library for random maps[PATCH] Add heightmap manipulation library for random maps

comment:2 by FeXoR, 8 years ago

Owner: set to FeXoR

comment:3 by elexis, 8 years ago

Milestone: BacklogAlpha 21

IMO it would be nice to commit this in two separate commits. The first one could move the duplicate functions to the new lib. The second one could add the new maps. (But I'm personally not insisting on splitting it.)

Mostly irrelevant style issues:

  • The JSdoc comments are missing a space in the second line:
    /**
     * foo
     */
    
  • If you add JSdoc comments and explain the variables ("Takes") and return values, use @param and @return etc.

BaseTerrainDiamondSquare.js:

  • L101 objects should be { "foo": bar } instead of {"foo":bar}
  • L119 could invert the condition and use an early return
  • L137 unneeded braces
  • L143 unneeded comment

Belgian Uplands:

  • L188 ff: better define every property on a single line (push(\nprop1:val1\nprop2:val2...))

realisticTerrainDemo.js:

  • What does that comment tell us?
    /**
    * initialize map
    */
    log("Initializing map..."); 
    InitMap(); 
    

*L45: Array function map? *L108: unneeded parenthesis

  • Actually do stuff and Some general functions, Water height in RMGEN are not really useful comments
  • L171, L370: commented out code
  • L211, L244: heighLimits, myBiome -> would be more beautiful to use an object instead of relying on array indices and comments

heightmap_manipulation.js

  • L305: early return!
  • some of the things mentioned above
  • L513 don't check for the type, check strictly for false, or more simple !pathsToCheck and an early return

More importantly this needs to be reviewed by swim too.

comment:4 by FeXoR, 8 years ago

Component: UI & SimulationMaps

by FeXoR, 8 years ago

Attachment: add_hm_lib.patch added

Minimal patch that only gathers functions/constants in libs

by FeXoR, 8 years ago

Attachment: add_hm_lib-2016_5_1.patch added

Added an early return

by FeXoR, 8 years ago

Attachment: add_hm_lib-2016_5_1b.patch added

Added spaces before stars for comments

by FeXoR, 8 years ago

Attachment: add_hm_lib-2016_5_1c.patch added

Replaced tabs in comments with spaces, added some spaces in schwarzwald

by FeXoR, 8 years ago

Attachment: add_hm_lib-2016_5_1d.patch added

Changed the spaces in schwarzwald

comment:5 by Stan, 8 years ago

Some problems with Doxygen Usually we use @brief for function descriptions example : http://imgur.com/eo5ckXA @return for returns @warning instead of WARNING: @todo instead of ToDo @note for NOTE: (Think it was removed in *d patch)

for (let) instead of for (var)

Apart from that patch looks fine.

by FeXoR, 8 years ago

Attachment: add_hm_lib-2016_5_1e.patch added

Added @return doxygen comments to heightmap.js, removed some more comments

by FeXoR, 8 years ago

Attachment: add_hm_lib-2016_5_1f.patch added

Added @todo and @warning, made a parameter optional, removed some dots "20."->"20", fixed an "use out of scope"

comment:6 by FeXoR, 8 years ago

For me it's good to go. Please tell me if you find anything else to change.

comment:7 by elexis, 8 years ago

About the patch:

This patch removes the following functions:

Index: binaries/data/mods/public/maps/random/belgian_uplands.js
-function getRandomReliefmap(minHeight, maxHeight)
-function getMinAndMaxHeight(reliefmap)
-function getRescaledReliefmap(reliefmap, minHeight, maxHeight)
-function getHeightErrosionedReliefmap(reliefmap, strength)

Index: binaries/data/mods/public/maps/random/island_stronghold.js
-function decayErrodeHeightmap(strength, heightmap)

Index: binaries/data/mods/public/maps/random/schwarzwald.js
-function getOrderOfPointsForShortestClosePath(points)
-function getMinAndMaxHeight(reliefmap)
-function rescaleHeightmap(minHeight, maxHeight, heightmap)
-function getStartLocationsByHeightmap(hightRange, maxTries, minDistToBorder, numberOfPlayers, heightmap)
-function derivateEntitiesByHeight(hightRange, startLoc, entityList, maxTries, minDistance, heightmap)
-function setBaseTerrainDiamondSquare(minHeight, maxHeight, smoothness, initialHeightmap, heightmap)
-function decayErrodeHeightmap(strength, heightmap)
-function rectangularSmoothToHeight(center, dx, dy, targetHeight, strength, heightmap)

and it adds:

Index: binaries/data/mods/public/maps/random/heightmap/heightmap.js
+function getMinAndMaxHeight(heightmap = g_Map.height)
+function rescaleHeightmap(minHeight = MIN_HEIGHT, maxHeight = MAX_HEIGHT, heightmap = g_Map.height)
+function getStartLocationsByHeightmap(hightRange, maxTries = 1000, minDistToBorder = 20, numberOfPlayers = g_MapSettings.PlayerData.length - 1, heightmap = g_Map.height)
+function distributeEntitiesByHeight(hightRange, avoidPoints, minDistance = 30, entityList = [g_Gaia.stoneLarge, g_Gaia.metalLarge], maxTries = 1000, heightmap = g_Map.height)
+function setRandomHeightmap(minHeight = MIN_HEIGHT, maxHeight = MAX_HEIGHT, heightmap = g_Map.height)
+function setBaseTerrainDiamondSquare(minHeight = MIN_HEIGHT, maxHeight = MAX_HEIGHT, initialHeightmap = undefined, smoothness = 0.5, heightmap = g_Map.height)
+function globalSmoothHeightmap(strength = 0.8, heightmap = g_Map.height, smoothMap = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]])
+function rectangularSmoothToHeight(center, dx, dy, targetHeight, strength = 0.8, heightmap = g_Map.height)

Can be checked using:

cat add_hm_lib-2016_5_1f.patch  | grep "\-function\|Index"

respectively

cat add_hm_lib-2016_5_1f.patch  | grep "\+function\|Index"

derivateEntitiesByHeight was renamed to distributeEntitiesByHeight. decayErrodeHeightmap was renamed to globalSmoothHeightmap. getRandomReliefmap was renamed to setRandomHeightmap. rescaleHeightmap now uses globals instead of hardcoded magic numbers.


On the necessity of splitting patches: Considering that this is still a huge patch, I'm very glad you split this. As you mentioned yesterday in IRC, dealing with such huge patches is quite annoying. Bigger patch -> review consumes more time and people are less confident that they noticed all mistakes.

Your random map scripts, ideas on that library are awesome and I'm looking forward to see more of your commits. In order to experience less hurdles, make minipatches instead of megapatches. Trivial / atomic changes basically don't need a review (assuming they don't break stuff). Looking at this patch, you could have committed few things right when you noticed them.


For example in this patch, getMinAndMaxHeight was an exact duplicate in two maps and was moved to the new library file. Now this is how this commit would have looked like:

-function getMinAndMaxHeight(reliefmap)
-{
-	var height = {};
-	height.min = Infinity;
-	height.max = -Infinity;
 
-	for (var x = 0; x <= mapSize; x++)
-		for (var y = 0; y <= mapSize; y++)
-		{
-			if (reliefmap[x][y] < height.min)
-				height.min = reliefmap[x][y];
-			else if (reliefmap[x][y] > height.max)
-				height.max = reliefmap[x][y];
-		}
-
-	return height;
-}
--
+function getMinAndMaxHeight(heightmap = g_Map.height)
+{
+	var height = {};
+	height.min = Infinity;
+	height.max = - Infinity;
+	for (let x = 0; x < heightmap.length; ++x)
+	{
+		for (let y = 0; y < heightmap[x].length; ++y)
+		{
+			if (heightmap[x][y] < height.min)
+				height.min = heightmap[x][y];
+			else if (heightmap[x][y] > height.max)
+				height.max = heightmap[x][y];
+		}
+	}
+	return height;
+}
--
-function getMinAndMaxHeight(reliefmap)
-{
-	var height = {};
-	height.min = Infinity;
-	height.max = - Infinity;
-
-	for (var x = 0; x < reliefmap.length; x++)
-		for (var y = 0; y < reliefmap[x].length; y++)
-		{
-			if (reliefmap[x][y] < height.min)
-				height.min = reliefmap[x][y];
-			else if (reliefmap[x][y] > height.max)
-				height.max = reliefmap[x][y];
-		}
-
-	return height;
-}

Can be checked using:

clear; cat add_hm_lib-2016_5_1f.patch | grep 'function getMinAndMaxHeight' -A 16

Such atomic diffs are much easier to read as one don't need to scroll anymore to compare the specific functions. For the megapatch it is hard to reverse. (See also my megapatch in #3258 that was split into like 20 parts, including the cleanup #3355 which had to be split into like 10.) Another example is the removal of the completely unused function getOrderOfPointsForShortestClosePath. Don't leave it an exercise to the reader of the ticket to figure out that it was unused, but mention this either when uploading the patch or in the commit message of an atomic commit.


Last style issues:

  • The introduction comment to the lib file is too long. 2 sentences for the warning, one for the @todo (last line of the comment). The only relevant giveaway of that comment is that the objects used by the functions are tile-centered, thus have a smaller array size as g_Map.height and hence shouldn't overwrite it.
  • Optional: If you use let for the counters of loops, you should use let also for the variables inside the scopes of loops (or plainly use them everywhere inside of functions). Notice that variables with let may not be used outside of scope (but shouldn't occur as you already fixed all out-of-scopes using jshint).

I can't estimate whether there are any logic flaws in the functions you move. If so, you wouldn't have introduced them, but they could/should, hypothetically speaking, still have been fixed in the same commit. If you tested the patch, made sure the JSdoc comments have proper syntax, don't add any bugs, then I think noone should complain, but be happy about the removal of unused and duplicate functions and moving shared code to a common, well-documented library. So commit it after fixing the comment (insert shia labeouf meme)

by FeXoR, 8 years ago

Attachment: add_hm_lib-2016_5_8.patch added

Fixed an out of scope, changed var to let, shortened lib description, added comments for circular maps

comment:8 by FeXoR, 8 years ago

The last out of scope usage was revealed by using let.

Tested again and closely read all code:

  • 2 functions doesn't support circular maps (to fix in another patch)
  • The window function of rectangularSmoothToHeight is by far the fastest to use (and still satisfying boundary condition and condition of continuity) AFAIK so not sure if making it optional is really needed.
Last edited 8 years ago by FeXoR (previous) (diff)

by FeXoR, 8 years ago

Optional patch with circular map support

by FeXoR, 8 years ago

Fixed typo hight, fixed a fail by one, used getDistance

comment:9 by FeXoR, 8 years ago

Resolution: fixed
Status: newclosed

In 18141:

Separate global heightmap manipulation functions to a library. Fixes #3764

comment:10 by FeXoR, 8 years ago

Keywords: review patch removed

comment:11 by elexis, 7 years ago

In 20142:

Don't use the default metal/stone mines of the random biome system in the independent heightmap library (following rP18141) that is only used by a map that doesn't use the random biome system, revealed by rP20127.
Don't mix alpine and mediterranean (rmbiome) mines on Schwarzwald as before rP18141. Refs #3764.

comment:12 by elexis, 6 years ago

In 20864:

Remove distributeEntitiesByHeight / derivateEntitiesByHeight from rP18141 / rP15327.
Fix collisions of mines with trees and berries on Schwarzwald.

It can't achieve anything that a createArea or createObjectGroups call with a HeightConstraint (rP20862) or HeightPlacer (rP15327, rP20361) can't achieve too,
while it can't perform many crucial tasks like testing for arbitrary Constraints, using custom shapes determined by a Placer or limiting the amount of entities,
thus the unconventional code is redundant, refs #4805, #3764.

comment:13 by elexis, 6 years ago

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.

comment:14 by elexis, 6 years ago

In 21176:

Migrate setRandomHeightmap from the heightmap library to a Painter that can be applied to arbitrary Areas, refs #3764.

The only current use-case is Belgian Uplands that has to smooth the map for 15-45 seconds to transform that noise into an acceptable map.
The general use-case of this painter is questionable.

comment:15 by elexis, 6 years ago

In 21182:

Implement ElevationBlendingPainter which interpolates the height of the given area with the desired height.

Primary use case, as represented on Caledonian Meadows, is creating a path through impassable area, mountains or water, refs #4952.
Supersedes placeRandomPathToHeight from the heightmap library, refs #3764.
The painter has the advantage that it can be applied to arbitrary areas with arbitrary forms of smoothing (or no smoothing).
Replace the rectangularSmoothToHeight calls that only smooth an area with a SmoothElevationPainter call.
Replace placeRandomPathToHeight which is a copy of the the RandomPathPlacer from rP20879, refs #4805.

comment:16 by elexis, 6 years ago

In 21390:

Fix JS type label in the heightmap library, refs #3764.
Remove an unused variable following rP21296.

comment:17 by elexis, 6 years ago

In 21403:

Add translateHeightmap function which allows repositioning of an imported heightmap before copying it to the map, refs #3764, #5018, #4816.

Inline some variables and return the heightmap in the heightmap library functions, so that one can apply multiple transformations within the same statement.

Note: See TracTickets for help on using tickets.