X-Git-Url: http://deadsoftware.ru/gitweb?a=blobdiff_plain;f=src%2Fgame%2Fg_grid.pas;h=427482fda6e4a61ab3d088df39acc4f73e46c3a0;hb=d7d166dc3cd287276202e862746208892c4cc89f;hp=55feca9a094f1ac89568f79b79e78f5ab2e72d93;hpb=4915b85cae0bdda83e7ae7ee0b049a07e550395f;p=d2df-sdl.git

diff --git a/src/game/g_grid.pas b/src/game/g_grid.pas
index 55feca9..427482f 100644
--- a/src/game/g_grid.pas
+++ b/src/game/g_grid.pas
@@ -21,17 +21,21 @@
   {.$DEFINE D2F_DEBUG_MOVER}
 {$ENDIF}
 {.$DEFINE GRID_USE_ORTHO_ACCEL}
+{$DEFINE LINEAABB2}
 unit g_grid;
 
 interface
 
+uses
+  mempool;
+
 const
   GridTileSize = 32; // must be power of two!
 
 type
   TBodyProxyId = Integer;
 
-  generic TBodyGridBase<ITP> = class(TObject)
+  generic TBodyGridBase<ITP> = class(TPoolObject)
   public
     type TGridQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
     type TGridRayQueryCB = function (obj: ITP; tag: Integer; x, y, prevx, prevy: Integer): Boolean is nested; // return `true` to stop
@@ -142,9 +146,6 @@ type
     function allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
     procedure freeProxy (body: TBodyProxyId);
 
-    procedure insertInternal (body: TBodyProxyId);
-    procedure removeInternal (body: TBodyProxyId);
-
     function forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
 
     function inserter (grida: Integer; bodyId: TBodyProxyId): Boolean;
@@ -252,12 +253,10 @@ type
   private
     wx0, wy0, wx1, wy1: Integer; // window coordinates
     stx, sty: Integer; // "steps" for x and y axes
-    dx2, dy2: Integer; // "double lengthes" for x and y axes
+    stleft: Integer; // "steps left"
+    err, errinc, errmax: Integer;
     xd, yd: Integer; // current coord
-    e: Integer; // "error" (as in bresenham algo)
-    term: Integer; // end for xd (xd = term: done)
-    //xptr, yptr: PInteger;
-    xyswapped: Boolean; // true: xd is y
+    horiz: Boolean;
 
   public
     // call `setyp` after this
@@ -281,18 +280,12 @@ type
     // move to next tile; return `true` if the line is complete (and walker state is undefined then)
     function stepToNextTile (): Boolean; inline;
 
-    // hack for line-vs-aabb; NOT PROPERLY TESTED!
-    procedure getPrevXY (out ox, oy: Integer); inline;
-
-    // current coords
-    function x (): Integer; inline;
-    function y (): Integer; inline;
-
     procedure getXY (out ox, oy: Integer); inline;
 
-    // move directions; always [-1..1] (can be zero!)
-    function dx (): Integer; inline;
-    function dy (): Integer; inline;
+  public
+    // current coords
+    property x: Integer read xd;
+    property y: Integer read yd;
   end;
 
 
@@ -327,6 +320,7 @@ uses
 
 // ////////////////////////////////////////////////////////////////////////// //
 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
+//procedure swapInt (var a: Integer; var b: Integer); inline; begin a := a xor b; b := b xor a; a := a xor b; end;
 //function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
 //function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
 
@@ -334,405 +328,337 @@ function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result :=
 
 
 // ////////////////////////////////////////////////////////////////////////// //
-constructor TLineWalker.Create (minx, miny, maxx, maxy: Integer);
-begin
-  setClip(minx, miny, maxx, maxy);
-end;
-
-procedure TLineWalker.setClip (minx, miny, maxx, maxy: Integer); inline;
-begin
-  // clip rectange
-  wx0 := minx;
-  wy0 := miny;
-  wx1 := maxx;
-  wy1 := maxy;
-end;
-
-function TLineWalker.done (): Boolean; inline; begin result := (xd = term); end;
+function clipLine (var x0, y0, x1, y1: Single; xmin, ymin, xmax, ymax: Single): Boolean;
+const
+  Inside = 0;
+  Left = 1;
+  Right = 2;
+  Bottom = 4;
+  Top = 8;
 
-function TLineWalker.step (): Boolean; inline;
-begin
-  if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
-  xd += stx;
-  result := (xd = term);
-end;
+  function xcode (x, y: Single): Byte; inline;
+  begin
+    result := Inside;
+    if (x < xmin) then result := result or Left else if (x > xmax) then result := result or Right;
+    if (y < ymin) then result := result or Bottom else if (y > ymax) then result := result or Top;
+  end;
 
-// move to next tile; return `true` if the line is complete (and walker state is undefined then)
-function TLineWalker.stepToNextTile (): Boolean; inline;
 var
