Line data Source code
1 0 : var API3 = function(m)
2 : {
3 :
4 : /**
5 : * TerrainAnalysis, inheriting from the Map Component.
6 : *
7 : * This creates a suitable passability map.
8 : * This is part of the Shared Script, and thus should only be used for things that are non-player specific.
9 : * This.map is a map of the world, where particular stuffs are pointed with a value
10 : * For example, impassable land is 0, water is 200, areas near tree (ie forest grounds) are 41…
11 : * This is intended for use with 8 bit maps for reduced memory usage.
12 : * Upgraded from QuantumState's original TerrainAnalysis for qBot.
13 : */
14 :
15 0 : m.TerrainAnalysis = function()
16 : {
17 : };
18 :
19 0 : m.copyPrototype(m.TerrainAnalysis, m.Map);
20 :
21 0 : m.TerrainAnalysis.prototype.IMPASSABLE = 0;
22 : /**
23 : * non-passable by land units
24 : */
25 0 : m.TerrainAnalysis.prototype.DEEP_WATER = 200;
26 : /**
27 : * passable by land units and water units
28 : */
29 0 : m.TerrainAnalysis.prototype.SHALLOW_WATER = 201;
30 : /**
31 : * passable by land units
32 : */
33 0 : m.TerrainAnalysis.prototype.LAND = 255;
34 :
35 0 : m.TerrainAnalysis.prototype.init = function(sharedScript, rawState)
36 : {
37 0 : let passabilityMap = rawState.passabilityMap;
38 0 : this.width = passabilityMap.width;
39 0 : this.height = passabilityMap.height;
40 0 : this.cellSize = passabilityMap.cellSize;
41 :
42 0 : let obstructionMaskLand = rawState.passabilityClasses["default-terrain-only"];
43 0 : let obstructionMaskWater = rawState.passabilityClasses["ship-terrain-only"];
44 :
45 0 : let obstructionTiles = new Uint8Array(passabilityMap.data.length);
46 :
47 :
48 0 : for (let i = 0; i < passabilityMap.data.length; ++i)
49 : {
50 0 : obstructionTiles[i] = (passabilityMap.data[i] & obstructionMaskLand) ? this.IMPASSABLE : this.LAND;
51 :
52 0 : if (!(passabilityMap.data[i] & obstructionMaskWater) && obstructionTiles[i] === this.IMPASSABLE)
53 0 : obstructionTiles[i] = this.DEEP_WATER;
54 0 : else if (!(passabilityMap.data[i] & obstructionMaskWater) && obstructionTiles[i] === this.LAND)
55 0 : obstructionTiles[i] = this.SHALLOW_WATER;
56 : }
57 :
58 0 : this.Map(rawState, "passability", obstructionTiles);
59 : };
60 :
61 : /**
62 : * Accessibility inherits from TerrainAnalysis
63 : *
64 : * This can easily and efficiently determine if any two points are connected.
65 : * it can also determine if any point is "probably" reachable, assuming the unit can get close enough
66 : * for optimizations it's called after the TerrainAnalyser has finished initializing his map
67 : * so this can use the land regions already.
68 : */
69 0 : m.Accessibility = function()
70 : {
71 : };
72 :
73 0 : m.copyPrototype(m.Accessibility, m.TerrainAnalysis);
74 :
75 0 : m.Accessibility.prototype.init = function(rawState, terrainAnalyser)
76 : {
77 0 : this.Map(rawState, "passability", terrainAnalyser.map);
78 0 : this.landPassMap = new Uint16Array(terrainAnalyser.length);
79 0 : this.navalPassMap = new Uint16Array(terrainAnalyser.length);
80 :
81 0 : this.maxRegions = 65535;
82 0 : this.regionSize = [];
83 0 : this.regionType = []; // "inaccessible", "land" or "water";
84 : // ID of the region associated with an array of region IDs.
85 0 : this.regionLinks = [];
86 :
87 : // initialized to 0, it's more optimized to start at 1 (I'm checking that if it's not 0, then it's already aprt of a region, don't touch);
88 : // However I actually store all unpassable as region 1 (because if I don't, on some maps the toal nb of region is over 256, and it crashes as the mapis 8bit.)
89 : // So start at 2.
90 0 : this.regionID = 2;
91 :
92 0 : for (let i = 0; i < this.landPassMap.length; ++i)
93 : {
94 0 : if (this.map[i] !== this.IMPASSABLE)
95 : { // any non-painted, non-inacessible area.
96 0 : if (this.landPassMap[i] == 0 && this.floodFill(i, this.regionID, false))
97 0 : this.regionType[this.regionID++] = "land";
98 0 : if (this.navalPassMap[i] == 0 && this.floodFill(i, this.regionID, true))
99 0 : this.regionType[this.regionID++] = "water";
100 : }
101 0 : else if (this.landPassMap[i] == 0)
102 : { // any non-painted, inacessible area.
103 0 : this.floodFill(i, 1, false);
104 0 : this.floodFill(i, 1, true);
105 : }
106 : }
107 :
108 : // calculating region links. Regions only touching diagonaly are not linked.
109 : // since we're checking all of them, we'll check from the top left to the bottom right
110 0 : let w = this.width;
111 0 : for (let x = 0; x < this.width-1; ++x)
112 : {
113 0 : for (let y = 0; y < this.height-1; ++y)
114 : {
115 : // checking right.
116 0 : let thisLID = this.landPassMap[x+y*w];
117 0 : let thisNID = this.navalPassMap[x+y*w];
118 0 : let rightLID = this.landPassMap[x+1+y*w];
119 0 : let rightNID = this.navalPassMap[x+1+y*w];
120 0 : let bottomLID = this.landPassMap[x+y*w+w];
121 0 : let bottomNID = this.navalPassMap[x+y*w+w];
122 0 : if (thisLID > 1)
123 : {
124 0 : if (rightNID > 1)
125 0 : if (this.regionLinks[thisLID].indexOf(rightNID) === -1)
126 0 : this.regionLinks[thisLID].push(rightNID);
127 0 : if (bottomNID > 1)
128 0 : if (this.regionLinks[thisLID].indexOf(bottomNID) === -1)
129 0 : this.regionLinks[thisLID].push(bottomNID);
130 : }
131 0 : if (thisNID > 1)
132 : {
133 0 : if (rightLID > 1)
134 0 : if (this.regionLinks[thisNID].indexOf(rightLID) === -1)
135 0 : this.regionLinks[thisNID].push(rightLID);
136 0 : if (bottomLID > 1)
137 0 : if (this.regionLinks[thisNID].indexOf(bottomLID) === -1)
138 0 : this.regionLinks[thisNID].push(bottomLID);
139 0 : if (thisLID > 1)
140 0 : if (this.regionLinks[thisNID].indexOf(thisLID) === -1)
141 0 : this.regionLinks[thisNID].push(thisLID);
142 : }
143 : }
144 : }
145 :
146 : // Engine.DumpImage("LandPassMap.png", this.landPassMap, this.width, this.height, 255);
147 : // Engine.DumpImage("NavalPassMap.png", this.navalPassMap, this.width, this.height, 255);
148 : };
149 :
150 0 : m.Accessibility.prototype.getAccessValue = function(position, onWater)
151 : {
152 0 : let gamePos = this.gamePosToMapPos(position);
153 0 : if (onWater)
154 0 : return this.navalPassMap[gamePos[0] + this.width*gamePos[1]];
155 0 : let ret = this.landPassMap[gamePos[0] + this.width*gamePos[1]];
156 0 : if (ret === 1)
157 : {
158 : // quick spiral search.
159 0 : let indx = [ [-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1]];
160 0 : for (let i of indx)
161 : {
162 0 : let id0 = gamePos[0] + i[0];
163 0 : let id1 = gamePos[1] + i[1];
164 0 : if (id0 < 0 || id0 >= this.width || id1 < 0 || id1 >= this.width)
165 0 : continue;
166 0 : ret = this.landPassMap[id0 + this.width*id1];
167 0 : if (ret !== 1)
168 0 : return ret;
169 : }
170 : }
171 0 : return ret;
172 : };
173 :
174 0 : m.Accessibility.prototype.getTrajectTo = function(start, end)
175 : {
176 0 : let pstart = this.gamePosToMapPos(start);
177 0 : let istart = pstart[0] + pstart[1]*this.width;
178 0 : let pend = this.gamePosToMapPos(end);
179 0 : let iend = pend[0] + pend[1]*this.width;
180 :
181 0 : let onLand = true;
182 0 : if (this.landPassMap[istart] <= 1 && this.navalPassMap[istart] > 1)
183 0 : onLand = false;
184 0 : if (this.landPassMap[istart] <= 1 && this.navalPassMap[istart] <= 1)
185 0 : return false;
186 :
187 0 : let endRegion = this.landPassMap[iend];
188 0 : if (endRegion <= 1 && this.navalPassMap[iend] > 1)
189 0 : endRegion = this.navalPassMap[iend];
190 0 : else if (endRegion <= 1)
191 0 : return false;
192 :
193 0 : let startRegion = onLand ? this.landPassMap[istart] : this.navalPassMap[istart];
194 0 : return this.getTrajectToIndex(startRegion, endRegion);
195 : };
196 :
197 : /**
198 : * Return a "path" of accessibility indexes from one point to another, including the start and the end indexes
199 : * this can tell you what sea zone you need to have a dock on, for example.
200 : * assumes a land unit unless start point is over deep water.
201 : */
202 0 : m.Accessibility.prototype.getTrajectToIndex = function(istart, iend)
203 : {
204 0 : if (istart === iend)
205 0 : return [istart];
206 :
207 0 : let trajects = new Set();
208 0 : let explored = new Set();
209 0 : trajects.add([istart]);
210 0 : explored.add(istart);
211 0 : while (trajects.size)
212 : {
213 0 : for (let traj of trajects)
214 : {
215 0 : let ilast = traj[traj.length-1];
216 0 : for (let inew of this.regionLinks[ilast])
217 : {
218 0 : if (inew === iend)
219 0 : return traj.concat(iend);
220 0 : if (explored.has(inew))
221 0 : continue;
222 0 : trajects.add(traj.concat(inew));
223 0 : explored.add(inew);
224 : }
225 0 : trajects.delete(traj);
226 : }
227 : }
228 0 : return undefined;
229 : };
230 :
231 0 : m.Accessibility.prototype.getRegionSize = function(position, onWater)
232 : {
233 0 : let pos = this.gamePosToMapPos(position);
234 0 : let index = pos[0] + pos[1]*this.width;
235 0 : let ID = onWater === true ? this.navalPassMap[index] : this.landPassMap[index];
236 0 : if (this.regionSize[ID] === undefined)
237 0 : return 0;
238 0 : return this.regionSize[ID];
239 : };
240 :
241 0 : m.Accessibility.prototype.getRegionSizei = function(index, onWater)
242 : {
243 0 : if (this.regionSize[this.landPassMap[index]] === undefined && (!onWater || this.regionSize[this.navalPassMap[index]] === undefined))
244 0 : return 0;
245 0 : if (onWater && this.regionSize[this.navalPassMap[index]] > this.regionSize[this.landPassMap[index]])
246 0 : return this.regionSize[this.navalPassMap[index]];
247 0 : return this.regionSize[this.landPassMap[index]];
248 : };
249 :
250 : /** Implementation of a fast flood fill. Reasonably good performances for JS. */
251 0 : m.Accessibility.prototype.floodFill = function(startIndex, value, onWater)
252 : {
253 0 : if (value > this.maxRegions)
254 : {
255 0 : error("AI accessibility map: too many regions.");
256 0 : this.landPassMap[startIndex] = 1;
257 0 : this.navalPassMap[startIndex] = 1;
258 0 : return false;
259 : }
260 :
261 0 : if (!onWater && this.landPassMap[startIndex] != 0 || onWater && this.navalPassMap[startIndex] != 0)
262 0 : return false; // already painted.
263 :
264 0 : let floodFor = "land";
265 0 : if (this.map[startIndex] === this.IMPASSABLE)
266 : {
267 0 : this.landPassMap[startIndex] = 1;
268 0 : this.navalPassMap[startIndex] = 1;
269 0 : return false;
270 : }
271 :
272 0 : if (onWater === true)
273 : {
274 0 : if (this.map[startIndex] !== this.DEEP_WATER && this.map[startIndex] !== this.SHALLOW_WATER)
275 : {
276 0 : this.navalPassMap[startIndex] = 1; // impassable for naval
277 0 : return false; // do nothing
278 : }
279 0 : floodFor = "water";
280 : }
281 0 : else if (this.map[startIndex] === this.DEEP_WATER)
282 : {
283 0 : this.landPassMap[startIndex] = 1; // impassable for land
284 0 : return false;
285 : }
286 :
287 : // here we'll be able to start.
288 0 : for (let i = this.regionSize.length; i <= value; ++i)
289 : {
290 0 : this.regionLinks.push([]);
291 0 : this.regionSize.push(0);
292 0 : this.regionType.push("inaccessible");
293 : }
294 0 : let w = this.width;
295 0 : let h = this.height;
296 :
297 0 : let y = 0;
298 : // Get x and y from index
299 0 : let IndexArray = [startIndex];
300 : let newIndex;
301 0 : while(IndexArray.length)
302 : {
303 0 : newIndex = IndexArray.pop();
304 :
305 0 : y = 0;
306 0 : let loop = false;
307 : // vertical iteration
308 0 : do {
309 0 : --y;
310 0 : loop = false;
311 0 : let index = newIndex + w*y;
312 0 : if (index < 0)
313 0 : break;
314 0 : if (floodFor === "land" && this.landPassMap[index] === 0 && this.map[index] !== this.IMPASSABLE && this.map[index] !== this.DEEP_WATER)
315 0 : loop = true;
316 0 : else if (floodFor === "water" && this.navalPassMap[index] === 0 && (this.map[index] === this.DEEP_WATER || this.map[index] === this.SHALLOW_WATER))
317 0 : loop = true;
318 : else
319 0 : break;
320 : } while (loop === true); // should actually break
321 0 : ++y;
322 0 : let reachLeft = false;
323 0 : let reachRight = false;
324 : let index;
325 0 : do {
326 0 : index = newIndex + w*y;
327 :
328 0 : if (floodFor === "land" && this.landPassMap[index] === 0 && this.map[index] !== this.IMPASSABLE && this.map[index] !== this.DEEP_WATER)
329 : {
330 0 : this.landPassMap[index] = value;
331 0 : this.regionSize[value]++;
332 : }
333 0 : else if (floodFor === "water" && this.navalPassMap[index] === 0 && (this.map[index] === this.DEEP_WATER || this.map[index] === this.SHALLOW_WATER))
334 : {
335 0 : this.navalPassMap[index] = value;
336 0 : this.regionSize[value]++;
337 : }
338 : else
339 0 : break;
340 :
341 0 : if (index%w > 0)
342 : {
343 0 : if (floodFor === "land" && this.landPassMap[index -1] === 0 && this.map[index -1] !== this.IMPASSABLE && this.map[index -1] !== this.DEEP_WATER)
344 : {
345 0 : if (!reachLeft)
346 : {
347 0 : IndexArray.push(index -1);
348 0 : reachLeft = true;
349 : }
350 : }
351 0 : else if (floodFor === "water" && this.navalPassMap[index -1] === 0 && (this.map[index -1] === this.DEEP_WATER || this.map[index -1] === this.SHALLOW_WATER))
352 : {
353 0 : if (!reachLeft)
354 : {
355 0 : IndexArray.push(index -1);
356 0 : reachLeft = true;
357 : }
358 : }
359 0 : else if (reachLeft)
360 0 : reachLeft = false;
361 : }
362 :
363 0 : if (index%w < w - 1)
364 : {
365 0 : if (floodFor === "land" && this.landPassMap[index +1] === 0 && this.map[index +1] !== this.IMPASSABLE && this.map[index +1] !== this.DEEP_WATER)
366 : {
367 0 : if (!reachRight)
368 : {
369 0 : IndexArray.push(index +1);
370 0 : reachRight = true;
371 : }
372 : }
373 0 : else if (floodFor === "water" && this.navalPassMap[index +1] === 0 && (this.map[index +1] === this.DEEP_WATER || this.map[index +1] === this.SHALLOW_WATER))
374 : {
375 0 : if (!reachRight)
376 : {
377 0 : IndexArray.push(index +1);
378 0 : reachRight = true;
379 : }
380 : }
381 0 : else if (reachRight)
382 0 : reachRight = false;
383 : }
384 0 : ++y;
385 : } while (index/w < h-1); // should actually break
386 : }
387 0 : return true;
388 : };
389 :
390 0 : return m;
391 :
392 : }(API3);
|
