[vJASS] Help Optimize This Script :\

[Nestharus]

I've been optimizing and optimizing and it still isn't fast enough ; |. I need it to stay above 32 fps on slower machines (no spike). It even spikes on mine atm :\. Spreading operations over timers isn't really an option >.<.

library IPB uses Table, IsPathable, Tile
    private keyword P
    
    private function NormalizeAngle takes real angle returns real
        local integer a
        
        if (0 > angle) then
            set a = R2I(angle*180/bj_PI - 45)/90*90
        else
            set a = R2I(angle*180/bj_PI + 45)/90*90
        endif
        
        if (0 > a or 360 < a) then
            set a = a - a/360*360
            
            if (0 > a) then
                set a = a + 360
            endif
        endif
        
        return a/180.*bj_PI
    endfunction
    private function CalculateAngleBetweenPoints takes real x, real y, real x2, real y2 returns real
        return Atan2(y2 - y, x2 - x)
    endfunction
    private function CalculateComponentX takes real angle returns real
        return 32*Cos(angle)
    endfunction
    private function CalculateComponentY takes real angle returns real
        return 32*Sin(angle)
    endfunction
    
    private module InitTiles
        private static method onInit takes nothing returns nothing
            set table = Table.create()
        endmethod
    endmodule
    private struct T extends array
        private static Table table
        method operator [] takes integer y returns boolean
            return table.boolean[this*(GetMaxRelativeY() + 1) + y]
        endmethod
        method operator []= takes integer y, boolean v returns nothing
            set table.boolean[this*(GetMaxRelativeY() + 1) + y] = v
        endmethod
        static method clear takes nothing returns nothing
            call table.flush()
        endmethod
        implement InitTiles
    endstruct
    private struct S extends array
        private static thistype t
        private P p
        static method operator first takes nothing returns thistype
            return t.p
        endmethod
        static method push takes P pt returns nothing
            set t = t + 1
            set t.p = pt
        endmethod
        static method pop takes nothing returns nothing
            set t = t - 1
        endmethod
        static method clear takes nothing returns nothing
            set t = 0
        endmethod
    endstruct
    
    private struct P extends array
        private static integer ic = 0
        private static integer array r
        readonly static real tx = 0
        readonly static real ty = 0
        readonly static real tr = 0
        readonly static integer pt = 0
        readonly static boolean ib = true
        readonly real x
        readonly real y
        readonly integer xi
        readonly integer yi
        readonly boolean og0
        readonly boolean og90
        readonly boolean og180
        readonly boolean og270
        readonly integer px
        readonly integer py
        readonly real ox
        readonly real oy
        readonly integer ax
        readonly integer ay
        readonly boolean op
        static method create takes real x, real y, real ox, real oy, boolean o returns thistype
            local thistype t
            
            local integer xi = NormalizeXY(x)
            local integer yi = NormalizeXY(y)
            
            local real angle
            
            if (T[xi - WorldBounds.minX][yi - WorldBounds.minY]) then
                return -1
            endif
            
            if (IsPathable(xi, yi, pt)) then
                set t = r[0]
                if (0 == t) then
                    set t = ic + 1
                    set ic = t
                else
                    set r[0] = r[t]
                endif
                
                set t.xi = NormalizeXY(x)
                set t.yi = NormalizeXY(y)
                set t.op = o
                
                if (o) then
                    set t.ax = 0
                    set t.ay = 0
                    set t.x = x
                    set t.y = y
                    set t.ox = ox
                    set t.oy = oy
                    
                    set angle = CalculateAngleBetweenPoints(x, y, tx, ty)
                    set t.ox = CalculateComponentX(angle)
                    set t.oy = CalculateComponentY(angle)
                    
                    set ib = x + tr < tx or x - tr > tx or y + tr < ty or y - tr > ty
                    
                    set t.og0 = IsPathable(t.xi + 32, t.yi, pt)
                    set t.og180 = IsPathable(t.xi - 32, t.yi, pt)
                    set t.og90 = IsPathable(t.xi, t.yi + 32, pt)
                    set t.og270 = IsPathable(t.xi, t.yi - 32, pt)
                else
                    set T[t.xi - WorldBounds.minX][t.yi - WorldBounds.minY] = true
                    
                    set ib = t.xi + tr < tx or t.xi - tr > tx or t.yi + tr < ty or t.yi - tr > ty
                    set t.ax = NormalizeXY(ox)
                    set t.ay = NormalizeXY(oy)
                    
                    if (0 == t.ax) then
                        set t.og0 = IsPathable(t.xi + 32, t.yi, pt)
                        set t.og180 = IsPathable(t.xi - 32, t.yi, pt)
                    else
                        set t.og90 = IsPathable(t.xi, t.yi + 32, pt)
                        set t.og270 = IsPathable(t.xi, t.yi - 32, pt)
                    endif
                endif
                
                return t
            endif
            
            return 0
        endmethod
        method destroy takes nothing returns nothing
            set r[this] = r[0]
            set r[0] = this
        endmethod
        static method clear takes nothing returns nothing
            set ic = 0
            set r[0] = 0
        endmethod
        static method initialize takes real targetX, real targetY, real targetRadius, integer pathingType returns nothing
            set thistype.tx = targetX
            set thistype.ty = targetY
            set thistype.tr = targetRadius
            set thistype.pt = pathingType
            set thistype.ib = true
        endmethod
        private method b2 takes boolean os, boolean oe, integer ax, integer ay returns nothing
            local P path
            
            if (os != oe) then
                if (os) then
                    set path = P.create(px + ax, py + ay, ax, ay, false)
                else
                    set path = P.create(xi + ax, yi + ay, ax, ay, false)
                endif
                if (0 < path) then
                    call S.pop()
                    call S.push(path)
                    call S.push(this)
                endif
            endif
        endmethod
        private method branchEx takes boolean os, boolean oe, integer ax, integer ay returns nothing
            local P path
            local real angle
            
            if (os != oe) then
                set angle = CalculateAngleBetweenPoints(xi, yi, tx, ty)
                set ox = CalculateComponentX(angle)
                set oy = CalculateComponentY(angle)
                
                if (os) then
                    set path = P.create(px + ax, py + ay, ax, ay, false)
                    if (0 < path) then
                        call S.push(path)
                    endif
                    set path = P.create(px + ox, py + oy, ox, oy, true)
                    if (0 < path) then
                        call S.push(path)
                    endif
                else
                    set path = P.create(xi + ax, yi + ay, ax, ay, false)
                    if (0 < path) then
                        call S.push(path)
                    endif
                    set path = P.create(xi + ox, yi + oy, ox, oy, true)
                    if (0 < path) then
                        call S.push(path)
                    endif
                endif
            endif
        endmethod
        method b takes integer ax, integer ay returns nothing
            set this = thistype.create(this.xi + ax, this.yi + ay, ax, ay, false)
            if (0 < this) then
                call S.push(this)
            endif
        endmethod
        method move takes nothing returns integer
            local boolean o0 = og0
            local boolean o90 = og90
            local boolean o180 = og180
            local boolean o270 = og270
            local boolean o = op
            
            local P np
            
            set px = xi
            set py = yi
            
            if (o) then
                set xi = NormalizeXY(x + ox)
                set yi = NormalizeXY(y + oy)
            else
                set xi = xi + ax
                set yi = yi + ay
            endif
            
            if (T[xi - WorldBounds.minX][yi - WorldBounds.minY]) then
                return -1
            endif
            
            if (IsPathable(xi, yi, pt)) then
                //      Test
                //call CreateUnit(Player(0), 'hfoo', xi, yi, 0)
                //      Test
                
                if (not o) then
                    set T[xi - WorldBounds.minX][yi - WorldBounds.minY] = true
                    
                    if (0 == ax) then   //vertical
                        set og0 = IsPathable(xi + 32, yi, pt)
                        set og180 = IsPathable(xi - 32, yi, pt)
                        call branchEx(o0, og0, 32, 0)
                        call branchEx(o180, og180, -32, 0)
                    else                //horizantal
                        set og90 = IsPathable(xi, yi + 32, pt)
                        set og270 = IsPathable(xi, yi - 32, pt)
                        call branchEx(o90, og90, 0, 32)
                        call branchEx(o270, og270, 0, -32)
                    endif
                else
                    set T[px - WorldBounds.minX][py - WorldBounds.minY] = true
                    
                    set og0 = IsPathable(xi + 32, yi, pt)
                    set og90 = IsPathable(xi, yi + 32, pt)
                    set og180 = IsPathable(xi - 32, yi, pt)
                    set og270 = IsPathable(xi, yi - 32, pt)
                
                    call b2(o0, og0, 32, 0)
                    call b2(o90, og90, 0, 32)
                    call b2(o180, og180, -32, 0)
                    call b2(o270, og270, 0, -32)
                endif
                
                if (o) then
                    set x = x + ox
                    set y = y + oy
                    set ib = x + tr < tx or x - tr > tx or y + tr < ty or y - tr > ty
                else
                    set ib = xi + tr < tx or xi - tr > tx or yi + tr < ty or yi - tr > ty
                endif
                
                return 1
            endif
            
            if (o) then
                set xi = NormalizeXY(x)
                set yi = NormalizeXY(y)
            else
                set xi = xi - ax
                set yi = yi - ay
            endif
            
            return 0
        endmethod
    endstruct
    
    private function ClearAll takes nothing returns nothing
        call P.clear()
        call S.clear()
        call T.clear()
    endfunction
    
    private module InitializeIsBlocked
        private static method onInit takes nothing returns nothing
            set isPathBlockedT = CreateTrigger()
            call TriggerAddCondition(isPathBlockedT, Condition(function thistype.isPathBlocked))
        endmethod
    endmodule
    private struct IsBlocked extends array
        private static trigger isPathBlockedT
        
        private static method isPathBlocked takes nothing returns boolean
            local P path
            local integer move
            local integer p = 519
            
            loop
                set path = S.first
                
                exitwhen 0 == path or 0 == p or not path.ib
                set p = p - 1
                
                set move = path.move()
                if (1 != move) then
                    call S.pop()
                    if (0 == move) then
                        if (not path.op) then
                            if (0 == path.ax) then
                                call path.b(32, 0)
                                call path.b(-32, 0)
                            else
                                call path.b(0, 32)
                                call path.b(0, -32)
                            endif
                        else
                            call path.b(0, 32)
                            call path.b(0, -32)
                            call path.b(32, 0)
                            call path.b(-32, 0)
                        endif
                    endif
                    call path.destroy()
                endif
            endloop
            
            /*
            if ((not P.ib or 0 == S.first) and null != GetExpiredTimer()) then
                if (P.ib) then
                    call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"Blocked")
                else
                    call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"Not Blocked")
                endif
                call PauseTimer(GetExpiredTimer())
                call DestroyTimer(GetExpiredTimer())
            endif
            */
            
            return not P.ib or 0 == S.first
        endmethod
        
        private static method initialize takes real originX, real originY, real targetX, real targetY, real targetRadius, integer pathingType returns boolean
            local P o
            local P origin
            local real angle
            local real ax
            local real ay
            local boolean init = false
            
            call ClearAll()
            
            call P.initialize(targetX, targetY, targetRadius, pathingType)
            
            set angle = CalculateAngleBetweenPoints(originX, originY, targetX, targetY)
            set o = P.create(originX, originY, CalculateComponentX(angle), CalculateComponentY(angle), true)
            
            set angle = NormalizeAngle(angle)
            
            set angle = NormalizeAngle(angle + bj_PI/2)
            set ax = CalculateComponentX(angle)
            set ay = CalculateComponentY(angle)
            set origin = P.create(originX + ax, originY + ay, ax, ay, false)
            if (0 != origin) then
                call S.push(origin)
                set init = true
            endif
            
            set angle = NormalizeAngle(angle + bj_PI/2)
            set ax = CalculateComponentX(angle)
            set ay = CalculateComponentY(angle)
            set origin = P.create(originX + ax, originY + ay, ax, ay, false)
            if (0 != origin) then
                call S.push(origin)
                set init = true
            endif
            
            set angle = NormalizeAngle(angle + bj_PI/2)
            set ax = CalculateComponentX(angle)
            set ay = CalculateComponentY(angle)
            set origin = P.create(originX + ax, originY + ay, ax, ay, false)
            if (0 != origin) then
                call S.push(origin)
                set init = true
            endif
            
            if (0 != o) then
                call S.push(o)
                set init = true
            endif
            
            return init
        endmethod
        
        static method calculate takes real originX, real originY, real targetX, real targetY, real targetRadius, integer pathingType returns boolean
            if (initialize(originX, originY, targetX, targetY, targetRadius, pathingType)) then
                ///*
                loop
                    exitwhen TriggerEvaluate(isPathBlockedT)
                endloop
                //*/
                //call TimerStart(CreateTimer(), .05, true, function thistype.isPathBlocked)
            endif
            
            return P.ib
        endmethod
        implement InitializeIsBlocked
    endstruct
    
    function IsPathBlocked takes real originX, real originY, real targetX, real targetY, real targetRadius, integer pathingType returns boolean
        return IsBlocked.calculate(originX, originY, targetX, targetY, targetRadius, pathingType)
    endfunction
