[Solved] Why is this so heavy?

[Kazeon]

This is about my PathingColor library. Here is the code:

Hidden

library PathingColor initializer onInit requires IsTerrainWalkable
    
    // Configuration
    
        globals
            private constant integer FLYING_CHECKER   = 'h008'
            private constant integer BUILDING_CHECKER = 'n000'
        endglobals
    
    /*
    
                PathingColor v1.2
                ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
                        by: Dalvengyr
        
        
        Description
        ¯¯¯¯¯¯¯¯¯¯¯
            An  extension to IsTerrainWalkable. This library  allows  you
            to detect 8 types of possible pathing colors in Warcraft III.
            Additionally,  it's  also  able to  check  terrain's  pathing
            type (walkability, flyability, and buildability).
            
            Here is the color specifications:
        
        
                Color	Buildable	Walkable	Flyable	    Red     Green   Blue
            ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
                White	    x	        x	 	    x	    255	     255	255
                Magenta	    x	        x		    o	    255	      0	    255
                Cyan	    x	        o		    x	     0	     255	255
                Blue	    x	        o		    o	     0	      0	    255
                Yellow	    o	        x		    x	    255	     255	 0
                Red	        o	        x		    o	    255	      0	     0
                Green	    o	        o		    x	     0	     255	 0
                Black	    o	        o		    o	     0	      0	     0
                
                
            (You can check your pathing map by pressing 'p' at terrain editor.)
            
            
        API
        ¯¯¯
            1. Used for checking certain point's pathability color.
            
                | function GetTerrainPathingColor takes real x, real y returns integer
                
                Returned values (pathing colors):
                    | PATHING_COLOR_WHITE
                    | PATHING_COLOR_MAGENTA
                    | PATHING_COLOR_CYAN
                    | PATHING_COLOR_BLUE
                    | PATHING_COLOR_YELLOW
                    | PATHING_COLOR_RED
                    | PATHING_COLOR_GREEN
                    | PATHING_COLOR_BLACK
                    
            2. Used for checking certain color's pathing type.
            
                | function IsColorPathingType takes integer color, integer pathingType returns boolean
                    
                    
            3. Used for checking certain point's pathing type.
            
                | function IsTerrainPathingType takes real x, real y, integer pathingType returns boolean
                
                Pathing types:
                    | PATHING_TYPE_FLYABLE
                    | PATHING_TYPE_WALKABLE
                    | PATHING_TYPE_BUILDABLE
                    
                    
        How to import
        ¯¯¯¯¯¯¯¯¯¯¯¯¯
            - Copy Fly Checker and Build Checker (units) at object editor.
            - Install IsTerrainWalkable correctly.
            - Make sure MAX_RANGE of that system is less than 32.
            - Configure this system (available above).
                    
                    
        Credits
        ¯¯¯¯¯¯¯
            - IsTerrainWalkable by Vexorian n Anitarf
            - TheHelper.net for complete pathing types tutorial
                    
                    
        Link
        ¯¯¯¯
            hiveworkshop.com/forums/spells-569/pathing-color-v1-0-a-263230/
    
    */
    
    globals
        
        private rect TempRect
        private unit FlyChecker
        private unit BuildChecker
        
        private real ReturnX
        private real ReturnY
        
        private group DisableGroup = CreateGroup()
        private group EnableGroup  = CreateGroup()
    
        private constant real BUILD_COLLISION_SIZE = 64
        private constant real FLY_COLLISION_SIZE   = 1
        
        constant integer PATHING_COLOR_WHITE   = 0
        constant integer PATHING_COLOR_MAGENTA = 1
        constant integer PATHING_COLOR_CYAN    = 2
        constant integer PATHING_COLOR_BLUE    = 3
        constant integer PATHING_COLOR_YELLOW  = 4
        constant integer PATHING_COLOR_RED     = 5
        constant integer PATHING_COLOR_GREEN   = 6
        constant integer PATHING_COLOR_BLACK   = 7
        
        constant integer PATHING_TYPE_FLYABLE  = 0
        constant integer PATHING_TYPE_WALKABLE = 1
        constant integer PATHING_TYPE_BUILDABLE= 2
        
    endglobals
    
    private function IsInRect takes real x, real y returns boolean
        return x > GetRectMinX(TempRect) and x < GetRectMaxX(TempRect) and y > GetRectMinY(TempRect) and y < GetRectMaxY(TempRect)
    endfunction
    
    private function IsInRadius takes real x, real y, real x2, real y2 returns boolean
        return (x-x2)*(x-x2)+(y-y2)*(y-y2) < FLY_COLLISION_SIZE*FLY_COLLISION_SIZE
    endfunction
    
    function GetTerrainPathingColor takes real x, real y returns integer
        
        local unit fog
        local integer color = 0
        
        call MoveRectTo(TempRect, x, y)
        call GroupEnumUnitsInRect(DisableGroup, TempRect, null)
        
        loop
            set fog = FirstOfGroup(DisableGroup)
            exitwhen fog == null
            call GroupRemoveUnit(DisableGroup, fog)
            call GroupAddUnit(EnableGroup, fog)
            call SetUnitPathing(fog, false)
        endloop
        
        call SetUnitPosition(FlyChecker, x, y)
        if IsInRadius(x, y, GetUnitX(FlyChecker), GetUnitY(FlyChecker)) then
            set color = color + 1
        endif
        call SetUnitX(FlyChecker, ReturnX)
        call SetUnitY(FlyChecker, ReturnY)
        
        if IsTerrainWalkable(x, y) then
            set color = color + 2
        endif
        
        
        call SetUnitPosition(BuildChecker, x, y)
        if IsInRect(GetUnitX(BuildChecker), GetUnitY(BuildChecker)) then
            set color = color + 4
        endif
        call SetUnitPosition(BuildChecker, ReturnX, ReturnY)
        
        loop
            set fog = FirstOfGroup(EnableGroup)
            exitwhen fog == null
            call GroupRemoveUnit(EnableGroup, fog)
            call SetUnitPathing(fog, true)
        endloop
        
        return color
    endfunction
    
    function IsColorPathingType takes integer color, integer pathing returns boolean
        
        if pathing == PATHING_TYPE_FLYABLE then
            return color == 1 or color == 3 or color == 5 or color == 7
        elseif pathing == PATHING_TYPE_WALKABLE then
            return color == 2 or color == 3 or color == 6 or color == 7
        elseif pathing == PATHING_TYPE_BUILDABLE then
            return color == 4 or color == 5 or color == 6 or color == 7
        endif
        
        return false
    endfunction
    
    function IsTerrainPathingType takes real x, real y, integer pathing returns boolean
        return IsColorPathingType(GetTerrainPathingColor(x, y), pathing)
    endfunction
    
    private function onInit takes nothing returns nothing
        
        local player p = Player(PLAYER_NEUTRAL_PASSIVE)
        
        set TempRect = Rect(0, 0, BUILD_COLLISION_SIZE, BUILD_COLLISION_SIZE)
    
        set BuildChecker = CreateUnit(p, BUILDING_CHECKER, 999999, 999999, 0)
        call PauseUnit(BuildChecker, true)
        call ShowUnit(BuildChecker, false)
    
        set FlyChecker = CreateUnit(p, FLYING_CHECKER, 999999, 999999, 0)
        call PauseUnit(FlyChecker, true)
        call ShowUnit(FlyChecker, false)
        
        call SetUnitPosition(BuildChecker, GetRectMaxX(bj_mapInitialPlayableArea), GetRectMaxY(bj_mapInitialPlayableArea))
        set ReturnX = GetUnitX(BuildChecker)
        set ReturnY = GetUnitY(BuildChecker)
        
    endfunction
    
