DEADSOFTWARE

alot of debugging code
[d2df-sdl.git] / src / game / g_monsters.pas
index 0d8f3841d1eab4f1127def30e016d7eabdd7852b..719a2b759d9da4b136d3c97275d411f187963cae 100644 (file)
@@ -19,8 +19,8 @@ unit g_monsters;
 interface
 
 uses
-  g_basic, e_graphics, g_phys, g_textures,
-  g_saveload, BinEditor, g_panel;
+  g_basic, e_graphics, g_phys, g_textures, g_grid,
+  g_saveload, BinEditor, g_panel, xprofiler;
 
 const
   MONSTATE_SLEEP  = 0;
@@ -80,6 +80,15 @@ type
     FFireAttacker: Word;
     vilefire: TAnimation;
 
+  {$IF DEFINED(D2F_DEBUG)}
+  public
+  {$ENDIF}
+    proxyId: Integer; // node in dyntree or -1
+    arrIdx: Integer; // in gMonsters
+  {$IF DEFINED(D2F_DEBUG)}
+  private
+  {$ENDIF}
+
     FDieTriggers: Array of Integer;
     FSpawnTrigger: Integer;
 
@@ -90,6 +99,7 @@ type
   public
     FNoRespawn: Boolean;
     FFireTime: Integer;
+    trapCheckFrameId: DWord; // for `g_weapons.CheckTrap()`
 
     constructor Create(MonsterType: Byte; aID: Integer; ForcedUID: Integer = -1);
     destructor Destroy(); override;
@@ -130,6 +140,8 @@ type
 
     procedure positionChanged (); //WARNING! call this after monster position was changed, or coldet will not work right!
 
+    procedure getMapBox (out x, y, w, h: Integer); inline;
+
     property MonsterType: Byte read FMonsterType;
     property MonsterHealth: Integer read FHealth write FHealth;
     property MonsterAmmo: Integer read FAmmo write FAmmo;
@@ -157,25 +169,79 @@ type
     property StartID: Integer read FStartID;
   end;
 
-procedure g_Monsters_LoadData();
-procedure g_Monsters_FreeData();
-procedure g_Monsters_Init();
-procedure g_Monsters_Free();
-function  g_Monsters_Create(MonsterType: Byte; X, Y: Integer;
-            Direction: TDirection; AdjCoord: Boolean = False; ForcedUID: Integer = -1): Integer;
-procedure g_Monsters_Update();
-procedure g_Monsters_Draw();
-procedure g_Monsters_DrawHealth();
-function  g_Monsters_Get(UID: Word): TMonster;
-procedure g_Monsters_killedp();
-procedure g_Monsters_SaveState(var Mem: TBinMemoryWriter);
-procedure g_Monsters_LoadState(var Mem: TBinMemoryReader);
-function  g_Monsters_GetIDByName(name: String): Integer;
-function  g_Monsters_GetNameByID(MonsterType: Byte): String;
-function  g_Monsters_GetKilledBy(MonsterType: Byte): String;
+
+// will be called from map loader
+procedure g_Mons_InitTree (x, y, w, h: Integer);
+
+procedure g_Monsters_LoadData ();
+procedure g_Monsters_FreeData ();
+procedure g_Monsters_Init ();
+procedure g_Monsters_Free ();
+function g_Monsters_Create (MonsterType: Byte; X, Y: Integer; Direction: TDirection;
+  AdjCoord: Boolean = False; ForcedUID: Integer = -1): TMonster;
+procedure g_Monsters_Update ();
+procedure g_Monsters_Draw ();
+procedure g_Monsters_DrawHealth ();
+function  g_Monsters_ByUID (UID: Word): TMonster;
+procedure g_Monsters_killedp ();
+procedure g_Monsters_SaveState (var Mem: TBinMemoryWriter);
+procedure g_Monsters_LoadState (var Mem: TBinMemoryReader);
+function  g_Monsters_GetIDByName (name: String): Integer;
+function  g_Monsters_GetNameByID (MonsterType: Byte): String;
+function  g_Monsters_GetKilledBy (MonsterType: Byte): String;
+
+
+type
+  TEachMonsterCB = function (mon: TMonster): Boolean is nested; // return `true` to stop
+
+// throws on invalid uid
+function g_Mons_ByIdx (uid: Integer): TMonster; inline;
+
+// can return null
+function g_Mons_ByIdx_NC (uid: Integer): TMonster; inline;
+
+function g_Mons_IsAnyAliveAt (x, y: Integer; width, height: Integer): Boolean;
+
+function g_Mons_ForEach (cb: TEachMonsterCB): Boolean;
+function g_Mons_ForEachAlive (cb: TEachMonsterCB): Boolean;
+
+function g_Mons_ForEachAt (x, y: Integer; width, height: Integer; cb: TEachMonsterCB): Boolean;
+function g_Mons_ForEachAliveAt (x, y: Integer; width, height: Integer; cb: TEachMonsterCB): Boolean;
+
+function g_Mons_getNewTrapFrameId (): DWord;
+
+
+type
+  TMonsAlongLineCB = function (mon: TMonster; tag: Integer): Boolean is nested;
+
+function g_Mons_AlongLine (x0, y0, x1, y1: Integer; cb: TMonsAlongLineCB; log: Boolean=false): TMonster;
+
 
 var
