mapent/EntityGrid.vc

   1 /**************************************************************************
   2  *    This program is free software; you can redistribute it and/or
   3  *  modify it under the terms of the GNU General Public License
   4  *  as published by the Free Software Foundation; either version 3
   5  *  of the License, or (at your option) any later version.
   6  *
   7  *    This program is distributed in the hope that it will be useful,
   8  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   9  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  10  *  GNU General Public License for more details.
  11  **************************************************************************/
  12 // code by Ketmar Dark
  13 // grid of entities
  14 // note that entity can occupy more than one cell
  15 class EntityGrid : Object;
  16
  17 enum CellSize = 16;
  18
  19
  20 struct CellObject {
  21   MapEntity e;
  22   int tag; // arbitrary userdata, set to 0 in new items
  23   // last known grid position
  24   int gx0, gy0, gx1, gy1;
  25   // previous item in alloced list
  26   int prev;
  27   // next item in free/alloced list
  28   int next;
  29   bool objectIsOwned; // will be `delete`d on removing
  30 }
  31
  32 struct Item {
  33   int cid; // index in `cobjs`
  34   // 0: end-of-list
  35   // otherwise either next item in cell, or next item in free list
  36   int next;
  37 }
  38
  39
  40 private array!CellObject cobjs;
  41 private int freeHeadCObj;
  42 private int firstInsertedCObj; // for `allObjects()`
  43 private int lastInsertedCObj; // for `allObjects()`
  44
  45 // item #0 is never used
  46 private array!Item items;
  47 private int freeHead;
  48
  49 //WARNING! don't change
  50 // grid size in cells
  51 private int mWidth, mHeight;
  52 // offset of the (0, 0) grid cell, in pixels
  53 private int mXOfs, mYOfs;
  54
  55 // grid cells, width*height in total
  56 // contains index in `items` or 0
  57 private array!int grid;
  58
  59 private transient int lastUsedTag;
  60
  61 bool ownObjects; // should we own and `delete` inserted objects?
  62
  63 // this is used in various grid queries
  64 transient private array!MapEntity collected;
  65
  66 transient int collUsed; // used items in `collected`
  67
  68
  69 // in pixels
  70 final int gridX0 { get mXOfs; }
  71 final int gridY0 { get mYOfs; }
  72 final int gridX1 { get { return mXOfs+mWidth*CellSize-1; } }
  73 final int gridY1 { get { return mYOfs+mHeight*CellSize-1; } }
  74 final int gridWidth { get { return mWidth*CellSize; } }
  75 final int gridHeight { get { return mHeight*CellSize; } }
  76
  77
  78 // ////////////////////////////////////////////////////////////////////////// //
  79 final void setup (int x0, int y0, int awidth, int aheight) {
  80   awidth = max(1, awidth);
  81   aheight = max(1, aheight);
  82   int xcells = max(1, (awidth+CellSize-1)/CellSize);
  83   int ycells = max(1, (aheight+CellSize-1)/CellSize);
  84   // setup offsets
  85   mXOfs = x0;
  86   mYOfs = y0;
  87   // setup dimensions
  88   mWidth = xcells;
  89   mHeight = ycells;
  90   // setup items and free list
  91   items.length = 32;
  92   cobjs.length = 32;
  93   grid.setSize(xcells, ycells);
  94   removeAllObjects();
  95 }
  96
  97
  98 final void clear () {
  99   if (collUsed) FatalError("EntityGrid::clear(): query in progress");
 100   if (lastSafeIter) FatalError("EntityGrid::clear(): safe query in progress");
 101   cobjs.length = 0;
 102   freeHeadCObj = 0;
 103   items.length = 0;
 104   freeHead = 0;
 105   mWidth = 0;
 106   mHeight = 0;
 107   mXOfs = 0;
 108   mYOfs = 0;
 109   grid.length = 0;
 110   lastUsedTag = 0;
 111   collected.length = 0;
 112 }
 113
 114
 115 final void removeAllObjects (optional bool doRemove) {
 116   if (collUsed) FatalError("EntityGrid::removeAllObjects(): query in progress");
 117   if (lastSafeIter) FatalError("EntityGrid::clear(): safe query in progress");
 118   lastUsedTag = 0;
 119   // clear grid
 120   foreach (ref auto oid; grid) oid = 0;
 121   // clear items
 122   items.length = 32;
 123   foreach (int f, ref auto item; items) item.next = f+1;
 124   items[0].next = 0; // as sentinel
 125   items[$-1].next = 0;
 126   freeHead = 1;
 127   // clear cobjects
 128   for (int f = firstInsertedCObj; f; f = cobjs[f].next) {
 129     if (doRemove || cobjs[f].objectIsOwned) delete cobjs[f].e; else cobjs[f].e = none;
 130   }
 131   cobjs.length = 32;
 132   foreach (int f, ref auto cobj; cobjs) {
 133     cobj.e = none;
 134     cobj.prev = -1;
 135     cobj.next = f+1;
 136     cobj.tag = 0;
 137     cobj.objectIsOwned = false;
 138   }
 139   cobjs[0].next = 0; // as sentinel
 140   cobjs[$-1].next = 0;
 141   freeHeadCObj = 1;
 142   firstInsertedCObj = 0;
 143   lastInsertedCObj = 0;
 144   collected.clear(); // just in case
 145 }
 146
 147
 148 private final void clearTags () {
 149   for (int oid = firstInsertedCObj; oid; oid = cobjs[oid].next) {
 150     cobjs[oid].tag = 0;
 151   }
 152 }
 153
 154
 155 private final int nextTag () {
 156   if (lastUsedTag >= 0x3fff_ffff && collUsed == 0) {
 157     lastUsedTag = 0;
 158     clearTags();
 159   }
 160   if (lastUsedTag == 0x7fff_ffff) FatalError("EntityGrid: tag overflow");
 161   return ++lastUsedTag;
 162 }
 163
 164
 165 // ////////////////////////////////////////////////////////////////////////// //
 166 private final int allocCObj () {
 167   int res = freeHeadCObj;
 168   if (res) {
 169     freeHeadCObj = cobjs[res].next;
 170   } else {
 171     res = cobjs.length;
 172     int newlen = (res > 3 ? res+res/2 : 8);
 173     cobjs.length = newlen;
 174     foreach (int f; res+1..newlen) { cobjs[f].prev = -1; cobjs[f].next = f+1; }
 175     cobjs[$-1].next = 0;
 176     freeHeadCObj = res+1;
 177   }
 178   // other fields will be set by caller
 179   auto cobj = &cobjs[res];
 180   if (lastInsertedCObj) cobjs[lastInsertedCObj].next = res; else firstInsertedCObj = res;
 181   cobj.tag = 0;
 182   cobj.prev = lastInsertedCObj;
 183   cobj.next = 0;
 184   cobj.objectIsOwned = ownObjects;
 185   lastInsertedCObj = res;
 186   return res;
 187 }
 188
 189
 190 private final void freeCObj (int idx) {
 191   if (idx < 1 || idx >= cobjs.length) FatalError("EntityGrid::freeCObj: invalid item index!");
 192   auto cobj = &cobjs[idx];
 193   if (cobj.prev == -1) FatalError("EntityGrid::freeCObj: double free!");
 194   // fix safe iterators
 195   for (AllObjSafeIterData *it = lastSafeIter; it; it = it.next) {
 196     if (it.cid == idx) {
 197       // move to the next one
 198       it.cid = cobjs[it.cid].next;
 199     }
 200   }
 201   // remove us from the alloced list
 202   if (cobj.prev) cobjs[cobj.prev].next = cobj.next;
 203   if (cobj.next) cobjs[cobj.next].prev = cobj.prev;
 204   // fix alloced list (and do some sanity checks)
 205   if (idx == lastInsertedCObj) {
 206     if (cobj.next != 0) FatalError("EntityGrid::freeCObj: invalid alloced list!");
 207     lastInsertedCObj = cobj.prev;
 208   }
 209   if (idx == firstInsertedCObj) {
 210     if (cobj.prev != 0) FatalError("EntityGrid::freeCObj: invalid alloced list!");
 211     firstInsertedCObj = cobj.next;
 212   }
 213   MapEntity e = cobj.e;
 214   if (cobj.objectIsOwned) {
 215     delete e;
 216   } else if (e) {
 217     e.gridId = 0;
 218     e.grid = none;
 219   }
 220   cobj.e = none;
 221   cobj.prev = -1;
 222   cobj.next = freeHeadCObj;
 223   cobj.objectIsOwned = false;
 224   freeHeadCObj = idx;
 225 }
 226
 227
 228 private final int allocItem () {
 229   int res = freeHead;
 230   if (res) {
 231     freeHead = items[res].next;
 232   } else {
 233     res = items.length;
 234     int newlen = (res > 3 ? res+res/2 : 8);
 235     items.length = newlen;
 236     foreach (int f; res+1..newlen) items[f].next = f+1;
 237     items[$-1].next = 0;
 238     freeHead = res+1;
 239   }
 240   // other fields will be set by caller
 241   return res;
 242 }
 243
 244
 245 private final void freeItem (int idx) {
 246   if (idx < 1 || idx >= items.length) FatalError("EntityGrid::freeItem: invalid item index!");
 247   if (items[idx].cid == -1) FatalError("EntityGrid::freeItem: double free!");
 248   items[idx].cid = -1;
 249   items[idx].next = freeHead;
 250   freeHead = idx;
 251 }
 252
 253
 254 // ////////////////////////////////////////////////////////////////////////// //
 255 private final void insertIntoCell (int cid, int gx, int gy) {
 256   int iid = allocItem();
 257   Item *it = &items[iid];
 258   it.cid = cid;
 259   it.next = grid[gx, gy];
 260   grid[gx, gy] = iid;
 261 }
 262
 263
 264 private final void removeFromCell (int cid, int gx, int gy) {
 265   // find item
 266   int iid = grid[gx, gy], iprev = 0;
 267   while (iid) {
 268     if (items[iid].cid == cid) break;
 269     iprev = iid;
 270     iid = items[iid].next;
 271   }
 272   if (iid) {
 273     // i found her!
 274     int next = items[iid].next;
 275     if (iprev) items[iprev].next = next; else grid[gx, gy] = next;
 276     freeItem(iid);
 277   }
 278 }
 279
 280
 281 // `cobjs[cid]` should be fully initialized
 282 private final void insertInternal (int cid) {
 283   auto cobj = &cobjs[cid];
 284   int gx0 = cobj.gx0, gx1 = cobj.gx1;
 285   foreach (int cy; cobj.gy0..cobj.gy1) {
 286     foreach (int cx; gx0..gx1) {
 287       insertIntoCell(cid, cx, cy);
 288     }
 289   }
 290 }
 291
 292
 293 // this won't free `cid`
 294 private final void removeInternal (int cid) {
 295   auto cobj = &cobjs[cid];
 296   int gx0 = cobj.gx0, gx1 = cobj.gx1;
 297   foreach (int cy; cobj.gy0..cobj.gy1) {
 298     foreach (int cx; gx0..gx1) {
 299       removeFromCell(cid, cx, cy);
 300     }
 301   }
 302 }
 303
 304
 305 // returns `true` if moved
 306 private final bool moveInternal (int cid, int nx0, int ny0, int nx1, int ny1) {
 307   auto cobj = &cobjs[cid];
 308   int gx0 = cobj.gx0, gy0 = cobj.gy0;
 309   int gx1 = cobj.gx1, gy1 = cobj.gy1;
 310   if (gx0 != nx0 || gy0 != ny0 || gx1 != nx1 || gy1 != ny1) {
 311     foreach (int gy; min(gy0, ny0)..max(gy1, ny1)) {
 312       foreach (int gx; min(gx0, nx0)..max(gx1, nx1)) {
 313         // are we inside the old rect?
 314         if (gx >= gx0 && gy >= gy0 && gx < gx1 && gy < gy1) {
 315           // old rect: inside
 316           // if not inside new, remove
 317           if (gx < nx0 || gy < ny0 || gx >= nx1 || gy >= ny1) {
 318             removeFromCell(cid, gx, gy);
 319           }
 320         } else {
 321           // old rec: outside
 322           // if inside new, insert
 323           if (gx >= nx0 && gy >= ny0 && gx < nx1 && gy < ny1) {
 324             insertIntoCell(cid, gx, gy);
 325           }
 326         }
 327       }
 328     }
 329     //removeInternal(cid);
 330     cobj.gx0 = nx0; cobj.gy0 = ny0;
 331     cobj.gx1 = nx1; cobj.gy1 = ny1;
 332     //insertInternal(cid);
 333     return true;
 334   }
 335   return false;
 336 }
 337
 338
 339 // `false`: out of grid/too thin/etc
 340 // returned coords are always valid
 341 // also, `gx1` and `gy1` are exclusive
 342 final bool calcObjGridPos (MapEntity e, out int gx0, out int gy0, out int gx1, out int gy1) {
 343   if (!e) { gx0 = 0; gy0 = 0; gx1 = 0; gy1 = 0; return false; } // no object
 344   int ew = max(1, e.width), eh = max(1, e.height);
 345   //if (ew < 1 || eh < 1) { gx0 = 0; gy0 = 0; gx1 = 0; gy1 = 0; return false; }
 346   int ex0 = e.x0-mXOfs, ey0 = e.y0-mYOfs;
 347   int ex1 = ex0+ew-1, ey1 = ey0+eh-1;
 348   // check if it fits in grid at all
 349   if (ex1 < 0 || ey1 < 0) { gx0 = 0; gy0 = 0; gx1 = 0; gy1 = 0; return false; } // out of grid
 350   int tgw = mWidth, tgh = mHeight;
 351   if (ex0 >= tgw*CellSize || ey0 >= tgh*CellSize) { gx0 = 0; gy0 = 0; gx1 = 0; gy1 = 0; return false; } // out of grid
 352   // calc grid coords
 353   ex0 /= CellSize;
 354   ey0 /= CellSize;
 355   ex1 /= CellSize;
 356   ey1 /= CellSize;
 357   gx0 = clamp(ex0, 0, tgw-1);
 358   gy0 = clamp(ey0, 0, tgh-1);
 359   gx1 = clamp(ex1+1, 0, tgw);
 360   gy1 = clamp(ey1+1, 0, tgh);
 361   return (gx1 > gx0 && gy1 > gy0);
 362 }
 363
 364
 365 // ////////////////////////////////////////////////////////////////////////// //
 366 // returns 0 if item is not put in grid, or cid
 367 final int insert (MapEntity e) {
 368   if (!e) return 0;
 369   if (e.gridId) {
 370     if (e.grid != self) FatalError("cannot instert entity in two grids");
 371     if (!update(e.gridId)) { e.gridId = 0; e.grid = none; }
 372     return e.gridId;
 373   }
 374   int gx0, gy0, gx1, gy1;
 375   bool doInsert = calcObjGridPos(e, out gx0, out gy0, out gx1, out gy1);
 376   // allocate cobj
 377   int cid = allocCObj();
 378   auto cobj = &cobjs[cid];
 379   e.gridId = cid;
 380   e.grid = self;
 381   cobj.e = e;
 382   cobj.tag = 0;
 383   cobj.gx0 = gx0; cobj.gy0 = gy0;
 384   cobj.gx1 = gx1; cobj.gy1 = gy1;
 385   if (doInsert) insertInternal(cid);
 386   return cid;
 387 }
 388
 389
 390 // returns `true` if item was in the grid, and now removed
 391 final bool remove (int cid) {
 392   if (cid < 1 || cid >= cobjs.length) return false;
 393   if (cobjs[cid].prev == -1) return false;
 394   removeInternal(cid);
 395   freeCObj(cid);
 396   return true;
 397 }
 398
 399
 400 // call this when object changed its position
 401 // it is harmless to call it even if position wasn't changed
 402 // returns `false` if item should be removed from grid
 403 // optionally sets `wasMoved` flag
 404 final bool update (int cid, optional out bool wasMoved/*, optional bool markAsDead*/) {
 405   if (specified_wasMoved) wasMoved = false;
 406   if (cid < 1 || cid >= cobjs.length) return false;
 407   auto cobj = &cobjs[cid];
 408   if (cobj.prev == -1) return false;
 409   MapEntity e = cobj.e;
 410   if (!e) return false;
 411   int gx0, gy0, gx1, gy1;
 412   if (!calcObjGridPos(e, out gx0, out gy0, out gx1, out gy1)) {
 413     //if (markAsDead && !e.isZeroDimsValid && (e.width < 1 || e.height < 1)) e.instanceRemove();
 414     removeInternal(cid);
 415     cobj.gx0 = 0; cobj.gy0 = 0;
 416     cobj.gx1 = 0; cobj.gy1 = 0;
 417     return false;
 418   }
 419   wasMoved = moveInternal(cid, gx0, gy0, gx1, gy1);
 420   return true;
 421 }
 422
 423
 424 // ////////////////////////////////////////////////////////////////////////// //
 425 // ok, it is not a real spawner, i just wanted to fake its return type
 426 final spawner MapEntity getObject (class!MapEntity cc, int cid) {
 427   if (cid < 1 || cid >= cobjs.length) return none;
 428   auto cobj = &cobjs[cid];
 429   if (cobj.prev == -1) return none;
 430   return cc(cobj.e);
 431 }
 432
 433 final bool getOwned (int cid) {
 434   if (cid < 1 || cid >= cobjs.length) return false;
 435   auto cobj = &cobjs[cid];
 436   return cobj.objectIsOwned;
 437 }
 438
 439 final void setOwned (int cid, bool v) {
 440   if (cid < 1 || cid >= cobjs.length) return;
 441   auto cobj = &cobjs[cid];
 442   if (cobj.prev != -1) cobj.objectIsOwned = v;
 443 }
 444
 445
 446 // ////////////////////////////////////////////////////////////////////////// //
 447 // ok, it is not a real spawner, i just wanted to fake its return type
 448 final spawner MapEntity getObjectByItem (class!MapEntity cc, int id) {
 449   if (id < 1 || id >= items.length) return none;
 450   MapEntity e = cobjs[items[id].cid].e;
 451   if (!e || !e.isInstanceAlive) return none;
 452   return cc(e);
 453 }
 454
 455
 456 // returns first item in cell, optionally tags it too (and skips the given tag)
 457 // returns 0 if there are no items
 458 final int getFirstItemInCell (int cx, int cy, optional int tag) {
 459   //writeln("specified_tag=", specified_tag, "; tag=", tag);
 460   if (cx < 0 || cy < 0 || cx >= mWidth || cy >= mHeight) return 0;
 461   int oid = grid[cx, cy];
 462   while (oid) {
 463     // check tag
 464     if (specified_tag) {
 465       CellObject *co = &cobjs[items[oid].cid];
 466       if (co.tag == tag) {
 467         //writeln("***TAG SKIP (0)");
 468         oid = items[oid].next;
 469         continue;
 470       }
 471       co.tag = tag; // mark it
 472     }
 473     return oid;
 474   }
 475   return 0;
 476 }
 477
 478
 479 // returns first item in cell, optionally tags it too (and skips the given tag)
 480 // returns 0 if there are no items
 481 final int getFirstItem (int x, int y, optional int tag) {
 482   return getFirstItemInCell((x-mXOfs)/CellSize, (y-mYOfs)/CellSize, tag!optional);
 483 }
 484
 485
 486 // returns next item in list, optionally tags it too (and skips the given tag)
 487 // returns 0 if there are no more items
 488 final int getNextItem (int oid, optional int tag) {
 489   oid = items[oid].next; // 0 contains sentinel anyway
 490   while (oid) {
 491     // check tag
 492     if (specified_tag) {
 493       CellObject *co = &cobjs[items[oid].cid];
 494       if (co.tag == tag) {
 495         //writeln("***TAG SKIP (1)");
 496         oid = items[oid].next;
 497         continue;
 498       }
 499       co.tag = tag; // mark it
 500     }
 501     return oid;
 502   }
 503   return 0;
 504 }
 505
 506
 507 // ////////////////////////////////////////////////////////////////////////// //
 508 // low-level iterator builder
 509 // `GridIteratorData` contents doesn't matter
 510 private final void collectObjectsInRect (out GridIteratorData idata, int ax, int ay, int aw, int ah, bool precise, class!MapEntity castClass,
 511                                          scope bool delegate (MapEntity e, int x0, int y0, int width, int height) cdg)
 512 {
 513   int cused = collUsed;
 514   idata.collIdx = cused;
 515   idata.collStart = cused;
 516   idata.collEnd = cused;
 517   if (aw < 1 || ah < 1) return;
 518   int grX = ax-mXOfs, grY = ay-mYOfs;
 519   if (grX+aw <= 0 || grY+ah <= 0 || grX >= mWidth*CellSize || grY >= mHeight*CellSize) return;
 520   int cx0 = max(0, grX/CellSize);
 521   int cy0 = max(0, grY/CellSize);
 522   int cx1 = min(mWidth, (grX+aw-1)/CellSize+1);
 523   int cy1 = min(mHeight, (grY+ah-1)/CellSize+1);
 524   auto tag = nextTag(); // the tag will be used to reject duplicate objects
 525   //writeln("(", ax, ",", ay, ")-(", ax+aw-1, ",", ay+ah-1, "): (", cx0, ",", cy0, ")-(", cx1, ",", cy1, ")");
 526   foreach (int cy; cy0..cy1) {
 527     foreach (int cx; cx0..cx1) {
 528       int oid = getFirstItemInCell(cx, cy, tag);
 529       while (oid) {
 530         MapEntity e = getObjectByItem(castClass, oid); // `e` is guaranteed to be valid or `none`
 531         if (e isa castClass) {
 532           if (!precise || cdg(e, ax, ay, aw, ah)) collected[cused++] = e;
 533         }
 534         oid = getNextItem(oid, tag);
 535       }
 536     }
 537   }
 538   idata.castClass = castClass;
 539   idata.collEnd = cused;
 540   collUsed = cused;
 541 }
 542
 543
 544 // ////////////////////////////////////////////////////////////////////////// //
 545 // high-level iterators
 546 // you can add/remove objects while iterating, it is harmless
 547 // newly added objects may, or may not participate in current frame processing
 548 // removed objects will be returned unless they are marked dead with `obj.instanceRemove()`
 549
 550 struct GridIteratorData {
 551   // positions in `collected`
 552   int collIdx; // current index
 553   int collStart; // first item for this iterator
 554   int collEnd; // last (exclusive) item for this iterator
 555   class!MapEntity castClass;
 556 }
 557
 558
 559 // ////////////////////////////////////////////////////////////////////////// //
 560 // pixel checker
 561 final private bool pixelCheckerDG (MapEntity e, int x0, int y0, int width, int height) {
 562   return e.isPointCollision(x0, y0);
 563 }
 564
 565
 566 // collect objects at a given pixel
 567 // if `precise` is `false`, collect objects with cell granularity
 568 final bool inCellPix_opIterInit (ref GridIteratorData it, int x, int y,
 569                                  optional bool precise, optional class!MapEntity castClass)
 570 {
 571   if (!specified_precise) precise = true;
 572   if (!castClass) castClass = MapEntity;
 573   collectObjectsInRect(it, x, y, 1, 1, precise, castClass, &pixelCheckerDG);
 574   //writeln("*** ICP_INIT: start=", it.collStart, "; end=", it.collEnd, "; collUsed=", collUsed, "; valid=", (it.collEnd > it.collStart));
 575   return (it.collEnd > it.collStart);
 576 }
 577
 578
 579 final bool inCellPix_opIterNext (ref GridIteratorData it, out MapEntity ge) {
 580   while (it.collIdx < it.collEnd) {
 581     MapEntity e = collected[it.collIdx++];
 582     // this object may be marked as dead or `delete`d, so check for this
 583     if (e && e.isInstanceAlive) {
 584       ge = e;
 585       return true;
 586     }
 587   }
 588   return false; // this iterator is no more
 589 }
 590
 591
 592 final void inCellPix_opIterDone (ref GridIteratorData it) {
 593   //writeln("*** ICP_DONE: start=", it.collStart, "; end=", it.collEnd, "; collUsed=", collUsed, "; new collUsed=", it.collStart);
 594   if (it.collEnd > it.collStart) {
 595     if (collUsed != it.collEnd) FatalError("EntityGrid::inCellPix: unbalanced iterators");
 596     collUsed = it.collStart;
 597   }
 598 }
 599
 600
 601 // ////////////////////////////////////////////////////////////////////////// //
 602 // rect checker
 603 final private bool rectCheckerDG (MapEntity e, int x0, int y0, int width, int height) {
 604   return e.isRectCollision(x0, y0, width, height);
 605 }
 606
 607
 608 // collect objects at a given pixel
 609 // if `precise` is `false`, collect objects with cell granularity
 610 final bool inRectPix_opIterInit (ref GridIteratorData it, int x, int y, int width, int height,
 611                                  optional bool precise, optional class!MapEntity castClass)
 612 {
 613   if (!specified_precise) precise = true;
 614   if (!castClass) castClass = MapEntity;
 615   collectObjectsInRect(it, x, y, width, height, precise, castClass, &rectCheckerDG);
 616   //writeln("*** IRP_INIT: start=", it.collStart, "; end=", it.collEnd, "; collUsed=", collUsed, "; valid=", (it.collEnd > it.collStart));
 617   return (it.collEnd > it.collStart);
 618 }
 619
 620
 621 final bool inRectPix_opIterNext (ref GridIteratorData it, out MapEntity ge) {
 622   while (it.collIdx < it.collEnd) {
 623     MapEntity e = collected[it.collIdx++];
 624     // this object may be marked as dead or `delete`d, so check for this
 625     if (e && e.isInstanceAlive) {
 626       ge = e;
 627       return true;
 628     }
 629   }
 630   return false; // this iterator is no more
 631 }
 632
 633
 634 final void inRectPix_opIterDone (ref GridIteratorData it) {
 635   //writeln("*** IRP_DONE: start=", it.collStart, "; end=", it.collEnd, "; collUsed=", collUsed, "; new collUsed=", it.collStart);
 636   if (it.collEnd > it.collStart) {
 637     if (collUsed != it.collEnd) FatalError("EntityGrid::inRectPix: unbalanced iterators");
 638     collUsed = it.collStart;
 639   }
 640 }
 641
 642
 643 // ////////////////////////////////////////////////////////////////////////// //
 644 // 0: no objects
 645 final int getFirstObjectCID () { return firstInsertedCObj; }
 646
 647 // 0: no more objects
 648 final int getNextObjectCID (int cid) {
 649   if (cid < 1 || cid >= cobjs.length || cobjs[cid].prev == -1) return 0;
 650   int n = cobjs[cid].next;
 651   /*
 652   if (removeThis) {
 653     removeInternal(cid);
 654     freeCObj(cid);
 655   }
 656   */
 657   return n;
 658 }
 659
 660
 661 // 0: no objects
 662 final int getLastObjectCID () { return lastInsertedCObj; }
 663
 664 // 0: no more objects
 665 final int getPrevObjectCID (int cid) {
 666   if (cid < 1 || cid >= cobjs.length || cobjs[cid].prev == -1) return 0;
 667   int n = cobjs[cid].prev;
 668   /*
 669   if (removeThis) {
 670     removeInternal(cid);
 671     freeCObj(cid);
 672   }
 673   */
 674   return n;
 675 }
 676
 677
 678 // ////////////////////////////////////////////////////////////////////////// //
 679 // creates "safe" iterator: you can insert/remove items while iterating
 680
 681 transient private AllObjSafeIterData *lastSafeIter;
 682
 683 struct AllObjSafeIterData {
 684   AllObjSafeIterData *next;
 685   int cid;
 686   class!MapEntity castClass;
 687 }
 688
 689 final bool allObjectsSafe_opIterInit (ref AllObjSafeIterData idata, optional class!MapEntity castClass) {
 690   if (!castClass) castClass = MapEntity;
 691   int cid = firstInsertedCObj;
 692   while (cid) {
 693     MapEntity e = cobjs[cid].e;
 694     if (e isa castClass && e.isInstanceAlive) {
 695       idata.next = lastSafeIter;
 696       lastSafeIter = &idata;
 697       idata.cid = cid;
 698       idata.castClass = castClass;
 699       return true;
 700     }
 701     cid = cobjs[cid].next;
 702   }
 703   idata.next = nullptr;
 704   idata.cid = -666; // "unused" flag
 705   return false;
 706 }
 707
 708 final bool allObjectsSafe_opIterNext (ref AllObjSafeIterData idata, out MapEntity ge) {
 709   int cid = idata.cid;
 710   auto cc = idata.castClass;
 711   while (cid > 0) {
 712     MapEntity e = cobjs[cid].e;
 713     cid = cobjs[cid].next;
 714     if (e isa cc && e.isInstanceAlive) {
 715       idata.cid = cid;
 716       ge = e;
 717       return true;
 718     }
 719   }
 720   idata.cid = 0; // mark "complete" (just in case)
 721   return false;
 722 }
 723
 724 final void allObjectsSafe_opIterDone (ref AllObjSafeIterData idata) {
 725   if (idata.cid != -666) {
 726     // remove iterator from list
 727     if (lastSafeIter != &idata) FatalError("EntityGrid::allObjectsSafe: unbalanced iterators");
 728     lastSafeIter = idata.next;
 729     idata.next = nullptr;
 730     idata.cid = -666;
 731   }
 732 }
 733
 734
 735 // ////////////////////////////////////////////////////////////////////////// //
 736 struct AllObjIterData {
 737   int cid;
 738   class!MapEntity castClass;
 739 }
 740
 741 final bool allObjects_opIterInit (ref AllObjIterData idata, optional class!MapEntity castClass) {
 742   if (!castClass) castClass = MapEntity;
 743   int cid = firstInsertedCObj;
 744   while (cid) {
 745     MapEntity e = cobjs[cid].e;
 746     if (e isa castClass && e.isInstanceAlive) {
 747       idata.cid = cid;
 748       idata.castClass = castClass;
 749       return true;
 750     }
 751     cid = cobjs[cid].next;
 752   }
 753   idata.cid = -666;
 754   return false;
 755 }
 756
 757 final bool allObjects_opIterNext (ref AllObjIterData idata, out MapEntity ge) {
 758   int cid = idata.cid;
 759   auto cc = idata.castClass;
 760   while (cid > 0) {
 761     MapEntity e = cobjs[cid].e;
 762     cid = cobjs[cid].next;
 763     if (e isa cc && e.isInstanceAlive) {
 764       idata.cid = cid;
 765       ge = e;
 766       return true;
 767     }
 768   }
 769   idata.cid = 0; // mark "complete" (just in case)
 770   return false;
 771 }
 772
 773
 774 // ////////////////////////////////////////////////////////////////////////// //
 775 /+
 776 final bool allObjectsBackwards_opIterInit (ref int cid) {
 777   cid = lastInsertedCObj;
 778   while (cid && !cobjs[cid].e) cid = cobjs[cid].prev;
 779   return (cid != 0);
 780 }
 781
 782 final bool allObjectsBackwards_opIterNext (ref int cid, out MapEntity ge) {
 783   while (cid) {
 784     MapEntity e = cobjs[cid].e;
 785     cid = cobjs[cid].prev;
 786     if (e && e.isInstanceAlive) { ge = e; return true; }
 787   }
 788   return false;
 789 }
 790 +/
 791
 792
 793 // ////////////////////////////////////////////////////////////////////////// //
 794 // some debug shit
 795 final int countObjects () {
 796   int objCount = 0;
 797   for (int f = firstInsertedCObj; f; f = cobjs[f].next) ++objCount;
 798   return objCount;
 799 }
 800
 801
 802 final void dumpStats () {
 803   // calculate max object in cell, number of free cells, and number of used items
 804   int freeCells = 0, maxInCell = 0, itemCount = 0;
 805   foreach (int oid; grid) {
 806     if (!oid) {
 807       ++freeCells;
 808     } else {
 809       int xc = 0;
 810       while (oid) {
 811         ++xc;
 812         oid = items[oid].next;
 813       }
 814       itemCount += xc;
 815       maxInCell = max(maxInCell, xc);
 816     }
 817   }
 818   int objCount = countObjects();
 819   writeln("=========== GRID STATS ===========");
 820   writeln("bounds: (", mXOfs, ",", mYOfs, ")-(", mXOfs+mWidth*CellSize-1, ",", mYOfs+mHeight*CellSize-1, ")");
 821   writeln("cells: ", grid.length, " (", grid.length1, "x", grid.length2, ")");
 822   writeln("objects: ", objCount, " (out of ", cobjs.length, " slots)");
 823   writeln("used items: ", itemCount, " out of ", items.length);
 824   writeln("max items in cell: ", maxInCell);
 825   writeln("used cells: ", grid.length-freeCells, " out of ", grid.length);
 826   writeln("----------------------------------");
 827 }
 828
 829
 830 // ////////////////////////////////////////////////////////////////////////// //
 831 /+
 832 struct LineWalker {
 833   int wx0, wy0, wx1, wy1; // window coordinates
 834   int stx, sty; // "steps" for x and y axes
 835   int stleft; // "steps left"
 836   int err, errinc, errmax;
 837   int xd, yd; // current coord
 838   int horiz; // bool
 839
 840   alias x = xd;
 841   alias y = yd;
 842 }
 843
 844
 845 // call `lwSetup()` after this
 846 static final void lwCreate (ref LineWalker lw, int minx, int miny, int maxx, int maxy) {
 847   // clip rectange
 848   lw.wx0 = minx;
 849   lw.wy0 = miny;
 850   lw.wx1 = maxx;
 851   lw.wy1 = maxy;
 852 }
 853
 854
 855 static final void lwSetClip (ref LineWalker lw, int minx, int miny, int maxx, int maxy) {
 856   // clip rectange
 857   lw.wx0 = minx;
 858   lw.wy0 = miny;
 859   lw.wx1 = maxx;
 860   lw.wy1 = maxy;
 861 }
 862
 863
 864 // this will use `w[xy][01]` to clip coords
 865 // return `false` if the whole line was clipped away
 866 // on `true`, you should process first point, and go on
 867 static final bool lwSetup (ref LineWalker lw, int x0, int y0, int x1, int y1) {
 868   if (lw.wx1 < lw.wx0 || lw.wy1 < lw.wy0) { lw.stleft = 0; lw.xd = x0; lw.yd = y0; return false; }
 869
 870   bool res;
 871   if (x0 >= lw.wx0 && y0 >= lw.wy0 && x0 <= lw.wx1 && y0 <= lw.wy1 &&
 872       x1 >= lw.wx0 && y1 >= lw.wy0 && x1 <= lw.wx1 && y1 <= lw.wy1)
 873   {
 874     res = true;
 875   } else {
 876     float sx0 = x0, sy0 = y0;
 877     float sx1 = x1, sy1 = y1;
 878     res = Geom.clipLine(sx0, sy0, sx1, sy1, lw.wx0, lw.wy0, lw.wx1, lw.wy1);
 879     if (!res) { lw.stleft = 0; lw.xd = x0; lw.yd = y0; return false; }
 880     x0 = trunc(sx0); y0 = trunc(sy0);
 881     x1 = trunc(sx1); y1 = trunc(sy1);
 882   }
 883
 884   // check for ortho lines
 885   if (y0 == y1) {
 886     // horizontal
 887     lw.horiz = true;
 888     lw.stleft = abs(x1-x0)+1;
 889     lw.stx = (x0 < x1 ? 1 : -1);
 890     lw.sty = 0;
 891     lw.errinc = 0;
 892     lw.errmax = 10; // anything that is greater than zero
 893   } else if (x0 == x1) {
 894     // vertical
 895     lw.horiz = false;
 896     lw.stleft = abs(y1-y0)+1;
 897     lw.stx = 0;
 898     lw.sty = (y0 < y1 ? 1 : -1);
 899     lw.errinc = 0;
 900     lw.errmax = 10; // anything that is greater than zero
 901   } else {
 902     // diagonal
 903     if (abs(x1-x0) >= abs(y1-y0)) {
 904       // horizontal
 905       lw.horiz = true;
 906       lw.stleft = abs(x1-x0)+1;
 907       lw.errinc = abs(y1-y0)+1;
 908     } else {
 909       // vertical
 910       lw.horiz = false;
 911       lw.stleft = abs(y1-y0)+1;
 912       lw.errinc = abs(x1-x0)+1;
 913     }
 914     lw.stx = (x0 < x1 ? 1 : -1);
 915     lw.sty = (y0 < y1 ? 1 : -1);
 916     lw.errmax = lw.stleft;
 917   }
 918   lw.xd = x0;
 919   lw.yd = y0;
 920   lw.err = -lw.errmax;
 921   return res;
 922 }
 923
 924
 925 // call this *after* doing a step
 926 // WARNING! if you will do a step when this returns `true`, you will fall into limbo
 927 static final bool lwIsDone (ref LineWalker lw) {
 928   return (lw.stleft <= 0);
 929 }
 930
 931
 932 // as you will prolly call `done()` after doing a step anyway, this will do it for you
 933 // move to next point, return `true` when the line is complete (i.e. you should stop)
 934 static final bool step (ref LineWalker lw) {
 935   if (lw.horiz) {
 936     lw.xd += lw.stx;
 937     lw.err += lw.errinc;
 938     if (lw.err >= 0) { lw.err -= lw.errmax; lw.yd += lw.sty; }
 939   } else {
 940     lw.yd += lw.sty;
 941     lw.err += lw.errinc;
 942     if (lw.err >= 0) { lw.err -= lw.errmax; lw.xd += lw.stx; }
 943   }
 944   --lw.stleft;
 945   return (lw.stleft <= 0);
 946 }
 947
 948
 949 // move to next tile; return `true` if the line is complete (and walker state is undefined then)
 950 static final bool stepToNextTile (ref LineWalker lw) {
 951   if (lw.stleft < 2) return true; // max one pixel left, nothing to do
 952
 953   int ex, ey;
 954
 955   // strictly horizontal?
 956   if (lw.sty == 0) {
 957     // only xd
 958     if (lw.stx < 0) {
 959       // xd: to left edge
 960       ex = (lw.xd&(~(CellSize-1)))-1;
 961       lw.stleft -= lw.xd-ex;
 962     } else {
 963       // xd: to right edge
 964       ex = (lw.xd|(CellSize-1))+1;
 965       lw.stleft -= ex-lw.xd;
 966     }
 967     lw.xd = ex;
 968     return (lw.stleft <= 0);
 969   }
 970
 971   // strictly vertical?
 972   if (lw.stx == 0) {
 973     // only xd
 974     if (lw.sty < 0) {
 975       // yd: to top edge
 976       ey = (lw.yd&(~(CellSize-1)))-1;
 977       lw.stleft -= lw.yd-ey;
 978     } else {
 979       // yd: to bottom edge
 980       ey = (lw.yd|(CellSize-1))+1;
 981       lw.stleft -= ey-lw.yd;
 982     }
 983     lw.yd = ey;
 984     return (lw.stleft <= 0);
 985   }
 986
 987   // diagonal
 988   int xwalk, ywalk;
 989
 990   // calculate xwalk
 991   if (lw.stx < 0) {
 992     ex = (lw.xd&(~(CellSize-1)))-1;
 993     xwalk = lw.xd-ex;
 994   } else {
 995     ex = (lw.xd|(CellSize-1))+1;
 996     xwalk = ex-lw.xd;
 997   }
 998
 999   // calculate ywalk
1000   if (lw.sty < 0) {
1001     ey = (lw.yd&(~(CellSize-1)))-1;
1002     ywalk = lw.yd-ey;
1003   } else {
1004     ey = (lw.yd|(CellSize-1))+1;
1005     ywalk = ey-lw.yd;
1006   }
1007
1008   int wklen = (xwalk <= ywalk ? xwalk : ywalk);
1009   while (true) {
1010     // in which dir we want to walk?
1011     lw.stleft -= wklen;
1012     if (lw.stleft <= 0) return true;
1013     if (lw.horiz) {
1014       lw.xd += wklen*lw.stx;
1015       for (int f = wklen; f > 0; --f) {
1016         lw.err += lw.errinc;
1017         if (lw.err >= 0) { lw.err -= lw.errmax; lw.yd += lw.sty; }
1018       }
1019     } else {
1020       lw.yd += wklen*lw.sty;
1021       for (int f = wklen; f > 0; --f) {
1022         lw.err += lw.errinc;
1023         if (lw.err >= 0) { lw.err -= lw.errmax; lw.xd += lw.stx; }
1024       }
1025     }
1026     // check for walk completion
1027     if (lw.xd == ex || lw.yd == ey) break;
1028     wklen = 1;
1029   }
1030
1031   return false;
1032 }
1033 +/
1034
1035
1036 // ////////////////////////////////////////////////////////////////////////// //
1037 // unfinished line walker from GameLevel
1038 //FIXME: optimize this with clipping first
1039 //TODO: moveable tiles
1040 /+
1041 final MapTile checkTilesAtLine (int ax0, int ay0, int ax1, int ay1, optional scope bool delegate (MapTile dg) dg) {
1042   // do it faster if we can
1043
1044   // strict vertical check?
1045   if (ax0 == ax1 && ay0 <= ay1) return checkTilesInRect(ax0, ay0, 1, ay1-ay0+1, dg!optional);
1046   // strict horizontal check?
1047   if (ay0 == ay1 && ax0 <= ax1) return checkTilesInRect(ax0, ay0, ax1-ax0+1, 1, dg!optional);
1048
1049   float x0 = float(ax0)/16.0, y0 = float(ay0)/16.0, x1 = float(ax1)/16.0, y1 = float(ay1)/16.0;
1050
1051   // fix delegate
1052   if (!dg) dg = &cbCollisionAnySolid;
1053
1054   // get starting and enging tile
1055   int tileSX = trunc(x0), tileSY = trunc(y0);
1056   int tileEX = trunc(x1), tileEY = trunc(y1);
1057
1058   // first hit is always landed
1059   if (tileSX >= 0 && tileSY >= 0 && tileSX < TilesWidth && tileSY < TilesHeight) {
1060     MapTile t = tiles[tileSX, tileSY];
1061     if (t && t.visible && Geom.lineAABBIntersects(ax0, ay0, ax1, ay1, tileSX*16, tileSY*16, 16, 16) && dg(t)) return t;
1062   }
1063
1064   // if starting and ending tile is the same, we don't need to do anything more
1065   if (tileSX == tileEX && tileSY == tileEY) return none;
1066
1067   // calculate ray direction
1068   TVec dv = (vector(x1, y1)-vector(x0, y0)).normalise2d;
1069
1070   // length of ray from one x or y-side to next x or y-side
1071   float deltaDistX = (fabs(dv.x) > 0.0001 ? fabs(1.0/dv.x) : 0.0);
1072   float deltaDistY = (fabs(dv.y) > 0.0001 ? fabs(1.0/dv.y) : 0.0);
1073
1074   // calculate step and initial sideDists
1075
1076   float sideDistX; // length of ray from current position to next x-side
1077   int stepX; // what direction to step in x (either +1 or -1)
1078   if (dv.x < 0) {
1079     stepX = -1;
1080     sideDistX = (x0-tileSX)*deltaDistX;
1081   } else {
1082     stepX = 1;
1083     sideDistX = (tileSX+1.0-x0)*deltaDistX;
1084   }
1085
1086   float sideDistY; // length of ray from current position to next y-side
1087   int stepY; // what direction to step in y (either +1 or -1)
1088   if (dv.y < 0) {
1089     stepY = -1;
1090     sideDistY = (y0-tileSY)*deltaDistY;
1091   } else {
1092     stepY = 1;
1093     sideDistY = (tileSY+1.0-y0)*deltaDistY;
1094   }
1095
1096   // perform DDA
1097   //int side; // was a NS or a EW wall hit?
1098   for (;;) {
1099     // jump to next map square, either in x-direction, or in y-direction
1100     if (sideDistX < sideDistY) {
1101       sideDistX += deltaDistX;
1102       tileSX += stepX;
1103       //side = 0;
1104     } else {
1105       sideDistY += deltaDistY;
1106       tileSY += stepY;
1107       //side = 1;
1108     }
1109     // check tile
1110     if (tileSX >= 0 && tileSY >= 0 && tileSX < TilesWidth && tileSY < TilesHeight) {
1111       MapTile t = tiles[tileSX, tileSY];
1112       if (t && t.visible && Geom.lineAABBIntersects(ax0, ay0, ax1, ay1, tileSX*16, tileSY*16, 16, 16) && dg(t)) return t;
1113     }
1114     // did we arrived at the destination?
1115     if (tileSX == tileEX && tileSY == tileEY) break;
1116   }
1117
1118   return none;
1119 }
1120 +/