endlibrary

I've also updated the IsPathable lib to make the safe pathing against bricks optional, and while it made this lib significantly faster, it still isn't fast enough.

 

[Cokemonkey11]

Why are you recreating pathing?

Wc3 does this with C++. I'm afraid you're playing with things that are out of the scope of jass' useful environment.

 

[Nestharus]

Uh, for anti block in tower wars and tower defense? lol

If you order a unit to attempt to go to a point that is blocked off, the order will still return true, hence why you need an anti block script.


So yes, this is extremely useful for an entire genre of maps ^)^. And no, giving attacks to the creeps can still easily bug, hence why I'm doing a whole anti block script =).

 

[Cokemonkey11]

You're notorious for building overly complicated things that don't receive much use...

Perhaps if you'd like efficiency you could try dropping hashtable use. Tough to say if that will help or hinder you though.

 

[Nestharus]

Hashtable use is required. It checks if a tile was previous hit or not. Without it, it there would be infinite loops ;p.

 

[Cokemonkey11]

Hashtable use is required.

Hashtable use is never required. But I don't dare call you lazy...

 

[Nestharus]

Uh... if you are checking if coordinates x,y which may be 4008,4008 are hit? Doing that in an array would require a Hash function, which would be slower than using a hashtable : P.

 

[Cokemonkey11]