-  gMonsters: array of TMonster;
+  gmon_debug_use_sqaccel: Boolean = true;
+
+
+//HACK!
+procedure g_Mons_ProfilersBegin ();
+procedure g_Mons_ProfilersEnd ();
+
+procedure g_Mons_LOS_Start (); inline;
+procedure g_Mons_LOS_End (); inline;
+
+var
+  profMonsLOS: TProfiler = nil; //WARNING: FOR DEBUGGING ONLY!
+
+
+type
+  TMonsterGrid = specialize TBodyGridBase<TMonster>;
+
+var
+  monsGrid: TMonsterGrid = nil;
+
+
+var
+  gmon_debug_think: Boolean = true;
+
 
 implementation
 
@@ -185,6 +251,95 @@ uses
   g_console, g_map, Math, SysUtils, g_menu, wadreader,
   g_language, g_netmsg;
 
+
+// ////////////////////////////////////////////////////////////////////////// //
+procedure g_Mons_ProfilersBegin ();
+begin
+  if (profMonsLOS = nil) then profMonsLOS := TProfiler.Create('LOS CALC', g_profile_history_size);
+  profMonsLOS.mainBegin(g_profile_los);
+  if g_profile_los then
+  begin
+    profMonsLOS.sectionBegin('loscalc');
+    profMonsLOS.sectionEnd();
+  end;
+end;
+
+procedure g_Mons_ProfilersEnd ();
+begin
+  if (profMonsLOS <> nil) and (g_profile_los) then profMapCollision.mainEnd();
+end;
+
+procedure g_Mons_LOS_Start (); inline;
+begin
+  profMonsLOS.sectionBeginAccum('loscalc');
+end;
+
+procedure g_Mons_LOS_End (); inline;
+begin
+  profMonsLOS.sectionEnd();
+end;
+
+
+// ////////////////////////////////////////////////////////////////////////// //
+var
+  monCheckTrapLastFrameId: DWord;
+
+
+procedure TMonster.getMapBox (out x, y, w, h: Integer); inline;
+begin
+  x := FObj.X+FObj.Rect.X;
+  y := FObj.Y+FObj.Rect.Y;
+  w := FObj.Rect.Width;
+  h := FObj.Rect.Height;
+end;
+
+
+// ////////////////////////////////////////////////////////////////////////// //
+function g_Mons_AlongLine (x0, y0, x1, y1: Integer; cb: TMonsAlongLineCB; log: Boolean=false): TMonster;
+begin
+  if not assigned(cb) then begin result := nil; exit; end;
+  result := monsGrid.forEachAlongLine(x0, y0, x1, y1, cb, -1, log);
+end;
+
+
+//WARNING! call this after monster position was changed, or coldet will not work right!
+procedure TMonster.positionChanged ();
+var
+  x, y: Integer;
+begin
+  {$IF DEFINED(D2F_DEBUG_MONS_MOVE)}
+  //e_WriteLog(Format('monster #%d(%u): pos=(%d,%d); rpos=(%d,%d)', [arrIdx, UID, FObj.X, FObj.Y, FObj.Rect.X, FObj.Rect.Y]), MSG_NOTIFY);
+  {$ENDIF}
+  if (proxyId = -1) then
+  begin
+    proxyId := monsGrid.insertBody(self, FObj.X+FObj.Rect.X, FObj.Y+FObj.Rect.Y, FObj.Rect.Width, FObj.Rect.Height);
+    {$IF DEFINED(D2F_DEBUG_MONS_MOVE)}
+    monsGrid.getBodyXY(proxyId, x, y);
+    e_WriteLog(Format('monster #%d(%u): inserted into the grid; proxyid=%d; x=%d; y=%d', [arrIdx, UID, proxyId, x, y]), MSG_NOTIFY);
+    {$ENDIF}
+  end
+  else
+  begin
+    monsGrid.getBodyXY(proxyId, x, y);
+    if (FObj.X+FObj.Rect.X = x) and (FObj.Y+FObj.Rect.Y = y) then exit; // nothing to do
+    {$IF DEFINED(D2F_DEBUG_MONS_MOVE)}e_WriteLog(Format('monster #%d(%u): updating tree; proxyid=%d; x=%d; y=%d', [arrIdx, UID, proxyId, x, y]), MSG_NOTIFY);{$ENDIF}
+
+    {$IF TRUE}
+    monsGrid.moveBody(proxyId, FObj.X+FObj.Rect.X, FObj.Y+FObj.Rect.Y);
+    {$ELSE}
+    monsGrid.removeBody(proxyId);
+    proxyId := monsGrid.insertBody(self, FObj.X+FObj.Rect.X, FObj.Y+FObj.Rect.Y, FObj.Rect.Width, FObj.Rect.Height);
+    {$ENDIF}
+
+    {$IF DEFINED(D2F_DEBUG_MONS_MOVE)}
+    monsGrid.getBodyXY(proxyId, x, y);
+    e_WriteLog(Format('monster #%d(%u): updated tree; proxyid=%d; x=%d; y=%d', [arrIdx, UID, proxyId, x, y]), MSG_NOTIFY);
+    {$ENDIF}
+  end;
+end;
+
+
+// ////////////////////////////////////////////////////////////////////////// //
 const
   ANIM_SLEEP   = 0;
   ANIM_GO      = 1;
