more SAP code; still not working right

diff --git a/src/game/g_game.pas b/src/game/g_game.pas
index 802425a68977ff8074cc0b4ba967bf6dcdfdafbb..c575ca4e4416f685509fef8af1b61536a47eb4f1 100644 (file)
--- a/src/game/g_game.pas
+++ b/src/game/g_game.pas
@@ -5062,10 +5062,10 @@ begin
   begin
     case getBool(1) of
       -1: begin end;
-       0: gdbg_map_use_sap := (cmd = 'sq_use_grid');
-       1: gdbg_map_use_sap := (cmd = 'sq_use_sap');
+       0: gdbg_map_use_sap_coldet := (cmd = 'sq_use_grid');
+       1: gdbg_map_use_sap_coldet := (cmd = 'sq_use_sap');
     end;
-    if gdbg_map_use_sap then g_Console_Add('coldet: sap') else g_Console_Add('coldet: grid');
+    if gdbg_map_use_sap_coldet then g_Console_Add('coldet: sap') else g_Console_Add('coldet: grid');
     exit;
   end;
 end;

diff --git a/src/game/g_map.pas b/src/game/g_map.pas
index c9851ee57bb6ec63e8822a8aeae444c19f4442eb..3c380f9bb0a15ea2efba4516bc78d5f2b6bcefbd 100644 (file)
--- a/src/game/g_map.pas
+++ b/src/game/g_map.pas
@@ -136,7 +136,8 @@ var
 
   gdbg_map_use_grid_render: Boolean = true;
   gdbg_map_use_grid_coldet: Boolean = true;
-  gdbg_map_use_sap: Boolean = false;
+  gdbg_map_use_sap_draw: Boolean = true;
+  gdbg_map_use_sap_coldet: Boolean = false;
   profMapCollision: TProfiler = nil; //WARNING: FOR DEBUGGING ONLY!
 
 implementation
@@ -1926,7 +1927,7 @@ begin
 
   if gdbg_map_use_grid_render then
   begin
-    if gdbg_map_use_sap then
+    if gdbg_map_use_sap_draw then
     begin
       gMapSAP.forEachInAABB(x0, y0, wdt, hgt, checker);
     end
@@ -1972,7 +1973,7 @@ procedure g_Map_DrawPanelShadowVolumes(lightX: Integer; lightY: Integer; radius:
   end;
 
 begin
-  if gdbg_map_use_sap then
+  if gdbg_map_use_sap_draw then
   begin
     gMapSAP.forEachInAABB(lightX-radius, lightY-radius, radius*2, radius*2, checker);
   end
@@ -2241,7 +2242,7 @@ begin
   try
     if gdbg_map_use_grid_coldet then
     begin
-      if gdbg_map_use_sap then
+      if gdbg_map_use_sap_coldet then
       begin
         gMapSAP.forEachInAABB(X, Y, Width, Height, checker);
       end
@@ -2313,7 +2314,7 @@ begin
     if gdbg_map_use_grid_coldet then
     begin
       texid := TEXTURE_NONE;
-      if gdbg_map_use_sap then
+      if gdbg_map_use_sap_coldet then
       begin
         gMapSAP.forEachInAABB(X, Y, Width, Height, checker);
       end

diff --git a/src/game/g_sap.pas b/src/game/g_sap.pas
index 5baf514892870dee09a3650c7e98d7b96edb8b71..7e968ea93915d10519c900f7b8db57f8ceb2530f 100644 (file)
--- a/src/game/g_sap.pas
+++ b/src/game/g_sap.pas
@@ -13,8 +13,12 @@
  * You should have received a copy of the GNU General Public License
  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  *)
-{$INCLUDE ../shared/a_modes.inc}
 // universal sweep-and-prune broad phase
+{$INCLUDE ../shared/a_modes.inc}
+{$DEFINE SAP_CHECKS}
+{$DEFINE SAP_ALWAYS_SORT}
+{$DEFINE SAP_WALK_DEBUG}
+{$DEFINE SAP_INSERT_DEBUG}
 unit g_sap;
 
 interface
