alot of depth fixes

[k8vacspelynky.git] / mapent / EntityGrid.vc

/**************************************************************************
 *    This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License
 *  as published by the Free Software Foundation; either version 3
 *  of the License, or (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 **************************************************************************/
// code by Ketmar Dark
// grid of entities
// note that entity can occupy more than one cell
class EntityGrid : Object;

//#define ENTITY_GRID_HAS_SCHEDULED_UPDATES

enum CellSize = 16;


struct CellObject {
  MapEntity e;
  int tag; // arbitrary userdata, set to 0 in new items
  // last known grid position
  int gx0, gy0, gx1, gy1;
  // previous item in alloced list
  int prev;
  // next item in free/alloced list
  int next;
#ifdef ENTITY_GRID_HAS_SCHEDULED_UPDATES
  bool updateScheduled;
#endif
  bool objectIsOwned;
}

struct Item {
  int cid; // index in `cobjs`
  // 0: end-of-list
  // otherwise either next item in cell, or next item in free list
  int next;
}


private array!CellObject cobjs;
private int freeHeadCObj;
private int firstInsertedCObj; // for `allObjects()`
private int lastInsertedCObj; // for `allObjects()`

#ifdef ENTITY_GRID_HAS_SCHEDULED_UPDATES
private array!int updateSchedule;
#endif

// item #0 is never used
private array!Item items;
private int freeHead;

//WARNING! don't change
// grid size in cells
private int mWidth, mHeight;
// offset of the (0, 0) grid cell, in pixels
private int mXOfs, mYOfs;

// grid cells, width*height in total
// contains index in `items` or 0
private array!int grid;

class!MapEntity objectType = MapEntity;

int lastUsedTag;

bool ownObjects;

// in pixels
final int gridX0 { get mXOfs; }
final int gridY0 { get mYOfs; }
final int gridX1 { get { return mXOfs+mWidth*CellSize-1; } }
final int gridY1 { get { return mYOfs+mHeight*CellSize-1; } }
final int gridWidth { get { return mWidth*CellSize; } }
final int gridHeight { get { return mHeight*CellSize; } }


// ////////////////////////////////////////////////////////////////////////// //
final void setup (int x0, int y0, int awidth, int aheight, optional class!MapEntity aotype) {
  if (specified_aotype) {
    if (!aotype) aotype = MapEntity;
    objectType = aotype;
  }
  awidth = max(1, awidth);
  aheight = max(1, aheight);
  int xcells = max(1, (awidth+CellSize-1)/CellSize);
  int ycells = max(1, (aheight+CellSize-1)/CellSize);
  // setup offsets
  mXOfs = x0;
  mYOfs = y0;
  // setup dimensions
  mWidth = xcells;
  mHeight = ycells;
  // setup items and free list
  items.length = 32;
  cobjs.length = 32;
  grid.setSize(xcells, ycells);
  removeAllObjects();
}


final void clear () {
  cobjs.length = 0;
  freeHeadCObj = 0;
  items.length = 0;
  freeHead = 0;
  mWidth = 0;
  mHeight = 0;
  mXOfs = 0;
  mYOfs = 0;
  grid.length = 0;
  lastUsedTag = 0;
}


final void removeAllObjects (optional bool doRemove) {
  lastUsedTag = 0;
  // clear grid
  foreach (ref auto oid; grid) oid = 0;
  // clear items
  items.length = 32;
  foreach (int f, ref auto item; items) item.next = f+1;
  items[0].next = 0; // as sentinel
  items[$-1].next = 0;
  freeHead = 1;
  // clear cobjects
  for (int f = firstInsertedCObj; f; f = cobjs[f].next) {
    if (doRemove || cobjs[f].objectIsOwned) delete cobjs[f].e; else cobjs[f].e = none;
  }
  cobjs.length = 32;
  foreach (int f, ref auto cobj; cobjs) {
    cobj.e = none;
    cobj.prev = -1;
    cobj.next = f+1;
    cobj.tag = 0;
    cobj.objectIsOwned = false;
  }
  cobjs[0].next = 0; // as sentinel
  cobjs[$-1].next = 0;
  freeHeadCObj = 1;
  firstInsertedCObj = 0;
  lastInsertedCObj = 0;
}


final void clearTags () {
  for (int oid = firstInsertedCObj; oid; oid = cobjs[oid].next) {
    cobjs[oid].tag = 0;
  }
}


final int nextTag () {
  if (lastUsedTag == 0x7fff_ffff) {
    lastUsedTag = 0;
    clearTags();
  }
  return ++lastUsedTag;
}


// ////////////////////////////////////////////////////////////////////////// //
private final int allocCObj () {
  int res = freeHeadCObj;
  if (res) {
    freeHeadCObj = cobjs[res].next;
  } else {
    res = cobjs.length;
    int newlen = (res > 3 ? res+res/2 : 8);
    cobjs.length = newlen;
    foreach (int f; res+1..newlen) { cobjs[f].prev = -1; cobjs[f].next = f+1; }
    cobjs[$-1].next = 0;
    freeHeadCObj = res+1;
  }
  // other fields will be set by caller
  auto cobj = &cobjs[res];
  if (lastInsertedCObj) cobjs[lastInsertedCObj].next = res; else firstInsertedCObj = res;
  cobj.tag = 0;
  cobj.prev = lastInsertedCObj;
  cobj.next = 0;
#ifdef ENTITY_GRID_HAS_SCHEDULED_UPDATES
  cobj.updateScheduled = false;
#endif
  cobj.objectIsOwned = ownObjects;
  lastInsertedCObj = res;
  return res;
}


