1 /**
2 * A grid wraps a 2D array to provide specialized grid-based functionality.
3 *
4 * Currently, the only grid type is RectGrid, which can serve as the base for an orthogonal or isometric map.
5 * HexGrid may be added in a later version to support hexagonal maps.
6 *
7 * Authors: <a href="https://github.com/rcorre">rcorre</a>
8 * License: <a href="http://opensource.org/licenses/MIT">MIT</a>
9 * Copyright: Copyright © 2015, Ryan Roden-Corrent
10 */
11 module dtiled.grid;
12
13 import std.range : only, chain, takeNone, hasLength;
14 import std.range : isInputRange, isForwardRange, isBidirectionalRange;
15 import std.format : format;
16 import std.algorithm : all, map, filter;
17 import std.exception : enforce;
18 import dtiled.coords;
19
20 /// True if T is a static or dynamic array type.
21 enum isArray2D(T) = is(typeof(T.init[0][0])) && // 2D random access
22 is(typeof(T.init.length) : size_t) && // stores count of rows
23 is(typeof(T.init[0].length) : size_t); // stores count of columns
24
25 ///
26 unittest {
27 import std.container : Array;
28
29 static assert(isArray2D!(int[][]));
30 static assert(isArray2D!(char[3][5]));
31 static assert(isArray2D!(Array!(Array!int)));
32 }
33
34 /// Convenience function to wrap a RectGrid around a 2D array.
35 auto rectGrid(T)(T tiles) if (isArray2D!T) { return RectGrid!T(tiles); }
36
37 ///
38 unittest {
39 auto dynamicArray = [
40 [1,2,3],
41 [4,5,6]
42 ];
43 auto dynamicGrid = rectGrid(dynamicArray);
44 assert(dynamicGrid.numRows == 2 && dynamicGrid.numCols == 3);
45 static assert(is(dynamicGrid.TileType == int));
46
47 char[3][2] staticArray = [
48 [ 'a', 'a', 'a' ],
49 [ 'a', 'a', 'a' ],
50 ];
51 auto staticGrid = rectGrid(staticArray);
52 assert(staticGrid.numRows == 2 && staticGrid.numCols == 3);
53 static assert(is(staticGrid.TileType == char));
54 }
55
56 /// A grid of rectangular tiles. Wraps a 2D array to provide grid-based access to tiles.
57 struct RectGrid(T) if (isArray2D!T) {
58 private T _tiles;
59
60 /// The type used to represent a tile in this grid
61 alias TileType = typeof(_tiles[0][0]);
62
63 /// Construct a grid from a 2D tile array. See rectGrid for a constructor with type inference.
64 this(T tiles) {
65 assertNotJagged(tiles, "RectGrid cannot be a constructed from a jagged array");
66 _tiles = tiles;
67 }
68
69 /// Number of columns along a grid's x axis.
70 auto numCols() { return _tiles[0].length; }
71
72 ///
73 unittest {
74 auto grid = rectGrid([
75 [ 0, 0, 0, 0 ],
76 [ 0, 0, 0, 0 ],
77 ]);
78
79 assert(grid.numCols == 4);
80 }
81
82 /// Number of rows along a grid's y axis.
83 auto numRows() { return _tiles.length; }
84
85 unittest {
86 auto grid = rectGrid([
87 [ 0, 0, 0, 0 ],
88 [ 0, 0, 0, 0 ],
89 ]);
90
91 assert(grid.numRows == 2);
92 }
93
94 /// The total number of tiles in a grid.
95 auto numTiles() { return this.numRows * this.numCols; }
96
97 unittest {
98 auto grid = rectGrid([
99 [ 0, 0, 0, 0 ],
100 [ 0, 0, 0, 0 ],
101 ]);
102
103 assert(grid.numTiles == 8);
104 }
105
106 /**
107 * True if the grid coordinate is within the grid bounds.
108 */
109 bool contains(RowCol coord) {
110 return
111 coord.row >= 0 &&
112 coord.col >= 0 &&
113 coord.row < this.numRows &&
114 coord.col < this.numCols;
115 }
116
117 ///
118 unittest {
119 // 5x3 map
120 auto grid = rectGrid([
121 //0 1 2 3 4 col row
122 [ 0, 0, 0, 0, 0 ], // 0
123 [ 0, 0, 0, 0, 0 ], // 1
124 [ 0, 0, 0, 0, 0 ], // 2
125 ]);
126
127 assert( grid.contains(RowCol(0 , 0))); // top left
128 assert( grid.contains(RowCol(2 , 4))); // bottom right
129 assert( grid.contains(RowCol(1 , 2))); // center
130 assert(!grid.contains(RowCol(0 , 5))); // beyond right border
131 assert(!grid.contains(RowCol(3 , 0))); // beyond bottom border
132 assert(!grid.contains(RowCol(0 ,-1))); // beyond left border
133 assert(!grid.contains(RowCol(-1, 0))); // beyond top border
134 }
135
136 /**
137 * Get the tile at a given position in the grid.
138 * The coord must be in bounds.
139 *
140 * Params:
141 * coord = a row/column pair identifying a point in the tile grid.
142 */
143 ref auto tileAt(RowCol coord) {
144 assert(this.contains(coord), "coord %s not in bounds".format(coord));
145 return _tiles[coord.row][coord.col];
146 }
147
148 ///
149 unittest {
150 auto grid = rectGrid([
151 [ 00, 01, 02, 03, 04 ],
152 [ 10, 11, 12, 13, 14 ],
153 [ 20, 21, 22, 23, 24 ],
154 ]);
155
156 assert(grid.tileAt(RowCol(0, 0)) == 00); // top left tile
157 assert(grid.tileAt(RowCol(2, 4)) == 24); // bottom right tile
158 assert(grid.tileAt(RowCol(1, 1)) == 11); // one down/right from the top left
159
160 // tileAt returns a reference:
161 grid.tileAt(RowCol(2,2)) = 99;
162 assert(grid.tileAt(RowCol(2,2)) == 99);
163 }
164
165 /**
166 * Access tiles via a range of coords. Tiles are returned by ref.
167 *
168 * Params:
169 * coords = A range that yields coords.
170 */
171 ref auto tilesAt(R)(R coords) if (isInputRange!R && is(typeof(coords.front) : RowCol)) {
172 alias GridType = typeof(this);
173
174 struct Result {
175 private GridType _grid;
176 private R _coords;
177
178 ref auto front() { return _grid.tileAt(_coords.front); }
179 bool empty() { return _coords.empty(); }
180 void popFront() { _coords.popFront(); }
181
182 static if (isForwardRange!R) {
183 auto save() { return Result(_grid, _coords.save); }
184 }
185
186 static if (isBidirectionalRange!R) {
187 auto back() { return _grid.tileAt(_coords.back); }
188 void popBack() { _coords.popBack(); }
189 }
190 }
191
192 return Result(this, coords);
193 }
194
195 unittest {
196 import std.range;
197 import std.algorithm : equal;
198
199 auto grid = rectGrid([
200 [ 00, 01, 02, 03, 04 ],
201 [ 10, 11, 12, 13, 14 ],
202 [ 20, 21, 22, 23, 24 ],
203 ]);
204
205 auto r1 = chain(RowCol(0,0).only, RowCol(2,2).only, RowCol(2,0).only);
206 assert(grid.tilesAt(r1).equal([00, 22, 20]));
207
208 auto r2 = grid.allCoords.filter!(x => x.row > 1 && x.col > 2);
209 auto tiles = grid.tilesAt(r2);
210 assert(tiles.equal([23, 24]));
211 assert(tiles.equal([23, 24]));
212 }
213
214 /**
215 * Get a range that iterates through every coordinate in the grid.
216 */
217 auto allCoords() {
218 return RowCol(0,0).span(RowCol(this.numRows, this.numCols));
219 }
220
221 /// Use allCoords to apply range-oriented functions to the coords in the grid.
222 unittest {
223 import std.algorithm;
224
225 auto myGrid = rectGrid([
226 [ 00, 01, 02, 03, 04 ],
227 [ 10, 11, 12, 13, 14 ],
228 [ 20, 21, 22, 23, 24 ],
229 ]);
230
231 auto coords = myGrid.allCoords
232 .filter!(x => x.col > 3)
233 .map!(x => x.row * 10 + x.col);
234
235 assert(coords.equal([04, 14, 24]));
236 }
237
238 /**
239 * Get a range that iterates through every tile in the grid.
240 */
241 auto allTiles() {
242 return tilesAt(this.allCoords);
243 }
244
245 /// Use allTiles to apply range-oriented functions to the tiles in the grid.
246 unittest {
247 import std.algorithm;
248
249 auto myGrid = rectGrid([
250 [ 00, 01, 02, 03, 04 ],
251 [ 10, 11, 12, 13, 14 ],
252 [ 20, 21, 22, 23, 24 ],
253 ]);
254
255 assert(myGrid.allTiles.filter!(x => x > 22).equal([23, 24]));
256
257 // use ref with allTiles to apply modifications
258 foreach(ref tile ; myGrid.allTiles.filter!(x => x < 10)) {
259 tile += 10;
260 }
261
262 assert(myGrid.tileAt(RowCol(0,0)) == 10);
263 }
264
265 /// Foreach over every tile in the grid. Supports `ref`.
266 int opApply(int delegate(ref TileType) fn) {
267 int res = 0;
268
269 foreach(coord ; this.allCoords) {
270 res = fn(this.tileAt(coord));
271 if (res) break;
272 }
273
274 return res;
275 }
276
277 /// foreach with coords
278 unittest {
279 auto myGrid = rectGrid([
280 [ 00, 01, 02, 03, 04 ],
281 [ 10, 11, 12, 13, 14 ],
282 [ 20, 21, 22, 23, 24 ],
283 ]);
284
285 int[] actual;
286 foreach(tile ; myGrid) { actual ~= tile; }
287
288 assert(actual == [
289 00, 01, 02, 03, 04,
290 10, 11, 12, 13, 14,
291 20, 21, 22, 23, 24]);
292 }
293
294 /// Foreach over every (coord,tile) pair in the grid. Supports `ref`.
295 int opApply(int delegate(RowCol, ref TileType) fn) {
296 int res = 0;
297
298 foreach(coord ; this.allCoords) {
299 res = fn(coord, this.tileAt(coord));
300 if (res) break;
301 }
302
303 return res;
304 }
305
306 /// foreach with coords
307 unittest {
308 auto myGrid = rectGrid([
309 [ 00, 01, 02, 03, 04 ],
310 [ 10, 11, 12, 13, 14 ],
311 [ 20, 21, 22, 23, 24 ],
312 ]);
313
314 foreach(coord, tile ; myGrid) {
315 assert(tile == coord.row * 10 + coord.col);
316 }
317 }
318
319 /**
320 * Same as maskTiles, but return coords instead of tiles.
321 *
322 * Params:
323 * offset = map coordinate on which to align the top-left corner of the mask.
324 * mask = a rectangular array of true/false values indicating which tiles to take.
325 * each true value takes the tile at that grid coordinate.
326 * the mask should be in row major order (indexed as mask[row][col]).
327 */
328 auto maskCoords(T)(RowCol offset, in T mask) if (isValidMask!T) {
329 assertNotJagged(mask, "mask cannot be a jagged array");
330
331 return RowCol(0,0).span(arraySize2D(mask))
332 .filter!(x => mask[x.row][x.col]) // remove elements that are 0 in the mask
333 .map!(x => x + offset) // add the offset to get the corresponding map coord
334 .filter!(x => this.contains(x)); // remove coords outside of bounds
335 }
336
337 /**
338 * Select specific tiles from this slice based on a mask.
339 *
340 * The upper left corner of the mask is positioned at the given offset.
341 * Each map tile that is overlaid with a 'true' value is included in the result.
342 * The mask is allowed to extend out of bounds - out of bounds coordinates are ignored
343 *
344 * Params:
345 * offset = map coordinate on which to align the top-left corner of the mask.
346 * mask = a rectangular array of true/false values indicating which tiles to take.
347 * each true value takes the tile at that grid coordinate.
348 * the mask should be in row major order (indexed as mask[row][col]).
349 *
350 * Examples:
351 * Suppose you are making a strategy game, and an attack hits all tiles in a cross pattern.
352 * This attack is used on the tile at row 2, column 3.
353 * You want to check each tile that was affected to see if any unit was hit:
354 * --------------
355 * // cross pattern
356 * ubyte[][] attackPattern = [
357 * [0,1,0]
358 * [1,1,1]
359 * [0,1,0]
360 * ];
361 *
362 * // get tiles contained by a cross pattern centered at (2,3)
363 * auto tilesHit = map.maskTilesAround((RowCol(2, 3), attackPattern));
364 *
365 * // now do something with those tiles
366 * auto unitsHit = tilesHit.map!(tile => tile.unitOnTile).filter!(unit => unit !is null);
367 * foreach(unit ; unitsHit) unit.applySomeEffect;
368 * --------------
369 */
370 auto maskTiles(T)(RowCol offset, in T mask) if (isValidMask!T) {
371 return this.maskCoords(mask).map!(x => this.tileAt(x));
372 }
373
374 /**
375 * Same as maskCoords, but centered.
376 *
377 * Params:
378 * center = map coord on which to position the center of the mask.
379 * if the mask has an even side length, rounds down to compute the 'center'
380 * mask = a rectangular array of true/false values indicating which tiles to take.
381 * each true value takes the tile at that grid coordinate.
382 * the mask should be in row major order (indexed as mask[row][col]).
383 */
384 auto maskCoordsAround(T)(RowCol center, in T mask) if (isValidMask!T) {
385 assertNotJagged(mask, "mask");
386
387 auto offset = center - RowCol(mask.length / 2, mask[0].length / 2);
388
389 return this.maskCoords(offset, mask);
390 }
391
392 /**
393 * Same as maskTiles, but centered.
394 *
395 * Params:
396 * center = map coord on which to position the center of the mask.
397 * if the mask has an even side length, rounds down to compute the 'center'
398 * mask = a rectangular array of true/false values indicating which tiles to take.
399 * each true value takes the tile at that grid coordinate.
400 * the mask should be in row major order (indexed as mask[row][col]).
401 */
402 auto maskTilesAround(T)(RowCol center, in T mask) if (isValidMask!T) {
403 return this.maskCoordsAround(center, mask).map!(x => this.tileAt(x));
404 }
405
406 /// More masking examples:
407 unittest {
408 import std.array : empty;
409 import std.algorithm : equal;
410
411 auto myGrid = rectGrid([
412 [ 00, 01, 02, 03, 04 ],
413 [ 10, 11, 12, 13, 14 ],
414 [ 20, 21, 22, 23, 24 ],
415 ]);
416
417 uint[3][3] mask1 = [
418 [ 1, 1, 1 ],
419 [ 0, 0, 0 ],
420 [ 0, 0, 0 ],
421 ];
422 assert(myGrid.maskTilesAround(RowCol(0,0), mask1).empty);
423 assert(myGrid.maskTilesAround(RowCol(1,1), mask1).equal([00, 01, 02]));
424 assert(myGrid.maskTilesAround(RowCol(2,1), mask1).equal([10, 11, 12]));
425 assert(myGrid.maskTilesAround(RowCol(2,4), mask1).equal([13, 14]));
426
427 auto mask2 = [
428 [ 0, 0, 1 ],
429 [ 0, 0, 1 ],
430 [ 1, 1, 1 ],
431 ];
432 assert(myGrid.maskTilesAround(RowCol(0,0), mask2).equal([01, 10, 11]));
433 assert(myGrid.maskTilesAround(RowCol(1,2), mask2).equal([03, 13, 21, 22, 23]));
434 assert(myGrid.maskTilesAround(RowCol(2,4), mask2).empty);
435
436 auto mask3 = [
437 [ 0 , 0 , 1 , 0 , 0 ],
438 [ 1 , 0 , 1 , 0 , 1 ],
439 [ 0 , 0 , 0 , 0 , 0 ],
440 ];
441 assert(myGrid.maskTilesAround(RowCol(0,0), mask3).equal([00, 02]));
442 assert(myGrid.maskTilesAround(RowCol(1,2), mask3).equal([02, 10, 12, 14]));
443
444 auto mask4 = [
445 [ 1 , 1 , 1 , 0 , 1 ],
446 ];
447 assert(myGrid.maskTilesAround(RowCol(0,0), mask4).equal([00, 02]));
448 assert(myGrid.maskTilesAround(RowCol(2,2), mask4).equal([20, 21, 22, 24]));
449
450 auto mask5 = [
451 [ 1 ],
452 [ 1 ],
453 [ 0 ],
454 [ 1 ],
455 [ 1 ],
456 ];
457 assert(myGrid.maskTilesAround(RowCol(0,4), mask5).equal([14, 24]));
458 assert(myGrid.maskTilesAround(RowCol(1,1), mask5).equal([01, 21]));
459 }
460
461 /**
462 * Return all tiles adjacent to the tile at the given coord (not including the tile itself).
463 *
464 * Params:
465 * coord = grid location of center tile.
466 * diagonals = if no, include tiles to the north, south, east, and west only.
467 * if yes, also include northwest, northeast, southwest, and southeast.
468 */
469 auto adjacentTiles(RowCol coord, Diagonals diagonals = Diagonals.no) {
470 return coord.adjacent(diagonals)
471 .filter!(x => this.contains(x))
472 .map!(x => this.tileAt(x));
473 }
474
475 ///
476 unittest {
477 import std.algorithm : equal;
478 auto myGrid = rectGrid([
479 [ 00, 01, 02, 03, 04 ],
480 [ 10, 11, 12, 13, 14 ],
481 [ 20, 21, 22, 23, 24 ],
482 ]);
483
484 assert(myGrid.adjacentTiles(RowCol(0,0)).equal([01, 10]));
485 assert(myGrid.adjacentTiles(RowCol(1,1)).equal([01, 10, 12, 21]));
486 assert(myGrid.adjacentTiles(RowCol(2,2)).equal([12, 21, 23]));
487 assert(myGrid.adjacentTiles(RowCol(2,4)).equal([14, 23]));
488
489 assert(myGrid.adjacentTiles(RowCol(0,0), Diagonals.yes)
490 .equal([01, 10, 11]));
491 assert(myGrid.adjacentTiles(RowCol(1,1), Diagonals.yes)
492 .equal([00, 01, 02, 10, 12, 20, 21, 22]));
493 assert(myGrid.adjacentTiles(RowCol(2,2), Diagonals.yes)
494 .equal([11, 12, 13, 21, 23]));
495 assert(myGrid.adjacentTiles(RowCol(2,4), Diagonals.yes)
496 .equal([13, 14, 23]));
497 }
498 }
499
500 // NOTE: declared outside of struct due to issues with alias parameters on templated structs.
501 // See https://issues.dlang.org/show_bug.cgi?id=11098
502 /**
503 * Generate a mask from a region of tiles based on a condition.
504 *
505 * For each tile in the grid, sets the corresponding element of mask to the result of fn(tile).
506 * If a coordinate is out of bounds (e.g. if you are generating a mask from a slice that extends
507 * over the map border) the mask value is the init value of the mask's element type.
508 *
509 * Params:
510 * fn = function that generates a mask entry from a tile
511 * grid = grid to generate mask from
512 * offset = map coord from which to start the top-left corner of the mask
513 * mask = rectangular array to populate with generated mask values.
514 * must match the size of the grid
515 */
516 void createMask(alias fn, T, U)(T grid, RowCol offset, ref U mask)
517 if(__traits(compiles, { mask[0][0] = fn(grid.tileAt(RowCol(0,0))); }))
518 {
519 assertNotJagged(mask, "mask");
520
521 foreach(coord ; RowCol(0,0).span(arraySize2D(mask))) {
522 auto mapCoord = coord + offset;
523
524 mask[coord.row][coord.col] = (grid.contains(mapCoord)) ?
525 fn(grid.tileAt(mapCoord)) : // in bounds, apply fn to generate mask value
526 typeof(mask[0][0]).init; // out of bounds, use default value
527 }
528 }
529
530 /**
531 * Same as createMask, but specify the offset of the mask's center rather than the top-left corner.
532 *
533 * Params:
534 * fn = function that generates a mask entry from a tile
535 * grid = grid to generate mask from
536 * center = center position around which to generate mask
537 * mask = rectangular array to populate with generated mask values.
538 * must match the size of the grid
539 */
540 void createMaskAround(alias fn, T, U)(T grid, RowCol center, ref U mask)
541 if(__traits(compiles, { mask[0][0] = fn(grid.tileAt(RowCol(0,0))); }))
542 {
543 assertNotJagged(mask, "mask");
544
545 auto offset = center - RowCol(mask.length / 2, mask[0].length / 2);
546 grid.createMask!fn(offset, mask);
547 }
548
549 ///
550 unittest {
551 auto myGrid = rectGrid([
552 [ 00, 01, 02, 03, 04 ],
553 [ 10, 11, 12, 13, 14 ],
554 [ 20, 21, 22, 23, 24 ],
555 ]);
556
557 uint[3][3] mask;
558
559 myGrid.createMaskAround!(tile => tile > 10)(RowCol(1,1), mask);
560
561 assert(mask == [
562 [0, 0, 0],
563 [0, 1, 1],
564 [1, 1, 1],
565 ]);
566
567 myGrid.createMaskAround!(tile => tile < 24)(RowCol(2,4), mask);
568
569 assert(mask == [
570 [1, 1, 0],
571 [1, 0, 0],
572 [0, 0, 0],
573 ]);
574 }
575
576 private:
577 // assertion helper for input array args
578 void assertNotJagged(T)(in T array, string msg) {
579 assert(array[].all!(x => x.length == array[0].length), msg);
580 }
581
582 // get a RowCol representing the size of a 2D array (assumed non-jagged).
583 auto arraySize2D(T)(in T array) {
584 return RowCol(array.length, array[0].length);
585 }
586
587 enum isValidMask(T) = is(typeof(cast(bool) T.init[0][0])) && // must have boolean elements
588 is(typeof(T.init.length) : size_t) && // must have row count
589 is(typeof(T.init[0].length) : size_t); // must have column count
590
591 unittest {
592 static assert(isValidMask!(int[][]));
593 static assert(isValidMask!(uint[][3]));
594 static assert(isValidMask!(uint[3][]));
595 static assert(isValidMask!(uint[3][3]));
596
597 static assert(!isValidMask!int);
598 static assert(!isValidMask!(int[]));
599 }