@@ -32,41 +36,85 @@ type
     mQueryMark: DWord; // was this object visited at this query?
     mObj: TObject;
     mTag: Integer;
-    //nextLink: TSAPProxy; // next free or nothing
-    mIIdx: array [0..1] of Integer; // indicies in corresponding intervals
+    mIdx: array [Boolean, 0..1] of Integer; // indicies in corresponding intervals
 
   private
     procedure setup (aX, aY, aWidth, aHeight: Integer; aObj: TObject; aTag: Integer);
 
+    function getx1 (): Integer; inline;
+    function gety1 (): Integer; inline;
+
+    function getidx (ismin: Boolean; iidx: Integer): Integer; inline;
+    procedure setidx (ismin: Boolean; iidx: Integer; v: Integer); inline;
+
+    function getnextfree (): Integer;
+    procedure setnextfree (v: Integer);
+
   public
     property x: Integer read mX;
     property y: Integer read mY;
     property width: Integer read mWidth;
     property height: Integer read mHeight;
+    property x0: Integer read mX;
+    property y0: Integer read mY;
+    property x1: Integer read getx1;
+    property y1: Integer read gety1;
     property obj: TObject read mObj;
     property tag: Integer read mTag;
-    //property grid: TBodyGrid read mGrid;
+    property idx[ismin: Boolean; iidx: Integer]: Integer read getidx write setidx;
+    property nextfree: Integer read getnextfree write setnextfree;
   end;
 
 
   TSweepAndPrune = class(TObject)
   private
     type
-      //PInterval = ^TInterval;
+      PIntervalRec = ^TIntervalRec;
+      TIntervalRec = record
+      public
+        val: Integer;
+        mpidx: DWord; // proxy idx; bit 31 is "ismin"
+
+      public
+        function less (var i: TIntervalRec): Boolean; inline;
+        function inside (v0, v1: Integer): Boolean; inline;
+
+        function getismin (): Boolean; inline;
+        procedure setismin (v: Boolean); inline;
+
+        function getpidx (): Integer; inline;
+        procedure setpidx (v: Integer); inline;
+
+        property ismin: Boolean read getismin write setismin;
+        property pidx: Integer read getpidx write setpidx;
+      end;
+
       TInterval = record
       public
-        min, max: Integer;
-        pidx: Integer; // proxy idx
+        type
+          TWalkCB = function (pidx: Integer; px: PSAPProxyRec): Boolean is nested; // return `true` to stop
+
+      public
+        intrs: array of TIntervalRec;
+        used: Integer;
+        mProxies: array of TSAPProxyRec; // copy of main mProxies
+        myidx: Integer; // index of this interval
 
       public
-        function less (var i: TInterval): Boolean; inline;
-        function intersects (v0, v1: Integer): Boolean; inline;
+        procedure setup (aIdx: Integer);
+        procedure cleanup ();
+
+        procedure sort ();
+        procedure insert (apidx: Integer);
+
+        function walk (v0, v1: Integer; cb: TWalkCB): Boolean;
+
+        procedure dump ();
       end;
 
   private
     mLastQuery: DWord;
-    mIntrs: array[0..1] of array of TInterval;
-    mIntrsUsed: array[0..1] of Integer;
+    mIntrs: array[0..1] of TInterval;
     mProxies: array of TSAPProxyRec;
     mProxyFree: TSAPProxy; // free
     mProxyCount: Integer; // currently used
@@ -121,31 +169,254 @@ begin
   mQueryMark := 0;
   mObj := aObj;
   mTag := aTag;
-  //nextLink := -1;
-  mIIdx[0] := -1;
-  mIIdx[1] := -1;
+  mIdx[false, 0] := -1;
+  mIdx[false, 1] := -1;
+  mIdx[true, 0] := -1;
+  mIdx[true, 1] := -1;
 end;
 
