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 // hack for make some iterations (especially frame thinker) slightly faster
 776 final void collectAllActiveObjects (ref array!MapEntity aoarr) {
 777   int cid = firstInsertedCObj;
 778   while (cid) {
 779     MapEntity e = cobjs[cid].e;
 780     if (e && e.active && e.isInstanceAlive) aoarr[$] = e;
 781     cid = cobjs[cid].next;
 782   }
 783 }
 784
 785
 786 // ////////////////////////////////////////////////////////////////////////// //
 787 /+
 788 final bool allObjectsBackwards_opIterInit (ref int cid) {
 789   cid = lastInsertedCObj;
 790   while (cid && !cobjs[cid].e) cid = cobjs[cid].prev;
 791   return (cid != 0);
 792 }
 793
 794 final bool allObjectsBackwards_opIterNext (ref int cid, out MapEntity ge) {
 795   while (cid) {
 796     MapEntity e = cobjs[cid].e;
 797     cid = cobjs[cid].prev;
 798     if (e && e.isInstanceAlive) { ge = e; return true; }
 799   }
 800   return false;
 801 }
 802 +/
 803
 804
 805 // ////////////////////////////////////////////////////////////////////////// //
 806 // some debug shit
 807 final int countObjects () {
 808   int objCount = 0;
 809   for (int f = firstInsertedCObj; f; f = cobjs[f].next) ++objCount;
 810   return objCount;
 811 }
 812
 813
 814 final void dumpStats () {
 815   // calculate max object in cell, number of free cells, and number of used items
 816   int freeCells = 0, maxInCell = 0, itemCount = 0;
 817   foreach (int oid; grid) {
 818     if (!oid) {
 819       ++freeCells;
 820     } else {
 821       int xc = 0;
 822       while (oid) {
 823         ++xc;
 824         oid = items[oid].next;
 825       }
 826       itemCount += xc;
 827       maxInCell = max(maxInCell, xc);
 828     }
 829   }
 830   int objCount = countObjects();
 831   writeln("=========== GRID STATS ===========");
 832   writeln("bounds: (", mXOfs, ",", mYOfs, ")-(", mXOfs+mWidth*CellSize-1, ",", mYOfs+mHeight*CellSize-1, ")");
 833   writeln("cells: ", grid.length, " (", grid.length1, "x", grid.length2, ")");
 834   writeln("objects: ", objCount, " (out of ", cobjs.length, " slots)");
 835   writeln("used items: ", itemCount, " out of ", items.length);
 836   writeln("max items in cell: ", maxInCell);
 837   writeln("used cells: ", grid.length-freeCells, " out of ", grid.length);
 838   writeln("----------------------------------");
 839 }
 840
 841
 842 // ////////////////////////////////////////////////////////////////////////// //
 843 /+
 844 struct LineWalker {
 845   int wx0, wy0, wx1, wy1; // window coordinates
 846   int stx, sty; // "steps" for x and y axes
 847   int stleft; // "steps left"
 848   int err, errinc, errmax;
 849   int xd, yd; // current coord
 850   int horiz; // bool
 851
 852   alias x = xd;
 853   alias y = yd;
 854 }
 855
 856
 857 // call `lwSetup()` after this
 858 static final void lwCreate (ref LineWalker lw, int minx, int miny, int maxx, int maxy) {
 859   // clip rectange
 860   lw.wx0 = minx;
 861   lw.wy0 = miny;
 862   lw.wx1 = maxx;
 863   lw.wy1 = maxy;
 864 }
 865
 866
 867 static final void lwSetClip (ref LineWalker lw, int minx, int miny, int maxx, int maxy) {
 868   // clip rectange
 869   lw.wx0 = minx;
 870   lw.wy0 = miny;
 871   lw.wx1 = maxx;
 872   lw.wy1 = maxy;
 873 }
 874
 875
 876 // this will use `w[xy][01]` to clip coords
 877 // return `false` if the whole line was clipped away
 878 // on `true`, you should process first point, and go on
 879 static final bool lwSetup (ref LineWalker lw, int x0, int y0, int x1, int y1) {
 880   if (lw.wx1 < lw.wx0 || lw.wy1 < lw.wy0) { lw.stleft = 0; lw.xd = x0; lw.yd = y0; return false; }
 881
 882   bool res;
 883   if (x0 >= lw.wx0 && y0 >= lw.wy0 && x0 <= lw.wx1 && y0 <= lw.wy1 &&
 884       x1 >= lw.wx0 && y1 >= lw.wy0 && x1 <= lw.wx1 && y1 <= lw.wy1)
 885   {
 886     res = true;
 887   } else {
 888     float sx0 = x0, sy0 = y0;
 889     float sx1 = x1, sy1 = y1;
 890     res = Geom.clipLine(sx0, sy0, sx1, sy1, lw.wx0, lw.wy0, lw.wx1, lw.wy1);
 891     if (!res) { lw.stleft = 0; lw.xd = x0; lw.yd = y0; return false; }
 892     x0 = trunc(sx0); y0 = trunc(sy0);
 893     x1 = trunc(sx1); y1 = trunc(sy1);
 894   }
 895
 896   // check for ortho lines
 897   if (y0 == y1) {
 898     // horizontal
 899     lw.horiz = true;
 900     lw.stleft = abs(x1-x0)+1;
 901     lw.stx = (x0 < x1 ? 1 : -1);
 902     lw.sty = 0;
 903     lw.errinc = 0;
 904     lw.errmax = 10; // anything that is greater than zero
 905   } else if (x0 == x1) {
 906     // vertical
 907     lw.horiz = false;
 908     lw.stleft = abs(y1-y0)+1;
 909     lw.stx = 0;
 910     lw.sty = (y0 < y1 ? 1 : -1);
 911     lw.errinc = 0;
 912     lw.errmax = 10; // anything that is greater than zero
 913   } else {
 914     // diagonal
 915     if (abs(x1-x0) >= abs(y1-y0)) {
 916       // horizontal
 917       lw.horiz = true;
 918       lw.stleft = abs(x1-x0)+1;
 919       lw.errinc = abs(y1-y0)+1;
 920     } else {
 921       // vertical
 922       lw.horiz = false;
 923       lw.stleft = abs(y1-y0)+1;
 924       lw.errinc = abs(x1-x0)+1;
 925     }
 926     lw.stx = (x0 < x1 ? 1 : -1);
 927     lw.sty = (y0 < y1 ? 1 : -1);
 928     lw.errmax = lw.stleft;
 929   }
 930   lw.xd = x0;
 931   lw.yd = y0;
 932   lw.err = -lw.errmax;
 933   return res;
 934 }
 935
 936
 937 // call this *after* doing a step
 938 // WARNING! if you will do a step when this returns `true`, you will fall into limbo
 939 static final bool lwIsDone (ref LineWalker lw) {
 940   return (lw.stleft <= 0);
 941 }
 942
 943
 944 // as you will prolly call `done()` after doing a step anyway, this will do it for you
 945 // move to next point, return `true` when the line is complete (i.e. you should stop)
 946 static final bool step (ref LineWalker lw) {
 947   if (lw.horiz) {
 948     lw.xd += lw.stx;
 949     lw.err += lw.errinc;
 950     if (lw.err >= 0) { lw.err -= lw.errmax; lw.yd += lw.sty; }
 951   } else {
 952     lw.yd += lw.sty;
 953     lw.err += lw.errinc;
 954     if (lw.err >= 0) { lw.err -= lw.errmax; lw.xd += lw.stx; }
 955   }
 956   --lw.stleft;
 957   return (lw.stleft <= 0);
 958 }
 959
 960
 961 // move to next tile; return `true` if the line is complete (and walker state is undefined then)
 962 static final bool stepToNextTile (ref LineWalker lw) {
 963   if (lw.stleft < 2) return true; // max one pixel left, nothing to do
 964
 965   int ex, ey;
 966
 967   // strictly horizontal?
 968   if (lw.sty == 0) {
 969     // only xd
 970     if (lw.stx < 0) {
 971       // xd: to left edge
 972       ex = (lw.xd&(~(CellSize-1)))-1;
 973       lw.stleft -= lw.xd-ex;
 974     } else {
 975       // xd: to right edge
 976       ex = (lw.xd|(CellSize-1))+1;
 977       lw.stleft -= ex-lw.xd;
 978     }
 979     lw.xd = ex;
 980     return (lw.stleft <= 0);
 981   }
 982
 983   // strictly vertical?
 984   if (lw.stx == 0) {
 985     // only xd
 986     if (lw.sty < 0) {
 987       // yd: to top edge
 988       ey = (lw.yd&(~(CellSize-1)))-1;
 989       lw.stleft -= lw.yd-ey;
 990     } else {
 991       // yd: to bottom edge
 992       ey = (lw.yd|(CellSize-1))+1;
 993       lw.stleft -= ey-lw.yd;
 994     }
 995     lw.yd = ey;
 996     return (lw.stleft <= 0);
 997   }
 998
 999   // diagonal
1000   int xwalk, ywalk;
1001
1002   // calculate xwalk
1003   if (lw.stx < 0) {
1004     ex = (lw.xd&(~(CellSize-1)))-1;
1005     xwalk = lw.xd-ex;
1006   } else {
1007     ex = (lw.xd|(CellSize-1))+1;
1008     xwalk = ex-lw.xd;
1009   }
1010
1011   // calculate ywalk
1012   if (lw.sty < 0) {
1013     ey = (lw.yd&(~(CellSize-1)))-1;
1014     ywalk = lw.yd-ey;
1015   } else {
1016     ey = (lw.yd|(CellSize-1))+1;
1017     ywalk = ey-lw.yd;
1018   }
1019
1020   int wklen = (xwalk <= ywalk ? xwalk : ywalk);
1021   while (true) {
1022     // in which dir we want to walk?
1023     lw.stleft -= wklen;
1024     if (lw.stleft <= 0) return true;
1025     if (lw.horiz) {
1026       lw.xd += wklen*lw.stx;
1027       for (int f = wklen; f > 0; --f) {
1028         lw.err += lw.errinc;
1029         if (lw.err >= 0) { lw.err -= lw.errmax; lw.yd += lw.sty; }
1030       }
1031     } else {
1032       lw.yd += wklen*lw.sty;
1033       for (int f = wklen; f > 0; --f) {
1034         lw.err += lw.errinc;
1035         if (lw.err >= 0) { lw.err -= lw.errmax; lw.xd += lw.stx; }
1036       }
1037     }
1038     // check for walk completion
1039     if (lw.xd == ex || lw.yd == ey) break;
1040     wklen = 1;
1041   }
1042
1043   return false;
1044 }
1045 +/
1046
1047
1048 // ////////////////////////////////////////////////////////////////////////// //
1049 // unfinished line walker from GameLevel
1050 //FIXME: optimize this with clipping first
1051 //TODO: moveable tiles
1052 /+
1053 final MapTile checkTilesAtLine (int ax0, int ay0, int ax1, int ay1, optional scope bool delegate (MapTile dg) dg) {
1054   // do it faster if we can
1055
1056   // strict vertical check?
1057   if (ax0 == ax1 && ay0 <= ay1) return checkTilesInRect(ax0, ay0, 1, ay1-ay0+1, dg!optional);
1058   // strict horizontal check?
1059   if (ay0 == ay1 && ax0 <= ax1) return checkTilesInRect(ax0, ay0, ax1-ax0+1, 1, dg!optional);
1060
1061   float x0 = float(ax0)/16.0, y0 = float(ay0)/16.0, x1 = float(ax1)/16.0, y1 = float(ay1)/16.0;
1062
1063   // fix delegate
1064   if (!dg) dg = &cbCollisionAnySolid;
1065
1066   // get starting and enging tile
1067   int tileSX = trunc(x0), tileSY = trunc(y0);
1068   int tileEX = trunc(x1), tileEY = trunc(y1);
1069
1070   // first hit is always landed
1071   if (tileSX >= 0 && tileSY >= 0 && tileSX < TilesWidth && tileSY < TilesHeight) {
1072     MapTile t = tiles[tileSX, tileSY];
1073     if (t && t.visible && Geom.lineAABBIntersects(ax0, ay0, ax1, ay1, tileSX*16, tileSY*16, 16, 16) && dg(t)) return t;
1074   }
1075
1076   // if starting and ending tile is the same, we don't need to do anything more
1077   if (tileSX == tileEX && tileSY == tileEY) return none;
1078
1079   // calculate ray direction
1080   TVec dv = (vector(x1, y1)-vector(x0, y0)).normalise2d;
1081
1082   // length of ray from one x or y-side to next x or y-side
1083   float deltaDistX = (fabs(dv.x) > 0.0001 ? fabs(1.0/dv.x) : 0.0);
1084   float deltaDistY = (fabs(dv.y) > 0.0001 ? fabs(1.0/dv.y) : 0.0);
1085
1086   // calculate step and initial sideDists
1087
1088   float sideDistX; // length of ray from current position to next x-side
1089   int stepX; // what direction to step in x (either +1 or -1)
1090   if (dv.x < 0) {
1091     stepX = -1;
1092     sideDistX = (x0-tileSX)*deltaDistX;
1093   } else {
1094     stepX = 1;
1095     sideDistX = (tileSX+1.0-x0)*deltaDistX;
1096   }
1097
1098   float sideDistY; // length of ray from current position to next y-side
1099   int stepY; // what direction to step in y (either +1 or -1)
1100   if (dv.y < 0) {
1101     stepY = -1;
1102     sideDistY = (y0-tileSY)*deltaDistY;
1103   } else {
1104     stepY = 1;
1105     sideDistY = (tileSY+1.0-y0)*deltaDistY;
1106   }
1107
1108   // perform DDA
1109   //int side; // was a NS or a EW wall hit?
1110   for (;;) {
1111     // jump to next map square, either in x-direction, or in y-direction
1112     if (sideDistX < sideDistY) {
1113       sideDistX += deltaDistX;
1114       tileSX += stepX;
1115       //side = 0;
1116     } else {
1117       sideDistY += deltaDistY;
1118       tileSY += stepY;
1119       //side = 1;
1120     }
1121     // check tile
1122     if (tileSX >= 0 && tileSY >= 0 && tileSX < TilesWidth && tileSY < TilesHeight) {
1123       MapTile t = tiles[tileSX, tileSY];
1124       if (t && t.visible && Geom.lineAABBIntersects(ax0, ay0, ax1, ay1, tileSX*16, tileSY*16, 16, 16) && dg(t)) return t;
1125     }
1126     // did we arrived at the destination?
1127     if (tileSX == tileEX && tileSY == tileEY) break;
1128   }
1129
1130   return none;
1131 }
1132 +/