Line data Source code
1 : /**
2 : * Heightmap manipulation functionality
3 : *
4 : * A heightmapt is an array of width arrays of height floats
5 : * Width and height is normally mapSize+1 (Number of vertices is one bigger than number of tiles in each direction)
6 : * The default heightmap is g_Map.height (See the Map object)
7 : *
8 : * @warning - Ambiguous naming and potential confusion:
9 : * To use this library use TILE_CENTERED_HEIGHT_MAP = false (default)
10 : * Otherwise TILE_CENTERED_HEIGHT_MAP has nothing to do with any tile centered map in this library
11 : * @todo - TILE_CENTERED_HEIGHT_MAP should be removed and g_Map.height should never be tile centered
12 : */
13 :
14 : /**
15 : * Get the height range of a heightmap
16 : * @param {array} [heightmap=g_Map.height] - The reliefmap the minimum and maximum height should be determined for
17 : * @return {Object} Height range with 2 floats in properties "min" and "max"
18 : */
19 : function getMinAndMaxHeight(heightmap = g_Map.height)
20 : {
21 0 : let height = {
22 : "min": Infinity,
23 : "max": -Infinity
24 : };
25 :
26 0 : for (let x = 0; x < heightmap.length; ++x)
27 0 : for (let y = 0; y < heightmap[x].length; ++y)
28 : {
29 0 : height.min = Math.min(height.min, heightmap[x][y]);
30 0 : height.max = Math.max(height.max, heightmap[x][y]);
31 : }
32 :
33 0 : return height;
34 : }
35 :
36 : /**
37 : * Rescales a heightmap so its minimum and maximum height is as the arguments told preserving it's global shape
38 : * @param {number} [minHeight=MIN_HEIGHT] - Minimum height that should be used for the resulting heightmap
39 : * @param {number} [maxHeight=MAX_HEIGHT] - Maximum height that should be used for the resulting heightmap
40 : * @param {array} [heightmap=g_Map.height] - A reliefmap
41 : * @todo Add preserveCostline to leave a certain height untoucht and scale below and above that seperately
42 : */
43 : function rescaleHeightmap(minHeight = MIN_HEIGHT, maxHeight = MAX_HEIGHT, heightmap = g_Map.height)
44 : {
45 0 : let oldHeightRange = getMinAndMaxHeight(heightmap);
46 0 : for (let x = 0; x < heightmap.length; ++x)
47 0 : for (let y = 0; y < heightmap[x].length; ++y)
48 0 : heightmap[x][y] = minHeight + (heightmap[x][y] - oldHeightRange.min) / (oldHeightRange.max - oldHeightRange.min) * (maxHeight - minHeight);
49 0 : return heightmap;
50 : }
51 :
52 : /**
53 : * Translates the heightmap by the given vector, i.e. moves the heights in that direction.
54 : *
55 : * @param {Vector2D} offset - A vector indicating direction and distance.
56 : * @param {number} [defaultHeight] - The elevation to be set for vertices that don't have a corresponding location on the source heightmap.
57 : * @param {Array} [heightmap=g_Map.height] - A reliefmap
58 : */
59 : function translateHeightmap(offset, defaultHeight = undefined, heightmap = g_Map.height)
60 : {
61 0 : if (defaultHeight === undefined)
62 0 : defaultHeight = getMinAndMaxHeight(heightmap).min;
63 0 : offset.round();
64 :
65 0 : let sourceHeightmap = clone(heightmap);
66 0 : for (let x = 0; x < heightmap.length; ++x)
67 0 : for (let y = 0; y < heightmap[x].length; ++y)
68 0 : heightmap[x][y] =
69 : sourceHeightmap[x + offset.x] !== undefined &&
70 : sourceHeightmap[x + offset.x][y + offset.y] !== undefined ?
71 : sourceHeightmap[x + offset.x][y + offset.y] :
72 : defaultHeight;
73 :
74 0 : return heightmap;
75 : }
76 :
77 : /**
78 : * Get start location with the largest minimum distance between players
79 : * @param {Object} [heightRange] - The height range start locations are allowed
80 : * @param {integer} [maxTries=1000] - How often random player distributions are rolled to be compared
81 : * @param {number} [minDistToBorder=20] - How far start locations have to be away from the map border
82 : * @param {integer} [numberOfPlayers=g_MapSettings.PlayerData.length] - How many start locations should be placed
83 : * @param {array} [heightmap=g_Map.height] - The reliefmap for the start locations to be placed on
84 : * @param {boolean} [isCircular=g_MapSettings.CircularMap] - If the map is circular or rectangular
85 : * @return {Vector2D[]}
86 : */
87 : function getStartLocationsByHeightmap(heightRange, maxTries = 1000, minDistToBorder = 20, numberOfPlayers = g_MapSettings.PlayerData.length - 1, heightmap = g_Map.height, isCircular = g_MapSettings.CircularMap)
88 : {
89 0 : let validStartLoc = [];
90 0 : let mapCenter = g_Map.getCenter();
91 0 : let mapSize = g_Map.getSize();
92 :
93 0 : let heightConstraint = new HeightConstraint(heightRange.min, heightRange.max);
94 :
95 0 : for (let x = minDistToBorder; x < mapSize - minDistToBorder; ++x)
96 0 : for (let y = minDistToBorder; y < mapSize - minDistToBorder; ++y)
97 : {
98 0 : let position = new Vector2D(x, y);
99 0 : if (heightConstraint.allows(position) && (!isCircular || position.distanceTo(mapCenter)) < mapSize / 2 - minDistToBorder)
100 0 : validStartLoc.push(position);
101 : }
102 :
103 0 : let maxMinDist = 0;
104 : let finalStartLoc;
105 :
106 0 : for (let tries = 0; tries < maxTries; ++tries)
107 : {
108 0 : let startLoc = [];
109 0 : let minDist = Infinity;
110 :
111 0 : for (let p = 0; p < numberOfPlayers; ++p)
112 0 : startLoc.push(pickRandom(validStartLoc));
113 :
114 0 : for (let p1 = 0; p1 < numberOfPlayers - 1; ++p1)
115 0 : for (let p2 = p1 + 1; p2 < numberOfPlayers; ++p2)
116 : {
117 0 : let dist = startLoc[p1].distanceTo(startLoc[p2]);
118 0 : if (dist < minDist)
119 0 : minDist = dist;
120 : }
121 :
122 0 : if (minDist > maxMinDist)
123 : {
124 0 : maxMinDist = minDist;
125 0 : finalStartLoc = startLoc;
126 : }
127 : }
128 :
129 0 : return finalStartLoc;
130 : }
131 :
132 : /**
133 : * Sets the heightmap to a relatively realistic shape
134 : * The function doubles the size of the initial heightmap (if given, else a random 2x2 one) until it's big enough, then the extend is cut off
135 : * @note min/maxHeight will not necessarily be present in the heightmap
136 : * @note On circular maps the edges (given by initialHeightmap) may not be in the playable map area
137 : * @note The impact of the initial heightmap depends on its size and target map size
138 : * @param {number} [minHeight=MIN_HEIGHT] - Lower limit of the random height to be rolled
139 : * @param {number} [maxHeight=MAX_HEIGHT] - Upper limit of the random height to be rolled
140 : * @param {array} [initialHeightmap] - Optional, Small (e.g. 3x3) heightmap describing the global shape of the map e.g. an island [[MIN_HEIGHT, MIN_HEIGHT, MIN_HEIGHT], [MIN_HEIGHT, MAX_HEIGHT, MIN_HEIGHT], [MIN_HEIGHT, MIN_HEIGHT, MIN_HEIGHT]]
141 : * @param {number} [smoothness=0.5] - Float between 0 (rough, more local structures) to 1 (smoother, only larger scale structures)
142 : * @param {array} [heightmap=g_Map.height] - The reliefmap that will be set by this function
143 : */
144 : function setBaseTerrainDiamondSquare(minHeight = MIN_HEIGHT, maxHeight = MAX_HEIGHT, initialHeightmap = undefined, smoothness = 0.5, heightmap = g_Map.height)
145 : {
146 0 : g_Map.log("Generating map using the diamond-square algorithm");
147 :
148 0 : initialHeightmap = (initialHeightmap || [[randFloat(minHeight / 2, maxHeight / 2), randFloat(minHeight / 2, maxHeight / 2)], [randFloat(minHeight / 2, maxHeight / 2), randFloat(minHeight / 2, maxHeight / 2)]]);
149 0 : let heightRange = maxHeight - minHeight;
150 0 : if (heightRange <= 0)
151 0 : warn("setBaseTerrainDiamondSquare: heightRange <= 0");
152 :
153 0 : let offset = heightRange / 2;
154 :
155 : // Double initialHeightmap width until target width is reached (diamond square method)
156 0 : let newHeightmap = [];
157 0 : while (initialHeightmap.length < heightmap.length)
158 : {
159 0 : newHeightmap = [];
160 0 : let oldWidth = initialHeightmap.length;
161 : // Square
162 0 : for (let x = 0; x < 2 * oldWidth - 1; ++x)
163 : {
164 0 : newHeightmap.push([]);
165 0 : for (let y = 0; y < 2 * oldWidth - 1; ++y)
166 : {
167 0 : if (x % 2 == 0 && y % 2 == 0) // Old tile
168 0 : newHeightmap[x].push(initialHeightmap[x/2][y/2]);
169 0 : else if (x % 2 == 1 && y % 2 == 1) // New tile with diagonal old tile neighbors
170 : {
171 0 : newHeightmap[x].push((initialHeightmap[(x-1)/2][(y-1)/2] + initialHeightmap[(x+1)/2][(y-1)/2] + initialHeightmap[(x-1)/2][(y+1)/2] + initialHeightmap[(x+1)/2][(y+1)/2]) / 4);
172 0 : newHeightmap[x][y] += (newHeightmap[x][y] - minHeight) / heightRange * randFloat(-offset, offset);
173 : }
174 : else // New tile with straight old tile neighbors
175 0 : newHeightmap[x].push(undefined); // Define later
176 : }
177 : }
178 : // Diamond
179 0 : for (let x = 0; x < 2 * oldWidth - 1; ++x)
180 : {
181 0 : for (let y = 0; y < 2 * oldWidth - 1; ++y)
182 : {
183 0 : if (newHeightmap[x][y] !== undefined)
184 0 : continue;
185 :
186 0 : if (x > 0 && x + 1 < newHeightmap.length - 1 && y > 0 && y + 1 < newHeightmap.length - 1) // Not a border tile
187 : {
188 0 : newHeightmap[x][y] = (newHeightmap[x+1][y] + newHeightmap[x][y+1] + newHeightmap[x-1][y] + newHeightmap[x][y-1]) / 4;
189 0 : newHeightmap[x][y] += (newHeightmap[x][y] - minHeight) / heightRange * randFloat(-offset, offset);
190 : }
191 0 : else if (x < newHeightmap.length - 1 && y > 0 && y < newHeightmap.length - 1) // Left border
192 : {
193 0 : newHeightmap[x][y] = (newHeightmap[x+1][y] + newHeightmap[x][y+1] + newHeightmap[x][y-1]) / 3;
194 0 : newHeightmap[x][y] += (newHeightmap[x][y] - minHeight) / heightRange * randFloat(-offset, offset);
195 : }
196 0 : else if (x > 0 && y > 0 && y < newHeightmap.length - 1) // Right border
197 : {
198 0 : newHeightmap[x][y] = (newHeightmap[x][y+1] + newHeightmap[x-1][y] + newHeightmap[x][y-1]) / 3;
199 0 : newHeightmap[x][y] += (newHeightmap[x][y] - minHeight) / heightRange * randFloat(-offset, offset);
200 : }
201 0 : else if (x > 0 && x < newHeightmap.length - 1 && y < newHeightmap.length - 1) // Bottom border
202 : {
203 0 : newHeightmap[x][y] = (newHeightmap[x+1][y] + newHeightmap[x][y+1] + newHeightmap[x-1][y]) / 3;
204 0 : newHeightmap[x][y] += (newHeightmap[x][y] - minHeight) / heightRange * randFloat(-offset, offset);
205 : }
206 0 : else if (x > 0 && x < newHeightmap.length - 1 && y > 0) // Top border
207 : {
208 0 : newHeightmap[x][y] = (newHeightmap[x+1][y] + newHeightmap[x-1][y] + newHeightmap[x][y-1]) / 3;
209 0 : newHeightmap[x][y] += (newHeightmap[x][y] - minHeight) / heightRange * randFloat(-offset, offset);
210 : }
211 : }
212 : }
213 0 : initialHeightmap = clone(newHeightmap);
214 0 : offset /= Math.pow(2, smoothness);
215 : }
216 :
217 : // Cut initialHeightmap to fit target width
218 0 : let shift = [Math.floor((newHeightmap.length - heightmap.length) / 2), Math.floor((newHeightmap[0].length - heightmap[0].length) / 2)];
219 0 : for (let x = 0; x < heightmap.length; ++x)
220 0 : for (let y = 0; y < heightmap[0].length; ++y)
221 0 : heightmap[x][y] = newHeightmap[x + shift[0]][y + shift[1]];
222 :
223 0 : return heightmap;
224 : }
225 :
226 : /**
227 : * Meant to place e.g. resource spots within a height range
228 : * @param {array} [heightRange] - The height range in which to place the entities (An associative array with keys "min" and "max" each containing a float)
229 : * @param {array} [avoidPoints=[]] - An array of objects of the form { "x": int, "y": int, "dist": int }, points that will be avoided in the given dist e.g. start locations
230 : * @param {Object} [avoidClass=undefined] - TileClass to be avoided
231 : * @param {integer} [minDistance=30] - How many tile widths the entities to place have to be away from each other, start locations and the map border
232 : * @param {array} [heightmap=g_Map.height] - The reliefmap the entities should be distributed on
233 : * @param {integer} [maxTries=2 * g_Map.size] - How often random player distributions are rolled to be compared (256 to 1024)
234 : * @param {boolean} [isCircular=g_MapSettings.CircularMap] - If the map is circular or rectangular
235 : */
236 : function getPointsByHeight(heightRange, avoidPoints = [], avoidClass = undefined, minDistance = 20, maxTries = 2 * g_Map.size, heightmap = g_Map.height, isCircular = g_MapSettings.CircularMap)
237 : {
238 0 : const points = [];
239 0 : const placements = clone(avoidPoints);
240 0 : const validVertices = [];
241 0 : const r = 0.5 * (heightmap.length - 1); // Map center x/y as well as radius
242 :
243 0 : for (let x = minDistance; x < heightmap.length - minDistance; ++x)
244 0 : for (let y = minDistance; y < heightmap[x].length - minDistance; ++y)
245 : {
246 0 : if (avoidClass &&
247 : (avoidClass.has(Math.max(x - 1, 0), y) ||
248 : avoidClass.has(x, Math.max(y - 1, 0)) ||
249 : avoidClass.has(Math.min(x + 1, avoidClass.size - 1), y) ||
250 : avoidClass.has(x, Math.min(y + 1, avoidClass.size - 1))))
251 0 : continue;
252 :
253 0 : if (heightmap[x][y] > heightRange.min && heightmap[x][y] < heightRange.max && // Has correct height
254 : (!isCircular || r - Math.euclidDistance2D(x, y, r, r) >= minDistance)) // Enough distance to the map border
255 0 : validVertices.push({ "x": x, "y": y, "dist": minDistance });
256 : }
257 :
258 0 : for (let tries = 0; tries < maxTries; ++tries)
259 : {
260 0 : const point = pickRandom(validVertices);
261 0 : if (placements.every(p => Math.euclidDistance2D(p.x, p.y, point.x, point.y) > Math.max(minDistance, p.dist)))
262 : {
263 0 : points.push(point);
264 0 : placements.push(point);
265 : }
266 : }
267 :
268 0 : return points;
269 : }
270 :
271 : /**
272 : * Returns an approximation of the heights of the tiles between the vertices, a tile centered heightmap
273 : * A tile centered heightmap is one smaller in width and height than an ordinary heightmap
274 : * It is meant to e.g. texture a map by height (x/y coordinates correspond to those of the terrain texture map)
275 : * Don't use this to override g_Map height (Potentially breaks the map)!
276 : * @param {array} [heightmap=g_Map.height] - A reliefmap the tile centered version should be build from
277 : */
278 : function getTileCenteredHeightmap(heightmap = g_Map.height)
279 : {
280 0 : let max_x = heightmap.length - 1;
281 0 : let max_y = heightmap[0].length - 1;
282 0 : let tchm = [];
283 0 : for (let x = 0; x < max_x; ++x)
284 : {
285 0 : tchm[x] = new Float32Array(max_y);
286 0 : for (let y = 0; y < max_y; ++y)
287 0 : tchm[x][y] = 0.25 * (heightmap[x][y] + heightmap[x + 1][y] + heightmap[x][y + 1] + heightmap[x + 1][y + 1]);
288 : }
289 0 : return tchm;
290 : }
291 :
292 : /**
293 : * Returns a slope map (same form as the a heightmap with one less width and height)
294 : * Not normalized. Only returns the steepness (float), not the direction of incline.
295 : * The x and y coordinates of a tile in the terrain texture map correspond to those of the slope map
296 : * @param {array} [inclineMap=getInclineMap(g_Map.height)] - A map with the absolute inclination for each tile
297 : */
298 : function getSlopeMap(inclineMap = getInclineMap(g_Map.height))
299 : {
300 0 : let max_x = inclineMap.length;
301 0 : let slopeMap = [];
302 0 : for (let x = 0; x < max_x; ++x)
303 : {
304 0 : let max_y = inclineMap[x].length;
305 0 : slopeMap[x] = new Float32Array(max_y);
306 0 : for (let y = 0; y < max_y; ++y)
307 0 : slopeMap[x][y] = Math.euclidDistance2D(0, 0, inclineMap[x][y].x, inclineMap[x][y].y);
308 : }
309 0 : return slopeMap;
310 : }
311 :
312 : /**
313 : * Returns an inclination map corresponding to the tiles between the heightmaps vertices:
314 : * array of heightmap width-1 arrays of height-1 vectors (associative arrays) of the form:
315 : * { "x": x_slope, "y": y_slope } - A 2D vector pointing to the highest incline (with the length the inclination in the vector's direction).
316 : * The x and y coordinates of a tile in the terrain texture map correspond to those of the inclination map.
317 : * @param {array} [heightmap=g_Map.height] - The reliefmap the inclination map is to be generated from.
318 : */
319 : function getInclineMap(heightmap)
320 : {
321 0 : heightmap = (heightmap || g_Map.height);
322 0 : let max_x = heightmap.length - 1;
323 0 : let max_y = heightmap[0].length - 1;
324 0 : let inclineMap = [];
325 0 : for (let x = 0; x < max_x; ++x)
326 : {
327 0 : inclineMap[x] = [];
328 0 : for (let y = 0; y < max_y; ++y)
329 : {
330 0 : let dx = heightmap[x + 1][y] - heightmap[x][y];
331 0 : let dy = heightmap[x][y + 1] - heightmap[x][y];
332 0 : let next_dx = heightmap[x + 1][y + 1] - heightmap[x][y + 1];
333 0 : let next_dy = heightmap[x + 1][y + 1] - heightmap[x + 1][y];
334 0 : inclineMap[x][y] = { "x": 0.5 * (dx + next_dx), "y": 0.5 * (dy + next_dy) };
335 : }
336 : }
337 0 : return inclineMap;
338 : }
339 :
340 : function getGrad(wrapped = true, scalarField = g_Map.height)
341 : {
342 0 : let vectorField = [];
343 0 : let max_x = scalarField.length;
344 0 : let max_y = scalarField[0].length;
345 0 : if (!wrapped)
346 : {
347 0 : max_x -= 1;
348 0 : max_y -= 1;
349 : }
350 :
351 0 : for (let x = 0; x < max_x; ++x)
352 : {
353 0 : vectorField.push([]);
354 0 : for (let y = 0; y < max_y; ++y)
355 : {
356 0 : vectorField[x].push({
357 : "x": scalarField[(x + 1) % max_x][y] - scalarField[x][y],
358 : "y": scalarField[x][(y + 1) % max_y] - scalarField[x][y]
359 : });
360 : }
361 : }
362 :
363 0 : return vectorField;
364 : }
365 :
366 : function splashErodeMap(strength = 1, heightmap = g_Map.height)
367 : {
368 0 : let max_x = heightmap.length;
369 0 : let max_y = heightmap[0].length;
370 :
371 0 : let dHeight = getGrad(heightmap);
372 :
373 0 : for (let x = 0; x < max_x; ++x)
374 : {
375 0 : let next_x = (x + 1) % max_x;
376 0 : let prev_x = (x + max_x - 1) % max_x;
377 0 : for (let y = 0; y < max_y; ++y)
378 : {
379 0 : let next_y = (y + 1) % max_y;
380 0 : let prev_y = (y + max_y - 1) % max_y;
381 :
382 0 : let slopes = [-dHeight[x][y].x, -dHeight[x][y].y, dHeight[prev_x][y].x, dHeight[x][prev_y].y];
383 :
384 0 : let sumSlopes = 0;
385 0 : for (let i = 0; i < slopes.length; ++i)
386 0 : if (slopes[i] > 0)
387 0 : sumSlopes += slopes[i];
388 :
389 0 : let drain = [];
390 0 : for (let i = 0; i < slopes.length; ++i)
391 : {
392 0 : drain.push(0);
393 0 : if (slopes[i] > 0)
394 0 : drain[i] += Math.min(strength * slopes[i] / sumSlopes, slopes[i]);
395 : }
396 :
397 0 : let sumDrain = 0;
398 0 : for (let i = 0; i < drain.length; ++i)
399 0 : sumDrain += drain[i];
400 :
401 : // Apply changes to maps
402 0 : heightmap[x][y] -= sumDrain;
403 0 : heightmap[next_x][y] += drain[0];
404 0 : heightmap[x][next_y] += drain[1];
405 0 : heightmap[prev_x][y] += drain[2];
406 0 : heightmap[x][prev_y] += drain[3];
407 : }
408 : }
409 0 : return heightmap;
410 : }
|