endlibrary

I use it in my game, somehow it causes the FPS to drop slowly. I just call the function (GetTerrainPathingColor) approximately 6 times every 0.06250 second. When I tried to disable the line that call this function, the fps drop is gone. I literally have no idea why is this happening. SetUnitPosition shouldn't be extremely heavy like that. If it's indeed that heavy, so I could say that wc3 is extremely retarded.

If someone can help me to find the problem, it will be so much appreciated.

Thank you.

 

[PurgeandFire]

6 times every 0.06250 seconds equates to 96 times every second. The main slow functions:

• GroupEnumUnitsInRect - generally, enumerating so often every second is expensive. In projectile systems, some people will even try to work around enumeration with weird tricks.
• SetUnitPosition is quite heavy. If you are doing it up to 3 times in the function, that makes it so that it is 3*96 = 288 times per second. Every time you use SetUnitPosition(), it does a number of things. It has to check for pathability, and if the point isn't pathable, it has to find the nearest position to place the unit. After that, it issues a stop order, which is a bit weird of Blizzard to do. Regardless, doing that 288 times per second will definitely cause an fps drop.

You'll have to explore more of the rules of pathing to try to figure out how to optimize it. For example, for buildability--perhaps you could have a peasant dummy and try to have him build the smallest building possible (another dummy object with a really tiny pathing map) at that particular point? The Issue<>Order() natives return a boolean of whether the order was successful, so maybe it would work as a quick check.

