From: Ketmar Dark Date: Thu, 17 Aug 2017 18:25:12 +0000 (+0300) Subject: Sweep-And-Prune broad phase implementation; not working yet X-Git-Url: http://deadsoftware.ru/gitweb?p=d2df-sdl.git;a=commitdiff_plain;h=e27a7539a5cd40fb3a15c6daef0e18817b7c9bd8 Sweep-And-Prune broad phase implementation; not working yet --- diff --git a/src/game/Doom2DF.dpr b/src/game/Doom2DF.dpr index e6f4740..3980b1b 100644 --- a/src/game/Doom2DF.dpr +++ b/src/game/Doom2DF.dpr @@ -70,6 +70,8 @@ uses g_nethandler in 'g_nethandler.pas', g_netmaster in 'g_netmaster.pas', g_res_downloader in 'g_res_downloader.pas', + g_grid in 'g_grid.pas', + g_sap in 'g_sap.pas', g_game in 'g_game.pas', g_gfx in 'g_gfx.pas', g_gui in 'g_gui.pas', @@ -96,6 +98,7 @@ uses fmodtypes in '../lib/FMOD/fmodtypes.pas', {$ENDIF} xprofiler in '../shared/xprofiler.pas', + binheap in '../shared/binheap.pas', BinEditor in '../shared/BinEditor.pas', envvars in '../shared/envvars.pas', g_panel in 'g_panel.pas', diff --git a/src/game/g_console.pas b/src/game/g_console.pas index 0231729..c41cb23 100644 --- a/src/game/g_console.pas +++ b/src/game/g_console.pas @@ -394,6 +394,9 @@ begin AddCommand('r_gridrender', ProfilerCommands); AddCommand('dbg_coldet_grid', ProfilerCommands); + AddCommand('sq_use_grid', ProfilerCommands); + AddCommand('sq_use_sap', ProfilerCommands); + AddCommand('p1_name', GameCVars); AddCommand('p2_name', GameCVars); AddCommand('p1_color', GameCVars); diff --git a/src/game/g_game.pas b/src/game/g_game.pas index cc97e4c..802425a 100644 --- a/src/game/g_game.pas +++ b/src/game/g_game.pas @@ -475,7 +475,7 @@ function drawProfiles (x, y: Integer; prof: TProfiler): Integer; var wdt, hgt: Integer; yy: Integer; - ii, idx: Integer; + ii: Integer; begin result := 0; if (prof = nil) then exit; @@ -5017,21 +5017,25 @@ var begin //if not gDebugMode then exit; cmd := LowerCase(P[0]); + if cmd = 'dpp' then begin g_profile_frame_draw := not g_profile_frame_draw; exit; end; + if cmd = 'dpu' then begin g_profile_frame_update := not g_profile_frame_update; exit; end; + if cmd = 'dpc' then begin g_profile_collision := not g_profile_collision; exit; end; + if cmd = 'r_gridrender' then begin case getBool(1) of @@ -5042,6 +5046,7 @@ begin if gdbg_map_use_grid_render then g_Console_Add('grid rendering: tan') else g_Console_Add('grid rendering: ona'); exit; end; + if cmd = 'dbg_coldet_grid' then begin case getBool(1) of @@ -5052,6 +5057,17 @@ begin if gdbg_map_use_grid_coldet then g_Console_Add('grid coldet: tan') else g_Console_Add('grid coldet: ona'); exit; end; + + if (cmd = 'sq_use_grid') or (cmd = 'sq_use_sap') then + 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'); + end; + if gdbg_map_use_sap then g_Console_Add('coldet: sap') else g_Console_Add('coldet: grid'); + exit; + end; end; procedure DebugCommands(P: SArray); diff --git a/src/game/g_grid.pas b/src/game/g_grid.pas index aeeba59..56d8ecb 100644 --- a/src/game/g_grid.pas +++ b/src/game/g_grid.pas @@ -13,13 +13,12 @@ * You should have received a copy of the GNU General Public License * along with this program. If not, see . *) +// universal spatial grid {$INCLUDE ../shared/a_modes.inc} unit g_grid; interface -uses e_log; - const GridDefaultTileSize = 32; @@ -73,7 +72,7 @@ type mGrid: array of Integer; // mWidth*mHeight, index in mCells mCells: array of TGridCell; // cell pool mFreeCell: Integer; // first free cell index or -1 - mLastQuery: Integer; + mLastQuery: DWord; mUsedCells: Integer; mProxies: array of TBodyProxyRec; mProxyFree: TBodyProxy; // free @@ -111,55 +110,13 @@ type end; -type - TBinaryHeapLessFn = function (a, b: TObject): Boolean; - - TBinaryHeapObj = class(TObject) - private - elem: array of TObject; - elemUsed: Integer; - lessfn: TBinaryHeapLessFn; - - private - procedure heapify (root: Integer); - - public - constructor Create (alessfn: TBinaryHeapLessFn); - destructor Destroy (); override; - - procedure clear (); - - procedure insert (val: TObject); - - function front (): TObject; - procedure popFront (); - - property count: Integer read elemUsed; - end; - - implementation uses - SysUtils; + SysUtils, e_log; // ////////////////////////////////////////////////////////////////////////// // -(* -constructor TBodyProxy.Create (aGrid: TBodyGrid; aX, aY, aWidth, aHeight: Integer; aObj: TObject; aTag: Integer); -begin - mGrid := aGrid; - setup(aX, aY, aWidth, aHeight, aObj, aTag); -end; - - -destructor TBodyProxy.Destroy (); -begin - inherited; -end; -*) - - procedure TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: TObject; aTag: Integer); begin mX := aX; @@ -213,8 +170,6 @@ end; destructor TBodyGrid.Destroy (); -var - px: TBodyProxy; begin mCells := nil; mGrid := nil; @@ -520,83 +475,4 @@ begin end; -// ////////////////////////////////////////////////////////////////////////// // -constructor TBinaryHeapObj.Create (alessfn: TBinaryHeapLessFn); -begin - if not assigned(alessfn) then raise Exception.Create('wutafuck?!'); - lessfn := alessfn; - SetLength(elem, 8192); // 'cause why not? - elemUsed := 0; -end; - - -destructor TBinaryHeapObj.Destroy (); -begin - inherited; -end; - - -procedure TBinaryHeapObj.clear (); -begin - elemUsed := 0; -end; - - -procedure TBinaryHeapObj.heapify (root: Integer); -var - smallest, right: Integer; - tmp: TObject; -begin - while true do - begin - smallest := 2*root+1; // left child - if (smallest >= elemUsed) then break; // anyway - right := smallest+1; // right child - if not lessfn(elem[smallest], elem[root]) then smallest := root; - if (right < elemUsed) and (lessfn(elem[right], elem[smallest])) then smallest := right; - if (smallest = root) then break; - // swap - tmp := elem[root]; - elem[root] := elem[smallest]; - elem[smallest] := tmp; - root := smallest; - end; -end; - - -procedure TBinaryHeapObj.insert (val: TObject); -var - i, par: Integer; -begin - if (val = nil) then exit; - i := elemUsed; - if (i = Length(elem)) then SetLength(elem, Length(elem)+16384); // arbitrary number - Inc(elemUsed); - while (i <> 0) do - begin - par := (i-1) div 2; // parent - if not lessfn(val, elem[par]) then break; - elem[i] := elem[par]; - i := par; - end; - elem[i] := val; -end; - -function TBinaryHeapObj.front (): TObject; -begin - if elemUsed > 0 then result := elem[0] else result := nil; -end; - - -procedure TBinaryHeapObj.popFront (); -begin - if (elemUsed > 0) then - begin - Dec(elemUsed); - elem[0] := elem[elemUsed]; - heapify(0); - end; -end; - - end. diff --git a/src/game/g_map.pas b/src/game/g_map.pas index 29750c9..c9851ee 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, g_sap, md5, xprofiler; type TMapInfo = record @@ -136,6 +136,7 @@ var gdbg_map_use_grid_render: Boolean = true; gdbg_map_use_grid_coldet: Boolean = true; + gdbg_map_use_sap: Boolean = false; profMapCollision: TProfiler = nil; //WARNING: FOR DEBUGGING ONLY! implementation @@ -145,7 +146,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; @@ -196,6 +197,7 @@ var FlagPoints: Array [FLAG_RED..FLAG_BLUE] of PFlagPoint; //DOMFlagPoints: Array of TFlagPoint; gMapGrid: TBodyGrid = nil; + gMapSAP: TSweepAndPrune = nil; procedure g_Map_ProfilersBegin (); @@ -984,12 +986,15 @@ var for idx := High(panels) downto 0 do begin gMapGrid.insertBody(panels[idx], panels[idx].X, panels[idx].Y, panels[idx].Width, panels[idx].Height, tag); + gMapSAP.insertBody(panels[idx], panels[idx].X, panels[idx].Y, panels[idx].Width, panels[idx].Height, tag); end; end; begin gMapGrid.Free(); gMapGrid := nil; + gMapSAP.Free(); + gMapSAP := nil; fixMinMax(gWalls); fixMinMax(gRenderBackgrounds); @@ -1008,6 +1013,7 @@ begin end; gMapGrid := TBodyGrid.Create(mapX0, mapY0, mapX1-mapX0+1, mapY1-mapY0+1); + gMapSAP := TSweepAndPrune.Create(); addPanelsToGrid(gWalls, PANEL_WALL); // and PANEL_CLOSEDOOR addPanelsToGrid(gRenderBackgrounds, PANEL_BACK); @@ -1020,6 +1026,7 @@ begin addPanelsToGrid(gBlockMon, PANEL_BLOCKMON); gMapGrid.dumpStats(); + gMapSAP.dumpStats(); end; function g_Map_Load(Res: String): Boolean; @@ -1056,6 +1063,8 @@ var begin gMapGrid.Free(); gMapGrid := nil; + gMapSAP.Free(); + gMapSAP := nil; Result := False; gMapInfo.Map := Res; @@ -1917,7 +1926,14 @@ begin if gdbg_map_use_grid_render then begin - gMapGrid.forEachInAABB(x0, y0, wdt, hgt, checker); + if gdbg_map_use_sap then + begin + gMapSAP.forEachInAABB(x0, y0, wdt, hgt, checker); + end + else + begin + gMapGrid.forEachInAABB(x0, y0, wdt, hgt, checker); + end; // sort and draw the list (we need to sort it, or rendering is fucked) while gDrawPanelList.count > 0 do begin @@ -1956,7 +1972,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_sap then + begin + gMapSAP.forEachInAABB(lightX-radius, lightY-radius, radius*2, radius*2, checker); + end + else + begin + gMapGrid.forEachInAABB(lightX-radius, lightY-radius, radius*2, radius*2, checker); + end; end; @@ -2218,7 +2241,14 @@ begin try if gdbg_map_use_grid_coldet then begin - result := gMapGrid.forEachInAABB(X, Y, Width, Height, checker); + if gdbg_map_use_sap then + begin + gMapSAP.forEachInAABB(X, Y, Width, Height, checker); + end + else + begin + result := gMapGrid.forEachInAABB(X, Y, Width, Height, checker); + end; end else begin @@ -2283,7 +2313,14 @@ begin if gdbg_map_use_grid_coldet then begin texid := TEXTURE_NONE; - gMapGrid.forEachInAABB(X, Y, Width, Height, checker); + if gdbg_map_use_sap then + begin + gMapSAP.forEachInAABB(X, Y, Width, Height, checker); + end + else + begin + gMapGrid.forEachInAABB(X, Y, Width, Height, checker); + end; result := texid; end else diff --git a/src/game/g_sap.pas b/src/game/g_sap.pas new file mode 100644 index 0000000..5baf514 --- /dev/null +++ b/src/game/g_sap.pas @@ -0,0 +1,406 @@ +(* Copyright (C) DooM 2D:Forever Developers + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + *) +{$INCLUDE ../shared/a_modes.inc} +// universal sweep-and-prune broad phase +unit g_sap; + +interface + +type + TSAPQueryCB = function (obj: TObject; tag: Integer): Boolean is nested; // return `true` to stop + +type + TSAPProxy = Integer; + + PSAPProxyRec = ^TSAPProxyRec; + TSAPProxyRec = record + private + mX, mY, mWidth, mHeight: Integer; // aabb + 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 + + private + procedure setup (aX, aY, aWidth, aHeight: Integer; aObj: TObject; aTag: Integer); + + public + property x: Integer read mX; + property y: Integer read mY; + property width: Integer read mWidth; + property height: Integer read mHeight; + property obj: TObject read mObj; + property tag: Integer read mTag; + //property grid: TBodyGrid read mGrid; + end; + + + TSweepAndPrune = class(TObject) + private + type + //PInterval = ^TInterval; + TInterval = record + public + min, max: Integer; + pidx: Integer; // proxy idx + + public + function less (var i: TInterval): Boolean; inline; + function intersects (v0, v1: Integer): Boolean; inline; + end; + + private + mLastQuery: DWord; + mIntrs: array[0..1] of array of TInterval; + mIntrsUsed: array[0..1] of Integer; + mProxies: array of TSAPProxyRec; + mProxyFree: TSAPProxy; // free + mProxyCount: Integer; // currently used + mProxyMaxCount: Integer; + mUpdateBlocked: Integer; // >0: updates are blocked + + private + function allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: TObject; aTag: Integer): TSAPProxy; + procedure freeProxy (body: TSAPProxy); + + procedure sortIntervals (); + + procedure insert (body: TSAPProxy); + //procedure remove (body: TSAPProxy); + + public + constructor Create (); + destructor Destroy (); override; + + function insertBody (aObj: TObject; ax, ay, aWidth, aHeight: Integer; aTag: Integer=0): TSAPProxy; + //procedure removeBody (aObj: TSAPProxy); // WARNING! this WILL destroy proxy! + + //procedure moveBody (body: TSAPProxy; dx, dy: Integer); + //procedure resizeBody (body: TSAPProxy; sx, sy: Integer); + //procedure moveResizeBody (body: TSAPProxy; dx, dy, sx, sy: Integer); + + function forEachInAABB (x, y, w, h: Integer; cb: TSAPQueryCB): Boolean; + + //function getProxyForBody (aObj: TObject; x, y, w, h: Integer): TSAPProxy; + + // call these functions before massive update (it may, or may be not faster) + procedure batchUpdateBegin (); + procedure batchUpdateEnd (); + + procedure dumpStats (); + end; + + +implementation + +uses + SysUtils, e_log; + + +// ////////////////////////////////////////////////////////////////////////// // +procedure TSAPProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: TObject; aTag: Integer); +begin + mX := aX; + mY := aY; + mWidth := aWidth; + mHeight := aHeight; + mQueryMark := 0; + mObj := aObj; + mTag := aTag; + //nextLink := -1; + mIIdx[0] := -1; + mIIdx[1] := -1; +end; + + +// ////////////////////////////////////////////////////////////////////////// // +function TSweepAndPrune.TInterval.less (var i: TInterval): 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); +end; + + +// v0 MUST be <= v1! +function TSweepAndPrune.TInterval.intersects (v0, v1: Integer): Boolean; +begin + result := false; + if (v1 < min) or (v0 > max) then exit; + result := true; +end; + + +// ////////////////////////////////////////////////////////////////////////// // +constructor TSweepAndPrune.Create (); +var + idx: Integer; +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; + 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; + + +destructor TSweepAndPrune.Destroy (); +var + idx: Integer; +begin + 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); +end; + + +procedure TSweepAndPrune.batchUpdateBegin (); +begin + Inc(mUpdateBlocked); +end; + + +procedure TSweepAndPrune.batchUpdateEnd (); +begin + if (mUpdateBlocked > 0) then + begin + Dec(mUpdateBlocked); + if (mUpdateBlocked = 0) then sortIntervals(); + end; +end; + + +function TSweepAndPrune.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: TObject; aTag: Integer): TSAPProxy; +var + olen, idx: Integer; + px: PSAPProxyRec; +begin + if (mProxyFree = -1) then + 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; + mProxyFree := olen; + end; + // get one from list + result := mProxyFree; + px := @mProxies[result]; + mProxyFree := px.mIIdx[0]; + px.setup(aX, aY, aWidth, aHeight, aObj, aTag); + // add to used list + px.mIIdx[0] := -1; + // statistics + Inc(mProxyCount); + if (mProxyMaxCount < mProxyCount) then mProxyMaxCount := mProxyCount; +end; + +procedure TSweepAndPrune.freeProxy (body: TSAPProxy); +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; + 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); +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); +end; + + +function TSweepAndPrune.insertBody (aObj: TObject; aX, aY, aWidth, aHeight: Integer; aTag: Integer=0): TSAPProxy; +begin + if (aObj = nil) or (aWidth < 1) or (aHeight < 1) then begin result := -1; exit; end; + result := allocProxy(aX, aY, aWidth, aHeight, aObj, aTag); + insert(result); +end; + + +function TSweepAndPrune.forEachInAABB (x, y, w, h: Integer; cb: TSAPQueryCB): Boolean; + + function walkInterval (val0, val1, lq, iidx: Integer): Boolean; + var + i, bot, mid, cmp: Integer; + px: PSAPProxyRec; + begin + result := false; + if (mIntrsUsed[iidx] < 1) then exit; // nothing to do + if (mIntrsUsed[iidx] = 1) then + begin + // one element + i := 0; + 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; + end; + end; + +var + idx: Integer; +begin + result := false; + if not assigned(cb) then exit; // no callback, not interesting + if (w < 1) or (h < 1) then exit; // nothing to do + + // increase query counter + Inc(mLastQuery); + if (mLastQuery = 0) then + begin + // just in case of overflow + mLastQuery := 1; + for idx := 0 to High(mProxies) do mProxies[idx].mQueryMark := 0; + end; + + (* + * 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); +end; + + +end. diff --git a/src/game/g_window.pas b/src/game/g_window.pas index 450afde..582c2d9 100644 --- a/src/game/g_window.pas +++ b/src/game/g_window.pas @@ -709,6 +709,8 @@ 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; end; e_WriteLog('Initializing OpenGL', MSG_NOTIFY); diff --git a/src/shared/binheap.pas b/src/shared/binheap.pas new file mode 100644 index 0000000..968c5f9 --- /dev/null +++ b/src/shared/binheap.pas @@ -0,0 +1,136 @@ +(* Copyright (C) DooM 2D:Forever Developers + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + *) +{$INCLUDE a_modes.inc} +// binary heap +unit binheap; + +interface + + +type + TBinaryHeapLessFn = function (a, b: TObject): Boolean; + + TBinaryHeapObj = class(TObject) + private + elem: array of TObject; + elemUsed: Integer; + lessfn: TBinaryHeapLessFn; + + private + procedure heapify (root: Integer); + + public + constructor Create (alessfn: TBinaryHeapLessFn); + destructor Destroy (); override; + + procedure clear (); + + procedure insert (val: TObject); + + function front (): TObject; + procedure popFront (); + + property count: Integer read elemUsed; + end; + + +implementation + +uses + SysUtils; + + +// ////////////////////////////////////////////////////////////////////////// // +constructor TBinaryHeapObj.Create (alessfn: TBinaryHeapLessFn); +begin + if not assigned(alessfn) then raise Exception.Create('wutafuck?!'); + lessfn := alessfn; + SetLength(elem, 8192); // 'cause why not? + elemUsed := 0; +end; + + +destructor TBinaryHeapObj.Destroy (); +begin + elem := nil; + inherited; +end; + + +procedure TBinaryHeapObj.clear (); +begin + elemUsed := 0; +end; + + +procedure TBinaryHeapObj.heapify (root: Integer); +var + smallest, right: Integer; + tmp: TObject; +begin + while true do + begin + smallest := 2*root+1; // left child + if (smallest >= elemUsed) then break; // anyway + right := smallest+1; // right child + if not lessfn(elem[smallest], elem[root]) then smallest := root; + if (right < elemUsed) and (lessfn(elem[right], elem[smallest])) then smallest := right; + if (smallest = root) then break; + // swap + tmp := elem[root]; + elem[root] := elem[smallest]; + elem[smallest] := tmp; + root := smallest; + end; +end; + + +procedure TBinaryHeapObj.insert (val: TObject); +var + i, par: Integer; +begin + if (val = nil) then exit; + i := elemUsed; + if (i = Length(elem)) then SetLength(elem, Length(elem)+16384); // arbitrary number + Inc(elemUsed); + while (i <> 0) do + begin + par := (i-1) div 2; // parent + if not lessfn(val, elem[par]) then break; + elem[i] := elem[par]; + i := par; + end; + elem[i] := val; +end; + +function TBinaryHeapObj.front (): TObject; +begin + if elemUsed > 0 then result := elem[0] else result := nil; +end; + + +procedure TBinaryHeapObj.popFront (); +begin + if (elemUsed > 0) then + begin + Dec(elemUsed); + elem[0] := elem[elemUsed]; + heapify(0); + end; +end; + + +end.