X-Git-Url: https://deadsoftware.ru/gitweb?a=blobdiff_plain;f=src%2Fgame%2Fg_map.pas;h=e439d17db2b9643ea8451966dc98354690f15be7;hb=9b63e74cbbb33cef5b1219c0afa82e43cfc40eeb;hp=2579d27fb143ab75fab9dab09da7e4d2a3a20c80;hpb=0a99955cc9ec0850709e5feb05cbefc47c441aff;p=d2df-sdl.git

diff --git a/src/game/g_map.pas b/src/game/g_map.pas
index 2579d27..e439d17 100644
--- a/src/game/g_map.pas
+++ b/src/game/g_map.pas
@@ -20,7 +20,7 @@ interface
 
 uses
   e_graphics, g_basic, MAPSTRUCT, g_textures, Classes,
-  g_phys, wadreader, BinEditor, g_panel, g_grid, md5, xprofiler;
+  g_phys, wadreader, BinEditor, g_panel, g_grid, z_aabbtree, md5, xprofiler;
 
 type
   TMapInfo = record
@@ -134,8 +134,11 @@ var
   BackID:  DWORD = DWORD(-1);
   gExternalResources: TStringList;
 
-  gdbg_map_use_grid_render: Boolean = true;
-  gdbg_map_use_grid_coldet: Boolean = true;
+  gdbg_map_use_accel_render: Boolean = true;
+  gdbg_map_use_accel_coldet: Boolean = true;
+  gdbg_map_use_tree_draw: Boolean = false;
+  gdbg_map_use_tree_coldet: Boolean = false;
+  gdbg_map_dump_coldet_tree_queries: Boolean = false;
   profMapCollision: TProfiler = nil; //WARNING: FOR DEBUGGING ONLY!
 
 implementation
@@ -145,7 +148,7 @@ uses
   GL, GLExt, g_weapons, g_game, g_sound, e_sound, CONFIG,
   g_options, MAPREADER, g_triggers, g_player, MAPDEF,
   Math, g_monsters, g_saveload, g_language, g_netmsg,
-  utils, sfs,
+  utils, sfs, binheap,
   ImagingTypes, Imaging, ImagingUtility,
   ImagingGif, ImagingNetworkGraphics;
 
@@ -154,16 +157,16 @@ const
   MUSIC_SIGNATURE = $4953554D; // 'MUSI'
   FLAG_SIGNATURE = $47414C46; // 'FLAG'
 
-  GridTagInvalid = -1;
-  GridTagWallDoor = 0;
-  GridTagBack = 1;
-  GridTagFore = 2;
-  GridTagWater = 3;
-  GridTagAcid1 = 4;
-  GridTagAcid2 = 5;
-  GridTagStep = 6;
-  GridTagLift = 7;
-  GridTagBlockMon = 8;
+  GridTagInvalid = 0;
+  GridTagWallDoor = $0001;
+  GridTagBack = $0002;
+  GridTagFore = $0004;
+  GridTagWater = $0008;
+  GridTagAcid1 = $0010;
+  GridTagAcid2 = $0020;
+  GridTagStep = $0040;
+  GridTagLift = $0080;
+  GridTagBlockMon = $0100;
 
 
 function panelTypeToTag (panelType: Word): Integer;
@@ -189,6 +192,26 @@ type
     PArrID: Integer;
   end;
 
+type
+  TDynAABBTreeMap = class(TDynAABBTree)
+    function getFleshAABB (var aabb: AABB2D; flesh: TTreeFlesh): Boolean; override;
+  end;
+
+function TDynAABBTreeMap.getFleshAABB (var aabb: AABB2D; flesh: TTreeFlesh): Boolean;
+var
+  pan: TPanel;
+begin
+  result := false;
+  if (flesh = nil) then begin aabb := AABB2D.Create(0, 0, 0, 0); exit; end;
+  pan := (flesh as TPanel);
+  aabb := AABB2D.Create(pan.X, pan.Y, pan.X+pan.Width, pan.Y+pan.Height);
+  if (pan.Width < 1) or (pan.Height < 1) then exit;
+  //if (pan.Width = 1) then aabb.maxX += 1;
+  //if (pan.Height = 1) then aabb.maxY += 1;
+  if not aabb.valid then raise Exception.Create('wutafuuuuuuu?!');
+  result := aabb.valid;
+end;
+
 var
   PanelById:     array of TPanelID;
   Textures:      TLevelTextureArray;