-  ex, ey, wklen, f: Integer;
+  outcode0, outcode1, outcodeOut: Byte;
+  x: Single = 0;
+  y: Single = 0;
 begin
-  result := false;
-
-  //writeln('stx=', stx, '; sty=', sty);
-
-  // ortho?
-  if (sty = 0) then
-  begin
-    // only xd
-    assert(sty <> 0);
-    if (stx < 0) then
+  result := false; // accept
+  outcode0 := xcode(x0, y0);
+  outcode1 := xcode(x1, y1);
+  while true do
+  begin
+    if ((outcode0 or outcode1) = 0) then begin result := true; exit; end; // accept
+    if ((outcode0 and outcode1) <> 0) then exit; // reject
+    outcodeOut := outcode0;
+    if (outcodeOut = 0) then outcodeOut := outcode1;
+    if ((outcodeOut and Top) <> 0) then
     begin
-      // xd: to left edge
-      xd := (xd and (not (TileSize-1)))-1;
-      result := (xd <= term);
-      exit;
+      x := x0+(x1-x0)*(ymax-y0)/(y1-y0);
+      y := ymax;
+    end
+    else if ((outcodeOut and Bottom) <> 0) then
+    begin
+      x := x0+(x1-x0)*(ymin-y0)/(y1-y0);
+      y := ymin;
+    end
+    else if ((outcodeOut and Right) <> 0) then
+    begin
+      y := y0+(y1-y0)*(xmax-x0)/(x1-x0);
+      x := xmax;
+    end
+    else if ((outcodeOut and Left) <> 0) then
+    begin
+      y := y0+(y1-y0)*(xmin-x0)/(x1-x0);
+      x := xmin;
+    end;
+    if (outcodeOut = outcode0) then
+    begin
+      x0 := x;
+      y0 := y;
+      outcode0 := xcode(x0, y0);
     end
     else
     begin
-      // xd: to right edge
-      xd := (xd or (TileSize-1))+1;
-      result := (xd >= term);
-      exit;
+      x1 := x;
+      y1 := y;
+      outcode1 := xcode(x1, y1);
     end;
   end;
+end;
 
-  assert(stx <> 0); // invariant
-
-  // not ortho
-  if (sty < 0) then ey := (yd and (not (TileSize-1)))-1 else ey := (yd or (TileSize-1))+1;
 
-  //FIXME: do some math to avoid single-stepping
-  if (stx < 0) then
-  begin
-    // xd: to left edge
-    ex := (xd and (not (TileSize-1)))-1;
-    if (ex <= term) then begin result := true; exit; end;
-    wklen := xd-ex;
+// returns `true` if there is an intersection, and enter coords
+// enter coords will be equal to (x0, y0) if starting point is inside the box
+// if result is `false`, `inx` and `iny` are undefined
+function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
+var
+  sx0, sy0, sx1, sy1: Single;
+begin
+  inx := x0;
+  iny := y0;
+  result := false;
+  if (bw < 1) or (bh < 1) then exit;
+  if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
+  sx0 := x0; sy0 := y0;
+  sx1 := x1; sy1 := y1;
+  result := clipLine(sx0, sy0, sx1, sy1, bx, by, bx+bw-1, by+bh-1);
+  if result then
+  begin
+    inx := trunc(sx0);
+    iny := trunc(sy0);
+    // hack!
+    if (inx = bx) then Dec(inx) else if (inx = bx+bw-1) then Inc(inx);
+    if (iny = by) then Dec(iny) else if (iny = by+bh-1) then Inc(iny);
   end
   else
   begin
-    // xd: to right edge
-    ex := (xd or (TileSize-1))+1;
-    if (ex >= term) then begin result := true; exit; end;
-    wklen := ex-xd;
+    inx := x1;
+    iny := y1;
   end;
+end;
 
-  //writeln('xd=', xd, '; yd=', yd, '; ex=', ex, '; ey=', ey, '; term=', term, '; wklen=', wklen);
-
-  for f := wklen downto 1 do
-  begin
-    // do step
-    if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
-    xd += stx;
-    if (xd = term) then begin result := true; exit; end;
-    if (xd = ex) or (yd = ey) then exit; // done
-  end;
 
-  raise Exception.Create('TLineWalker.stepToNextTile: the thing that should not be!');
+// ////////////////////////////////////////////////////////////////////////// //
+constructor TLineWalker.Create (minx, miny, maxx, maxy: Integer);
+begin
+  setClip(minx, miny, maxx, maxy);
 end;
 
-// NOT TESTED!
-procedure TLineWalker.getPrevXY (out ox, oy: Integer); inline;
+procedure TLineWalker.setClip (minx, miny, maxx, maxy: Integer); inline;
 begin