private final void freeCObj (int idx) {
  if (idx < 1 || idx >= cobjs.length) FatalError("EntityGrid::freeCObj: invalid item index!");
  auto cobj = &cobjs[idx];
  if (cobj.prev == -1) FatalError("EntityGrid::freeCObj: double free!");
  // remove us from the alloced list
  if (cobj.prev) cobjs[cobj.prev].next = cobj.next;
  if (cobj.next) cobjs[cobj.next].prev = cobj.prev;
  // fix alloced list (and do some sanity checks)
  if (idx == lastInsertedCObj) {
    if (cobj.next != 0) FatalError("EntityGrid::freeCObj: invalid alloced list!");
    lastInsertedCObj = cobj.prev;
  }
  if (idx == firstInsertedCObj) {
    if (cobj.prev != 0) FatalError("EntityGrid::freeCObj: invalid alloced list!");
    firstInsertedCObj = cobj.next;
  }
  MapEntity e = cobj.e;
  if (cobj.objectIsOwned) {
    delete e;
  } else if (e) {
    e.gridId = 0;
    e.grid = none;
  }
  cobj.e = none;
  cobj.prev = -1;
  cobj.next = freeHeadCObj;
#ifdef ENTITY_GRID_HAS_SCHEDULED_UPDATES
  cobj.updateScheduled = false;
#endif
  cobj.objectIsOwned = false;
  freeHeadCObj = idx;
}


private final int allocItem () {
  int res = freeHead;
  if (res) {
    freeHead = items[res].next;
  } else {
    res = items.length;
    int newlen = (res > 3 ? res+res/2 : 8);
    items.length = newlen;
    foreach (int f; res+1..newlen) items[f].next = f+1;
    items[$-1].next = 0;
    freeHead = res+1;
  }
  // other fields will be set by caller
  return res;
}


private final void freeItem (int idx) {
  if (idx < 1 || idx >= items.length) FatalError("EntityGrid::freeItem: invalid item index!");
  if (items[idx].cid == -1) FatalError("EntityGrid::freeItem: double free!");
  items[idx].cid = -1;
  items[idx].next = freeHead;
  freeHead = idx;
}


// ////////////////////////////////////////////////////////////////////////// //
private final void insertIntoCell (int cid, int gx, int gy) {
  int iid = allocItem();
  Item *it = &items[iid];
  it.cid = cid;
  it.next = grid[gx, gy];
  grid[gx, gy] = iid;
}


private final void removeFromCell (int cid, int gx, int gy) {
  // find item
  int iid = grid[gx, gy], iprev = 0;
  while (iid) {
    if (items[iid].cid == cid) break;
    iprev = iid;
    iid = items[iid].next;
  }
  if (iid) {
    // i found her!
    int next = items[iid].next;
    if (iprev) items[iprev].next = next; else grid[gx, gy] = next;
    freeItem(iid);
  }
}


// `cobjs[cid]` should be fully initialized
private final void insertInternal (int cid) {
  auto cobj = &cobjs[cid];
  int gx0 = cobj.gx0, gx1 = cobj.gx1;
  foreach (int cy; cobj.gy0..cobj.gy1) {
    foreach (int cx; gx0..gx1) {
      insertIntoCell(cid, cx, cy);
    }
  }
}


// this won't free `cid`
private final void removeInternal (int cid) {
  auto cobj = &cobjs[cid];
  int gx0 = cobj.gx0, gx1 = cobj.gx1;
  foreach (int cy; cobj.gy0..cobj.gy1) {
    foreach (int cx; gx0..gx1) {
      removeFromCell(cid, cx, cy);
    }
  }
}


// returns `true` if moved
private final bool moveInternal (int cid, int nx0, int ny0, int nx1, int ny1) {
  auto cobj = &cobjs[cid];
  int gx0 = cobj.gx0, gy0 = cobj.gy0;
  int gx1 = cobj.gx1, gy1 = cobj.gy1;
  if (gx0 != nx0 || gy0 != ny0 || gx1 != nx1 || gy1 != ny1) {
    foreach (int gy; min(gy0, ny0)..max(gy1, ny1)) {
      foreach (int gx; min(gx0, nx0)..max(gx1, nx1)) {
        // are we inside the old rect?
        if (gx >= gx0 && gy >= gy0 && gx < gx1 && gy < gy1) {
          // old rect: inside
          // if not inside new, remove
          if (gx < nx0 || gy < ny0 || gx >= nx1 || gy >= ny1) {
            removeFromCell(cid, gx, gy);
          }
        } else {
          // old rec: outside
          // if inside new, insert
          if (gx >= nx0 && gy >= ny0 && gx < nx1 && gy < ny1) {
            insertIntoCell(cid, gx, gy);
          }
        }
      }
    }
    //removeInternal(cid);
    cobj.gx0 = nx0; cobj.gy0 = ny0;
    cobj.gx1 = nx1; cobj.gy1 = ny1;
    //insertInternal(cid);
    return true;
  }
  return false;
}


