[System] DestructableHider

[Zwiebelchen]

Jass:

library DestructableHider initializer init

    /*
        by Zwiebelchen      v1.3
   
            Destructables create an enormous amount of overhead on warcraft III maps, almost the same as units, especially walkable destructables.
            Thus, a large amount of destructables creates a huge drop of FPS in the game, even on fast machines, due to the poor engine of WC3.
            This effect is fairly noticable at an amount of even less than 1000 destructables, which is reached very fast when using invisible platforms.
            Warcraft III automaticly hides units outside the screen to save performance, however it does not do so for destructables, for unknown reasons.
           
            The purpose of this fully automatic system is to hide all those destructables, that are currently not viewed anyway, to save a lot of processing time.
            To do that, the entire map is splitted into tiles of an editable size and all destructables within those tiles are stored into a table, to allow fast access.
            When a tile is viewed, all destructables on adjacent tiles will also be shown, so that moving the camera doesnt create ugly popup effects when the center of the view is on the edge of a tile.
           
            However, there are some rules you need to consider, in order to make your map work without desyncs in multiplayer:
            - never hide destructables units or players can interact with (attackable, selectable or destructable)
            - hiding destructables that block pathing is safe, as hiding the destructable will not change its pathing
            - hiding destructables that need to be enumed is safe; hidden destructables can be enumerated
            - hiding walkable platforms is also safe, as long as you dont get a location Z for a location placed on that destructable globally; this is not 100% safe anyway, as
              the returned value of GetLocationZ() is dependant on the render state of the destructable
           
           
            API:
                   
                private function filt returns boolean
                    - add custom filter code for the automatic enumeration of destructables on map init inside
                    - if all destructables should be added to the system, let it return true
                    - example:
                        private function filt returns boolean
                            return GetDestructableMaxLife(GetFilterDestructable()) == 1
                        endfunction
                        -> automaticly adds all destructables on the map with a maximum life of 1 on map init to the system
           
           
            Optional:
           
                public function register takes destructable returns nothing
                    - adds a destructable to the system, also hides/shows the destructable depending on the position of the camera
               
                public function unregister takes destructable returns nothing
                    - removes a destructable from the system, also unhides the destructable in case it was hidden
           
           
    */
   
globals
    //==== CONFIGURABLES ====
    private constant real INTERVAL = 0.1 //Update interval in seconds.
                                         //[in multiplayer, the camera positions will only get updated every 0.05-0.1 seconds, so setting it to a lower value than 0.05 makes no sense]
                                         //[update frequency can be much higher in single player mode!]
    private constant integer DRAW_DISTANCE = 512 //the radius around the camera target in which the tiles are considered visible; should be about the same as sight radius (not diameter) of the camera; for 3d cams, use the FarZ value
                                                 //Use multiples of 1024 for maximum efficiency on square division. Recommended value: 5120
    private constant integer TILE_RESOLUTION = 4 //amount of tiles spread over DRAW_DISTANCE
                                        //- higher resolution = more overhead to incrementing loop variables, but less amounts of destructables checked when moving the camera
                                        //- lower resolution = less overhead to incrementing loop variables, but higher amounts of destructables checked when moving the camera
                                        //-> Recommended value: 8-12
    //==== END OF CONFIGURABLES ====
   
    private hashtable hash = InitHashtable()
    private integer columns = 0
    private integer rows = 0
    private integer lastrow = 0
    private integer lastcolumn = 0
    private integer lastid = 0
    private real mapMinX = 0
    private real mapMinY = 0
    private constant integer TILESIZE = DRAW_DISTANCE/TILE_RESOLUTION
endglobals

private function filt takes nothing returns boolean
    //Add code for the enum filter of the automatic registration of destructables on map init
   
    //example:
    //return GetDestructableMaxLife(GetFilterDestructable()) == 1
    //-> automaticly adds all destructables on the map with a maximum life of 1 on map init to the system
    return true
endfunction