@@ -385,6 +540,38 @@ const
   MAX_ATM = 89; // Âðåìÿ îæèäàíèÿ ïîñëå ïîòåðè öåëè
   MAX_SOUL = 512; // Îãðàíè÷åíèå Lost_Soul'îâ
 
+
+var
+  gMonsters: array of TMonster;
+  uidMap: array [0..65535] of TMonster; // monster knows it's index
+
+
+procedure clearUidMap ();
+var
+  idx: Integer;
+begin
+  for idx := 0 to High(uidMap) do uidMap[idx] := nil;
+end;
+
+
+function g_Mons_getNewTrapFrameId (): DWord;
+var
+  f: Integer;
+begin
+  Inc(monCheckTrapLastFrameId);
+  if monCheckTrapLastFrameId = 0 then
+  begin
+    // wraparound
+    monCheckTrapLastFrameId := 1;
+    for f := 0 to High(gMonsters) do
+    begin
+      if (gMonsters[f] <> nil) then gMonsters[f].trapCheckFrameId := 0;
+    end;
+  end;
+  result := monCheckTrapLastFrameId;
+end;
+
+
 var
   pt_x: Integer = 0;
   pt_xs: Integer = 1;
@@ -392,30 +579,34 @@ var
   pt_ys: Integer = 1;
   soulcount: Integer = 0;
 
-function FindMonster(): DWORD;
+
+function allocMonster(): DWORD;
 var
-  i: Integer;
+  i, olen: Integer;
 begin
-  if gMonsters <> nil then
-    for i := 0 to High(gMonsters) do
-      if gMonsters[i] = nil then
-      begin
-        Result := i;
-        Exit;
-      end;
-
-  if gMonsters = nil then
-    begin
-      SetLength(gMonsters, 32);
-      Result := 0;
-    end
-  else
+  for i := 0 to High(gMonsters) do
+  begin
+    if (gMonsters[i] = nil) then
     begin
-      Result := High(gMonsters) + 1;
-      SetLength(gMonsters, Length(gMonsters) + 32);
+      result := i;
+      exit;
     end;
+  end;
+
+  olen := Length(gMonsters);
+  if (olen = 0) then
+  begin
+    SetLength(gMonsters, 64);
+    result := 0;
+  end
+  else
+  begin
+    result := olen;
+    SetLength(gMonsters, Length(gMonsters)+32);
+  end;
 end;
 
+
 function IsFriend(a, b: Byte): Boolean;
 begin
   Result := True;
@@ -443,6 +634,7 @@ begin
   Result := False;
 end;
 
+
 function BehaviourDamage(SpawnerUID: Word; BH, SelfType: Byte): Boolean;
 var
   m: TMonster;
@@ -454,7 +646,7 @@ begin
   UIDType := g_GetUIDType(SpawnerUID);
   if UIDType = UID_MONSTER then
   begin
-    m := g_Monsters_Get(SpawnerUID);
+    m := g_Monsters_ByUID(SpawnerUID);
     if m = nil then Exit;
     MonsterType := m.FMonsterType;
   end;
@@ -472,6 +664,7 @@ begin
   end;
 end;
 
+
 function canShoot(m: Byte): Boolean;
 begin
   Result := False;
@@ -484,24 +677,45 @@ begin
   end;
 end;
 
-function isCorpse(o: PObj; immediately: Boolean): Integer;
+
+function isCorpse (o: PObj; immediately: Boolean): Integer;
+
+  function monsCollCheck (mon: TMonster; atag: Integer): Boolean;
+  begin
+    atag := atag; // shut up, fpc!
+    result := false; // don't stop
+    if (mon.FState = STATE_DEAD) and g_Obj_Collide(o, @mon.FObj) then
+    begin
+      case mon.FMonsterType of // Íå âîñêðåñèòü:
+        MONSTER_SOUL, MONSTER_PAIN, MONSTER_CYBER, MONSTER_SPIDER,
+        MONSTER_VILE, MONSTER_BARREL, MONSTER_ROBO: exit;
+      end;
+      // Îñòàëüíûõ ìîæíî âîñêðåñèòü
+      result := true;
+    end;
+  end;
+
 var
   a: Integer;
+  mon: TMonster;
 begin
-  Result := -1;
+  result := -1;
 
-// Åñëè íóæíà âåðîÿòíîñòü:
-  if not immediately then
-    if Random(8) <> 0 then
-      Exit;
-
-  if gMonsters = nil then
-    Exit;
+  // Åñëè íóæíà âåðîÿòíîñòü
+  if not immediately and (Random(8) <> 0) then exit;
 