// `false`: out of grid/too thin/etc
// returned coords are always valid
// also, `gx1` and `gy1` are exclusive
final bool calcObjGridPos (MapEntity e, out int gx0, out int gy0, out int gx1, out int gy1) {
  if (!e) { gx0 = 0; gy0 = 0; gx1 = 0; gy1 = 0; return false; } // no object
  int ew = max(1, e.width), eh = max(1, e.height);
  //if (ew < 1 || eh < 1) { gx0 = 0; gy0 = 0; gx1 = 0; gy1 = 0; return false; }
  int ex0 = e.x0-mXOfs, ey0 = e.y0-mYOfs;
  int ex1 = ex0+ew-1, ey1 = ey0+eh-1;
  // check if it fits in grid at all
  if (ex1 < 0 || ey1 < 0) { gx0 = 0; gy0 = 0; gx1 = 0; gy1 = 0; return false; } // out of grid
  int tgw = mWidth, tgh = mHeight;
  if (ex0 >= tgw*CellSize || ey0 >= tgh*CellSize) { gx0 = 0; gy0 = 0; gx1 = 0; gy1 = 0; return false; } // out of grid
  // calc grid coords
  ex0 /= CellSize;
  ey0 /= CellSize;
  ex1 /= CellSize;
  ey1 /= CellSize;
  gx0 = clamp(ex0, 0, tgw-1);
  gy0 = clamp(ey0, 0, tgh-1);
  gx1 = clamp(ex1+1, 0, tgw);
  gy1 = clamp(ey1+1, 0, tgh);
  return (gx1 > gx0 && gy1 > gy0);
}


// ////////////////////////////////////////////////////////////////////////// //
// returns 0 if item is not put in grid, or cid
final int insert (MapEntity e) {
  if (!e) return 0;
  if (e.gridId) {
    if (e.grid != self) FatalError("cannot instert entity in two grids");
    if (!update(e.gridId)) { e.gridId = 0; e.grid = none; }
    return e.gridId;
  }
  int gx0, gy0, gx1, gy1;
  bool doInsert = calcObjGridPos(e, out gx0, out gy0, out gx1, out gy1);
  /*
  if (e isa MapTileRope) {
    writeln("ROPE; pos=(", e.x0, ",", e.y0, "); size=(", e.width, "x", e.height, "); grid=(", gx0, ",", gy0, ")-(", gx1, ",", gy1, ")");
  }
  */
  /*
  if (e isa TitleTileCopy) {
    writeln("ROPE; pos=(", e.x0, ",", e.y0, "); size=(", e.width, "x", e.height, "); grid=(", gx0, ",", gy0, ")-(", gx1, ",", gy1, ")");
  }
  */
  // allocate cobj
  int cid = allocCObj();
  auto cobj = &cobjs[cid];
  e.gridId = cid;
  e.grid = self;
  cobj.e = e;
  cobj.tag = 0;
  cobj.gx0 = gx0; cobj.gy0 = gy0;
  cobj.gx1 = gx1; cobj.gy1 = gy1;
  if (doInsert) insertInternal(cid);
  return cid;
}


// returns `true` if item was in the grid, and now removed
final bool remove (int cid) {
  if (cid < 1 || cid >= cobjs.length) return false;
  if (cobjs[cid].prev == -1) return false;
  removeInternal(cid);
  freeCObj(cid);
#ifdef ENTITY_GRID_HAS_SCHEDULED_UPDATES
  foreach (int idx, int v; updateSchedule) {
    if (v == cid) {
      updateSchedule.remove(idx);
      break;
    }
  }
#endif
  return true;
}


#ifdef ENTITY_GRID_HAS_SCHEDULED_UPDATES
// returns `true` if item will be updated
final bool scheduleUpdate (int cid) {
  if (cid < 1 || cid >= cobjs.length) return false;
  auto cobj = &cobjs[cid];
  if (cobj.prev == -1) return false;
  if (cobj.updateScheduled) return true; // already marked
  MapEntity e = cobj.e;
  if (!e) {
    // remove it
    cobjs[cid].updateScheduled = true;
    updateSchedule[$] = cid;
    return false;
  }
  int gx0, gy0, gx1, gy1;
  calcObjGridPos(cobj.e, out gx0, out gy0, out gx1, out gy1);
  if (gx0 != cobj.gx0 || gy0 != cobj.gy0 || gx1 != cobj.gx1 || gy1 == cobj.gy1) {
    // update it
    cobjs[cid].updateScheduled = true;
    updateSchedule[$] = cid;
  }
  return true;
}


final void performUpdates () {
  while (updateSchedule.length) {
    int cid = updateSchedule[$-1];
    updateSchedule.length -= 1;
    update(cid);
  }
}
#endif


// call this when object changed its position
// it is harmless to call it even if position wasn't changed
// returns `false` if item should be removed from grid
// optionally sets `wasMoved` flag
final bool update (int cid, optional out bool wasMoved/*, optional bool markAsDead*/) {
  if (specified_wasMoved) wasMoved = false;
  if (cid < 1 || cid >= cobjs.length) return false;
  auto cobj = &cobjs[cid];
  if (cobj.prev == -1) return false;
  MapEntity e = cobj.e;
  if (!e) return false;
/*
#ifdef ENTITY_GRID_HAS_SCHEDULED_UPDATES
  cobjs[cid].updateScheduled = false;
#endif
*/
  int gx0, gy0, gx1, gy1;
  if (!calcObjGridPos(e, out gx0, out gy0, out gx1, out gy1)) {
    //if (markAsDead && !e.isZeroDimsValid && (e.width < 1 || e.height < 1)) e.instanceRemove();
    removeInternal(cid);
    cobj.gx0 = 0; cobj.gy0 = 0;
    cobj.gx1 = 0; cobj.gy1 = 0;
    return false;
  }
  wasMoved = moveInternal(cid, gx0, gy0, gx1, gy1);
  return true;
}