-  //writeln('e=', e, '; dx2=', dx2, '; dy2=', dy2);
-  if xyswapped then
-  begin
-    if (e >= 0) then ox := yd-sty else ox := yd;
-    oy := xd-stx;
-  end
-  else
-  begin
-    if (e >= 0) then oy := yd-sty else oy := yd;
-    ox := xd-stx;
-  end;
+  // clip rectange
+  wx0 := minx;
+  wy0 := miny;
+  wx1 := maxx;
+  wy1 := maxy;
 end;
 
-function TLineWalker.x (): Integer; inline; begin if xyswapped then result := yd else result := xd; end;
-function TLineWalker.y (): Integer; inline; begin if xyswapped then result := xd else result := yd; end;
-procedure TLineWalker.getXY (out ox, oy: Integer); inline; begin if xyswapped then begin ox := yd; oy := xd; end else begin ox := xd; oy := yd; end; end;
-
-function TLineWalker.dx (): Integer; inline; begin if xyswapped then result := stx else result := sty; end;
-function TLineWalker.dy (): Integer; inline; begin if xyswapped then result := sty else result := stx; end;
-
 function TLineWalker.setup (x0, y0, x1, y1: Integer): Boolean;
-  procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
 var
-  dsx, dsy: Integer; // "lengthes" for x and y axes
-  rem: Integer;
-  xfixed: Boolean;
-  temp: Integer;
+  sx0, sy0, sx1, sy1: Single;
 begin
-  result := false;
-  xyswapped := false;
+  if (wx1 < wx0) or (wy1 < wy0) then begin stleft := 0; xd := x0; yd := y0; result := false; exit; end;
 
-  // horizontal setup
-  if (x0 < x1) then
+  if (x0 >= wx0) and (y0 >= wy0) and (x0 <= wx1) and (y0 <= wy1) and
+     (x1 >= wx0) and (y1 >= wy0) and (x1 <= wx1) and (y1 <= wy1) then
   begin
-    // from left to right
-    if (x0 > wx1) or (x1 < wx0) then exit; // out of screen
-    stx := 1; // going right
+    result := true;
   end
   else
   begin
-    // from right to left
-    if (x1 > wx1) or (x0 < wx0) then exit; // out of screen
-    stx := -1; // going left
-    x0 := -x0;
-    x1 := -x1;
-    wx0 := -wx0;
-    wx1 := -wx1;
-    swapInt(wx0, wx1);
+    sx0 := x0; sy0 := y0;
+    sx1 := x1; sy1 := y1;
+    result := clipLine(sx0, sy0, sx1, sy1, wx0, wy0, wx1, wy1);
+    if not result then begin stleft := 0; xd := x0; yd := y0; exit; end;
+    x0 := trunc(sx0); y0 := trunc(sy0);
+    x1 := trunc(sx1); y1 := trunc(sy1);
   end;
 
-  // vertical setup
-  if (y0 < y1) then
+  // check for ortho lines
+  if (y0 = y1) then
   begin
-    // from top to bottom
-    if (y0 > wy1) or (y1 < wy0) then exit; // out of screen
-    sty := 1; // going down
+    // horizontal
+    horiz := true;
+    stleft := abs(x1-x0)+1;
+    if (x0 < x1) then stx := 1 else stx := -1;
+    sty := 0;
+    errinc := 0;
+    errmax := 10; // anything that is greater than zero
   end
-  else
-  begin
-    // from bottom to top
-    if (y1 > wy1) or (y0 < wy0) then exit; // out of screen
-    sty := -1; // going up
-    y0 := -y0;
-    y1 := -y1;
-    wy0 := -wy0;
-    wy1 := -wy1;
-    swapInt(wy0, wy1);
-  end;
-
-  dsx := x1-x0;
-  dsy := y1-y0;
-
-  if (dsx < dsy) then
+  else if (x0 = x1) then
   begin
-    xyswapped := true;
-    //xptr := @yd;
-    //yptr := @xd;
-    swapInt(x0, y0);
-    swapInt(x1, y1);
-    swapInt(dsx, dsy);
-    swapInt(wx0, wy0);
-    swapInt(wx1, wy1);
-    swapInt(stx, sty);
+    // vertical
+    horiz := false;
+    stleft := abs(y1-y0)+1;
+    stx := 0;
+    if (y0 < y1) then sty := 1 else sty := -1;
+    errinc := 0;
+    errmax := 10; // anything that is greater than zero
   end
   else
   begin
-    //xptr := @xd;
-    //yptr := @yd;
+    // diagonal
+    if (abs(x1-x0) >= abs(y1-y0)) then
+    begin
+      // horizontal
+      horiz := true;
+      stleft := abs(x1-x0)+1;
+      errinc := abs(y1-y0)+1;
+    end
+    else
+    begin
+      // vertical
+      horiz := false;
+      stleft := abs(y1-y0)+1;
+      errinc := abs(x1-x0)+1;
+    end;
+    if (x0 < x1) then stx := 1 else stx := -1;
+    if (y0 < y1) then sty := 1 else sty := -1;
+    errmax := stleft;
   end;