+function TSAPProxyRec.getx1 (): Integer; begin result := mX+mWidth-1; end;
+function TSAPProxyRec.gety1 (): Integer; begin result := mY+mHeight-1; end;
+
+function TSAPProxyRec.getidx (ismin: Boolean; iidx: Integer): Integer; begin result := mIdx[ismin, iidx]; end;
+procedure TSAPProxyRec.setidx (ismin: Boolean; iidx: Integer; v: Integer); begin mIdx[ismin, iidx] := v; end;
+
+function TSAPProxyRec.getnextfree (): Integer; begin result := mIdx[false, 0]; end;
+procedure TSAPProxyRec.setnextfree (v: Integer); begin mIdx[false, 0] := v; end;
+
 
 // ////////////////////////////////////////////////////////////////////////// //
-function TSweepAndPrune.TInterval.less (var i: TInterval): Boolean;
+function TSweepAndPrune.TIntervalRec.getismin (): Boolean; begin result := ((mpidx and $80000000) <> 0); end;
+procedure TSweepAndPrune.TIntervalRec.setismin (v: Boolean); begin if (v) then mpidx := mpidx or $80000000 else mpidx := mpidx and $7fffffff; end;
+
+function TSweepAndPrune.TIntervalRec.getpidx (): Integer; begin result := Integer(mpidx and $7fffffff); end;
+procedure TSweepAndPrune.TIntervalRec.setpidx (v: Integer); begin mpidx := (v and $7fffffff) or (mpidx and $80000000); end;
+
+
+function TSweepAndPrune.TIntervalRec.less (var i: TIntervalRec): Boolean;
 var
   n: Integer;
 begin
-  n := min-i.min;
-  if (n <> 0) then begin result := (n < 0); exit; end;
-  n := max-i.max;
-  if (n <> 0) then begin result := (n < 0); exit; end;
-  result := (pidx < i.pidx);
+  n := val-i.val;
+  if (n <> 0) then result := (n < 0) else result := (pidx < i.pidx);
 end;
 
 
 // v0 MUST be <= v1!