// ////////////////////////////////////////////////////////////////////////// //
// snap coords to grid cell
final void snapXY (ref int x, ref int y) {
  x = (x-mXOfs)/CellSize*CellSize+mXOfs;
  y = (y-mYOfs)/CellSize*CellSize+mYOfs;
}


/*
final void calcCellSize (out int xcount, out int ycount, int x, int y, int w, int h) {
  if (w < 1 || h < 1) {
    xcount = 0;
    ycount = 0;
  } else {
    int x1 = x+w-1;
    int y1 = y+h-1;
    snapXY(x, y);
    snapXY(x1, y1);
    xcount = (x1-x)/CellSize+1;
    ycount = (y1-y)/CellSize+1;
  }
}
*/


// ////////////////////////////////////////////////////////////////////////// //
// ok, it is not a real spawner, i just wanted to fake its return type
final spawner MapEntity getObject (class!MapEntity cc, int cid) {
  if (cid < 1 || cid >= cobjs.length) return none;
  auto cobj = &cobjs[cid];
  if (cobj.prev == -1) return none;
  return cc(cobj.e);
}

final bool getOwned (int cid) {
  if (cid < 1 || cid >= cobjs.length) return false;
  auto cobj = &cobjs[cid];
  return cobj.objectIsOwned;
}

final void setOwned (int cid, bool v) {
  if (cid < 1 || cid >= cobjs.length) return;
  auto cobj = &cobjs[cid];
  if (cobj.prev != -1) cobj.objectIsOwned = v;
}


// ////////////////////////////////////////////////////////////////////////// //
// ok, it is not a real spawner, i just wanted to fake its return type
final spawner MapEntity getObjectByItem (class!MapEntity cc, int id) {
  if (id < 1 || id >= items.length) return none;
  MapEntity e = cobjs[items[id].cid].e;
  if (e && (!e.visible || !e.isInstanceAlive)) return none;
  return cc(e);
}


// returns first item in cell, optionally tags it too (and skips the given tag)
// returns 0 if there are no items
final int getFirstItemInCell (int cx, int cy, optional int tag) {
  //writeln("specified_tag=", specified_tag, "; tag=", tag);
  if (cx < 0 || cy < 0 || cx >= mWidth || cy >= mHeight) return 0;
  int oid = grid[cx, cy];
  while (oid) {
    // check tag
    if (specified_tag) {
      CellObject *co = &cobjs[items[oid].cid];
      if (co.tag == tag) {
        //writeln("***TAG SKIP (0)");
        oid = items[oid].next;
        continue;
      }
      co.tag = tag; // mark it
    }
    return oid;
  }
  return 0;
}


// returns first item in cell, optionally tags it too (and skips the given tag)
// returns 0 if there are no items
final int getFirstItem (int x, int y, optional int tag) {
  return getFirstItemInCell((x-mXOfs)/CellSize, (y-mYOfs)/CellSize, tag!optional);
}


// returns next item in list, optionally tags it too (and skips the given tag)
// returns 0 if there are no more items
final int getNextItem (int oid, optional int tag) {
  oid = items[oid].next; // 0 contains sentinel anyway
  while (oid) {
    // check tag
    if (specified_tag) {
      CellObject *co = &cobjs[items[oid].cid];
      if (co.tag == tag) {
        //writeln("***TAG SKIP (1)");
        oid = items[oid].next;
        continue;
      }
      co.tag = tag; // mark it
    }
    return oid;
  }
  return 0;
}


// ////////////////////////////////////////////////////////////////////////// //
struct CellIter {
  int oid;
  int tag;
  int px, py;
  bool precise;
  bool hasTag;
}

final bool inCellPix_opIterInit (ref CellIter it, int x, int y, optional int tag, bool precise) {
  //if (!specified_precise) precise = true;
  int oid = getFirstItem(x, y, tag!optional);
  while (oid) {
    MapEntity e = getObjectByItem(objectType, oid);
    if (e && (!precise || e.isPointCollision(x, y))) {
      it.oid = oid;
      it.px = x;
      it.py = y;
      it.tag = tag;
      it.precise = precise;
      it.hasTag = specified_tag;
      return true;
    }
    oid = getNextItem(oid, tag!optional);
  }
  return false;
}

final bool inCellPix_opIterNext (ref CellIter it, out MapEntity ge) {
  int oid = it.oid, x = it.px, y = it.py;
  bool hasTag = it.hasTag;
  bool precise = it.precise;
  int tag = it.tag;
  while (oid) {
    MapEntity e = getObjectByItem(objectType, oid);
    oid = (hasTag ? getNextItem(oid, tag) : getNextItem(oid));
    if (e && (!precise || e.isPointCollision(x, y))) {
      it.oid = oid;
      ge = e;
      return true;
    }
  }
  return false;
}


