1 /**
2  * This module helps handle coordinate systems within a map.
3  *
4  * When dealing with a grid, do you ever forget whether the row or column is the first index?
5  *
6  * Me too.
7  *
8  * For this reason, all functions dealing with grid coordinates take a RowCol argument.
9  * This makes it abundantly clear that the map is indexed in row-major order.
10  * Furthormore, it prevents confusion between **grid** coordinates and **pixel** coordinates.
11  *
12  * A 'pixel' coordinate refers to an (x,y) location in 'pixel' space.
13  * The units used by 'pixel' coords are the same as used in MapData tilewidth and tileheight.
14  *
15  * Within dtiled, pixel locations are represented by a PixelCoord.
16  * However, you may already be using a game library that provides some 'Vector' implementation
17  * used to represent positions.
18  * You can pass any such type to dtiled functions expecting a pixel coordinate so long as it
19  * satisfies isPixelCoord.
20  */
21 module dtiled.coords;
22 
23 import std.conv      : to;
24 import std.math      : abs, sgn;
25 import std.range     : iota, only, take, chain;
26 import std.traits    : Signed;
27 import std.format    : format;
28 import std.typecons  : Tuple, Flag;
29 import std.algorithm : map, canFind, cartesianProduct;
30 
31 /* This is the type used for map coordinates.
32  * Use the platform's size_t as it will be used to index arrays.
33  * However, make it signed to represent 'virtual' coordinates outside the maps
34  * bounds.
35  * This is useful for representing, for example, a mouse that is positioned
36  * to the left of the leftmost tile in a map.
37  */
38 private alias coord_t = Signed!size_t;
39 
40 /// Whether to consider diagonals adjacent in situations dealing with the concept of adjacency.
41 alias Diagonals = Flag!"Diagonals";
42 
43 /// Represents a discrete location within the map grid.
44 struct RowCol {
45   coord_t row, col;
46 
47   /// Construct a row column pair
48   @nogc
49   this(coord_t row, coord_t col) {
50     this.row = row;
51     this.col = col;
52   }
53 
54   /// Get a string representation of the coordinate, useful for debugging
55   @property {
56     string toString() {
57       return "(%d,%d)".format(row, col);
58     }
59 
60     /**
61      * Get a coordinate above this coordinate
62      * Params:
63      *  dist = distance in number of tiles
64      */
65     auto north(int dist = 1) { return RowCol(row - dist, col); }
66 
67     /**
68      * Get a coordinate below this coordinate
69      * Params:
70      *  dist = distance in number of tiles
71      */
72     auto south(int dist = 1) { return RowCol(row + dist, col); }
73 
74     /**
75      * Get a coordinate to the left of this coordinate
76      * Params:
77      *  dist = distance in number of tiles
78      */
79     auto west(int dist = 1)  { return RowCol(row, col - dist); }
80 
81     /**
82      * Get a coordinate to the right of this coordinate
83      * Params:
84      *  dist = distance in number of tiles
85      */
86     auto east(int dist = 1)  { return RowCol(row, col + dist); }
87 
88     /**
89      * Return a range containing the coords adjacent to this coord.
90      *
91      * The returned coords are ordered from north to south, west to east.
92      *
93      * Params:
94      *  diagonal = if no, include coords to the north, south, east, and west only.
95      *             if yes, additionaly include northwest, northeast, southwest, and southeast.
96      */
97     auto adjacent(Diagonals diagonal = Diagonals.no) {
98       // the 'take' statements are used to conditionally include the diagonal coords
99       return chain(
100           (this.north.west).only.take(diagonal ? 1 : 0),
101           (this.north).only,
102           (this.north.east).only.take(diagonal ? 1 : 0),
103           (this.west ).only,
104           (this.east ).only,
105           (this.south.west).only.take(diagonal ? 1 : 0),
106           (this.south).only,
107           (this.south.east).only.take(diagonal ? 1 : 0));
108     }
109   }
110 
111   /// convenient access of nearby coordinates
112   unittest {
113     import std.algorithm : equal;
114 
115     assert(RowCol(1,1).north == RowCol(0,1));
116     assert(RowCol(1,1).south == RowCol(2,1));
117     assert(RowCol(1,1).east  == RowCol(1,2));
118     assert(RowCol(1,1).west  == RowCol(1,0));
119 
120     assert(RowCol(1,1).south(5)         == RowCol(6,1));
121     assert(RowCol(1,1).south(2).east(5) == RowCol(3,6));
122 
123     assert(RowCol(1,1).adjacent.equal([
124       RowCol(0,1),
125       RowCol(1,0),
126       RowCol(1,2),
127       RowCol(2,1)
128     ]));
129 
130     assert(RowCol(1,1).adjacent(Diagonals.yes).equal([
131       RowCol(0,0),
132       RowCol(0,1),
133       RowCol(0,2),
134       RowCol(1,0),
135       RowCol(1,2),
136       RowCol(2,0),
137       RowCol(2,1),
138       RowCol(2,2)
139     ]));
140   }
141 
142   /// Add, subtract, multiply, or divide one coordinate from another.
143   @nogc
144   RowCol opBinary(string op)(RowCol rhs) const
145   if (op == "+" || op == "-" || op == "*" || op == "/")
146   {
147     return mixin(q{RowCol(this.row %s rhs.row, this.col %s rhs.col)}.format(op, op));
148   }
149 
150   /// Binary operations can be performed between coordinates.
151   unittest {
152     assert(RowCol(1, 2) + RowCol(4,  1) == RowCol( 5,  3));
153     assert(RowCol(4, 2) - RowCol(6,  1) == RowCol(-2,  1));
154     assert(RowCol(4, 2) * RowCol(2, -3) == RowCol( 8, -6));
155     assert(RowCol(8, 4) / RowCol(2, -4) == RowCol( 4, -1));
156   }
157 
158   /// A coordinate can be multiplied or divided by an integer.
159   @nogc
160   RowCol opBinary(string op, T : coord_t)(T rhs) const
161   if (op == "*" || op == "/")
162   {
163     return mixin(q{RowCol(this.row %s rhs, this.col %s rhs)}.format(op, op));
164   }
165 
166   /// Multiply/divide a coord by a constant
167   unittest {
168     assert(RowCol(1, 2) * -4 == RowCol(-4, -8));
169     assert(RowCol(4, -6) / 2 == RowCol(2, -3));
170   }
171 
172   /// Add, subtract, multiply, or divide one coordinate from another in place.
173   @nogc
174   void opOpAssign(string op, T)(T rhs)
175   if (is(typeof(this.opBinary!op(rhs))))
176   {
177     this = this.opBinary!op(rhs);
178   }
179 
180   unittest {
181     auto rc = RowCol(1, 2);
182     rc += RowCol(4, 1);
183     assert(rc == RowCol(5, 3));
184     rc -= RowCol(2, -1);
185     assert(rc == RowCol(3, 4));
186     rc *= RowCol(-2, 4);
187     assert(rc == RowCol(-6, 16));
188     rc /= RowCol(-3, 2);
189     assert(rc == RowCol(2, 8));
190     rc *= 2;
191     assert(rc == RowCol(4, 16));
192     rc /= 4;
193     assert(rc == RowCol(1, 4));
194   }
195 }
196 
197 /**
198  * Enumerate all row/col pairs spanning the rectangle bounded by the corners start and end.
199  *
200  * The order of enumeration is determined as follows:
201  * Enumerate all columns in a row before moving to the next row.
202  * If start.row >= end.row, enumerate rows in increasing order, otherwise enumerate in decreasing.
203  * If start.col >= end.col, enumerate cols in increasing order, otherwise enumerate in decreasing.
204  *
205  * Params:
206  *  bound = Determines whether each bound is "[" (inclusive) or  ")" (exclusive).
207  *          The default of "[)" includes start but excludes end.
208  *          See_Also: std.random.uniform.
209  *  start = RowCol pair to start enumeration from, $(B inclusive)
210  *  end   = RowCol pair to end enumeration at, $(B exclusive)
211  */
212 auto span(string bound = "[)")(RowCol start, RowCol end) {
213   enum validBounds = [ "()",  "(]", "[)", "[]" ];
214   static assert(validBounds.canFind(bound),
215       bound ~ " is an invalid span bound. Try one of " ~ validBounds.toString);
216 
217   // direction to increment the rows/cols (1 or -1)
218   auto colInc = sgn(end.col - start.col);
219   auto rowInc = sgn(end.row - start.row);
220 
221   colInc = (colInc == 0) ? 1 : colInc;
222   rowInc = (rowInc == 0) ? 1 : rowInc;
223 
224   // iota is inclusive on the lower bound; adjust if we want exclusive
225   static if (bound[0] == '(') start += RowCol(rowInc, colInc);
226 
227   // iota is exclusive on the upper bound; adjust if we want inclusive
228   static if (bound[1] == ']') end += RowCol(rowInc, colInc);
229 
230   auto colRange = iota(start.col, end.col, colInc);
231   auto rowRange = iota(start.row, end.row, rowInc);
232 
233   return rowRange.cartesianProduct(colRange).map!(x => RowCol(x[0], x[1]));
234 }
235 
236 ///
237 unittest {
238   import std.algorithm : equal;
239 
240   assert(RowCol(0,0).span(RowCol(2,3)).equal([
241     RowCol(0,0), RowCol(0,1), RowCol(0,2),
242     RowCol(1,0), RowCol(1,1), RowCol(1,2)]));
243 
244   assert(RowCol(2,2).span(RowCol(0,0)).equal([
245     RowCol(2,2), RowCol(2,1),
246     RowCol(1,2), RowCol(1,1)]));
247 
248   assert(RowCol(2,2).span(RowCol(1,3)).equal([RowCol(2,2)]));
249 
250   assert(RowCol(2,2).span(RowCol(3,1)).equal([RowCol(2,2)]));
251 
252   // as the upper bound of span is exclusive, both of these are empty (span over 0 columns):
253   assert(RowCol(2,2).span(RowCol(2,2)).empty);
254   assert(RowCol(2,2).span(RowCol(5,2)).empty);
255 }
256 
257 /// You can control whether the bounds are inclusive or exclusive
258 unittest {
259   import std.algorithm : equal;
260   assert(RowCol(2,2).span!"[]"(RowCol(2,2)).equal([ RowCol(2,2) ]));
261 
262   assert(RowCol(2,2).span!"[]"(RowCol(2,5)).equal(
263         [ RowCol(2,2), RowCol(2,3), RowCol(2,4), RowCol(2,5) ]));
264 
265   assert(RowCol(5,2).span!"[]"(RowCol(2,2)).equal(
266         [ RowCol(5,2), RowCol(4,2), RowCol(3,2), RowCol(2,2) ]));
267 
268   assert(RowCol(2,2).span!"[]"(RowCol(0,0)).equal([
269         RowCol(2,2), RowCol(2,1), RowCol(2,0),
270         RowCol(1,2), RowCol(1,1), RowCol(1,0),
271         RowCol(0,2), RowCol(0,1), RowCol(0,0)]));
272 
273   assert(RowCol(2,2).span!"(]"(RowCol(3,3)).equal([ RowCol(3,3) ]));
274 
275   assert(RowCol(2,2).span!"()"(RowCol(3,3)).empty);
276 }
277 
278 /// ditto
279 auto span(RowCol start, coord_t endRow, coord_t endCol) {
280   return span(start, RowCol(endRow, endCol));
281 }
282 
283 unittest {
284   import std.algorithm : equal;
285 
286   assert(RowCol(0,0).span(2,3).equal([
287     RowCol(0,0), RowCol(0,1), RowCol(0,2),
288     RowCol(1,0), RowCol(1,1), RowCol(1,2)]));
289 }
290 
291 /// Represents a location in continuous 2D space.
292 alias PixelCoord = Tuple!(float, "x", float, "y");
293 
294 /// True if T is a type that can represent a location in terms of pixels.
295 enum isPixelCoord(T) = is(typeof(T.x) : real) &&
296                        is(typeof(T.y) : real) &&
297                        is(T == struct); // must be a struct/tuple
298 
299 ///
300 unittest {
301   // PixelCoord is dtiled's vector representation within pixel coordinate space.
302   static assert(isPixelCoord!PixelCoord);
303 
304   // as a user, you may choose any (x,y) numeric pair to use as a pixel coordinate
305   struct MyVector(T) { T x, y; }
306 
307   static assert(isPixelCoord!(MyVector!int));
308   static assert(isPixelCoord!(MyVector!uint));
309   static assert(isPixelCoord!(MyVector!float));
310   static assert(isPixelCoord!(MyVector!double));
311   static assert(isPixelCoord!(MyVector!real));
312 
313   // To avoid confusion, grid coordinates are distinct from pixel coordinates
314   static assert(!isPixelCoord!RowCol);
315 }
316 
317 /// Convert a PixelCoord to a user-defined (x,y) numeric pair.
318 T as(T)(PixelCoord pos) if (isPixelCoord!T) {
319   T t;
320   t.x = pos.x.to!(typeof(t.x));
321   t.y = pos.y.to!(typeof(t.y));
322   return t;
323 }
324 
325 /// Convert dtiled's pixel-space coordinates to your own types:
326 unittest {
327   // your own representation may be a struct
328   struct MyVector(T) { T x, y; }
329 
330   assert(PixelCoord(5, 10).as!(MyVector!double) == MyVector!double(5, 10));
331   assert(PixelCoord(5.5, 10.2).as!(MyVector!int) == MyVector!int(5, 10));
332 
333   // or it may be a tuple
334   alias MyPoint(T) = Tuple!(T, "x", T, "y");
335 
336   assert(PixelCoord(5, 10).as!(MyPoint!double) == MyPoint!double(5, 10));
337   assert(PixelCoord(5.5, 10.2).as!(MyPoint!int) == MyPoint!int(5, 10));
338 
339   // std.conv.to is used internally, so it should detect overflow
340   import std.conv : ConvOverflowException;
341   import std.exception : assertThrown;
342   assertThrown!ConvOverflowException(PixelCoord(-1, -1).as!(MyVector!ulong));
343 }
344 
345 /**
346  * Return the manhattan distance between two tile coordinates.
347  * For two coordinates a and b, this is defined as abs(a.row - b.row) + abs(a.col - b.col)
348  */
349 @nogc
350 auto manhattan(RowCol a, RowCol b) {
351   return abs(a.row - b.row) + abs(a.col - b.col);
352 }
353 
354 unittest {
355   assert(manhattan(RowCol(0,0), RowCol(2,2))     == 4);
356   assert(manhattan(RowCol(2,2), RowCol(2,2))     == 0);
357   assert(manhattan(RowCol(-2,-2), RowCol(-2,-2)) == 0);
358   assert(manhattan(RowCol(4,-2), RowCol(2,2))    == 6);
359   assert(manhattan(RowCol(4,-2), RowCol(-2,-2))  == 6);
360 }