-// Èùåì ìåðòâûõ ìîíñòðîâ ïîáëèçîñòè:
-  for a := 0 to High(gMonsters) do
-    if (gMonsters[a] <> nil) and (gMonsters[a].FState = STATE_DEAD) then
-      if g_Obj_Collide(o, @gMonsters[a].FObj) then
+  // Èùåì ìåðòâûõ ìîíñòðîâ ïîáëèçîñòè
+  if gmon_debug_use_sqaccel then
+  begin
+    mon := monsGrid.forEachInAABB(o.X+o.Rect.X, o.Y+o.Rect.Y, o.Rect.Width, o.Rect.Height, monsCollCheck);
+    if (mon <> nil) then result := mon.arrIdx;
+  end
+  else
+  begin
+    for a := 0 to High(gMonsters) do
+    begin
+      if (gMonsters[a] <> nil) and (gMonsters[a].FState = STATE_DEAD) and g_Obj_Collide(o, @gMonsters[a].FObj) then
+      begin
         case gMonsters[a].FMonsterType of // Íå âîñêðåñèòü:
           MONSTER_SOUL, MONSTER_PAIN, MONSTER_CYBER, MONSTER_SPIDER,
           MONSTER_VILE, MONSTER_BARREL, MONSTER_ROBO: Continue;
@@ -511,6 +725,9 @@ begin
               Exit;
             end;
         end;
+      end;
+    end;
+  end;
 end;
 
 procedure g_Monsters_LoadData();
@@ -750,6 +967,9 @@ begin
   g_Sound_CreateWADEx('SOUND_MONSTER_SPIDER_WALK', GameWAD+':MSOUNDS\SPIDER_WALK');
 
   g_Sound_CreateWADEx('SOUND_MONSTER_FISH_ATTACK', GameWAD+':MSOUNDS\FISH_ATTACK');
+
+  clearUidMap();
+  monCheckTrapLastFrameId := 0;
 end;
 
 procedure g_Monsters_FreeData();
@@ -977,48 +1197,63 @@ procedure g_Monsters_Free();
 var
   a: Integer;
 begin
-  if gMonsters <> nil then
-    for a := 0 to High(gMonsters) do
-      gMonsters[a].Free();
-
+  monsGrid.Free();
+  monsGrid := nil;
+  for a := 0 to High(gMonsters) do gMonsters[a].Free();
   gMonsters := nil;
+  clearUidMap();
+  monCheckTrapLastFrameId := 0;
+end;
+
+
+// will be called from map loader
+procedure g_Mons_InitTree (x, y, w, h: Integer);
+begin
+  monsGrid.Free();
+  monsGrid := TMonsterGrid.Create(x, y, w, h);
 end;
 
+
 function g_Monsters_Create(MonsterType: Byte; X, Y: Integer;
-           Direction: TDirection; AdjCoord: Boolean = False; ForcedUID: Integer = -1): Integer;
+           Direction: TDirection; AdjCoord: Boolean = False; ForcedUID: Integer = -1): TMonster;
 var
   find_id: DWORD;
+  mon: TMonster;
 begin
-  Result := -1;
+  result := nil;
 
-// Íåò òàêîãî ìîíñòðà:
-  if (MonsterType > MONSTER_MAN) or (MonsterType = 0) then
-    Exit;
+  // Íåò òàêîãî ìîíñòðà
+  if (MonsterType > MONSTER_MAN) or (MonsterType = 0) then exit;
 
-// Ñîáëþäàåì îãðàíè÷åíèå Lost_Soul'îâ:
+  // Ñîáëþäàåì îãðàíè÷åíèå Lost_Soul'îâ
   if MonsterType = MONSTER_SOUL then
-    if soulcount > MAX_SOUL then
-      Exit
-    else
-      soulcount := soulcount + 1;
+  begin
+    if soulcount > MAX_SOUL then exit;
+    soulcount := soulcount + 1;
+  end;
+
+  find_id := allocMonster();
 
-  find_id := FindMonster();
+  mon := TMonster.Create(MonsterType, find_id, ForcedUID);
+  gMonsters[find_id] := mon;
+  mon.arrIdx := find_id;
+  mon.proxyId := -1;
 
-  gMonsters[find_id] := TMonster.Create(MonsterType, find_id, ForcedUID);
+  uidMap[mon.FUID] := mon;
 
-// Íàñòðàèâàåì ïîëîæåíèå:
-  with gMonsters[find_id] do
+  // Íàñòðàèâàåì ïîëîæåíèå
+  with mon do
   begin
     if AdjCoord then
-      begin
-        FObj.X := X-FObj.Rect.X - (FObj.Rect.Width div 2);
-        FObj.Y := Y-FObj.Rect.Y - FObj.Rect.Height;
-      end
+    begin
+      FObj.X := X-FObj.Rect.X - (FObj.Rect.Width div 2);
+      FObj.Y := Y-FObj.Rect.Y - FObj.Rect.Height;
+    end
     else
-      begin
-        FObj.X := X-FObj.Rect.X;
-        FObj.Y := Y-FObj.Rect.Y;
-      end;
+    begin
+      FObj.X := X-FObj.Rect.X;
+      FObj.Y := Y-FObj.Rect.Y;
+    end;
 
     FDirection := Direction;
     FStartDirection := Direction;
@@ -1026,7 +1261,9 @@ begin
     FStartY := GameY;
   end;
 