-function TSweepAndPrune.TInterval.intersects (v0, v1: Integer): Boolean;
+function TSweepAndPrune.TIntervalRec.inside (v0, v1: Integer): Boolean;
+begin
+  result := (val >= v0) and (val <= v1);
+end;
+
+
+// ////////////////////////////////////////////////////////////////////////// //
+procedure TSweepAndPrune.TInterval.setup (aIdx: Integer);
+begin
+  SetLength(intrs, 8192*2);
+  used := 0;
+  mProxies := nil;
+  myidx := aIdx;
+end;
+
+
+procedure TSweepAndPrune.TInterval.cleanup ();
+begin
+  intrs := nil;
+  mProxies := nil;
+end;
+
+
+procedure TSweepAndPrune.TInterval.sort ();
+var
+  len, i, j: Integer;
+  x: TIntervalRec;
+  arr: array of TIntervalRec;
+  pxa: array of TSAPProxyRec;
+  iidx: Integer;
+begin
+  len := used;
+  if (len = 0) then exit;
+  arr := intrs;
+  pxa := mProxies;
+  iidx := myidx;
+  {$IFDEF SAP_CHECKS}
+  for i := 0 to len-1 do
+  begin
+    if (pxa[arr[i].pidx].idx[arr[i].ismin, iidx] <> i) then
+    begin
+      e_WriteLog(Format('FUCKUP: interval %d; i=%d; val=%d; ismin=%d; got=%d', [iidx, i, arr[i].val, Integer(arr[i].ismin), pxa[arr[i].pidx].idx[arr[i].ismin, iidx]]), MSG_NOTIFY);
+      dump();
+      raise Exception.Create('sorting fuckup (5)');
+    end;
+  end;
+  {$ENDIF}
+  if (len > 1) then
+  begin
+    i := 1;
+    while (i < len) do
+    begin
+      if (arr[i].less(arr[i-1])) then
+      begin
+        x := arr[i];
+        j := i-1;
+        while (j >= 0) and (x.less(arr[j])) do
+        begin
+          arr[j+1] := arr[j];
+          pxa[arr[j+1].pidx].idx[arr[j+1].ismin, iidx] := j+1;
+          Dec(j);
+        end;
+        pxa[x.pidx].idx[x.ismin, iidx] := j+1;
+        arr[j+1] := x;
+      end;
+      Inc(i);
+    end;
+  end;
+  // check
+  {$IFDEF SAP_CHECKS}
+  for i := 0 to len-1 do
+  begin
+    if (i <> 0) then
+    begin
+      if arr[i].less(arr[i-1]) then begin dump(); raise Exception.Create('sorting fuckup (2)'); end;
+      if (arr[i-1].val > arr[i].val) then begin dump(); raise Exception.Create('sorting fuckup (3)'); end;
+    end;
+    if (pxa[arr[i].pidx].idx[arr[i].ismin, iidx] <> i) then begin dump(); raise Exception.Create('sorting fuckup (4)'); end;
+  end;
+  {$ENDIF}
+end;
+
+
+procedure TSweepAndPrune.TInterval.insert (apidx: Integer);
+var
+  v0, v1, i: Integer;
+  pi: PIntervalRec;
+  px: PSAPProxyRec;
+begin
+  px := @mProxies[apidx];
+  // get min/max
+  if (myidx = 0) then
+  begin
+    v0 := px.x0;
+    v1 := px.x1;
+  end
+  else
+  begin
+    v0 := px.y0;
+    v1 := px.y1;
+  end;
+  // append min
+  i := used;
+  if (i+2 >= Length(intrs)) then SetLength(intrs, i+8192*2);
+  {$IFDEF SAP_INSERT_DEBUG}
+  e_WriteLog(Format('inserting proxy %d into interval %d; v0=%d; i=%d', [apidx, myidx, v0, i]), MSG_NOTIFY);
+  {$ENDIF}
+  pi := @intrs[i];
+  pi.val := v0;
+  pi.pidx := apidx;
+  pi.ismin := true;
+  px.idx[true, myidx] := i;
+  // append max
+  Inc(i);
+  {$IFDEF SAP_INSERT_DEBUG}
+  e_WriteLog(Format('inserting proxy %d into interval %d; v1=%d; i=%d', [apidx, myidx, v1, i]), MSG_NOTIFY);
+  {$ENDIF}
+  pi := @intrs[i];
+  pi.val := v1;
+  pi.pidx := apidx;
+  pi.ismin := false;
+  px.idx[false, myidx] := i;
+  // done
+  Inc(used, 2);
+  {$IFDEF SAP_CHECKS}
+  if (used <> i+1) then raise Exception.Create('something is VERY wrong in SAP');
+  {$ENDIF}
+end;
+
+
+function TSweepAndPrune.TInterval.walk (v0, v1: Integer; cb: TWalkCB): Boolean;
+var
+  len: Integer;
+  i, bot, mid, cmp: Integer;
+  px: PSAPProxyRec;
+  arr: array of TIntervalRec;
+  pxa: array of TSAPProxyRec;
 begin
   result := false;