-
-  dx2 := 2*dsx;
-  dy2 := 2*dsy;
   xd := x0;
   yd := y0;
-  e := 2*dsy-dsx;
-  term := x1;
+  err := -errmax;
+end;
 
-  xfixed := false;
-  if (y0 < wy0) then
-  begin
-    // clip at top
-    temp := dx2*(wy0-y0)-dsx;
-    xd += temp div dy2;
-    rem := temp mod dy2;
-    if (xd > wx1) then exit; // x is moved out of clipping rect, nothing to do
-    if (xd+1 >= wx0) then
-    begin
-      yd := wy0;
-      e -= rem+dsx;
-      if (rem > 0) then begin Inc(xd); e += dy2; end;
-      xfixed := true;
-    end;
-  end;
+function TLineWalker.done (): Boolean; inline; begin result := (stleft <= 0); end;
 
-  if (not xfixed) and (x0 < wx0) then
+// true: done
+function TLineWalker.step (): Boolean; inline;
+begin
+  if horiz then
   begin
-    // clip at left
-    temp := dy2*(wx0-x0);
-    yd += temp div dx2;
-    rem := temp mod dx2;
-    if (yd > wy1) or (yd = wy1) and (rem >= dsx) then exit;
-    xd := wx0;
-    e += rem;
-    if (rem >= dsx) then begin Inc(yd); e -= dx2; end;
-  end;
-
-  if (y1 > wy1) then
+    xd += stx;
+    err += errinc;
+    if (err >= 0) then begin err -= errmax; yd += sty; end;
+  end
+  else
   begin
-    // clip at bottom
-    temp := dx2*(wy1-y0)+dsx;
-    term := x0+temp div dy2;
-    rem := temp mod dy2;
-    if (rem = 0) then Dec(term);
+    yd += sty;
+    err += errinc;
+    if (err >= 0) then begin err -= errmax; xd += stx; end;
   end;
-
-  if (term > wx1) then term := wx1; // clip at right
-
-  Inc(term); // draw last point (it is ok to inc here, as `term` sign will be changed later
-  //if (term = xd) then exit; // this is the only point, get out of here
-
-  if (sty = -1) then yd := -yd;
-  if (stx = -1) then begin xd := -xd; term := -term; end;
-  dx2 -= dy2;
-
-  result := true;
+  Dec(stleft);
+  result := (stleft <= 0);
 end;
 
-
-// ////////////////////////////////////////////////////////////////////////// //
-// you are not supposed to understand this
-// returns `true` if there is an intersection, and enter coords
-// enter coords will be equal to (x0, y0) if starting point is inside the box
-// if result is `false`, `inx` and `iny` are undefined
-function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
+// true: done
+function TLineWalker.stepToNextTile (): Boolean; inline;
 var
-  wx0, wy0, wx1, wy1: Integer; // window coordinates
-  stx, sty: Integer; // "steps" for x and y axes
-  dsx, dsy: Integer; // "lengthes" for x and y axes
-  dx2, dy2: Integer; // "double lengthes" for x and y axes
-  xd, yd: Integer; // current coord
-  e: Integer; // "error" (as in bresenham algo)
-  rem: Integer;
-  //!term: Integer;
-  d0, d1: PInteger;
-  xfixed: Boolean;
-  temp: Integer;
+  ex, ey: Integer;
+  xwalk, ywalk, wklen: Integer; // to the respective edges
+  f: Integer;
 begin
   result := false;
-  // why not
-  inx := x0;
-  iny := y0;
-  if (bw < 1) or (bh < 1) then exit; // impossible box
 
-  if (x0 = x1) and (y0 = y1) then
+  if (stleft < 2) then begin result := true; exit; end; // max one pixel left, nothing to do
+
+  // strictly horizontal?
+  if (sty = 0) then
   begin
-    // check this point
-    result := (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh);
+    // only xd
+    if (stx < 0) then
+    begin
+      // xd: to left edge
+      ex := (xd and (not (TileSize-1)))-1;
+      stleft -= xd-ex;
+    end
+    else
+    begin
+      // xd: to right edge
+      ex := (xd or (TileSize-1))+1;
+      stleft -= ex-xd;
+    end;
+    result := (stleft <= 0);
+    xd := ex;
     exit;
   end;
 
-  // check if staring point is inside the box
-  if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
-
-  // clip rectange
-  wx0 := bx;
-  wy0 := by;
-  wx1 := bx+bw-1;
-  wy1 := by+bh-1;
-
-  // horizontal setup
-  if (x0 < x1) then
-  begin
-    // from left to right
-    if (x0 > wx1) or (x1 < wx0) then exit; // out of screen
-    stx := 1; // going right
-  end
-  else
+  // strictly vertical?
+  if (stx = 0) then
   begin