-  Result := find_id;
+  mon.positionChanged();
+
+  result := mon;
 end;
 
 procedure g_Monsters_killedp();
@@ -1055,34 +1292,36 @@ procedure g_Monsters_Update();
 var
   a: Integer;
 begin
-// Öåëåóêàçàòåëü:
+  // Öåëåóêàçàòåëü
   if gTime mod (GAME_TICK*2) = 0 then
   begin
     pt_x := pt_x+pt_xs;
     pt_y := pt_y+pt_ys;
-    if Abs(pt_x) > 246 then
-      pt_xs := -pt_xs;
-    if Abs(pt_y) > 100 then
-      pt_ys := -pt_ys;
+    if abs(pt_x) > 246 then pt_xs := -pt_xs;
+    if abs(pt_y) > 100 then pt_ys := -pt_ys;
   end;
 
   gMon := True; // Äëÿ ðàáîòû BlockMon'à
 
-  if gMonsters <> nil then
+  if (gmon_debug_think) then
+  begin
     for a := 0 to High(gMonsters) do
-      if (gMonsters[a] <> nil) then
-        if not gMonsters[a].FRemoved then
-        begin
-          if g_Game_IsClient then
-            gMonsters[a].ClientUpdate()
-          else
-            gMonsters[a].Update();
-        end
+    begin
+      if (gMonsters[a] = nil) then continue;
+      if not gMonsters[a].FRemoved then
+      begin
+        if g_Game_IsClient then
+          gMonsters[a].ClientUpdate()
         else
-          begin
-            gMonsters[a].Free();
-            gMonsters[a] := nil;
-          end;
+          gMonsters[a].Update();
+      end
+      else
+      begin
+        gMonsters[a].Free();
+        gMonsters[a] := nil;
+      end;
+    end;
+  end;
 
   gMon := False;
 end;
@@ -1114,12 +1353,12 @@ begin
     end;
 end;
 
-function g_Monsters_Get(UID: Word): TMonster;
-var
-  a: Integer;
+function g_Monsters_ByUID (UID: Word): TMonster;
+//var a: Integer;
 begin
+  result := uidMap[UID];
+  {
   Result := nil;
-
   if gMonsters <> nil then
     for a := 0 to High(gMonsters) do
       if (gMonsters[a] <> nil) and
@@ -1128,6 +1367,7 @@ begin
         Result := gMonsters[a];
         Break;
       end;
+  }
 end;
 
 procedure g_Monsters_SaveState(var Mem: TBinMemoryWriter);
@@ -1172,39 +1412,35 @@ end;
 
 procedure g_Monsters_LoadState(var Mem: TBinMemoryReader);
 var
-  count, i, a: Integer;
+  count, a: Integer;
   b: Byte;
+  mon: TMonster;
 begin
-  if Mem = nil then
-    Exit;
+  if Mem = nil then exit;
 
   g_Monsters_Free();
 
-// Çàãðóæàåì èíôîðìàöèþ öåëåóêàçàòåëÿ:
+  // Çàãðóæàåì èíôîðìàöèþ öåëåóêàçàòåëÿ
   Mem.ReadInt(pt_x);
   Mem.ReadInt(pt_xs);
   Mem.ReadInt(pt_y);
   Mem.ReadInt(pt_ys);
 
-// Êîëè÷åñòâî ìîíñòðîâ:
+  // Êîëè÷åñòâî ìîíñòðîâ
   Mem.ReadInt(count);
 
-  if count = 0 then
-    Exit;
+  if count = 0 then exit;
 
-// Çàãðóæàåì ìîíñòðîâ:
+  // Çàãðóæàåì ìîíñòðîâ
   for a := 0 to count-1 do
   begin
-  // Òèï ìîíñòðà:
+    // Òèï ìîíñòðà
     Mem.ReadByte(b);
-  // Ñîçäàåì ìîíñòðà:
-    i := g_Monsters_Create(b, 0, 0, D_LEFT);
-    if i < 0 then
-    begin
-      raise EBinSizeError.Create('g_Monsters_LoadState: ID = -1 (Can''t create)');
-    end;
-  // Çàãðóæàåì äàííûå ìîíñòðà:
-    gMonsters[i].LoadState(Mem);
+    // Ñîçäàåì ìîíñòðà
+    mon := g_Monsters_Create(b, 0, 0, D_LEFT);
+    if mon = nil then raise EBinSizeError.Create('g_Monsters_LoadState: ID = -1 (Can''t create)');
+    // Çàãðóæàåì äàííûå ìîíñòðà
+    mon.LoadState(Mem);
   end;
 end;
 
@@ -1461,7 +1697,7 @@ end;
 constructor TMonster.Create(MonsterType: Byte; aID: Integer; ForcedUID: Integer = -1);
 var
   a: Integer;
-  FramesID: DWORD;
+  FramesID: DWORD = 0;
   s: String;
   res: Boolean;
 begin
@@ -1491,6 +1727,10 @@ begin
   FFirePainTime := 0;
   FFireAttacker := 0;
 
+  proxyId := -1;
+  arrIdx := -1;
+  trapCheckFrameId := 0;
+
   if FMonsterType in [MONSTER_ROBO, MONSTER_BARREL] then
     FBloodKind := BLOOD_SPARKS
   else