// ////////////////////////////////////////////////////////////////////////// //
struct CellRectIter {
  int cx0, cx1;
  int cy0, cy1;
  int cx, cy;
  int x0, y0, w, h;
  int oid;
  int tag;
  bool precise;
  bool hasTag;
}

final bool inRectPix_opIterInit (ref CellRectIter it, int ax, int ay, int aw, int ah, optional int tag, bool precise) {
  if (aw < 1 || ah < 1) return false;
  //if (!specified_precise) precise = true;
  it.x0 = ax; it.y0 = ay;
  it.w = aw; it.h = ah;
  int grX = ax-mXOfs, grY = ay-mYOfs;
  if (grX+aw <= 0 || grY+ah <= 0 || grX >= mWidth*CellSize || grY >= mHeight*CellSize) return false;
  int cx0 = max(0, grX/CellSize);
  int cy0 = max(0, grY/CellSize);
  int cx1 = min(mWidth, (grX+aw-1)/CellSize+1);
  int cy1 = min(mHeight, (grY+ah-1)/CellSize+1);
  //writeln("(", ax, ",", ay, ")-(", ax+aw-1, ",", ay+ah-1, "): (", cx0, ",", cy0, ")-(", cx1, ",", cy1, ")");
  foreach (int cy; cy0..cy1) {
    foreach (int cx; cx0..cx1) {
      int oid = getFirstItemInCell(cx, cy, tag!optional);
      while (oid) {
        MapEntity e = getObjectByItem(objectType, oid);
        if (e && (!precise || e.isRectCollision(ax, ay, aw, ah))) {
          //if (e) writeln("!!! cx=", cx, "; cy=", cy, " (", GetClassName(e.Class), ") (name:", e.objName, "; type:", e.objType, ")");
          it.oid = oid;
          it.cx = cx; it.cy = cy;
          it.cx0 = cx0; it.cy0 = cy0;
          it.cx1 = cx1; it.cy1 = cy1;
          it.tag = tag;
          it.hasTag = specified_tag;
          it.precise = precise;
          return true;
        }
        oid = getNextItem(oid, tag!optional);
      }
    }
  }
  return false;
}

final bool inRectPix_opIterNext (ref CellRectIter it, out MapEntity ge) {
  int oid = it.oid;
  bool hasTag = it.hasTag;
  int tag = it.tag;
  int ix = it.x0, iy = it.y0, iw = it.w, ih = it.h;
  bool precise = it.precise;
  while (oid) {
    MapEntity e = getObjectByItem(objectType, oid);
    oid = (hasTag ? getNextItem(oid, tag) : getNextItem(oid));
    if (e && (!precise || e.isRectCollision(ix, iy, iw, ih))) {
      ge = e;
      it.oid = oid;
      return true;
    }
  }
  // move to the next cell
  ++it.cx;
  foreach (int cy; it.cy..it.cy1) {
    foreach (int cx; it.cx..it.cx1) {
      oid = (hasTag ? getFirstItemInCell(cx, cy, tag) : getFirstItemInCell(cx, cy));
      while (oid) {
        MapEntity e = getObjectByItem(objectType, oid);
        oid = (hasTag ? getNextItem(oid, tag) : getNextItem(oid));
        if (e && (!precise || e.isRectCollision(ix, iy, iw, ih))) {
          ge = e;
          it.oid = oid;
          it.cx = cx;
          it.cy = cy;
          return true;
        }
      }
    }
    it.cx = it.cx0;
  }
  it.oid = 0;
  return false;
}


// ////////////////////////////////////////////////////////////////////////// //
// 0: no objects
final int getFirstObject () { return firstInsertedCObj; }

// 0: no more objects
final int getNextObject (int cid, optional bool removeThis) {
  if (cid < 1 || cid >= cobjs.length || cobjs[cid].prev == -1) return 0;
  int n = cobjs[cid].next;
  if (removeThis) {
    removeInternal(cid);
    freeCObj(cid);
  }
  return n;
}


// 0: no objects
final int getLastObject () { return lastInsertedCObj; }

// 0: no more objects
final int getPrevObject (int cid, optional bool removeThis) {
  if (cid < 1 || cid >= cobjs.length || cobjs[cid].prev == -1) return 0;
  int n = cobjs[cid].prev;
  if (removeThis) {
    removeInternal(cid);
    freeCObj(cid);
  }
  return n;
}


// ////////////////////////////////////////////////////////////////////////// //
final bool allObjects_opIterInit (ref int cid) {
  cid = firstInsertedCObj;
  while (cid && !cobjs[cid].e) cid = cobjs[cid].next;
  return (cid != 0);
}

final bool allObjects_opIterNext (ref int cid, out MapEntity ge) {
  if (!cid) return false;
  while (cid) {
    ge = cobjs[cid].e;
    cid = cobjs[cid].next;
    if (ge) return true;
  }
  return true;
}


final bool allObjectsBackwards_opIterInit (ref int cid) {
  cid = lastInsertedCObj;
  while (cid && !cobjs[cid].e) cid = cobjs[cid].prev;
  return (cid != 0);
}

final bool allObjectsBackwards_opIterNext (ref int cid, out MapEntity ge) {
  while (cid) {
    ge = cobjs[cid].e;
    cid = cobjs[cid].prev;
    if (ge) return true;
  }
  return true;
}