-    // from right to left
-    if (x1 > wx1) or (x0 < wx0) then exit; // out of screen
-    stx := -1; // going left
-    x0 := -x0;
-    x1 := -x1;
-    wx0 := -wx0;
-    wx1 := -wx1;
-    swapInt(wx0, wx1);
+    // only xd
+    if (sty < 0) then
+    begin
+      // yd: to top edge
+      ey := (yd and (not (TileSize-1)))-1;
+      stleft -= yd-ey;
+    end
+    else
+    begin
+      // yd: to bottom edge
+      ey := (yd or (TileSize-1))+1;
+      stleft -= ey-yd;
+    end;
+    result := (stleft <= 0);
+    yd := ey;
+    exit;
   end;
 
-  // vertical setup
-  if (y0 < y1) then
+  // diagonal
+
+  // calculate xwalk
+  if (stx < 0) then
   begin
-    // from top to bottom
-    if (y0 > wy1) or (y1 < wy0) then exit; // out of screen
-    sty := 1; // going down
+    ex := (xd and (not (TileSize-1)))-1;
+    xwalk := xd-ex;
   end
   else
   begin
-    // from bottom to top
-    if (y1 > wy1) or (y0 < wy0) then exit; // out of screen
-    sty := -1; // going up
-    y0 := -y0;
-    y1 := -y1;
-    wy0 := -wy0;
-    wy1 := -wy1;
-    swapInt(wy0, wy1);
+    ex := (xd or (TileSize-1))+1;
+    xwalk := ex-xd;
   end;
 
-  dsx := x1-x0;
-  dsy := y1-y0;
-
-  if (dsx < dsy) then
+  // calculate ywalk
+  if (sty < 0) then
   begin
-    d0 := @yd;
-    d1 := @xd;
-    swapInt(x0, y0);
-    swapInt(x1, y1);
-    swapInt(dsx, dsy);
-    swapInt(wx0, wy0);
-    swapInt(wx1, wy1);
-    swapInt(stx, sty);
+    ey := (yd and (not (TileSize-1)))-1;
+    ywalk := yd-ey;
   end
   else
   begin
-    d0 := @xd;
-    d1 := @yd;
+    ey := (yd or (TileSize-1))+1;
+    ywalk := ey-yd;
   end;
 
-  dx2 := 2*dsx;
-  dy2 := 2*dsy;
-  xd := x0;
-  yd := y0;
-  e := 2*dsy-dsx;
-  //!term := x1;
-
-  xfixed := false;
-  if (y0 < wy0) then
+  {
+  while (xd <> ex) and (yd <> ey) do
   begin
-    // clip at top
-    temp := dx2*(wy0-y0)-dsx;
-    xd += temp div dy2;
-    rem := temp mod dy2;
-    if (xd > wx1) then exit; // x is moved out of clipping rect, nothing to do
-    if (xd+1 >= wx0) then
+    if horiz then
     begin
-      yd := wy0;
-      e -= rem+dsx;
-      if (rem > 0) then begin Inc(xd); e += dy2; end;
-      xfixed := true;
+      xd += stx;
+      err += errinc;
+      if (err >= 0) then begin err -= errmax; yd += sty; end;
+    end
+    else
+    begin
+      yd += sty;
+      err += errinc;
+      if (err >= 0) then begin err -= errmax; xd += stx; end;
     end;
+    Dec(stleft);
+    if (stleft < 1) then begin result := true; exit; end;
   end;
+  }
 
-  if (not xfixed) and (x0 < wx0) then
-  begin
-    // clip at left
-    temp := dy2*(wx0-x0);
-    yd += temp div dx2;
-    rem := temp mod dx2;
-    if (yd > wy1) or (yd = wy1) and (rem >= dsx) then exit;
-    xd := wx0;
-    e += rem;
-    if (rem >= dsx) then begin Inc(yd); e -= dx2; end;
-  end;
-
-  (*
-  if (y1 > wy1) then
+  if (xwalk <= ywalk) then wklen := xwalk else wklen := ywalk;
+  while true do
   begin
-    // clip at bottom
-    temp := dx2*(wy1-y0)+dsx;
-    term := x0+temp div dy2;
-    rem := temp mod dy2;
-    if (rem = 0) then Dec(term);
+    // in which dir we want to walk?
+    stleft -= wklen;
+    if (stleft <= 0) then begin result := true; exit; end;
+    if horiz then
+    begin
+      xd += wklen*stx;
+      for f := 1 to wklen do
+      begin
+        err += errinc;
+        if (err >= 0) then begin err -= errmax; yd += sty; end;
+      end;
+    end
+    else
+    begin
+      yd += wklen*sty;
+      for f := 1 to wklen do
+      begin
+        err += errinc;
+        if (err >= 0) then begin err -= errmax; xd += stx; end;
+      end;
+    end;
+    // check for walk completion
+    if (xd = ex) or (yd = ey) then exit;
+    wklen := 1;
   end;
-
-  if (term > wx1) then term := wx1; // clip at right
-
-  Inc(term); // draw last point
-  //if (term = xd) then exit; // this is the only point, get out of here
-  *)
-
-  if (sty = -1) then yd := -yd;
-  if (stx = -1) then begin xd := -xd; {!term := -term;} end;
-  //!dx2 -= dy2;
-
-  inx := d0^;
-  iny := d1^;
-  result := true;
 end;
 