@@ -1640,8 +1880,7 @@ begin
   end;
 
 // Òåïåðü öåëü - óäàðèâøèé, åñëè òîëüêî íå ñàì ñåáÿ:
-  if (SpawnerUID <> FUID) and
-  (BehaviourDamage(SpawnerUID, FBehaviour, FMonsterType)) then
+  if (SpawnerUID <> FUID) and (BehaviourDamage(SpawnerUID, FBehaviour, FMonsterType)) then
   begin
     FTargetUID := SpawnerUID;
     FTargetTime := 0;
@@ -1688,8 +1927,8 @@ begin
         it := g_Items_Create(FObj.X + (FObj.Rect.Width div 2),
                              FObj.Y + (FObj.Rect.Height div 2),
                              c, True, False);
-        g_Obj_Push(@gItems[it].Obj, (FObj.Vel.X div 2)-3+Random(7),
-                                    (FObj.Vel.Y div 2)-Random(4));
+        g_Obj_Push(g_Items_ObjByIdx(it), (FObj.Vel.X div 2)-3+Random(7),
+                                        (FObj.Vel.Y div 2)-Random(4));
         positionChanged(); // this updates spatial accelerators
         if g_Game_IsServer and g_Game_IsNet then
           MH_SEND_ItemSpawn(True, it);
@@ -1747,8 +1986,7 @@ begin
   if FHealth < FMaxHealth then
   begin
     IncMax(FHealth, Value, FMaxHealth);
-    if g_Game_IsServer and g_Game_IsNet then
-      MH_SEND_MonsterState(FUID);
+    if g_Game_IsServer and g_Game_IsNet then MH_SEND_MonsterState(FUID);
     Result := True;
   end;
 end;
@@ -1765,6 +2003,23 @@ begin
 
   vilefire.Free();
 
+  if (proxyId <> -1) then
+  begin
+    if (monsGrid <> nil) then
+    begin
+      monsGrid.removeBody(proxyId);
+      {$IF DEFINED(D2F_DEBUG_MONS_MOVE)}
+      e_WriteLog(Format('monster #%d(%u): removed from tree; proxyid=%d', [arrIdx, UID, proxyId]), MSG_NOTIFY);
+      {$ENDIF}
+    end;
+    proxyId := -1;
+  end;
+
+  if (arrIdx <> -1) and (arrIdx < Length(gMonsters)) then gMonsters[arrIdx] := nil;
+  arrIdx := -1;
+
+  uidMap[FUID] := nil;
+
   inherited Destroy();
 end;
 
@@ -1869,8 +2124,7 @@ procedure TMonster.Push(vx, vy: Integer);
 begin
   FObj.Accel.X := FObj.Accel.X + vx;
   FObj.Accel.Y := FObj.Accel.Y + vy;
-  if g_Game_IsServer and g_Game_IsNet then
-    MH_SEND_MonsterPos(FUID);
+  if g_Game_IsServer and g_Game_IsNet then MH_SEND_MonsterPos(FUID);
 end;
 
 procedure TMonster.SetState(State: Byte; ForceAnim: Byte = 255);
@@ -1965,6 +2219,7 @@ begin
 
   FObj.X := X - FObj.Rect.X;
   FObj.Y := Y - FObj.Rect.Y;
+  positionChanged();
 
   if dir = 1 then
     FDirection := D_LEFT
@@ -1993,8 +2248,7 @@ begin
                     NET_GFX_TELE);
   end;
 
-  if g_Game_IsServer and g_Game_IsNet then
-    MH_SEND_MonsterPos(FUID);
+  if g_Game_IsServer and g_Game_IsNet then MH_SEND_MonsterPos(FUID);
   Result := True;
 end;
 
@@ -2004,6 +2258,7 @@ var
   st: Word;
   o, co: TObj;
   fall: Boolean;
+  mon: TMonster;
 label
   _end;
 begin
@@ -2378,8 +2633,7 @@ begin
                     if g_Obj_CollideLevel(@FObj, 0, 1) or g_Obj_StayOnStep(@FObj) then
                     begin // "Ñòîèò" òâåðäî
                     // Ðûáà òðåïûõàåòñÿ íà ïîâåðõíîñòè:
-                      if FObj.Accel.Y = 0 then
-                        FObj.Vel.Y := -6;
+                      if FObj.Accel.Y = 0 then FObj.Vel.Y := -6;
                       FObj.Accel.X := FObj.Accel.X - 8 + Random(17);
                     end;
 
@@ -2442,7 +2696,6 @@ begin
                   begin
                     g_Obj_PushA(@gGibs[a].Obj, b, Random(61));    // íàïðàâî
                   end;
-                  positionChanged(); // this updates spatial accelerators
                 end;
               end;
             end;
@@ -2681,36 +2934,37 @@ _end:
     // Pain_Elemental ïðè ñìåðòè âûïóñêàåò 3 Lost_Soul'à:
       if (FMonsterType = MONSTER_PAIN) then
       begin