Uh... if you are checking if coordinates x,y which may be 4008,4008 are hit? Doing that in an array would require a Hash function, which would be slower than using a hashtable : P.

I'm pretty sure that depends on how efficient you make your hash function.

You can probably get to O(logN). You're a smart guy

 

[Nestharus]

The hashtable native will still be faster.. can't compete with c++

 

[emjlr3]

i still don't quite get why you need this?

can you give a scenario?

 

[Cokemonkey11]

The hashtable native will still be faster.. can't compete with c++

When you make the logN search function and remove Table dependency, you can time it and prove me wrong.

For now, I don't believe you. Hashtable is generally a slow utility.

 

[Magtheridon96]

I wonder how Ammorth does it >:l

 

[Nestharus]

When you make the logN search function and remove Table dependency, you can time it and prove me wrong.

For now, I don't believe you. Hashtable is generally a slow utility.

Trees are slower than hashtable natives and are logN and I have made trees in JASS >.>. J4L has also made a Hash function in JASS.

i still don't quite get why you need this?

can you give a scenario?

Any td or tw?? If you are making a maze and you block, the creeps can't get through?

I wonder how Ammorth does it >:l

More than likely, a map specific script ; ).

 

[Cokemonkey11]

What if you made the calculate arguments also take an "allowed rect" which defines a subset of the map in which the script is bound to.