-  if (v1 < min) or (v0 > max) then exit;
-  result := true;
+  if not assigned(cb) or (v0 > v1) then exit; // alas
+  len := used;
+  if (len < 1) then exit; // nothing to do
+  arr := intrs;
+  pxa := mProxies;
+
+  {$IFDEF SAP_WALK_DEBUG}
+  e_WriteLog(Format('walking interval #%d; v0=%d; v1=%d; len=%d', [myidx, v0, v1, len]), MSG_NOTIFY);
+  {$ENDIF}
+
+  if (len = 1) then
+  begin
+    // one element
+    i := 0;
+  end
+  else
+  begin
+    // do search
+    bot := 0;
+    i := len-1;
+    while (bot <> i) do
+    begin
+      mid := i-(i-bot) div 2;
+      cmp := v0-arr[mid].val;
+      if (cmp = 0) then break;
+      if (cmp < 0) then i := mid-1 else bot := mid;
+    end;
+    //return (cmpfn(lines+i) == 0 ? i : -1);
+    {$IFDEF SAP_WALK_DEBUG}
+    e_WriteLog(Format('  binsearch interval #%d; i=%d; len=%d; isect=%d', [myidx, i, len, Integer(arr[i].inside(v0, v1))]), MSG_NOTIFY);
+    {$ENDIF}
+    if not arr[i].inside(v0, v1) then
+    begin
+      {$IFDEF SAP_WALK_DEBUG}e_WriteLog('    bin: not good', MSG_NOTIFY);{$ENDIF}
+           if (i > 0) and arr[i-1].inside(v0, v1) then begin Dec(i); {$IFDEF SAP_WALK_DEBUG}e_WriteLog('    bin: up', MSG_NOTIFY);{$ENDIF} end
+      else if (i+1 < len) and arr[i+1].inside(v0, v1) then begin Inc(i); {$IFDEF SAP_WALK_DEBUG}e_WriteLog('    bin: down', MSG_NOTIFY);{$ENDIF} end
+      else begin {$IFDEF SAP_WALK_DEBUG}e_WriteLog('    bin: wtf?!', MSG_NOTIFY);{$ENDIF} end;
+    end;
+    // find first interval
+    while (i > 0) and arr[i-1].inside(v0, v1) do Dec(i);
+  end;
+
+  {$IFDEF SAP_WALK_DEBUG}
+  if (i >= 0) and (i < len) and arr[i].inside(v0, v1) then
+    e_WriteLog(Format('  start interval #%d; i=%d; v0=%d; v1=%d; len=%d; val=%d; ismin=%d', [myidx, i, v0, v1, len, arr[i].val, Integer(arr[i].ismin)]), MSG_NOTIFY);
+  {$ENDIF}
+
+  // walk
+  while (i >= 0) and (i < len) and arr[i].inside(v0, v1) do
+  begin
+    px := @pxa[arr[i].pidx];
+    result := cb(arr[i].pidx, px);
+    if result then break;
+    Inc(i);
+  end;
+
+  {$IFDEF SAP_WALK_DEBUG}
+  Dec(i);
+  if (i >= 0) and (i < len) then
+    e_WriteLog(Format('  end interval #%d; i=%d; v0=%d; v1=%d; len=%d; val=%d; ismin=%d', [myidx, i, v0, v1, len, arr[i].val, Integer(arr[i].ismin)]), MSG_NOTIFY);
+  {$ENDIF}
+end;
+
+
+procedure TSweepAndPrune.TInterval.dump ();
+var
+  idx: Integer;
+  pi: PIntervalRec;
+begin
+  e_WriteLog(Format('interval #%d; len=%d', [myidx, used]), MSG_NOTIFY);
+  for idx := 0 to used-1 do
+  begin
+    pi := @intrs[idx];
+    e_WriteLog(Format('  pi #%d; val=%d; ismin=%d; pidx=%d; px0=%d; py0=%d; px1=%d; py1=%d', [idx, pi.val, Integer(pi.ismin), pi.pidx, mProxies[pi.pidx].x0, mProxies[pi.pidx].y0, mProxies[pi.pidx].x1, mProxies[pi.pidx].y1]), MSG_NOTIFY);
+  end;
 end;
 
 
@@ -156,29 +427,29 @@ var
 begin
   mLastQuery := 0;
 
-  // init intervals
-  for idx := 0 to High(mIntrs) do
-  begin
-    SetLength(mIntrs[idx], 8192);
-    mIntrsUsed[idx] := 0;
-  end;
-
   // init proxies
   SetLength(mProxies, 8192);
   for idx := 0 to High(mProxies) do
   begin