public function register takes destructable d returns nothing
    local integer id = R2I((GetDestructableY(d)-mapMinY)/TILESIZE)*columns + R2I((GetDestructableX(d)-mapMinX)/TILESIZE)
    local integer count = LoadInteger(hash, id, 0)+1
    call SaveInteger(hash, id, 0, count)
    call SaveDestructableHandle(hash, id, count, d)
    call ShowDestructable(d, LoadBoolean(hash, id, -1)) //match visibility state
    call SaveInteger(hash, GetHandleId(d), 0, count) //store the list position for fast lookup
endfunction

public function unregister takes destructable d returns nothing
    local integer id = R2I((GetDestructableY(d)-mapMinY)/TILESIZE)*columns + R2I((GetDestructableX(d)-mapMinX)/TILESIZE)
    local integer count = LoadInteger(hash, id, 0)
    local integer a = LoadInteger(hash, GetHandleId(d), 0)
    local destructable temp
    if a < count then //move the last in list up to this slot
        set temp = LoadDestructableHandle(hash, id, count)
        call SaveDestructableHandle(hash, id, a, temp)
        call SaveInteger(hash, GetHandleId(temp), 0, a) //update list position
        set temp = null
    endif
    call RemoveSavedHandle(hash, id, count) //clean up the deserted slot
    call SaveInteger(hash, id, 0, count-1)
    call FlushChildHashtable(hash, GetHandleId(d)) //clean up list position
    call ShowDestructable(d, true) //make sure its shown again in case it was hidden
endfunction

private function autoregister takes nothing returns nothing
    local destructable d = GetEnumDestructable()
    local integer id = R2I((GetDestructableY(d)-mapMinY)/TILESIZE)*columns + R2I((GetDestructableX(d)-mapMinX)/TILESIZE)
    local integer count = LoadInteger(hash, id, 0)+1
    call SaveInteger(hash, id, 0, count)
    call SaveDestructableHandle(hash, id, count, d)
    call ShowDestructable(d, false) //initially hide everything
    call SaveInteger(hash, GetHandleId(d), 0, count) //store the list position for fast lookup
    set d = null
endfunction

private function EnumGrid takes integer x1, integer x2, integer y1, integer y2, boolean show returns nothing
    local integer a = x1
    local integer b
    local integer j
    local integer id
    local integer count
    loop
        set b = y1
        exitwhen a > x2
        loop
            exitwhen b > y2
            set id = b*columns+a
            call SaveBoolean(hash, id, -1, show)
            set count = LoadInteger(hash, id, 0)
            set j = 0
            loop
                exitwhen j >= count
                set j = j + 1
                call ShowDestructable(LoadDestructableHandle(hash, id, j), show)
            endloop
            set b = b + 1
        endloop
        set a = a + 1
    endloop
endfunction

private function ChangeTiles takes integer r, integer c, integer lr, integer lc returns nothing
    local integer AminX = c-TILE_RESOLUTION
    local integer AmaxX = c+TILE_RESOLUTION
    local integer AminY = r-TILE_RESOLUTION
    local integer AmaxY = r+TILE_RESOLUTION
    local integer BminX = lc-TILE_RESOLUTION
    local integer BmaxX = lc+TILE_RESOLUTION
    local integer BminY = lr-TILE_RESOLUTION
    local integer BmaxY = lr+TILE_RESOLUTION
    //border safety:
    if AminX < 0 then
        set AminX = 0
    endif
    if AminY < 0 then
        set AminY = 0
    endif
    if BminX < 0 then
        set BminX = 0
    endif
    if BminY < 0 then
        set BminY = 0
    endif
    if AmaxX >= columns then
        set AmaxX = columns-1
    endif
    if AmaxY >= rows then
        set AmaxX = rows-1
    endif
    if BmaxX >= columns then
        set BmaxX = columns-1
    endif
    if BmaxY >= rows then
        set BmaxX = rows-1
    endif
   
    if BmaxX < AminX or AmaxX < BminX or BmaxY < AminY or AmaxY < BminY then
        call EnumGrid(AminX, AmaxX, AminY, AmaxY, true)
        call EnumGrid(BminX, BmaxX, BminY, BmaxY, false)
    else
        if c >= lc then
            if c != lc then
                call EnumGrid(BmaxX+1, AmaxX, AminY, AmaxY, true)
                call EnumGrid(BminX, AminX-1, BminY, BmaxY, false)
            endif
            if AminY < BminY then
                call EnumGrid(AminX, BmaxX, AmaxY+1, BmaxY, false)
                call EnumGrid(AminX, BmaxX, AminY, BminY-1, true)
            elseif BminY < AminY then
                call EnumGrid(AminX, BmaxX, BmaxY+1, AmaxY, true)
                call EnumGrid(AminX, BmaxX, BminY, AminY-1, false)
            endif
        else
            call EnumGrid(AminX, BminX-1, AminY, AmaxY, true)
            call EnumGrid(AmaxX+1, BmaxX, BminY, BmaxY, false)
            if AminY < BminY then
                call EnumGrid(BminX, AmaxX, AminY, BminY-1, true)
                call EnumGrid(BminX, AmaxX, AmaxY+1, BmaxY, false)
            elseif BminY < AminY then
                call EnumGrid(BminX, AmaxX, BminY, AminY-1, false)
                call EnumGrid(BminX, AmaxX, BmaxY+1, AmaxY, true)
            endif
        endif
    endif