// ////////////////////////////////////////////////////////////////////////// //
/*
private static final void siftDownCIDSort (ref array!int arr, int start, int end, bool delegate (int cida, int cidb) dgLess) {
  auto root = start;
  for (;;) {
    auto child = 2*root+1; // left child
    if (child > end) break;
    auto swap = root;
    if (dgLess(arr[swap], arr[child])) swap = child;
    if (child+1 <= end && dgLess(arr[swap], arr[child+1])) swap = child+1;
    if (swap == root) break;
    auto tmp = arr[swap];
    arr[swap] = arr[root];
    arr[root] = tmp;
    root = swap;
  }
}
*/

static final void sortCIDList (ref array!int arr, bool delegate (int a, int b) dgLess, optional int count) {
  if (!specified_count) count = arr.length;
  if (count < 2 || !dgLess) return; // nothing to do

  if (count == 2) {
    if (dgLess(arr[1], arr[0])) {
      auto t = arr[0];
      arr[0] = arr[1];
      arr[1] = t;
    }
    return;
  }

  auto end = count-1;

  // heapify
  auto start = (end-1)/2; // parent; always safe, as our array has at least two items
  for (;;) {
    //siftDownCIDSort(arr, start, end, dgLess);
    auto root = start;
    for (;;) {
      auto child = 2*root+1; // left child
      if (child > end) break;
      auto swap = root;
      if (dgLess(arr[swap], arr[child])) swap = child;
      if (child+1 <= end && dgLess(arr[swap], arr[child+1])) swap = child+1;
      if (swap == root) break;
      auto tmp = arr[swap];
      arr[swap] = arr[root];
      arr[root] = tmp;
      root = swap;
    }
    if (start-- == 0) break; // as `start` cannot be negative, use this condition
  }

  while (end > 0) {
    auto tmp = arr[0];
    arr[0] = arr[end];
    arr[end] = tmp;
    --end;
    //siftDownCIDSort(arr, 0, end, dgLess);
    auto root = 0;
    for (;;) {
      auto child = 2*root+1; // left child
      if (child > end) break;
      auto swap = root;
      if (dgLess(arr[swap], arr[child])) swap = child;
      if (child+1 <= end && dgLess(arr[swap], arr[child+1])) swap = child+1;
      if (swap == root) break;
      tmp = arr[swap];
      arr[swap] = arr[root];
      arr[root] = tmp;
      root = swap;
    }
  }
}


/*
private static final void siftDownObjSort (ref array!MapEntity arr, int start, int end, bool delegate (MapEntity a, MapEntity b) dgLess) {
  auto root = start;
  for (;;) {
    auto child = 2*root+1; // left child
    if (child > end) break;
    auto swap = root;
    if (dgLess(arr[swap], arr[child])) swap = child;
    if (child+1 <= end && dgLess(arr[swap], arr[child+1])) swap = child+1;
    if (swap == root) break;
    auto tmp = arr[swap];
    arr[swap] = arr[root];
    arr[root] = tmp;
    root = swap;
  }
}
*/

static final void sortEntList (ref array!MapEntity arr, bool delegate (MapEntity a, MapEntity b) dgLess, optional int count) {
  if (!specified_count) count = arr.length;
  if (count < 2 || !dgLess) return; // nothing to do

  if (count == 2) {
    if (dgLess(arr[1], arr[0])) {
      auto t = arr[0];
      arr[0] = arr[1];
      arr[1] = t;
    }
    return;
  }

  auto end = count-1;

  // heapify
  auto start = (end-1)/2; // parent; always safe, as our array has at least two items
  for (;;) {
    //siftDownObjSort(arr, start, end, dgLess);
    auto root = start;
    for (;;) {
      auto child = 2*root+1; // left child
      if (child > end) break;
      auto swap = root;
      if (dgLess(arr[swap], arr[child])) swap = child;
      if (child+1 <= end && dgLess(arr[swap], arr[child+1])) swap = child+1;
      if (swap == root) break;
      auto tmp = arr[swap];
      arr[swap] = arr[root];
      arr[root] = tmp;
      root = swap;
    }
    if (start-- == 0) break; // as `start` cannot be negative, use this condition
  }

  while (end > 0) {
    auto tmp = arr[0];
    arr[0] = arr[end];
    arr[end] = tmp;
    --end;
    //siftDownObjSort(arr, 0, end, dgLess);
    auto root = 0;
    for (;;) {
      auto child = 2*root+1; // left child
      if (child > end) break;
      auto swap = root;
      if (dgLess(arr[swap], arr[child])) swap = child;
      if (child+1 <= end && dgLess(arr[swap], arr[child+1])) swap = child+1;
      if (swap == root) break;
      tmp = arr[swap];
      arr[swap] = arr[root];
      arr[root] = tmp;
      root = swap;
    }
  }
}


// ////////////////////////////////////////////////////////////////////////// //
private final bool cmpSortXYRev (int cida, int cidb) {
  MapEntity a = cobjs[cida].e;
  MapEntity b = cobjs[cidb].e;
  if (!a) return !!b; // empty a is always less, except if b is empty too
  if (!b) return false; // non empty a is never less than empty b
  if (a.y0 == b.y0) return (a.x0 > b.x0);
  return (a.y0 > b.y0);
}


// ////////////////////////////////////////////////////////////////////////// //
struct CellItemIter {
  int gx, gy; // next cell
  int tag;
  // in current cell, sorted backwards, so we can use [$-1] and decrement length
  array!int cidlist;
}