-    mProxies[idx].mIIdx[0] := idx+1;
-    mProxies[idx].mIIdx[1] := -1;
+    mProxies[idx].idx[true, 0] := idx+1;
+    mProxies[idx].idx[true, 1] := -1;
+    mProxies[idx].idx[false, 0] := -1;
+    mProxies[idx].idx[false, 1] := -1;
+  end;
+  mProxies[High(mProxies)].idx[true, 0] := -1;
+
+  // init intervals
+  for idx := 0 to High(mIntrs) do
+  begin
+    mIntrs[idx].setup(idx);
+    mIntrs[idx].mProxies := mProxies;
   end;
-  mProxies[High(mProxies)].mIIdx[0] := -1;
 
   mProxyFree := 0;
   mProxyCount := 0;
   mProxyMaxCount := 0;
 
   mUpdateBlocked := 0;
-
-  //e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
 end;
 
 
@@ -186,15 +457,17 @@ destructor TSweepAndPrune.Destroy ();
 var
   idx: Integer;
 begin
+  for idx := 0 to High(mIntrs) do mIntrs[idx].cleanup();
   mProxies := nil;
-  for idx := 0 to High(mIntrs) do mIntrs[idx] := nil;
   inherited;
 end;
 
 
 procedure TSweepAndPrune.dumpStats ();
 begin
-  e_WriteLog(Format('used intervals: %d; max proxies allocated: %d; proxies used: %d', [mIntrsUsed[0], mProxyMaxCount, mProxyCount]), MSG_NOTIFY);
+  e_WriteLog(Format('used intervals: [%d;%d]; max proxies allocated: %d; proxies used: %d', [mIntrs[0].used, mIntrs[1].used, mProxyMaxCount, mProxyCount]), MSG_NOTIFY);
+  mIntrs[0].dump();
+  mIntrs[1].dump();
 end;
 
 
@@ -224,89 +497,63 @@ begin
     // no free proxies, resize list
     olen := Length(mProxies);
     SetLength(mProxies, olen+8192); // arbitrary number
-    for idx := olen to High(mProxies) do mProxies[idx].mIIdx[0] := idx+1;
-    mProxies[High(mProxies)].mIIdx[0] := -1;
+    for idx := olen to High(mProxies) do mProxies[idx].idx[true, 0] := idx+1;
+    mProxies[High(mProxies)].idx[true, 0] := -1;
     mProxyFree := olen;
+    // fix intervals cache
+    for idx := 0 to High(mIntrs) do mIntrs[idx].mProxies := mProxies;
   end;
   // get one from list
   result := mProxyFree;
   px := @mProxies[result];
-  mProxyFree := px.mIIdx[0];
+  mProxyFree := px.idx[true, 0];
   px.setup(aX, aY, aWidth, aHeight, aObj, aTag);
   // add to used list
-  px.mIIdx[0] := -1;
+  px.idx[true, 0] := idx+1;
+  px.idx[true, 1] := -1;
+  px.idx[false, 0] := -1;
+  px.idx[false, 1] := -1;
   // statistics
   Inc(mProxyCount);
   if (mProxyMaxCount < mProxyCount) then mProxyMaxCount := mProxyCount;
 end;
 
+
 procedure TSweepAndPrune.freeProxy (body: TSAPProxy);
+var
+  px: PSAPProxyRec;
 begin
   if (body < 0) or (body > High(mProxies)) then exit; // just in case
   if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
   // add to free list
-  mProxies[body].mObj := nil;
-  mProxies[body].mIIdx[0] := mProxyFree;
-  mProxies[body].mIIdx[1] := -1;
+  px := @mProxies[body];
+  px.mObj := nil;
+  px.idx[true, 0] := mProxyFree;
+  px.idx[true, 1] := -1;
+  px.idx[false, 0] := -1;
+  px.idx[false, 1] := -1;
   mProxyFree := body;
   Dec(mProxyCount);
 end;
 
 
 procedure TSweepAndPrune.sortIntervals ();