endfunction

private function periodic takes nothing returns nothing
    local integer row = R2I((GetCameraTargetPositionY()-mapMinY)/TILESIZE)
    local integer column = R2I((GetCameraTargetPositionX()-mapMinX)/TILESIZE)
    local integer id = row*columns + column
    if id == lastid then //only check for tiles if the camera has left the last tile
        return
    endif
    call ChangeTiles(row, column, lastrow, lastcolumn)
    set lastrow = row
    set lastcolumn = column
    set lastid = id
endfunction

private function init takes nothing returns nothing
    set mapMinX = GetRectMinX(bj_mapInitialPlayableArea)
    set mapMinY = GetRectMinY(bj_mapInitialPlayableArea)
    set lastrow = R2I((GetCameraTargetPositionY()-mapMinY)/TILESIZE)
    set lastcolumn = R2I((GetCameraTargetPositionX()-mapMinX)/TILESIZE)
    set rows = R2I((GetRectMaxY(bj_mapInitialPlayableArea)-mapMinY)/TILESIZE)+1
    set columns = R2I((GetRectMaxX(bj_mapInitialPlayableArea)-mapMinX)/TILESIZE)+1
    if lastcolumn <= columns/2 then //to make sure the game starts with a full make-visible enum of all destructables on screen
        set lastcolumn = columns-1
    else
        set lastcolumn = 0
    endif
    if lastrow <= rows/2 then
        set lastrow = rows-1
    else
        set lastrow = 0
    endif
    set lastid = lastrow*columns + lastcolumn
    call EnumDestructablesInRect(bj_mapInitialPlayableArea, Filter(function filt), function autoregister)
    call TimerStart(CreateTimer(), INTERVAL, true, function periodic)
    call periodic() //to make sure the destructables on screen after the map loading process finishes are initially shown
endfunction

endlibrary

EDIT:
I forgot to change the documentation inside the demo map. Hiding destructables that block pathing is SAFE! Don't worry about it, the pathing is not affected at all!

[PurgeandFire]

Ah, so that is the method you were talking about. I was considering something similar, using rects. However, I see that you hashed them to avoid enumeration (so you don't need rects), gj creative.

However, for a system like this we'll probably need someone to run some benchmarks with /fps. (of any kind, it doesn't necessarily have to be a stress-test) I tried doing something similar to this on a map with like 5000 invisible destructables and the results were kinda so-so, they were usually within 3-4 fps of not having the system at all (either above or below). Although, your technique most likely has a lot less overhead since it doesn't constantly enumerate, so the results may be different. :)

Good job overall though.

[Troll-Brain]

That was basically what i have in mind.
That's probably enough in the current state but you could even improve by using a MAX number : if the number of not hidden destructables is lower than this constant number, then you don't have to bother to hide destructables.

[Magtheridon96]

I'd totally recommend changing things like this: i+1 to this: i + 1 because it makes the system a bit more readable :P