+procedure TLineWalker.getXY (out ox, oy: Integer); inline; begin ox := xd; oy := yd; end;
+
 
 // ////////////////////////////////////////////////////////////////////////// //
 function sweepAABB (mex0, mey0, mew, meh: Integer; medx, medy: Integer; itx0, ity0, itw, ith: Integer;
@@ -935,7 +861,7 @@ begin
   mProxyFree := 0;
   mProxyCount := 0;
   mProxyMaxCount := 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);
+  e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), TMsgType.Notify);
 end;
 
 
@@ -965,7 +891,7 @@ begin
     end;
     if (mcb < cnt) then mcb := cnt;
   end;
-  e_WriteLog(Format('grid size: %dx%d (tile size: %d); pix: %dx%d; used cells: %d; max bodies in cell: %d; max proxies allocated: %d; proxies used: %d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize, mUsedCells, mcb, mProxyMaxCount, mProxyCount]), MSG_NOTIFY);
+  e_WriteLog(Format('grid size: %dx%d (tile size: %d); pix: %dx%d; used cells: %d; max bodies in cell: %d; max proxies allocated: %d; proxies used: %d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize, mUsedCells, mcb, mProxyMaxCount, mProxyCount]), TMsgType.Notify);
 end;
 
 
@@ -1198,8 +1124,9 @@ end;
 // ////////////////////////////////////////////////////////////////////////// //
 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
 var
-  gx, gy: Integer;
   gw, gh: Integer;
+  ex, ey: Integer;
+  gx, gy: Integer;
 begin
   result := false;
   if (w < 1) or (h < 1) or not assigned(cb) then exit;
@@ -1210,16 +1137,22 @@ begin
   if (x+w <= 0) or (y+h <= 0) then exit;
   gw := mWidth;
   gh := mHeight;
-  //tsize := mTileSize;
   if (x >= gw*mTileSize) or (y >= gh*mTileSize) then exit;
-  for gy := y div mTileSize to (y+h-1) div mTileSize do
-  begin
-    if (gy < 0) then continue;
-    if (gy >= gh) then break;
-    for gx := x div mTileSize to (x+w-1) div mTileSize do
+  ex := (x+w-1) div mTileSize;
+  ey := (y+h-1) div mTileSize;
+  x := x div mTileSize;
+  y := y div mTileSize;
+  // clip rect
+  if (x < 0) then x := 0 else if (x >= gw) then x := gw-1;
+  if (y < 0) then y := 0 else if (y >= gh) then y := gh-1;
+  if (ex < 0) then ex := 0 else if (ex >= gw) then ex := gw-1;
+  if (ey < 0) then ey := 0 else if (ey >= gh) then ey := gh-1;
+  if (x > ex) or (y > ey) then exit; // just in case
+  // do the work
+  for gy := y to ey do
+  begin
+    for gx := x to ex do
     begin
-      if (gx < 0) then continue;
-      if (gx >= gw) then break;
       result := cb(gy*gw+gx, bodyId);
       if result then exit;
     end;
@@ -1286,15 +1219,6 @@ begin
   mGrid[grida] := ccidx;
 end;
 
-procedure TBodyGridBase.insertInternal (body: TBodyProxyId);
-var
-  px: PBodyProxyRec;
-begin
-  if (body < 0) or (body > High(mProxies)) then exit; // just in case
-  px := @mProxies[body];
-  forGridRect(px.mX, px.mY, px.mWidth, px.mHeight, inserter, body);
-end;
-
 
 // assume that we cannot have one object added to bucket twice
 function TBodyGridBase.remover (grida: Integer; bodyId: TBodyProxyId): Boolean;
@@ -1337,29 +1261,25 @@ begin
   end;
 end;
 
-procedure TBodyGridBase.removeInternal (body: TBodyProxyId);
-var
-  px: PBodyProxyRec;
-begin
-  if (body < 0) or (body > High(mProxies)) then exit; // just in case
-  px := @mProxies[body];
-  forGridRect(px.mX, px.mY, px.mWidth, px.mHeight, remover, body);
-end;
-
 
 // ////////////////////////////////////////////////////////////////////////// //
 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
 begin
   aTag := aTag and TagFullMask;
   result := allocProxy(aX, aY, aWidth, aHeight, aObj, aTag);
-  insertInternal(result);
+  //insertInternal(result);
+  forGridRect(aX, aY, aWidth, aHeight, inserter, result);
 end;
 
 
 procedure TBodyGridBase.removeBody (body: TBodyProxyId);
+var
+  px: PBodyProxyRec;
 begin
   if (body < 0) or (body > High(mProxies)) then exit; // just in case
-  removeInternal(body);
+  px := @mProxies[body];
+  //removeInternal(body);
+  forGridRect(px.mX, px.mY, px.mWidth, px.mHeight, remover, body);
   freeProxy(body);
 end;
 
@@ -1388,15 +1308,18 @@ begin
   // did any corner crossed tile boundary?
   if (x0 div mTileSize <> nx div mTileSize) or
      (y0 div mTileSize <> ny div mTileSize) or
-     ((x0+w) div mTileSize <> (nx+nw) div mTileSize) or
-     ((y0+h) div mTileSize <> (ny+nh) div mTileSize) then
+     ((x0+w-1) div mTileSize <> (nx+nw-1) div mTileSize) or
+     ((y0+h-1) div mTileSize <> (ny+nh-1) div mTileSize) then
   begin
-    removeInternal(body);
+    //writeln('moveResizeBody: cell occupation changed! old=(', x0, ',', y0, ')-(', x0+w-1, ',', y0+h-1, '); new=(', nx, ',', ny, ')-(', nx+nw-1, ',', ny+nh-1, ')');
+    //removeInternal(body);
+    forGridRect(px.mX, px.mY, px.mWidth, px.mHeight, remover, body);
     px.mX := nx+mMinX;
     px.mY := ny+mMinY;
     px.mWidth := nw;
     px.mHeight := nh;
-    insertInternal(body);
+    //insertInternal(body);
+    forGridRect(px.mX, px.mY, nw, nh, inserter, body);
   end
   else
   begin
@@ -1407,6 +1330,7 @@ begin
   end;
 end;
 
+
 //TODO: optimize for horizontal/vertical moves
 procedure TBodyGridBase.moveBody (body: TBodyProxyId; nx, ny: Integer);
 var
@@ -1546,6 +1470,7 @@ begin
   px.mY := ny+mMinY;
 end;
 
+
 procedure TBodyGridBase.resizeBody (body: TBodyProxyId; nw, nh: Integer);
 var
   px: PBodyProxyRec;
@@ -1561,14 +1486,16 @@ begin
   {$IF DEFINED(D2F_DEBUG_MOVER)}
   e_WriteLog(Format('proxy #%d: RESIZE: xg=%d;yg=%d;w=%d;h=%d;nw=%d;nh=%d', [body, x0, y0, w, h, nw, nh]), MSG_NOTIFY);
   {$ENDIF}
-  if ((x0+w) div mTileSize <> (x0+nw) div mTileSize) or
-     ((y0+h) div mTileSize <> (y0+nh) div mTileSize) then
+  if ((x0+w-1) div mTileSize <> (x0+nw-1) div mTileSize) or
+     ((y0+h-1) div mTileSize <> (y0+nh-1) div mTileSize) then
   begin
     // crossed tile boundary, do heavy work
-    removeInternal(body);
+    //removeInternal(body);
+    forGridRect(px.mX, px.mY, px.mWidth, px.mHeight, remover, body);
     px.mWidth := nw;
     px.mHeight := nh;
-    insertInternal(body);
+    //insertInternal(body);
+    forGridRect(px.mX, px.mY, nw, nh, inserter, body);
   end
   else
   begin
@@ -1690,12 +1617,13 @@ function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tag
 var
   idx: Integer;
   gx, gy: Integer;
+  sx, sy, ex, ey: Integer;
   curci: Integer;
   f: Integer;
   cc: PGridCell = nil;
   px: PBodyProxyRec;
   lq: LongWord;
-  gw: Integer;
+  gw, gh: Integer;
   x0, y0: Integer;
   ptag: Integer;
 begin
@@ -1712,11 +1640,24 @@ begin
   Dec(y, mMinY);
 
   gw := mWidth;
-  //tsize := mTileSize;
+  gh := mHeight;
 
   if (x+w <= 0) or (y+h <= 0) then exit;
-  if (x >= gw*mTileSize) or (y >= mHeight*mTileSize) then exit;
+  if (x >= gw*mTileSize) or (y >= gh*mTileSize) then exit;
+
+  sx := x div mTileSize;
+  sy := y div mTileSize;
+  ex := (x+w-1) div mTileSize;
+  ey := (y+h-1) div mTileSize;
+
+  // clip rect
+  if (sx < 0) then sx := 0 else if (sx >= gw) then sx := gw-1;
+  if (sy < 0) then sy := 0 else if (sy >= gh) then sy := gh-1;
+  if (ex < 0) then ex := 0 else if (ex >= gw) then ex := gw-1;
+  if (ey < 0) then ey := 0 else if (ey >= gh) then ey := gh-1;
+  if (sx > ex) or (sy > ey) then exit; // just in case
 
+  // has something to do
   if mInQuery then raise Exception.Create('recursive queries aren''t supported');
   mInQuery := true;
 
@@ -1732,14 +1673,10 @@ begin
   lq := mLastQuery;
 
   // go on
-  for gy := y div mTileSize to (y+h-1) div mTileSize do
+  for gy := sy to ey do
   begin
-    if (gy < 0) then continue;
-    if (gy >= mHeight) then break;
-    for gx := x div mTileSize to (x+w-1) div mTileSize do
+    for gx := sx to ex do
     begin
-      if (gx < 0) then continue;
-      if (gx >= gw) then break;
       // process cells
       curci := mGrid[gy*gw+gx];
       while (curci <> -1) do
@@ -1749,7 +1686,7 @@ begin
         begin
           if (cc.bodies[f] = -1) then break;
           px := @mProxies[cc.bodies[f]];
-          // shit. has to do it this way, so i can change tag in callback
+          // shit! has to do it this way, so i can change tag in callback
           if (px.mQueryMark = lq) then continue;
           px.mQueryMark := lq;
           ptag := px.mTag;
@@ -2112,7 +2049,7 @@ end;
 // you are not supposed to understand this
 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
 var
-  lw, sweepw: TLineWalker;
+  lw: TLineWalker;
   ccidx: Integer;
   cc: PGridCell;
   px: PBodyProxyRec;
@@ -2145,10 +2082,12 @@ begin
   lw := TLineWalker.Create(0, 0, gw*mTileSize-1, gh*mTileSize-1);
   if not lw.setup(x0, y0, x1, y1) then exit; // out of screen
 
-  sweepw := TLineWalker.Create(0, 0, 1, 1); // doesn't matter, just shut ups the compiler
-
   lastDistSq := distanceSq(ax0, ay0, ax1, ay1)+1;
 
+  {$IF DEFINED(D2F_DEBUG)}
+  //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln('*** traceRay: (%s,%s)-(%s,%s)', [x0, y0, x1, y1]);
+  {$ENDIF}
+
   if mInQuery then raise Exception.Create('recursive queries aren''t supported');
   mInQuery := true;
 
@@ -2164,6 +2103,9 @@ begin
 
   repeat
     lw.getXY(cx, cy);
+    {$IF DEFINED(D2F_DEBUG)}
+    if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB(cx+mMinX, cy+mMinY);
+    {$ENDIF}
     // check tile
     ccidx := mGrid[(cy div mTileSize)*gw+(cx div mTileSize)];
     // process cells
@@ -2188,6 +2130,9 @@ begin
           py0 := px.mY-miny;
           px1 := px0+px.mWidth-1;
           py1 := py0+px.mHeight-1;
+          {$IF DEFINED(D2F_DEBUG)}
+          //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' cxy=(%s,%s); pan=(%s,%s)-(%s,%s)', [cx, cy, px0, py0, px1, py1]);
+          {$ENDIF}
           // inside?
           if firstCell and (x0 >= px0) and (y0 >= py0) and (x0 <= px1) and (y0 <= py1) then
           begin
@@ -2196,23 +2141,25 @@ begin
             ey := ay0;
             result := px.mObj;
             mInQuery := false;
+            {$IF DEFINED(D2F_DEBUG)}
+            if assigned(dbgRayTraceTileHitCB) then e_LogWriteln('  INSIDE!');
+            {$ENDIF}
             exit;
           end;
           // do line-vs-aabb test
-          sweepw.setClip(px0, py0, px1, py1);
-          if sweepw.setup(x0, y0, x1, y1) then
+          if lineAABBIntersects(x0, y0, x1, y1, px0, py0, px1-px0+1, py1-py0+1, hx, hy) then
           begin
             // hit detected
-            sweepw.getPrevXY(hx, hy);
             distSq := distanceSq(x0, y0, hx, hy);
+            {$IF DEFINED(D2F_DEBUG)}
+            //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln('  hit=(%s,%s); distSq=%s; lastDistSq=%s', [hx, hy, distSq, lastDistSq]);
+            {$ENDIF}
             if (distSq < lastDistSq) then
             begin
               lastDistSq := distSq;
               ex := hx+minx;
               ey := hy+miny;
               result := px.mObj;
-              // if this is not a first cell, get outta here
-              if not firstCell then begin mInQuery := false; exit; end;
               wasHit := true;
             end;
           end;
@@ -2406,7 +2353,8 @@ begin
     begin
       yd := wy0;
       e -= rem+dsx;
-      if (rem > 0) then begin Inc(xd); e += dy2; end;
+      //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
+      if (xd < wx0) then begin xd += 1; e += dy2; end; //???
       xfixed := true;
     end;
   end;