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+1, y-radius+1, x+radius-1, y+radius-1);
  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+1, y-radius+1, x+radius-1, y+radius-1);
  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   initFieldOffsets();
  76
  77   auto aptr = a.data.ptr;
  78   uint af = *cast(uint*)(aptr+fflags);
  79
  80   if (af&AF_NOCOLLISION) return;
  81
  82   int ax = *cast(int*)(aptr+fxofs);
  83   int ay = *cast(int*)(aptr+fyofs);
  84   int ar = *cast(int*)(aptr+frofs);
  85   int ah = *cast(int*)(aptr+fhofs);
  86
  87   ugModifyAABB!doput(a.id, ax-ar+1, ay-ah+1, ax+ar-1, ay);
  88 }
  89
  90
  91 // i HAET copypasta!
  92 uint[] ugActorPossibleHitList (ActorId a, uint[] dest) {
  93   if (!a.valid) return null;
  94   initFieldOffsets();
  95
  96   auto aptr = a.data.ptr;
  97   uint af = *cast(uint*)(aptr+fflags);
  98
  99   if (af&AF_NOCOLLISION) return null;
 100
 101   int ax = *cast(int*)(aptr+fxofs);
 102   int ay = *cast(int*)(aptr+fyofs);
 103   int ar = *cast(int*)(aptr+frofs);
 104   int ah = *cast(int*)(aptr+fhofs);
 105
 106   return ugHitListAABB(dest, ax-ar+1, ay-ah+1, ax+ar-1, ay);
 107 }
 108
 109
 110 // i HAET copypasta!
 111 uint[] ugActorHitList (ActorId a, uint[] dest) {
 112   if (!a.valid) return null;
 113   initFieldOffsets();
 114
 115   auto aptr = a.data.ptr;
 116   uint af = *cast(uint*)(aptr+fflags);
 117
 118   if (af&AF_NOCOLLISION) return null;
 119
 120   int ax = *cast(int*)(aptr+fxofs);
 121   int ay = *cast(int*)(aptr+fyofs);
 122   int ar = *cast(int*)(aptr+frofs);
 123   int ah = *cast(int*)(aptr+fhofs);
 124
 125   // get possible hitlist
 126   auto res = ugHitListAABB(dest, ax-ar+1, ay-ah+1, ax+ar-1, ay);
 127
 128   // and filter it
 129   for (usize pos = 0; pos < res.length; ++pos) {
 130     bool killIt = (res.ptr[pos] == a.id);
 131     if (!killIt) {
 132       // check for real collision
 133       import dengapi : actorsOverlap;
 134       killIt = !actorsOverlap(a, ActorId(res.ptr[pos]));
 135     }
 136     if (killIt) {
 137       // no collision, remove this actor from list
 138       foreach (immutable c; pos+1..res.length) res.ptr[c-1] = res.ptr[c];
 139       res.length -= 1;
 140       --pos; // compensate loop increment
 141     }
 142   }
 143
 144   return res;
 145 }
 146
 147
 148 // ////////////////////////////////////////////////////////////////////////// //
 149 private: // api
 150
 151 //FIXME
 152 static uint fxofs = uint.max;
 153 static uint fyofs = uint.max;
 154 static uint fhofs = uint.max;
 155 static uint frofs = uint.max;
 156 static uint fflags = uint.max;
 157
 158 void initFieldOffsets () {
 159   pragma(inline, true);
 160   if (fxofs == uint.max) {
 161     fxofs = Actor.fields["x"].ofs;
 162     fyofs = Actor.fields["y"].ofs;
 163     fhofs = Actor.fields["height"].ofs;
 164     frofs = Actor.fields["radius"].ofs;
 165     fflags = Actor.fields["flags"].ofs;
 166   }
 167 }
 168
 169
 170 struct GridBucket {
 171   uint[32] acts; // actorids
 172   uint actCount;
 173   uint[] macts; // dynamically grows
 174   uint mactCount; // actorids
 175 }
 176
 177 __gshared int gwidth, gheight; // in cells
 178 __gshared int gcw, gch; // cell size
 179 __gshared GridBucket[] grid;
 180
 181
 182 // `x1` and `y1` are included
 183 void doModifyAABB(bool doadd) (uint aid, int x0, int y0, int x1, int y1) @trusted {
 184   if (x0 < 0) x0 = 0;
 185   if (y0 < 0) y0 = 0;
 186   if (x1 >= gwidth*gcw) x1 = gwidth*gcw-1;
 187   if (y1 >= gheight*gch) y1 = gheight*gch-1;
 188   if (x0 > x1 || y0 > y1 || x1 < 0 || y1 < 0 || x0 >= gwidth*gcw || y0 >= gheight*gch) return;
 189   GridBucket* gdata = grid.ptr+(y0/gch)*gwidth+(x0/gcw);
 190   for (; y0 <= y1; y0 += gch, gdata += gwidth) {
 191     auto p = gdata;
 192     for (int x = x0; x <= x1; x += gcw, ++p) {
 193       bool found = false;
 194       static if (doadd) {
 195         // add
 196         foreach (uint id; p.acts[0..p.actCount]) if (id == aid) { found = true; break; }
 197         if (!found) foreach (uint id; p.macts[0..p.mactCount]) if (id == aid) { found = true; break; }
 198         if (!found) {
 199           if (p.actCount < p.acts.length) {
 200             // easy case
 201             p.acts[p.actCount++] = aid;
 202           } else if (p.mactCount < p.macts.length) {
 203             // second easy case
 204             p.macts[p.mactCount++] = aid;
 205           } else {
 206             // alas, we have to allocate
 207             p.macts.assumeSafeAppend; // no, really
 208             p.macts ~= aid;
 209             ++p.mactCount;
 210           }
 211         }
 212       } else {
 213         // remove
 214         foreach (immutable idx, uint id; p.acts[0..p.actCount]) {
 215           if (id == aid) {
 216             // kill the clown!
 217             found = true;
 218             foreach (immutable c; idx+1..p.actCount) p.acts.ptr[c-1] = p.acts[c];
 219             break;
 220           }
 221         }
 222         if (!found) {
 223           foreach (immutable idx, uint id; p.macts[0..p.mactCount]) {
 224             if (id == aid) {
 225               // kill the clown!
 226               foreach (immutable c; idx+1..p.mactCount) p.macts.ptr[c-1] = p.macts[c];
 227               break;
 228             }
 229           }
 230         }
 231       }
 232     }
 233   }
 234 }
 235
 236
 237 // i HAET copypasta!
 238 // `x1` and `y1` are included
 239 uint[] getHitListAABB (uint[] dest, int x0, int y0, int x1, int y1) @trusted {
 240   // we have alot of memory!
 241   static uint[65536] wasSeen;
 242   static uint hitCount = 0;
 243
 244   if (x0 < 0) x0 = 0;
 245   if (y0 < 0) y0 = 0;
 246   if (x1 >= gwidth*gcw) x1 = gwidth*gcw-1;
 247   if (y1 >= gheight*gch) y1 = gheight*gch-1;
 248   if (x0 > x1 || y0 > y1 || x1 < 0 || y1 < 0 || x0 >= gwidth*gcw || y0 >= gheight*gch) return null;
 249   uint dpos = 0;
 250
 251   if (++hitCount == 0) {
 252     // rare case of overflow
 253     hitCount = 1;
 254     wasSeen[] = 0;
 255   }
 256
 257   bool addToRes (uint id) {
 258     if (wasSeen.ptr[id&0xffff] != hitCount) {
 259       if (dpos >= dest.length) return false;
 260       wasSeen.ptr[id&0xffff] = hitCount;
 261       dest.ptr[dpos++] = id;
 262     }
 263     return true;
 264   }
 265
 266   GridBucket* gdata = grid.ptr+(y0/gch)*gwidth+(x0/gcw);
 267   mainloop: for (; y0 <= y1; y0 += gch, gdata += gwidth) {
 268     auto p = gdata;
 269     for (int x = x0; x <= x1; x += gcw, ++p) {
 270       foreach (uint id; p.acts[0..p.actCount]) if (!addToRes(id)) break mainloop;
 271       foreach (uint id; p.macts[0..p.mactCount]) if (!addToRes(id)) break mainloop;
 272     }
 273   }
 274   return dest[0..dpos];
 275 }