Then, like in the movie above, you could define a rect in the buildable area which is smaller than the whole map and therefor would not lag.

 

[Nestharus]

not a bad idea ; ), except that in most cases you are already checking a closed in area or you have to check a whole area D;, so the extra check would just slow it down.

 

[emjlr3]

what does it matter

ive always preferred the more elegant, and not surprisingly rather easier approach of, if they can't get past, they destroy the towers!

 

[Nestharus]

ive always preferred the more elegant, and not surprisingly rather easier approach of, if they can't get past, they destroy the towers!

unfortunately, if you have blocked before the units are placed, then they won't attack the towers.

 

[Cokemonkey11]

except that in most cases you are already checking a closed in area or you have to check a whole area D;, so the extra check would just slow it down.

not really. without the rect param, your script would check the whole white space. not every td has an enclosed area

 

[Nestharus]

My script would only trace the white space... it does not check every single spot, it traces >.>. And you need to check the outer edges for blocks anyways. Furthermore, if you wanted to check for any block, you'd have to check that entire area as you could build into different areas of the map :\.


Anyways, I think the script is as good as it's going to get ^)^.

 

[Cokemonkey11]

Obviously the red rectangles would be expanded to overlap with the black ones. I just did this in 15 seconds in paint.

I think if you add this it could be ridiculously faster...

 

[Nestharus]

And you are saying the white space in the center is unbuildable? Otherwise the player could possibly block. If it's unbuildable, you should check for buildability ->PATH_TYPE_BUILDABILITY ; ). Actually, you wouldn't really be able to as the origin would be blocked then... hmmm.

But then you'd be out of bounds at the origin with your idea anyways >.<, heh. If the origin was included, then could just block based on buildability .

 

[Cokemonkey11]

The creator of the map may also have defined zones which the builder cannot walk or build...

 

[Nestharus]

Ok, I have just solved how to make this script blazing fast ^)^. Rather than checking between 2 points, check for a local block. For example, when a unit builds a new tower, we don't care about the rest of the map, we just care about whether that tower blocked something or not.

1. check to see if it possibly blocked something
2. check for blockage between possibly blocked points

Now, making it not outline everything when there is a block is going to be my challenge ;o.