@@ -196,11 +219,12 @@ var
   FlagPoints:    Array [FLAG_RED..FLAG_BLUE] of PFlagPoint;
   //DOMFlagPoints: Array of TFlagPoint;
   gMapGrid: TBodyGrid = nil;
+  mapTree: TDynAABBTree = nil;
 
 
 procedure g_Map_ProfilersBegin ();
 begin
-  if (profMapCollision = nil) then profMapCollision := TProfiler.Create('MAP COLLISION');
+  if (profMapCollision = nil) then profMapCollision := TProfiler.Create('MAP COLLISION', g_profile_history_size);
   profMapCollision.mainBegin(g_profile_collision);
   // create sections
   if g_profile_collision then
@@ -427,6 +451,7 @@ begin
 
   panels^[len] := TPanel.Create(PanelRec, AddTextures, CurTex, Textures);
   panels^[len].ArrIdx := len;
+  panels^[len].tag := panelTypeToTag(PanelRec.PanelType);
   if sav then
     panels^[len].SaveIt := True;
 
@@ -983,13 +1008,17 @@ var
     tag := panelTypeToTag(tag);
     for idx := High(panels) downto 0 do
     begin
+      panels[idx].tag := tag;
       gMapGrid.insertBody(panels[idx], panels[idx].X, panels[idx].Y, panels[idx].Width, panels[idx].Height, tag);
+      mapTree.insertObject(panels[idx], tag, true); // as static object
     end;
   end;
 
 begin
   gMapGrid.Free();
   gMapGrid := nil;
+  mapTree.Free();
+  mapTree := nil;
 
   fixMinMax(gWalls);
   fixMinMax(gRenderBackgrounds);
@@ -1008,6 +1037,7 @@ begin
   end;
 
   gMapGrid := TBodyGrid.Create(mapX0, mapY0, mapX1-mapX0+1, mapY1-mapY0+1);
+  mapTree := TDynAABBTreeMap.Create();
 
   addPanelsToGrid(gWalls, PANEL_WALL); // and PANEL_CLOSEDOOR
   addPanelsToGrid(gRenderBackgrounds, PANEL_BACK);
@@ -1020,6 +1050,8 @@ begin
   addPanelsToGrid(gBlockMon, PANEL_BLOCKMON);
 
   gMapGrid.dumpStats();
+  e_WriteLog(Format('tree depth: %d; %d nodes used, %d nodes allocated', [mapTree.computeTreeHeight, mapTree.nodeCount, mapTree.nodeAlloced]), MSG_NOTIFY);
+  mapTree.forEachLeaf(nil);
 end;
 
 function g_Map_Load(Res: String): Boolean;
@@ -1056,6 +1088,8 @@ var
 begin
   gMapGrid.Free();
   gMapGrid := nil;
+  mapTree.Free();
+  mapTree := nil;
 
   Result := False;
   gMapInfo.Map := Res;
@@ -1869,8 +1903,8 @@ var
     pan: TPanel;
   begin
     result := false; // don't stop, ever
+    //e_WriteLog(Format('  *body: tag:%d; ptag:%d; pantype=%d', [tag, ptag, PanelType]), MSG_NOTIFY);
     if (tag <> ptag) then exit;
-    //e_WriteLog(Format('  *body: tag:%d; qtag:%d', [tag, PanelType]), MSG_NOTIFY);
 
     if obj = nil then begin e_WriteLog(Format('  !bodyFUUUUU0: tag:%d; qtag:%d', [tag, PanelType]), MSG_NOTIFY); exit; end;
     if not (obj is TPanel) then begin e_WriteLog(Format('  !bodyFUUUUU1: tag:%d; qtag:%d', [tag, PanelType]), MSG_NOTIFY); exit; end;
@@ -1915,9 +1949,16 @@ begin
   dplClear();
   ptag := panelTypeToTag(PanelType);
 
-  if gdbg_map_use_grid_render then
+  if gdbg_map_use_accel_render then
   begin
-    gMapGrid.forEachInAABB(x0, y0, wdt, hgt, checker);
+    if gdbg_map_use_tree_draw then
+    begin
+      mapTree.aabbQuery(x0, y0, wdt, hgt, checker, ptag);
+    end
+    else
+    begin
+      gMapGrid.forEachInAABB(x0, y0, wdt, hgt, checker, ptag);
+    end;
     // sort and draw the list (we need to sort it, or rendering is fucked)
     while gDrawPanelList.count > 0 do
     begin