edit
Placing line breaks in between blocks of code (if blocks, loops, etc..) would also make things more readable.

[Zwiebelchen]

Updated to v1.1; fixed a small bug that caused the last center tile not to hide correctly.
Also fixed comments (south is north and north is south, due to the tiles starting from the bottom left corner of the map, not the top left corner). Also added a debug mode counter that shows how many destructables got hidden and shown each update.

[Zwiebelchen]

Just to prove what this thing is capable of:

I implemented it in Gaias Retaliation, edge size 6144, 0.05s ticks.
Almost 900 destructables, 750 of them platforms. 480x256 map size, 50.000 doodads.

The system only hides those destructables, nothing else. This is what happens in the opening scene (you know, when you spawn your level 1 hero at the inn):

Left picture: without the system. Right picture: with the system. Note that those values are pretty stable, with a fluctuation of less than +/- 3 fps on my machine. Also, what this doesn't show: without the system, there are short random freezes due to fps drop spikes. With the system activated, this is totally gone; camera movement is 100% smooth, no fps spikes at all.



For rpgs, this thing is nothing less than a miracle.

Originally Posted by Troll-Brain

That was basically what i have in mind.
That's probably enough in the current state but you could even improve by using a MAX number : if the number of not hidden destructables is lower than this constant number, then you don't have to bother to hide destructables.

I don't think that would actually be neccesary. This thing sucks almost no performance at all, as it only updates if you leave the current tile you are looking at. And everything is simple maths operations. No powers, no squareroots, no handles.
Well I could improve it by splitting the hide and show process over seperate ticks/threads. The amount of processing time would be the same, but it evens out over time better than the current approach. Not that anyone would ever notice a difference...

EDIT:
I also did some further testing. It seems that the pathing of hidden destructables remains intact, so this is safe to use on pathing blockers aswell.

[PurgeandFire]

Nice!

Does this work in multiplayer?

[Troll-Brain]

You just asked for moar performance, now just like i said, it should be enough in the current state.

Also, you should probably give a way to create/remove destructables in game with custom functions (hooks are not enough)

[Zwiebelchen]

Originally Posted by PurgeandFire111

Nice!

Does this work in multiplayer?

It works fine - as long as you exclude targetable destructables.

Also, you should probably give a way to create/remove destructables in game with custom functions (hooks are not enough)

You can always do so by using ordinary natives. No need for custom functions here.

[Troll-Brain]

No, destructables are "picked up" only once, on init.
The destructables which are created later are not considered, plus destructables which are removed are not removed of the lists.

[Zwiebelchen]

Originally Posted by Troll-Brain

No, destructables are "picked up" only once, on init.
The destructables which are created later are not considered, plus destructables which are removed are not removed of the lists.

Hmm, correct. Then again, when would you ever need that? I can probably write an unregister function and make the register function public, if you wish.

[Troll-Brain]

Don't ask me, i hardly open the editor these times, and since months or even years in fact.

It's just something easy to add and could be useful.

Oh and btw it should be a mistake but the function "register" is public, while it should be private.

[Zwiebelchen]

Well, at first I wanted to add register and unregister functions as public functions so that people can manually add the destructables they like. Then I came up with the maxlife check idea so it became obsolete. Looks like it could be useful again.

[Troll-Brain]

If i would had made a such resource i would use a config function where you manually put each rawcode of destructable.
Now using directly the object editor, i'm just not sure the max life is an appropriate choice, i mean if you open the map (especially if it's since a while you have not opened it) that wouldn't be obvious.
The script way seems more reliable imho, but maybe more annoying, idk.

[Zwiebelchen]

Originally Posted by Troll-Brain

If i would had made a such resource i would use a config function where you manually put each rawcode of destructable.
Now using directly the object editor, i'm just not sure the max life is an appropriate choice, i mean if you open the map (especially if it's since a while you have not opened it) that wouldn't be obvious.
The script way seems more reliable imho, but maybe more annoying, idk.

Sure, it might not be a clean method to set up the registry, but it's very elegant and efficient to do so. Well, if I leave it to the player to register/unregister the destructables, there's no need for this anymore anyway.