d2dunigrid.d

   1 /* DooM2D: Midnight on the Firing Line
   2  * coded by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
   3  * Understanding is not required. Only obedience.
   4  *
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation, either version 3 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program. If not, see <http://www.gnu.org/licenses/>.
  17  */
  18 // uniform grid to speed up collision detection
  19 module d2dunigrid is aliced;
  20
  21 private import dacs.actor;
  22 private import d2dadefs : AF_NOCOLLISION;
  23
  24
  25 // ////////////////////////////////////////////////////////////////////////// //
  26 public: // api
  27
  28
  29 void ugInit (int width, int height, int cellSizeX=32, int cellSizeY=32) {
  30   assert(width > 0 && height > 0);
  31   assert(cellSizeX > 0 && cellSizeY > 0);
  32   gwidth = (width+cellSizeX-1)/cellSizeX;
  33   gheight = (height+cellSizeY-1)/cellSizeY;
  34   gcw = cellSizeX;
  35   gch = cellSizeY;
  36   grid.length = gwidth*gheight;
  37   grid[] = GridBucket.init;
  38 }
  39
  40
  41 void ugClear () {
  42   foreach (ref bt; grid) bt.actCount = bt.mactCount = 0;
  43 }
  44
  45
  46 // x, y: center
  47 void ugModifyRadius(bool doput) (uint aid, int x, int y, int radius) {
  48   pragma(inline, true);
  49   doModifyAABB!doput(aid, x-radius, y-radius, x+radius, y+radius);
  50 }
  51
  52
  53 // `x1` and `y1` are included
  54 void ugModifyAABB(bool doput) (uint aid, int x0, int y0, int x1, int y1) {
  55   pragma(inline, true);
  56   doModifyAABB!doput(aid, x0, y0, x1, y1);
  57 }
  58
  59
  60 uint[] ugHitListRadius (uint[] dest, int x, int y, int radius) {
  61   pragma(inline, true);
  62   return getHitListAABB(dest, x-radius, y-radius, x+radius, y+radius);
  63 }
  64
  65
  66 uint[] ugHitListAABB (uint[] dest, int x0, int y0, int x1, int y1) {
  67   pragma(inline, true);
  68   return getHitListAABB(dest, x0, y0, x1, y1);
  69 }
  70
  71
  72 // i HAET copypasta!
  73 void ugActorModify(bool doput) (ActorId a) {
  74   if (!a.valid) return;
  75
  76   if (a.fget_flags&AF_NOCOLLISION) return;
  77
  78   int ax = a.fget_x;
  79   int ay = a.fget_y;
  80   int ar = a.fget_radius;
  81   int ah = a.fget_height;
  82   if (ar < 1 || ah < 1) return;
  83
  84   ugModifyAABB!doput(a.id, ax-ar, ay-ah+1, ax+ar, ay);
  85 }
  86
  87
  88 // i HAET copypasta!
  89 uint[] ugActorPossibleHitList (ActorId a, uint[] dest) {
  90   if (!a.valid) return null;
  91
  92   if (a.fget_flags&AF_NOCOLLISION) return null;
  93
  94   int ax = a.fget_x;
  95   int ay = a.fget_y;
  96   int ar = a.fget_radius;
  97   int ah = a.fget_height;
  98   if (ar < 1 || ah < 1) return null;
  99
 100   return ugHitListAABB(dest, ax-ar, ay-ah+1, ax+ar, ay);
 101 }
 102
 103
 104 // i HAET copypasta!
 105 uint[] ugActorHitList (ActorId a, uint[] dest) {
 106   auto res = ugActorPossibleHitList(a, dest);
 107
 108   // and filter it
 109   for (usize pos = 0; pos < res.length; ++pos) {
 110     bool killIt = (res.ptr[pos] == a.id);
 111     if (!killIt) {
 112       // check for real collision
 113       import dengapi : actorsOverlap;
 114       killIt = !actorsOverlap(a, ActorId(res.ptr[pos]));
 115     }
 116     if (killIt) {
 117       // no collision, remove this actor from list
 118       foreach (immutable c; pos+1..res.length) res.ptr[c-1] = res.ptr[c];
 119       res.length -= 1;
 120       --pos; // compensate loop increment
 121     }
 122   }
 123
 124   return res;
 125 }
 126
 127
 128 // ////////////////////////////////////////////////////////////////////////// //
 129 private: // api
 130
 131 mixin(Actor.FieldGetMixin!("x", int));
 132 mixin(Actor.FieldGetMixin!("y", int));
 133 mixin(Actor.FieldGetMixin!("height", int));
 134 mixin(Actor.FieldGetMixin!("radius", int));
 135 mixin(Actor.FieldGetMixin!("flags", uint));
 136
 137
 138 struct GridBucket {
 139   uint[32] acts; // actorids
 140   uint actCount;
 141   uint[] macts; // dynamically grows
 142   uint mactCount; // actorids
 143
 144   @disable this (this); // no copies
 145 }
 146
 147 __gshared int gwidth, gheight; // in cells
 148 __gshared int gcw, gch; // cell size
 149 __gshared GridBucket[] grid;
 150
 151
 152 GridBucket* calcNormAABB (ref int x0, ref int y0, ref int x1, ref int y1) {
 153   x0 /= gcw;
 154   x1 /= gcw;
 155   y0 /= gch;
 156   y1 /= gch;
 157   if (x0 < 0) x0 = 0;
 158   if (y0 < 0) y0 = 0;
 159   if (x1 >= gwidth) x1 = gwidth-1;
 160   if (y1 >= gheight) y1 = gheight-1;
 161   if (x0 > x1 || y0 > y1 || x1 < 0 || y1 < 0 || x0 >= gwidth || y0 >= gheight) return null;
 162   return grid.ptr+y0*gwidth+x0;
 163 }
 164
 165
 166 // `x1` and `y1` are included
 167 void doModifyAABB(bool doadd) (uint aid, int x0, int y0, int x1, int y1) @trusted {
 168   GridBucket* gdata = calcNormAABB(ref x0, ref y0, ref x1, ref y1);
 169   if (gdata is null) return;
 170   for (; y0 <= y1; ++y0, gdata += gwidth) {
 171     auto p = gdata;
 172     for (int x = x0; x <= x1; ++x, ++p) {
 173       bool found = false;
 174       static if (doadd) {
 175         // add
 176         foreach (uint id; p.acts[0..p.actCount]) if (id == aid) { found = true; break; }
 177         if (!found) foreach (uint id; p.macts[0..p.mactCount]) if (id == aid) { found = true; break; }
 178         if (!found) {
 179           if (p.actCount < p.acts.length) {
 180             // easy case
 181             p.acts.ptr[p.actCount++] = aid;
 182           } else if (p.mactCount < p.macts.length) {
 183             // second easy case
 184             p.macts.ptr[p.mactCount++] = aid;
 185           } else {
 186             assert(p.mactCount == p.macts.length);
 187             // alas, we have to allocate
 188             p.macts.assumeSafeAppend; // no, really
 189             p.macts.length += 1;
 190             p.macts.ptr[p.mactCount++] = aid;
 191           }
 192         }
 193       } else {
 194         // remove
 195         foreach (immutable idx, uint id; p.acts[0..p.actCount]) {
 196           if (id == aid) {
 197             // kill the clown!
 198             found = true;
 199             foreach (immutable c; idx+1..p.actCount) p.acts.ptr[c-1] = p.acts.ptr[c];
 200             break;
 201           }
 202         }
 203         if (!found) {
 204           foreach (immutable idx, uint id; p.macts[0..p.mactCount]) {
 205             if (id == aid) {
 206               // kill the clown!
 207               foreach (immutable c; idx+1..p.mactCount) p.macts.ptr[c-1] = p.macts.ptr[c];
 208               break;
 209             }
 210           }
 211         }
 212       }
 213     }
 214   }
 215 }
 216
 217
 218 // i HAET copypasta!
 219 // `x1` and `y1` are included
 220 uint[] getHitListAABB (uint[] dest, int x0, int y0, int x1, int y1) @trusted {
 221   // we have alot of memory!
 222   __gshared uint[65536] wasSeen = 0;
 223   __gshared uint hitCount = 0;
 224
 225   GridBucket* gdata = calcNormAABB(ref x0, ref y0, ref x1, ref y1);
 226   if (gdata is null) return null;
 227
 228   if (++hitCount == 0) {
 229     // rare case of overflow
 230     hitCount = 1;
 231     wasSeen[] = 0;
 232   }
 233
 234   uint dpos = 0;
 235
 236   bool addToRes (uint id) {
 237     if (wasSeen.ptr[id&0xffff] != hitCount) {
 238       if (dpos >= dest.length) return false;
 239       wasSeen.ptr[id&0xffff] = hitCount;
 240       dest.ptr[dpos++] = id;
 241     }
 242     return true;
 243   }
 244
 245   mainloop: for (; y0 <= y1; ++y0, gdata += gwidth) {
 246     auto p = gdata;
 247     for (int x = x0; x <= x1; ++x, ++p) {
 248       foreach (uint id; p.acts[0..p.actCount]) if (!addToRes(id)) break mainloop;
 249       foreach (uint id; p.macts[0..p.mactCount]) if (!addToRes(id)) break mainloop;
 250     }
 251   }
 252   return dest[0..dpos];
 253 }