Also, if you're just checking static pathing type, you can always just iterate through the tiles of the map on initialization and cache the results within a hashtable. That way, you can just look up the pathing color within a table. Of course, you still have to worry about units and destructables etc. blocking things, but it could help. I'm not sure whether your system is supposed to determine the pathing type statically (e.g. as it is in the .wpm) or whether you want it to dynamically check whether a flying unit can be there/if someone can build there.

 

[Kazeon]

GroupEnumUnitsInRect - generally, enumerating so often every second is expensive. In projectile systems, some people will even try to work around enumeration with weird tricks.

The rect is just 64x64 wide. I'm not sure if it's really heavy. What I know is that unit enumeration is getting heavier as the area radius is bigger and there are more units to be enumerated. But in a 64x64 rect, how many units can it be?

SetUnitPosition is quite heavy. If you are doing it up to 3 times in the function, that makes it so that it is 3*96 = 288 times per second. Every time you use SetUnitPosition(), it does a number of things. It has to check for pathability, and if the point isn't pathable, it has to find the nearest position to place the unit. After that, it issues a stop order, which is a bit weird of Blizzard to do. Regardless, doing that 288 times per second will definitely cause an fps drop.

The thing is, it's still heavy even if there is no any pathing blocker around. Logically, SetUnitPosition shouldn't be heavy in this case because the function doesn't need to move the unit anywhere else, right?

You'll have to explore more of the rules of pathing to try to figure out how to optimize it. For example, for buildability--perhaps you could have a peasant dummy and try to have him build the smallest building possible (another dummy object with a really tiny pathing map) at that particular point? The Issue<>Order() natives return a boolean of whether the order was successful, so maybe it would work as a quick check.

Ordering peasant to build something is pretty neat. I should try it. Thanks!

Also, if you're just checking static pathing type, you can always just iterate through the tiles of the map on initialization and cache the results within a hashtable. That way, you can just look up the pathing color within a table. Of course, you still have to worry about units and destructables etc. blocking things, but it could help. I'm not sure whether your system is supposed to determine the pathing type statically (e.g. as it is in the .wpm) or whether you want it to dynamically check whether a flying unit can be there/if someone can build there.

In my map, static pathability is okay, but dunno if others will need it to be dynamic. But the problem is my map is 480x480 in size. It would be really something to initialize the whole pathing.

But still, I don't understand why the FPS drop is happening slowly, little by little. I'm afraid I leaked something there.

 

[PurgeandFire]

Ah, if the rect is 64x64, it probably won't be a big deal.

As for SetUnitPosition--it is often slow even if there is no pathing blocking the location. xD Try commenting it out and see if the fps improves. I am not 100% sure if it is that function causing the slowness.

As for the 480x480 thing, you can always split it up and do it over time. E.g. every 1 second, do a couple of tiles (until you finish them all). In your function, you just need to check if the hashtable is filled. Once all the tiles are filled up, then all calls to the function will be practically instant. Until it finishes filling the hashtable, it will use the routine you have above.

 

[Kazeon]

I took a nap and when I woke up, I got a clue that the fps drop is probably caused by the buildability checker. So I ran some tests and the result is positive. So I came into one conclusion: SetUnitPosition become even heavier for a building unit. I suppose it's because building has not only circle or square pathing map but it could be any shape, right? It seems that the function run an even crazier iteration to look for closest placable location.

So now I gonna try your peasant trick, I think it should be much faster.

 

[Kazeon]

It works great! It should become a new better approach to check walkability as well. Thanks a lot, purge!

 

[PurgeandFire]

Sweet. I'm glad it worked.

 

[Zwiebelchen]