-  procedure insSort (var arr: array of TInterval; iidx: Integer);
-  var
-    i, j: Integer;
-    x: TInterval;
-  begin
-    if (Length(arr) < 2) then exit; // nothing to do
-    i := 1;
-    while (i < Length(arr)) do
-    begin
-      if (arr[i].less(arr[i-1])) then
-      begin
-        x := arr[i];
-        j := i-1;
-        while (j >= 0) and (x.less(arr[j])) do
-        begin
-          arr[j+1] := arr[j];
-          mProxies[arr[j+1].pidx].mIIdx[iidx] := j+1;
-          Dec(j);
-        end;
-        mProxies[x.pidx].mIIdx[iidx] := j+1;
-        arr[j+1] := x;
-      end;
-      Inc(i);
-    end;
-  end;
-
 begin
-  insSort(mIntrs[0], 0);
-  insSort(mIntrs[1], 1);
+  mIntrs[0].sort();
+  mIntrs[1].sort();
 end;
 
 
 procedure TSweepAndPrune.insert (body: TSAPProxy);
-var
-  px: PSAPProxyRec;
-
-  procedure insIntr (v0, v1, iidx: Integer);
-  var
-    i: Integer;
-  begin
-    i := mIntrsUsed[iidx];
-    if (i >= Length(mIntrs[iidx])) then SetLength(mIntrs[iidx], i+8192);
-    mIntrs[iidx][i].min := v0;
-    mIntrs[iidx][i].max := v1;
-    mIntrs[iidx][i].pidx := i;
-    Inc(mIntrsUsed[iidx]);
-  end;
-
 begin
   if (body < 0) or (body > High(mProxies)) then exit; // just in case
-  px := @mProxies[body];
-  insIntr(px.mX, px.mX+px.mWidth-1, 0);
-  insIntr(px.mY, px.mY+px.mHeight-1, 1);
+  mIntrs[0].insert(body);
+  mIntrs[1].insert(body);
+  {$IFDEF SAP_ALWAYS_SORT}
+  sortIntervals();
+  {$ELSE}
+  if (mUpdateBlocked = 0) then sortIntervals();
+  {$ENDIF}
 end;
 
 
@@ -319,58 +566,33 @@ end;
 
 
 function TSweepAndPrune.forEachInAABB (x, y, w, h: Integer; cb: TSAPQueryCB): Boolean;
+var
+  lq: Integer;
+
+  function walker0 (pidx: Integer; px: PSAPProxyRec): Boolean;
+  begin
+    result := false; // don't stop
+    {$IFDEF SAP_WALK_DEBUG}
+    e_WriteLog(Format('    walker0: pidx=%d; x0=%d; y0=%d; x1=%d; y1=%d; lq=%d', [pidx, px.x0, px.y0, px.x1, px.y1, lq]), MSG_NOTIFY);
+    {$ENDIF}
+    px.mQueryMark := lq;
+  end;
 
-  function walkInterval (val0, val1, lq, iidx: Integer): Boolean;
-  var
-    i, bot, mid, cmp: Integer;
-    px: PSAPProxyRec;
+  function walker1 (pidx: Integer; px: PSAPProxyRec): Boolean;
   begin
-    result := false;
-    if (mIntrsUsed[iidx] < 1) then exit; // nothing to do
-    if (mIntrsUsed[iidx] = 1) then
+    {$IFDEF SAP_WALK_DEBUG}
+    e_WriteLog(Format('    walker1: pidx=%d; x0=%d; y0=%d; x1=%d; y1=%d; lq=%d', [pidx, px.x0, px.y0, px.x1, px.y1, px.mQueryMark]), MSG_NOTIFY);
+    {$ENDIF}
+    if (px.mQueryMark = lq) then
     begin