-        sx := g_Monsters_Create(MONSTER_SOUL, FObj.X+FObj.Rect.X+(FObj.Rect.Width div 2)-30,
-                                FObj.Y+FObj.Rect.Y+20, D_LEFT);
-        if sx <> -1 then
+        mon := g_Monsters_Create(MONSTER_SOUL, FObj.X+FObj.Rect.X+(FObj.Rect.Width div 2)-30,
+                                 FObj.Y+FObj.Rect.Y+20, D_LEFT);
+        if mon <> nil then
         begin
-          gMonsters[sx].SetState(STATE_GO);
-          gMonsters[sx].FNoRespawn := True;
+          mon.SetState(STATE_GO);
+          mon.FNoRespawn := True;
           Inc(gTotalMonsters);
-          if g_Game_IsNet then MH_SEND_MonsterSpawn(gMonsters[sx].UID);
+          if g_Game_IsNet then MH_SEND_MonsterSpawn(mon.UID);
         end;
 
-        sx := g_Monsters_Create(MONSTER_SOUL, FObj.X+FObj.Rect.X+(FObj.Rect.Width div 2),
-                                FObj.Y+FObj.Rect.Y+20, D_RIGHT);
-        if sx <> -1 then
+        mon := g_Monsters_Create(MONSTER_SOUL, FObj.X+FObj.Rect.X+(FObj.Rect.Width div 2),
+                                 FObj.Y+FObj.Rect.Y+20, D_RIGHT);
+        if mon <> nil then
         begin
-          gMonsters[sx].SetState(STATE_GO);
-          gMonsters[sx].FNoRespawn := True;
+          mon.SetState(STATE_GO);
+          mon.FNoRespawn := True;
           Inc(gTotalMonsters);
-          if g_Game_IsNet then MH_SEND_MonsterSpawn(gMonsters[sx].UID);
+          if g_Game_IsNet then MH_SEND_MonsterSpawn(mon.UID);
         end;
 
-        sx := g_Monsters_Create(MONSTER_SOUL, FObj.X+FObj.Rect.X+(FObj.Rect.Width div 2)-15,
-                                FObj.Y+FObj.Rect.Y, D_RIGHT);
-        if sx <> -1 then
+        mon := g_Monsters_Create(MONSTER_SOUL, FObj.X+FObj.Rect.X+(FObj.Rect.Width div 2)-15,
+                                 FObj.Y+FObj.Rect.Y, D_RIGHT);
+        if mon <> nil then
         begin
-          gMonsters[sx].SetState(STATE_GO);
-          gMonsters[sx].FNoRespawn := True;
+          mon.SetState(STATE_GO);
+          mon.FNoRespawn := True;
           Inc(gTotalMonsters);
-          if g_Game_IsNet then MH_SEND_MonsterSpawn(gMonsters[sx].UID);
+          if g_Game_IsNet then MH_SEND_MonsterSpawn(mon.UID);
         end;
-        if g_Game_IsNet then MH_SEND_CoopStats(gMonsters[sx].UID);
+
+        if g_Game_IsNet then MH_SEND_CoopStats();
       end;
 
     // Ó ýòèõ ìîíñòðîâ íåò òðóïîâ:
@@ -2870,20 +3124,20 @@ _end:
                   g_Weapon_ball2(wx, wy, tx, ty, FUID);
                 MONSTER_PAIN:
                   begin // Ñîçäàåì Lost_Soul:
-                    sx := g_Monsters_Create(MONSTER_SOUL, FObj.X+(FObj.Rect.Width div 2),
-                                            FObj.Y+FObj.Rect.Y, FDirection);
+                    mon := g_Monsters_Create(MONSTER_SOUL, FObj.X+(FObj.Rect.Width div 2),
+                                             FObj.Y+FObj.Rect.Y, FDirection);
 
-                    if sx <> -1 then
+                    if mon <> nil then
                     begin // Öåëü - öåëü Pain_Elemental'à. Ëåòèì ê íåé:
-                      gMonsters[sx].FTargetUID := FTargetUID;
+                      mon.FTargetUID := FTargetUID;
                       GetPos(FTargetUID, @o);
-                      gMonsters[sx].FTargetTime := 0;
-                      gMonsters[sx].FNoRespawn := True;
-                      gMonsters[sx].SetState(STATE_GO);
-                      gMonsters[sx].shoot(@o, True);
+                      mon.FTargetTime := 0;
+                      mon.FNoRespawn := True;
+                      mon.SetState(STATE_GO);
+                      mon.shoot(@o, True);
                       Inc(gTotalMonsters);
 
-                      if g_Game_IsNet then MH_SEND_MonsterSpawn(gMonsters[sx].UID);
+                      if g_Game_IsNet then MH_SEND_MonsterSpawn(mon.UID);
                     end;
                   end;
               end;
@@ -4213,8 +4467,7 @@ procedure TMonster.CatchFire(Attacker: Word);
 begin
   FFireTime := 100;
   FFireAttacker := Attacker;
-  if g_Game_IsNet and g_Game_IsServer then
-    MH_SEND_MonsterState(FUID);
+  if g_Game_IsNet and g_Game_IsServer then MH_SEND_MonsterState(FUID);
 end;
 
 procedure TMonster.OnFireFlame(Times: DWORD = 1);