@@ -1956,7 +1997,14 @@ procedure g_Map_DrawPanelShadowVolumes(lightX: Integer; lightY: Integer; radius:
   end;
 
 begin
-  gMapGrid.forEachInAABB(lightX-radius, lightY-radius, radius*2, radius*2, checker);
+  if gdbg_map_use_tree_draw then
+  begin
+    mapTree.aabbQuery(lightX-radius, lightY-radius, radius*2, radius*2, checker, GridTagWallDoor);
+  end
+  else
+  begin
+    gMapGrid.forEachInAABB(lightX-radius, lightY-radius, radius*2, radius*2, checker, GridTagWallDoor);
+  end;
 end;
 
 
@@ -2215,18 +2263,27 @@ function g_Map_CollidePanel(X, Y: Integer; Width, Height: Word; PanelType: Word;
 begin
   //TODO: detailed profile
   if (profMapCollision <> nil) then profMapCollision.sectionBeginAccum('wall coldet');
-  try
-    if gdbg_map_use_grid_coldet then
+  if gdbg_map_use_accel_coldet then
+  begin
+    if gdbg_map_use_tree_coldet then
     begin
-      result := gMapGrid.forEachInAABB(X, Y, Width, Height, checker);
+      result := (mapTree.aabbQuery(X, Y, Width, Height, checker, (GridTagWallDoor or GridTagWater or GridTagAcid1 or GridTagAcid2 or GridTagStep or GridTagLift or GridTagBlockMon)) <> nil);
+      if (gdbg_map_dump_coldet_tree_queries) and (mapTree.nodesVisited <> 0) then
+      begin
+        //e_WriteLog(Format('map collision: %d nodes visited (%d deep)', [mapTree.nodesVisited, mapTree.nodesDeepVisited]), MSG_NOTIFY);
+        g_Console_Add(Format('map collision: %d nodes visited (%d deep)', [mapTree.nodesVisited, mapTree.nodesDeepVisited]));
+      end;
     end
     else
     begin
-      result := g_Map_CollidePanelOld(X, Y, Width, Height, PanelType, b1x3);
+      result := gMapGrid.forEachInAABB(X, Y, Width, Height, checker, (GridTagWallDoor or GridTagWater or GridTagAcid1 or GridTagAcid2 or GridTagStep or GridTagLift or GridTagBlockMon));
     end;
-  finally
-    if (profMapCollision <> nil) then profMapCollision.sectionEnd();
+  end
+  else
+  begin
+    result := g_Map_CollidePanelOld(X, Y, Width, Height, PanelType, b1x3);
   end;
+  if (profMapCollision <> nil) then profMapCollision.sectionEnd();
 end;
 
 
@@ -2242,6 +2299,7 @@ var
     a: Integer;
   begin
     result := false; // don't stop, ever
+    if (tag <> GridTagWater) and (tag <> GridTagAcid1) and (tag <> GridTagAcid2) then exit;
     pan := (obj as TPanel);
     a := pan.ArrIdx;
     // water
@@ -2279,20 +2337,24 @@ var
 begin
   //TODO: detailed profile?
   if (profMapCollision <> nil) then profMapCollision.sectionBeginAccum('liquid coldet');
-  try
-    if gdbg_map_use_grid_coldet then
+  if gdbg_map_use_accel_coldet then
+  begin
+    texid := TEXTURE_NONE;
+    if gdbg_map_use_tree_coldet then
     begin
-      texid := TEXTURE_NONE;
-      gMapGrid.forEachInAABB(X, Y, Width, Height, checker);
-      result := texid;
+      mapTree.aabbQuery(X, Y, Width, Height, checker, (GridTagWater or GridTagAcid1 or GridTagAcid2));
     end
     else
     begin
-      result := g_Map_CollideLiquid_TextureOld(X, Y, Width, Height);
+      gMapGrid.forEachInAABB(X, Y, Width, Height, checker, (GridTagWater or GridTagAcid1 or GridTagAcid2));
     end;
-  finally
-    if (profMapCollision <> nil) then profMapCollision.sectionEnd();
+    result := texid;
+  end
+  else
+  begin
+    result := g_Map_CollideLiquid_TextureOld(X, Y, Width, Height);
   end;
+  if (profMapCollision <> nil) then profMapCollision.sectionEnd();
 end;
 
 procedure g_Map_EnableWall(ID: DWORD);