src/myfov.d

   1 import map;
   2 import tile;
   3 import util;
   4 import stdlib;
   5
   6 // Adam Milazzo's "my algorithm" for FOV.  Adapted from the c# code at http://www.adammil.net/blog/v125_Roguelike_Vision_Algorithms.html
   7
   8 void do_fov(const ref Map map, ref Lightmap lightmap, uint x, uint y, int rangeLimit, int lightLimit) {
   9         lightmap.for_all((ref Lightpt x) { x.visible = false; x.visibility = 0; x.lit = false; x.light = 0; });
  10
  11         lightmap[y, x].visible = true;
  12         foreach (octant; 0 .. 8) {
  13                 compute(map, lightmap, octant, Point(x, y), rangeLimit, lightLimit, 1, Slope(1, 1), Slope(0, 1));
  14         }
  15 }
  16
  17 // represents the slope Y/X as a rational number
  18 private struct Slope {
  19         int y, x;
  20
  21         bool greater(int y, int x) { return this.y*x > this.x*y; } // this > y/x
  22         bool greater_or_equal(int y, int x) { return this.y*x >= this.x*y; } // this >= y/x
  23         bool less(int y, int x) { return this.y*x < this.x*y; } // this < y/x
  24         bool less_or_equal(int y, int x) { return this.y*x <= this.x*y; } // this <= y/x
  25 }
  26
  27 private struct Point {
  28         int x, y;
  29 }
  30
  31
  32 private void compute(const ref Map map, ref Lightmap lightmap, int octant, Point origin, int rangeLimit, int lightLimit, int x, Slope top, Slope bottom) {
  33         // NOTE: the code duplication between blocks_light and set_visible is for performance. don't refactor the octant
  34         // translation out unless you don't mind an 18% drop in speed
  35         bool blocks_light(int x, int y, int octant, Point origin) {
  36                 int nx = origin.x, ny = origin.y;
  37                 switch(octant) {
  38                         case 0: nx += x; ny -= y; break;
  39                         case 1: nx += y; ny -= x; break;
  40                         case 2: nx -= y; ny -= x; break;
  41                         case 3: nx -= x; ny -= y; break;
  42                         case 4: nx -= x; ny += y; break;
  43                         case 5: nx -= y; ny += x; break;
  44                         case 6: nx += y; ny += x; break;
  45                         case 7: nx += x; ny += y; break;
  46                         default: break;
  47                 }
  48                 return map[ny, nx].blocks_light;
  49         }
  50
  51         pragma(inline, true) void set_visible(int x, int y, int octant, Point origin) {
  52                 int nx = origin.x, ny = origin.y;
  53                 switch(octant) {
  54                         case 0: nx += x; ny -= y; break;
  55                         case 1: nx += y; ny -= x; break;
  56                         case 2: nx -= y; ny -= x; break;
  57                         case 3: nx -= x; ny -= y; break;
  58                         case 4: nx -= x; ny += y; break;
  59                         case 5: nx -= y; ny += x; break;
  60                         case 6: nx += y; ny += x; break;
  61                         case 7: nx += x; ny += y; break;
  62                         default: break;
  63                 }
  64                 lightmap[ny, nx].visible = true;
  65                 float vis_sq = dist_sq(nx, ny, origin.x, origin.y);
  66                 float f = sqrt(rangeLimit) / (vis_sq);
  67                 lightmap[ny, nx].visibility = f;
  68
  69                 float light_sq = dist_sq(nx, ny, origin.x, origin.y);
  70                 if (light_sq <= lightLimit) {
  71                         lightmap[ny, nx].lit = true;
  72                         float f2 = sqrt(lightLimit) / light_sq;
  73                         lightmap[ny, nx].light = f2;
  74                 }
  75
  76                 // this makes conentric squares.  Probably faster
  77                 //lightmap[ny, nx].visibility = 1 - cast(float)max(abs(nx - origin.x), abs(ny - origin.y)) / 32.;
  78         }
  79
  80
  81
  82
  83
  84         /*
  85          * throughout this function there are references to various parts of tiles. a tile's coordinates refer to its
  86          * center, and the following diagram shows the parts of the tile and the vectors from the origin that pass through
  87          * those parts. given a part of a tile with vector u, a vector v passes above it if v > u and below it if v < u
  88          *    g         center:        y / x
  89          * a------b   a top left:      (y*2+1) / (x*2-1)   i inner top left:      (y*4+1) / (x*4-1)
  90          * |  /\  |   b top right:     (y*2+1) / (x*2+1)   j inner top right:     (y*4+1) / (x*4+1)
  91          * |i/__\j|   c bottom left:   (y*2-1) / (x*2-1)   k inner bottom left:   (y*4-1) / (x*4-1)
  92          *e|/|  |\|f  d bottom right:  (y*2-1) / (x*2+1)   m inner bottom right:  (y*4-1) / (x*4+1)
  93          * |\|__|/|   e middle left:   (y*2) / (x*2-1)
  94          * |k\  /m|   f middle right:  (y*2) / (x*2+1)     a-d are the corners of the tile
  95          * |  \/  |   g top center:    (y*2+1) / (x*2)     e-h are the corners of the inner (wall) diamond
  96          * c------d   h bottom center: (y*2-1) / (x*2)     i-m are the corners of the inner square (1/2 tile width)
  97          *    h
  98          */
  99         for(; x <= rangeLimit; x++) /* (x <= rangeLimit) == (rangeLimit < 0 || x <= rangeLimit) */ {
 100                 // compute the Y coordinates of the top and bottom of the sector. we maintain that top > bottom
 101                 int topY;
 102
 103                 // if top == ?/1 then it must be 1/1 because 0/1 < top <= 1/1. this is special-cased because top
 104                 // starts at 1/1 and remains 1/1 as long as it doesn't hit anything, so it's a common case
 105                 if(top.x == 1) {
 106                         topY = x;
 107                 // top < 1
 108                 } else {
 109                         /*
 110                          * get the tile that the top vector enters from the left. since our coordinates refer to the center of the
 111                          * tile, this is (x-0.5)*top+0.5, which can be computed as (x-0.5)*top+0.5 = (2(x+0.5)*top+1)/2 =
 112                          * ((2x+1)*top+1)/2. since top == a/b, this is ((2x+1)*a+b)/2b. if it enters a tile at one of the left
 113                          * corners, it will round up, so it'll enter from the bottom-left and never the top-left
 114                          */
 115                         // the Y coordinate of the tile entered from the left
 116                         topY = ((x*2-1) * top.y + top.x) / (top.x*2);
 117                         /* now it's possible that the vector passes from the left side of the tile up into the tile above before
 118                          * exiting from the right side of this column. so we may need to increment topY
 119                          */
 120
 121                         // if the tile blocks light (i.e. is a wall)...
 122                         if (blocks_light(x, topY, octant, origin)) {
 123                                 /* if the tile entered from the left blocks light, whether it
 124                                  * passes into the tile above depends on the shape of the wall tile
 125                                  * as well as the angle of the vector. if the tile has does not
 126                                  * have a beveled top-left corner, then it is blocked. the corner is
 127                                  * beveled if the tiles above and to the left are not walls. we can
 128                                  * ignore the tile to the left because if it was a wall tile, the
 129                                  * top vector must have entered this tile from the bottom-left
 130                                  * corner, in which case it can't possibly enter the tile above.
 131                                  *
 132                                  * otherwise, with a beveled top-left corner, the slope of the
 133                                  * vector must be greater than or equal to the slope of the vector
 134                                  * to the top center of the tile (x*2, topY*2+1) in order for it to
 135                                  * miss the wall and pass into the tile above
 136                                  */
 137                                 if (top.greater_or_equal(topY*2+1, x*2) && !blocks_light(x, topY+1, octant, origin)) {
 138                                         topY++;
 139                                 }
 140                         }
 141                         // the tile doesn't block light
 142                         else {
 143                                 /* since this tile doesn't block light, there's nothing to stop it
 144                                  * from passing into the tile above, and it does so if the vector is greater than the
 145                                  * vector for the bottom-right corner of the tile above. however,
 146                                  * there is one additional consideration. later code in this method
 147                                  * assumes that if a tile blocks light then it must be visible, so
 148                                  * if the tile above blocks light we have to make sure the light
 149                                  * actually impacts the wall shape. now there are three cases:
 150                                  *
 151                                  * 1) the tile above is clear, in which case the vector must be
 152                                  *    above the bottom-right corner of the tile above,
 153                                  *
 154                                  * 2) the tile above blocks light and does not have a beveled
 155                                  *    bottom-right corner, in which case the vector must be above
 156                                  *    the bottom-right corner, and
 157                                  *
 158                                  * 3) the tile above blocks light and does have a beveled bottom-
 159                                  *    right corner, in which case the vector must be above the bottom
 160                                  *    center of the tile above (i.e. the corner of the beveled edge).
 161                                  *
 162                                  *
 163                                  * now it's possible to merge 1 and 2 into a single check, and we
 164                                  * get the following: if the tile above and to the right is a wall,
 165                                  * then the vector must be above the bottom-right corner. otherwise,
 166                                  * the vector must be above the bottom center. this works because if
 167                                  * the tile above and to the right is a wall, then there are two
 168                                  * cases:
 169                                  *
 170                                  * 1) the tile above is also a wall, in which case we must check
 171                                  *    against the bottom-right corner, or
 172                                  *
 173                                  * 2) the tile above is not a wall, in which case the vector passes
 174                                  *    into it if it's above the bottom-right corner.
 175                                  *
 176                                  *
 177                                  * so either way we use the bottom-right corner in that case. now,
 178                                  * if the tile above and to the right is not a wall, then we again
 179                                  * have two cases:
 180                                  *
 181                                  * 1) the tile above is a wall with a beveled edge, in which case we
 182                                  *    must check against the bottom center, or
 183                                  *
 184                                  * 2) the tile above is not a wall, in which case it will only be
 185                                  *    visible if light passes through the inner square, and the
 186                                  *    inner square is guaranteed to be no larger than a wall
 187                                  *    diamond, so if it wouldn't pass through a wall diamond then it
 188                                  *    can't be visible, so there's no point in incrementing topY
 189                                  *    even if light passes through the corner of the tile above. so
 190                                  *    we might as well use the bottom center for both cases.
 191                                  */
 192                                 int ax = x*2; // center
 193
 194                                 // use bottom-right if the tile above and right is a wall
 195                                 if (blocks_light(x+1, topY+1, octant, origin)) {
 196                                         ax++;
 197                                 }
 198
 199                                 if (top.greater(topY*2+1, ax)) {
 200                                         topY++;
 201                                 }
 202                         }
 203                 }
 204
 205                 int bottomY;
 206                 // if bottom == 0/?, then it's hitting the tile at Y=0 dead center. this is special-cased because
 207                 // bottom.y starts at zero and remains zero as long as it doesn't hit anything, so it's common
 208                 if(bottom.y == 0) {
 209                         bottomY = 0;
 210                 }
 211                 // bottom > 0
 212                 else {
 213                         // the tile that the bottom vector enters from the left
 214                         bottomY = ((x*2-1) * bottom.y + bottom.x) / (bottom.x*2);
 215
 216                         /*
 217                          * code below assumes that if a tile is a wall then it's visible, so if the tile contains a wall we have to
 218                          * ensure that the bottom vector actually hits the wall shape. it misses the wall shape if the top-left corner
 219                          * is beveled and bottom >= (bottomY*2+1)/(x*2). finally, the top-left corner is beveled if the tiles to the
 220                          * left and above are clear. we can assume the tile to the left is clear because otherwise the bottom vector
 221                          * would be greater, so we only have to check above
 222                          */
 223                         if (bottom.greater_or_equal(bottomY*2+1, x*2) &&
 224                                         blocks_light(x, bottomY, octant, origin) &&
 225                                         !blocks_light(x, bottomY+1, octant, origin)) {
 226                                 bottomY++;
 227                         }
 228                 }
 229
 230                 // go through the tiles in the column now that we know which ones could possibly be visible
 231                 int wasOpaque = -1; // 0:false, 1:true, -1:not applicable
 232
 233                 // use a signed comparison because y can wrap around when decremented
 234                 for (int y = topY; y >= bottomY; y--) {
 235                         // skip the tile if it's out of visual range
 236                         if (rangeLimit < 0 || get_distance(x, y) <= rangeLimit) {
 237                                 bool isOpaque = blocks_light(x, y, octant, origin);
 238                                 /*
 239                                  * every tile where topY > y > bottomY is guaranteed to be visible.
 240                                  * also, the code that initializes topY and bottomY guarantees that
 241                                  * if the tile is opaque then it's visible. so we only have to do
 242                                  * extra work for the case where the tile is clear and y == topY or
 243                                  * y == bottomY. if y == topY then we have to make sure that the top
 244                                  * vector is above the bottom-right corner of the inner square.
 245                                  * if y == bottomY then we have to make sure that the bottom vector
 246                                  * is below the top-left corner of the inner square
 247                                  */
 248                                 bool isVisible = isOpaque || ((y != topY || top.greater(y*4-1, x*4+1)) && (y != bottomY || bottom.less(y*4+1, x*4-1)));
 249                                 /*
 250                                  * NOTE: if you want the algorithm to be either fully or mostly
 251                                  * symmetrical, replace the line above with the following line (and
 252                                  * uncomment the Slope.less_or_equal method). the line ensures that a
 253                                  * clear tile is visible only if there's an unobstructed line to its
 254                                  * center. if you want it to be fully symmetrical, also remove the
 255                                  * "isOpaque ||" part and see NOTE comments further down
 256                                  *
 257                                  * bool isVisible = isOpaque || ((y != topY || top.greaterOrEqual(y, x)) && (y != bottomY || bottom.less_or_equal(y, x)));
 258                                  */
 259                                 if (isVisible) {
 260                                         set_visible(x, y, octant, origin);
 261                                 }
 262
 263                                 // if we found a transition from clear to opaque or vice versa, adjust the top and bottom vectors
 264                                 // but don't bother adjusting them if this is the last column anyway
 265                                 if (x != rangeLimit) {
 266                                         if (isOpaque) {
 267                                                 // if we found a transition from clear to opaque, this sector is done in this column,
 268                                                 // so adjust the bottom vector upward and continue processing it in the next column
 269                                                 if (wasOpaque == 0) {
 270                                                         /*
 271                                                          * if the opaque tile has a beveled top-left
 272                                                          * corner, move the bottom vector up to the
 273                                                          * top center.  otherwise, move it up to the
 274                                                          * top left. the corner is beveled if the
 275                                                          * tiles above and to the left are clear. we
 276                                                          * can assume the tile to the left is clear
 277                                                          * because otherwise the vector would be
 278                                                          * higher, so we only have to check the tile
 279                                                          * above
 280                                                          */
 281                                                         int nx = x*2, ny = y*2+1; // top center by default
 282                                                         // NOTE: if you're using full symmetry and
 283                                                         // want more expansive walls (recommended),
 284                                                         // comment out the next line
 285
 286                                                         // top left if the corner is not beveled
 287                                                         if (blocks_light(x, y+1, octant, origin))
 288                                                                 nx--;
 289
 290                                                         // we have to maintain the invariant that top > bottom, so the new sector
 291                                                         // created by adjusting the bottom is only valid if that's the case
 292                                                         if (top.greater(ny, nx)) {
 293                                                                 // if we're at the bottom of the column,
 294                                                                 // then just adjust the current sector rather than recursing
 295                                                                 // since there's no chance that this sector
 296                                                                 // can be split in two by a later transition back to clear
 297                                                                 if(y == bottomY) {
 298                                                                         bottom = Slope(ny, nx); break;
 299                                                                 }
 300                                                                 // don't recurse unless necessary
 301                                                                 else {
 302                                                                         compute(map, lightmap, octant, origin, rangeLimit, lightLimit, x+1, top, Slope(ny, nx));
 303                                                                 }
 304                                                         }
 305                                                         // the new bottom is greater than or equal
 306                                                         // to the top, so the new sector is empty
 307                                                         // and we'll ignore it. if we're at the
 308                                                         // bottom of the column, we'd normally
 309                                                         // adjust the current sector rather than
 310                                                         else {
 311                                                                 // recursing, so that invalidates the current sector and we're done
 312                                                                 if (y == bottomY)
 313                                                                         return;
 314                                                         }
 315                                                 }
 316                                                 wasOpaque = 1;
 317                                         } else {
 318                                                 // if we found a transition from opaque to clear, adjust the top vector downwards
 319                                                 if (wasOpaque > 0) {
 320                                                         // if the opaque tile has a beveled bottom-
 321                                                         // right corner, move the top vector down to
 322                                                         // the bottom center.  otherwise, move it
 323                                                         // down to the bottom right. the corner is
 324                                                         // beveled if the tiles below and to the
 325                                                         // right are clear. we know the tile below
 326                                                         // is clear because that's the current tile,
 327                                                         // so just check to the right
 328
 329                                                         // the bottom of the opaque tile (oy*2-1) equals the top of this tile (y*2+1)
 330                                                         int nx = x*2, ny = y*2+1;
 331
 332                                                         // NOTE: if you're using full symmetry and
 333                                                         // want more expansive walls (recommended),
 334                                                         // comment out the next line
 335
 336                                                         // check the right of the opaque tile (y+1), not this one
 337                                                         if (blocks_light(x+1, y+1, octant, origin)) {
 338                                                                 nx++;
 339                                                         }
 340
 341                                                         // we have to maintain the invariant that
 342                                                         // top > bottom. if not, the sector is empty
 343                                                         // and we're done
 344                                                         if (bottom.greater_or_equal(ny, nx)) {
 345                                                                 return;
 346                                                         }
 347
 348                                                         top = Slope(ny, nx);
 349                                                 }
 350                                                 wasOpaque = 0;
 351                                         }
 352                                 }
 353                         }
 354                 }
 355
 356                 // if the column didn't end in a clear tile, then there's no reason to continue processing the current sector
 357                 // because that means either 1) wasOpaque == -1, implying that the sector is empty or at its range limit, or 2)
 358                 // wasOpaque == 1, implying that we found a transition from clear to opaque and we recursed and we never found
 359                 // a transition back to clear, so there's nothing else for us to do that the recursive method hasn't already. (if
 360                 // we didn't recurse (because y == bottomY), it would have executed a break, leaving wasOpaque equal to 0.)
 361                 if(wasOpaque != 0) {
 362                         break;
 363                 }
 364         }
 365 }
 366
 367 private int get_distance(int x, int y) {
 368         return x * x + y * y;
 369 }