// from the right-bottom to left-up
final void getAllObjectsBackSorted (ref array!int cidlist, optional bool includeAll) {
  cidlist.clear();
  for (int f = lastInsertedCObj; f; f = cobjs[f].prev) {
    MapEntity e = cobjs[f].e;
    if (e && (includeAll || (e.visible && e.isInstanceAlive))) cidlist[$] = f;
  }
  sortCIDList(cidlist, &cmpSortXYRev);
}


/+
final bool allCellsBackwards_opIterInit (ref CellItemIter it) {
  it.cidlist.length -= it.cidlist.length; // just in case
  int tag = nextTag();
  foreach (int gy; 0..mHeight; backward) {
    foreach (int gx; 0..mWidth; backward) {
      int oid = getFirstInCell(gx, gy, tag);
      while (oid) {
        MapEntity e = getObject(MapEntity, oid);
        if (e) it.cidlist[$] = items[oid].cid;
        oid = getNext(oid, tag);
      }
      if (it.cidlist.length) {
        sortCIDList(it.cidlist, &cmpSortXYRev);
        it.gx = gx;
        it.gy = gy;
        it.tag = tag;
        return true;
      }
    }
  }
  return false;
}

final bool allCellsBackwards_opIterNext (ref CellItemIter it, out MapEntity ge) {
  while (it.cidlist.length) {
    int cid = it.cidlist[$-1];
    it.cidlist.length -= 1;
    ge = cobjs[cid].e;
    if (ge) return true;
  }
  // next grid cell
  --it.gx;
  int tag = it.tag;
  foreach (int gy; 0..it.gy+1; backward) {
    foreach (int gx; 0..it.gx+1; backward) {
      int oid = getFirstInCell(gx, gy, tag);
      while (oid) {
        MapEntity e = getObject(MapEntity, oid);
        if (e) it.cidlist[$] = items[oid].cid;
        oid = getNext(oid, tag);
      }
      if (it.cidlist.length) {
        sortCIDList(it.cidlist, &cmpSortXYRev);
        it.gx = gx;
        it.gy = gy;
        int cid = it.cidlist[$-1];
        it.cidlist.length -= 1;
        ge = cobjs[cid].e;
        return true;
      }
    }
    it.gx = mWidth-1;
  }
  return false;
}
+/


// ////////////////////////////////////////////////////////////////////////// //
// some debug shit
final int countObjects () {
  int objCount = 0;
  for (int f = firstInsertedCObj; f; f = cobjs[f].next) ++objCount;
  return objCount;
}


final void dumpStats () {
  // calculate max object in cell, number of free cells, and number of used items
  int freeCells = 0, maxInCell = 0, itemCount = 0;
  foreach (int oid; grid) {
    if (!oid) {
      ++freeCells;
    } else {
      int xc = 0;
      while (oid) {
        ++xc;
        oid = items[oid].next;
      }
      itemCount += xc;
      maxInCell = max(maxInCell, xc);
    }
  }
  int objCount = countObjects();
  writeln("=========== GRID STATS ===========");
  writeln("bounds: (", mXOfs, ",", mYOfs, ")-(", mXOfs+mWidth*CellSize-1, ",", mYOfs+mHeight*CellSize-1, ")");
  writeln("cells: ", grid.length, " (", grid.length1, "x", grid.length2, ")");
  writeln("objects: ", objCount, " (out of ", cobjs.length, " slots)");
  writeln("used items: ", itemCount, " out of ", items.length);
  writeln("max items in cell: ", maxInCell);
  writeln("used cells: ", grid.length-freeCells, " out of ", grid.length);
  writeln("----------------------------------");
}


// ////////////////////////////////////////////////////////////////////////// //
struct LineWalker {
  int wx0, wy0, wx1, wy1; // window coordinates
  int stx, sty; // "steps" for x and y axes
  int stleft; // "steps left"
  int err, errinc, errmax;
  int xd, yd; // current coord
  int horiz; // bool

  alias x = xd;
  alias y = yd;
}


// call `lwSetup()` after this
static final void lwCreate (ref LineWalker lw, int minx, int miny, int maxx, int maxy) {
  // clip rectange
  lw.wx0 = minx;
  lw.wy0 = miny;
  lw.wx1 = maxx;
  lw.wy1 = maxy;
}


static final void lwSetClip (ref LineWalker lw, int minx, int miny, int maxx, int maxy) {
  // clip rectange
  lw.wx0 = minx;
  lw.wy0 = miny;
  lw.wx1 = maxx;
  lw.wy1 = maxy;
}