-      // one element
-      i := 0;
+      result := cb(px.mObj, px.mTag);
+      {$IFDEF SAP_WALK_DEBUG}
+      e_WriteLog(Format('      CB walker1: pidx=%d; x0=%d; y0=%d; x1=%d; y1=%d; lq=%d; res=%d', [pidx, px.x0, px.y0, px.x1, px.y1, px.mQueryMark, Integer(result)]), MSG_NOTIFY);
+      {$ENDIF}
     end
     else
     begin
-      // do search
-      bot := 0;
-      i := mIntrsUsed[iidx]-1;
-      while (bot <> i) do
-      begin
-        mid := i-(i-bot) div 2;
-        cmp := val0-mIntrs[iidx][mid].min;
-        if (cmp = 0) then break;
-        if (cmp < 0) then i := mid-1 else bot := mid;
-      end;
-      //return (cmpfn(lines+i) == 0 ? i : -1);
-      if (i > 0) and not mIntrs[iidx][i].intersects(val0, val1) and mIntrs[iidx][i-1].intersects(val0, val1) then Dec(i);
-      if (i+1 < mIntrsUsed[iidx]) and not mIntrs[iidx][i].intersects(val0, val1) and mIntrs[iidx][i+1].intersects(val0, val1) then Inc(i);
-      while (i > 0) and mIntrs[iidx][i].intersects(val0, val1) do Dec(i);
-      if (iidx = 0) then
-      begin
-        // first pass
-        while (i < mIntrsUsed[iidx]) and mIntrs[iidx][i].intersects(val0, val1) do
-        begin
-          mProxies[mIntrs[iidx][i].pidx].mQueryMark := lq;
-          Inc(i);
-        end;
-      end
-      else
-      begin
-        // second pass
-        while (i < mIntrsUsed[iidx]) and mIntrs[iidx][i].intersects(val0, val1) do
-        begin
-          px := @mProxies[mIntrs[iidx][i].pidx];
-          if (px.mQueryMark = lq) then
-          begin
-            result := cb(px.mObj, px.mTag);
-            if result then exit;
-          end;
-          Inc(i);
-        end;
-      end;
+      result := false; // don't stop
     end;
   end;
 
@@ -394,12 +616,12 @@ begin
    * the algorithm is simple:
    *   find start for first interval (binary search will do)
    *   walk the interval, marking proxies with mLastQuery
-   *   increment mLastQuery
    *   find start for second interval (binary search will do)
    *   walk the interval, returning proxies marked with mLastQuery
    *)
-  walkInterval(x, x+w-1, mLastQuery, 0);
-  result := walkInterval(x, x+w-1, mLastQuery, 1);
+  lq := mLastQuery;
+  mIntrs[0].walk(x, x+w-1, walker0);
+  result := mIntrs[1].walk(y, y+h-1, walker1);
 end;
 
 

diff --git a/src/game/g_window.pas b/src/game/g_window.pas
index 582c2d98973da6f38b5819829fc5c807d10e1a3b..c91ff6cc555cedcf224827fcd9fac0f0f12437ea 100644 (file)
--- a/src/game/g_window.pas
+++ b/src/game/g_window.pas
@@ -709,8 +709,10 @@ begin
     if ParamStr(idx) = '--opengl-dump-exts' then gwin_dump_extensions := true;
     if ParamStr(idx) = '--twinkletwinkle' then gwin_k8_enable_light_experiments := true;
     if ParamStr(idx) = '--jah' then g_profile_history_size := 100;
-    if ParamStr(idx) = '--sap' then gdbg_map_use_sap := true;
-    if ParamStr(idx) = '--grid' then gdbg_map_use_sap := false;
+    if ParamStr(idx) = '--sap-draw' then gdbg_map_use_sap_draw := true;
+    if ParamStr(idx) = '--grid-draw' then gdbg_map_use_sap_draw := false;
+    if ParamStr(idx) = '--sap-coldet' then gdbg_map_use_sap_coldet := true;
+    if ParamStr(idx) = '--grid-coldet' then gdbg_map_use_sap_coldet := false;
   end;
 
   e_WriteLog('Initializing OpenGL', MSG_NOTIFY);