@@ -4238,9 +4491,174 @@ begin
   end;
 end;
 
-//WARNING! call this after monster position was changed, or coldet will not work right!
-procedure TMonster.positionChanged ();
+
+// ////////////////////////////////////////////////////////////////////////// //
+// throws on invalid uid
+function g_Mons_ByIdx (uid: Integer): TMonster; inline;
 begin
+  result := g_Mons_ByIdx_NC(uid);
+  if (result = nil) then raise Exception.Create('g_Mons_ByIdx: invalid monster id');
 end;
 
+
+// can return null
+function g_Mons_ByIdx_NC (uid: Integer): TMonster; inline;
+begin
+  if (uid < 0) or (uid > High(gMonsters)) then begin result := nil; exit; end;
+  result := gMonsters[uid];
+end;
+
+
+function g_Mons_ForEach (cb: TEachMonsterCB): Boolean;
+var
+  idx: Integer;
+  mon: TMonster;
+begin
+  result := false;
+  if (gMonsters = nil) or not assigned(cb) then exit;
+  for idx := 0 to High(gMonsters) do
+  begin
+    mon := gMonsters[idx];
+    if (mon <> nil) then
+    begin
+      result := cb(mon);
+      if result then exit;
+    end;
+  end;
+end;
+
+
+function g_Mons_ForEachAlive (cb: TEachMonsterCB): Boolean;
+var
+  idx: Integer;
+  mon: TMonster;
+begin
+  result := false;
+  if (gMonsters = nil) or not assigned(cb) then exit;
+  for idx := 0 to High(gMonsters) do
+  begin
+    mon := gMonsters[idx];
+    if (mon <> nil) and mon.Live then
+    begin
+      result := cb(mon);
+      if result then exit;
+    end;
+  end;
+end;
+
+
+function g_Mons_IsAnyAliveAt (x, y: Integer; width, height: Integer): Boolean;
+
+  function monsCollCheck (mon: TMonster; atag: Integer): Boolean;
+  begin
+    result := mon.Live;// and g_Obj_Collide(x, y, width, height, @mon.Obj));
+  end;
+
+var
+  idx: Integer;
+  mon: TMonster;
+begin
+  result := false;
+  if (width < 1) or (height < 1) then exit;
+  if gmon_debug_use_sqaccel then
+  begin
+    result := (monsGrid.forEachInAABB(x, y, width, height, monsCollCheck) <> nil);
+  end
+  else
+  begin
+    for idx := 0 to High(gMonsters) do
+    begin
+      mon := gMonsters[idx];
+      if (mon <> nil) and mon.Live then
+      begin
+        if g_Obj_Collide(x, y, width, height, @mon.Obj) then
+        begin
+          result := true;
+          exit;
+        end;
+      end;
+    end;
+  end;
+end;
+
+
+function g_Mons_ForEachAt (x, y: Integer; width, height: Integer; cb: TEachMonsterCB): Boolean;
+
+  function monsCollCheck (mon: TMonster; atag: Integer): Boolean;
+  begin
+    result := cb(mon);
+  end;
+
+var
+  idx: Integer;
+  mon: TMonster;
+begin
+  result := false;
+  if (width < 1) or (height < 1) then exit;
+  if gmon_debug_use_sqaccel then
+  begin
+    result := (monsGrid.forEachInAABB(x, y, width, height, monsCollCheck) <> nil);
+  end
+  else
+  begin
+    for idx := 0 to High(gMonsters) do
+    begin
+      mon := gMonsters[idx];
+      if (mon <> nil) and mon.Live then
+      begin
+        if g_Obj_Collide(x, y, width, height, @mon.Obj) then
+        begin
+          result := cb(mon);
+          if result then exit;
+        end;
+      end;
+    end;
+  end;
+end;
+
+
+function g_Mons_ForEachAliveAt (x, y: Integer; width, height: Integer; cb: TEachMonsterCB): Boolean;
+
+  function monsCollCheck (mon: TMonster; atag: Integer): Boolean;
+  begin
+    //result := false;
+    //if mon.Live and g_Obj_Collide(x, y, width, height, @mon.Obj) then result := cb(mon);
+    if mon.Live then result := cb(mon) else result := false;
+  end;
+
+var
+  idx: Integer;
+  mon: TMonster;
+begin
+  result := false;
+  if (width < 1) or (height < 1) then exit;
+  if gmon_debug_use_sqaccel then
+  begin
+    if (width = 1) and (height = 1) then
+    begin
+      result := (monsGrid.forEachAtPoint(x, y, monsCollCheck) <> nil);
+    end
+    else
+    begin
+      result := (monsGrid.forEachInAABB(x, y, width, height, monsCollCheck) <> nil);
+    end;
+  end
+  else
+  begin
+    for idx := 0 to High(gMonsters) do
+    begin
+      mon := gMonsters[idx];
+      if (mon <> nil) and mon.Live then
+      begin
+        if g_Obj_Collide(x, y, width, height, @mon.Obj) then
+        begin
+          result := cb(mon);
+          if result then exit;
+        end;
+      end;
+    end;
+  end;
+end;
+
+
 end.