// this will use `w[xy][01]` to clip coords
// return `false` if the whole line was clipped away
// on `true`, you should process first point, and go on
static final bool lwSetup (ref LineWalker lw, int x0, int y0, int x1, int y1) {
  if (lw.wx1 < lw.wx0 || lw.wy1 < lw.wy0) { lw.stleft = 0; lw.xd = x0; lw.yd = y0; return false; }

  bool res;
  if (x0 >= lw.wx0 && y0 >= lw.wy0 && x0 <= lw.wx1 && y0 <= lw.wy1 &&
      x1 >= lw.wx0 && y1 >= lw.wy0 && x1 <= lw.wx1 && y1 <= lw.wy1)
  {
    res = true;
  } else {
    float sx0 = x0, sy0 = y0;
    float sx1 = x1, sy1 = y1;
    res = Geom.clipLine(sx0, sy0, sx1, sy1, lw.wx0, lw.wy0, lw.wx1, lw.wy1);
    if (!res) { lw.stleft = 0; lw.xd = x0; lw.yd = y0; return false; }
    x0 = trunc(sx0); y0 = trunc(sy0);
    x1 = trunc(sx1); y1 = trunc(sy1);
  }

  // check for ortho lines
  if (y0 == y1) {
    // horizontal
    lw.horiz = true;
    lw.stleft = abs(x1-x0)+1;
    lw.stx = (x0 < x1 ? 1 : -1);
    lw.sty = 0;
    lw.errinc = 0;
    lw.errmax = 10; // anything that is greater than zero
  } else if (x0 == x1) {
    // vertical
    lw.horiz = false;
    lw.stleft = abs(y1-y0)+1;
    lw.stx = 0;
    lw.sty = (y0 < y1 ? 1 : -1);
    lw.errinc = 0;
    lw.errmax = 10; // anything that is greater than zero
  } else {
    // diagonal
    if (abs(x1-x0) >= abs(y1-y0)) {
      // horizontal
      lw.horiz = true;
      lw.stleft = abs(x1-x0)+1;
      lw.errinc = abs(y1-y0)+1;
    } else {
      // vertical
      lw.horiz = false;
      lw.stleft = abs(y1-y0)+1;
      lw.errinc = abs(x1-x0)+1;
    }
    lw.stx = (x0 < x1 ? 1 : -1);
    lw.sty = (y0 < y1 ? 1 : -1);
    lw.errmax = lw.stleft;
  }
  lw.xd = x0;
  lw.yd = y0;
  lw.err = -lw.errmax;
  return res;
}


// call this *after* doing a step
// WARNING! if you will do a step when this returns `true`, you will fall into limbo
static final bool lwIsDone (ref LineWalker lw) {
  return (lw.stleft <= 0);
}


// as you will prolly call `done()` after doing a step anyway, this will do it for you
// move to next point, return `true` when the line is complete (i.e. you should stop)
static final bool step (ref LineWalker lw) {
  if (lw.horiz) {
    lw.xd += lw.stx;
    lw.err += lw.errinc;
    if (lw.err >= 0) { lw.err -= lw.errmax; lw.yd += lw.sty; }
  } else {
    lw.yd += lw.sty;
    lw.err += lw.errinc;
    if (lw.err >= 0) { lw.err -= lw.errmax; lw.xd += lw.stx; }
  }
  --lw.stleft;
  return (lw.stleft <= 0);
}


// move to next tile; return `true` if the line is complete (and walker state is undefined then)
static final bool stepToNextTile (ref LineWalker lw) {
  if (lw.stleft < 2) return true; // max one pixel left, nothing to do

  int ex, ey;

  // strictly horizontal?
  if (lw.sty == 0) {
    // only xd
    if (lw.stx < 0) {
      // xd: to left edge
      ex = (lw.xd&(~(CellSize-1)))-1;
      lw.stleft -= lw.xd-ex;
    } else {
      // xd: to right edge
      ex = (lw.xd|(CellSize-1))+1;
      lw.stleft -= ex-lw.xd;
    }
    lw.xd = ex;
    return (lw.stleft <= 0);
  }

  // strictly vertical?
  if (lw.stx == 0) {
    // only xd
    if (lw.sty < 0) {
      // yd: to top edge
      ey = (lw.yd&(~(CellSize-1)))-1;
      lw.stleft -= lw.yd-ey;
    } else {
      // yd: to bottom edge
      ey = (lw.yd|(CellSize-1))+1;
      lw.stleft -= ey-lw.yd;
    }
    lw.yd = ey;
    return (lw.stleft <= 0);
  }

  // diagonal
  int xwalk, ywalk;

  // calculate xwalk
  if (lw.stx < 0) {
    ex = (lw.xd&(~(CellSize-1)))-1;
    xwalk = lw.xd-ex;
  } else {
    ex = (lw.xd|(CellSize-1))+1;
    xwalk = ex-lw.xd;
  }

  // calculate ywalk
  if (lw.sty < 0) {
    ey = (lw.yd&(~(CellSize-1)))-1;
    ywalk = lw.yd-ey;
  } else {
    ey = (lw.yd|(CellSize-1))+1;
    ywalk = ey-lw.yd;
  }

  int wklen = (xwalk <= ywalk ? xwalk : ywalk);
  while (true) {
    // in which dir we want to walk?
    lw.stleft -= wklen;
    if (lw.stleft <= 0) return true;
    if (lw.horiz) {
      lw.xd += wklen*lw.stx;
      for (int f = wklen; f > 0; --f) {
        lw.err += lw.errinc;
        if (lw.err >= 0) { lw.err -= lw.errmax; lw.yd += lw.sty; }
      }
    } else {
      lw.yd += wklen*lw.sty;
      for (int f = wklen; f > 0; --f) {
        lw.err += lw.errinc;
        if (lw.err >= 0) { lw.err -= lw.errmax; lw.xd += lw.stx; }
      }
    }
    // check for walk completion
    if (lw.xd == ex || lw.yd == ey) break;
    wklen = 1;
  }

  return false;
}