The peasant building placement idea is awesome! Why didn't anyone use this before?! This basicly includes units blocking a place aswell, so it's a surefire way to detect pathability for any types of knockback or jump spells (as a bonus, it doesn't require moving an item or unit around and is 100% precise). Plus, you can import a custom shape for the building pathing to customize your pathing check (for example, for a circle shaped pathing test).

x o o x
o o o o
o o o o
x o o x

Dalvengyr, would you like to code us a new IsTerrainWalkable function using a circular build order? I'd love to replace the IsTerrainPathable by something more precise.

 

[Kazeon]

Yeah, it worked like a charm ^^

Anyway, the buildability checking accuracy can not be less than 64. Because as far as I noticed, buildings have minimum pathing size of 64. At least in WE. Because I see some inconsistencies between WE and in-game about pathing.

 

[Zwiebelchen]

Yeah, it worked like a charm ^^

Anyway, the buildability checking accuracy can not be less than 64. Because as far as I noticed, buildings have minimum pathing size of 64. At least in WE. Because I see some inconsistencies between WE and in-game about pathing.

That's not really a problem, as the same restriction applies to any kind of pathing blocker.

Checked out your submission to the spells section and damn! Effective script is effective!
Can you offer an optional function that uses a 128x128 blocker? This has a couple of advantages when trying to detect diagonal pathing blockers (like the fence doodad) on IsLineBetweenPointsPathable-type functions or when checking pathing for big units like bosses.

I think that a single 128x128 check has a reduced performance hit compared to 4 64x64 checks.

Also, I think I found a bug with your resource: if the point is not blocked, the unit will actually try to build the checker there... You should probably issue a stop command after performing the IssueBuildOrder, to make sure there's no dummy being built all over the place.

 

[Kazeon]

That's not really a problem, as the same restriction applies to any kind of pathing blocker.

Checked out your submission to the spells section and damn! Effective script is effective!
Can you offer an optional function that uses a 128x128 blocker? This has a couple of advantages when trying to detect diagonal pathing blockers (like the fence doodad) on IsLineBetweenPointsPathable-type functions or when checking pathing for big units like bosses.

I think that a single 128x128 check has a reduced performance hit compared to 4 64x64 checks.

Like "IsAreaWalkable"? Sounds good to me!

Also, I think I found a bug with your resource: if the point is not blocked, the unit will actually try to build the checker there... You should probably issue a stop command after performing the IssueBuildOrder, to make sure there's no dummy being built all over the place.

I have removed its feet so it can't build anything
call UnitRemoveAbility(PathChecker, 'Amov')

EDIT:
Second thought, anything other that buildability check is quite pixel-precise so less accuracy won't mean better. I think this is still accurate against diagonal pathing map. That's if I understand you correctly. If you need less accuracy, you will need to increase checkers' collision sizes. Another function is not enough.

 

[Zwiebelchen]

EDIT:
Second thought, anything other that buildability check is quite pixel-precise so less accuracy won't mean better. I think this is still accurate against diagonal pathing map. That's if I understand you correctly. If you need less accuracy, you will need to increase checkers' collision sizes. Another function is not enough.

I illustrated the problem with diagonal blockers here:
http://www.hiveworkshop.com/forums/2645970-post18.html

Basicly, to circumvent this problem, one would perform 4 64x64 cell checks, in order to find out if there are two blocked cells in any diagonal pattern (which, by the way collision works in WC3, means that the unit can not walk through). This could be optimized by providing a pathability checker that is 128x128 in size (so 1 function call instead of 4).

To implement this in your system, you just need to create a copy of your functions like "IsTerrainWalkable128" that uses a blocker with a 2x2 cell pathing texture.

 

[Kazeon]

To implement this in your system, you just need to create a copy of your functions like "IsTerrainWalkable128" that uses a blocker with a 2x2 cell pathing texture.

That means we need another dummy units.

 

[Zwiebelchen]

That means we need another dummy units.

Which isn't really a problem

 

[Dr Super Good]

The rect is just 64x64 wide. I'm not sure if it's really heavy. What I know is that unit enumeration is getting heavier as the area radius is bigger and there are more units to be enumerated. But in a 64x64 rect, how many units can it be?

Does it matter? If the game is poorly written it will enumerate through all units on the map each time checking if they are in the rect. The operation cost is outside of the number of units it returns. It should be using a quad tree which depending on scale might limit the complexity to something more reasonable.

 

[Kazeon]

Does it matter? If the game is poorly written it will enumerate through all units on the map each time checking if they are in the rect. The operation cost is outside of the number of units it returns. It should be using a quad tree which depending on scale might limit the complexity to something more reasonable.

How about EnumUnitsInRange? Does it work that way as well?

 

[Dr Super Good]

How about EnumUnitsInRange? Does it work that way as well?

All positional searches should be using structures like quad trees. As such the performance should not depend on many units outside the search area.

This is why the game still performs well when there are several thousand units on the map doing stuff.