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 }