[Snippet] IsPathBlocked

[Nestharus]

This resource has moved here.

--

gone

 

[Bribe]

Any way to cut the trigger evaluations maybe in half? The lag is pretty impressive right when you're about to plot the buildings each time, about 1-2 seconds.

 

[Nestharus]

Already updated to so that users can modify evaluations based on size of area ; ). However, for areas that aren't tiny, it'll still cause freezes ; |.

edit
bleh, it wasn't freezing in the demo map for me D:, but it is now freezing in the wmw map. I'll see what I can do to optimize this.

edit
I'm going to upgrade this to something between my own idea for a pathing algorithm and A* Pathing ; ).

edit
hmm... need to ponder now D:. A* is good for finding the shortest path, but I am sure that there are better ways to detect a simple block : ).

 

[Bribe]

Isn't it when you order a second peasant to build, but the pathing point is blocked, that he stops before even moving? You can just have a peasant at start point and tell him to build at finish point.

If not, here's another idea:

Make a dummy that can build a dummy building, and when IssuePointOrderById returns true the point is pathable, and then you can skip right to the next grid space instead of checking every x, y, you check every 32x * 32y all at once.

I know that IssuePointOrderById will return true or false because I used a similar technique in Knockback 2D.

 

[Nestharus]

hm... I'll check it out o-o

edit
failure -.-, he has to run to the blocking place first >.>


Trust me, my latest algorithm finds blocks very quickly : ).

 

[Bribe]

Does it do a check once every 1x1 gridspace or a check every 32x32 (or 16x16)?

 

[Nestharus]

Bribe, I actually have an idea for an extremely fast algorithm ; ).

while (not found obstruction)
    go towards target
end while

add 2 directions to stack (both perpendicular)

while (stack not empty and not found target)
    while (not found target and not blocked)
        go in perpendicular direction and add other perpendicular direction to a stack
    end while
end while

It won't find the fastest route, but it's short and sweet .


It's worst case scenario would be when following a maze, but even then it would be quite fast ; P.


I think that wc3 is just too slow for A* Pathing ;\

 

[Bribe]

Hmm so it's like a tree structure, doesn't sound too bad.

 

[Magtheridon96]

Why does the user have to pass an op-count? :/
Does that make it less user-friendly? D:

edit
I noticed that your documentation ignores the last parameter.
I guess this is only for debug-purposes at the moment, right? :/

 

[Nestharus]

I would not recommend using this as wc3 isn't fast enough to handle the A* Pathing Algorithm :\.

 

[Magtheridon96]

If Warcraft III can't handle something like this only in the form of a bunch of reals (meaning there's absolutely no visuals), then this is hopeless >_>

I hope your new algorithm will beat this by at least 100-fold >

edit

On a side-note, Warcraft uses something like this internally:

I know this because this is exactly how units move when you issue a distant move order

 

[Nestharus]

I hope your new algorithm will beat this by at least 100-fold >

New algorithm is strictly anti-block. It does not find the shortest path : p.


And yes, that first one is in fact the A* Pathing Algorithm, which is what this resource currently uses. In fact, if you create a unit with locust every time it checks a node, it operates exactly like that gif ;D.

edit
Realize that for pathing, you need a binary heap. It is O(log(n)) for every operation. Furthermore, you are going over 32x32 tiles, meaning that you could be going through 2500 tiles for a rather small area ; ). log(2500) is rather large, and in fact the algorithm hits the op limit at around 135 iterations (with the optimizations), meaning that there may be 2500/(8*135) trigger evaluations for a very small area.

 

[Bribe]

So does your current version have the most up-to-date algorithm, or are you still working on it?

I still recommend IssuePointOrderById, because it can cover a wide area at a time (can be set by the user to either 16x16 or 32x32 for example).

 

[Nestharus]

Bribe, I'm not using IssuePointOrderById, and no, the current version up is not the latest. When the latest is done, I will bump the thread, don't you worry ; P. Just working out some bugs in it ; ). Need to make sure it works in every situation : D. And yes, it is very, very fast teehee ^)^.

 

[Nestharus]

Here is the working lib. It needs some serious optimization, but it runs through a LOT less processes than the A* did ; ).

Now the reason that it is slow is because of all of the normalization crap : P, heh. I'm going to split path up into real paths and integer paths to speed the hell out of this (remove all of the normalization stuff and if statements).


However, I want you to notice that op limit in this is 200. A* was 100. This means that this is 2x faster w/o the optimizations, hehehe ; ).


I'll be getting to optimizing it tomorrow. It is 3:30 am right now... sooo it's bed time ^^, lol.

library IsPathBlocked uses Table, IsPathable
    private keyword Path
    
    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 NormalizeComponent takes real p returns integer
        if (0 < p) then
            return R2I(p + 16)/32*32
        endif
        return R2I(p - 16)/32*32
    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 Tile extends array
        private static Table table
        method operator [] takes integer y returns boolean
            return table.boolean[this*256+y]
        endmethod
        method operator []= takes integer y, boolean v returns nothing
            set table.boolean[this*256+y] = v
        endmethod
        static method clear takes nothing returns nothing
            call table.flush()
        endmethod
        implement InitTiles
    endstruct
    private struct Stack extends array
        private static thistype this
        private Path pathp
        static method operator first takes nothing returns thistype
            return this.pathp
        endmethod
        static method push takes Path path returns nothing
            set this = this + 1
            set this.pathp = path
        endmethod
        static method pop takes nothing returns nothing
            set this = this - 1
        endmethod
        static method clear takes nothing returns nothing
            set this = 0
        endmethod
    endstruct
    
    private struct Path extends array
        private static integer instanceCount = 0
        private static integer array recycler
        readonly static real tx = 0
        readonly static real ty = 0
        readonly static real tr = 0
        readonly static integer pt = 0
        readonly static boolean isBlocked = true
        readonly real x
        readonly real y
        readonly integer xi
        readonly integer yi
        readonly boolean open0
        readonly boolean open90
        readonly boolean open180
        readonly boolean open270
        readonly integer px
        readonly integer py
        readonly real ox
        readonly real oy
        readonly integer ax
        readonly integer ay
        readonly boolean open
        static method create takes real x, real y, real ox, real oy, boolean o returns thistype
            local thistype this
            
            local integer xi = NormalizeComponent(x)
            local integer yi = NormalizeComponent(y)
            
            local real angle
            
            if (Tile[xi][yi]) then
                return -1
            endif
            
            if (IsPathable(xi, yi, pt)) then
                set Tile[xi][yi] = true
                
                set this = recycler[0]
                if (0 == this) then
                    set this = instanceCount + 1
                    set instanceCount = this
                else
                    set recycler[0] = recycler[this]
                endif
                
                set this.xi = NormalizeComponent(x)
                set this.yi = NormalizeComponent(y)
                set this.ax = NormalizeComponent(ox)
                set this.ay = NormalizeComponent(oy)
                set this.open = o
                
                if (o) then
                    set this.x = x
                    set this.y = y
                    set this.ox = ox
                    set this.oy = oy
                    
                    set angle = CalculateAngleBetweenPoints(x, y, tx, ty)
                    set ox = CalculateComponentX(angle)
                    set oy = CalculateComponentY(angle)
                    
                    set isBlocked = x + tr < tx or x - tr > tx or y + tr < ty or y - tr > ty
                else
                    set isBlocked = xi + tr < tx or xi - tr > tx or yi + tr < ty or yi - tr > ty
                endif
                
                set open0 = IsPathable(xi + 32, yi, pt)
                set open90 = IsPathable(xi, yi + 32, pt)
                set open180 = IsPathable(xi - 32, yi, pt)
                set open270 = IsPathable(xi, yi - 32, pt)
                
                return this
            endif
            
            return 0
        endmethod
        method destroy takes nothing returns nothing
            set recycler[this] = recycler[0]
            set recycler[0] = this
        endmethod
        static method clear takes nothing returns nothing
            set instanceCount = 0
            set recycler[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.isBlocked = true
        endmethod
        private method branchEx2 takes boolean os, boolean oe, integer ax, integer ay returns nothing
            local Path path
            
            if (os != oe) then
                if (os) then
                    set path = Path.create(px + ax, py + ay, ax, ay, false)
                else
                    set path = Path.create(xi + ax, yi + ay, ax, ay, false)
                endif
                if (0 < path) then
                    call Stack.push(path)
                endif
            endif
        endmethod
        private method branchEx takes boolean os, boolean oe, integer ax, integer ay returns nothing
            local Path path
            
            if (os != oe) then
                if (os) then
                    set path = Path.create(px + ox, py + oy, ox, oy, true)
                    if (0 < path) then
                        call Stack.push(path)
                    endif
                    set path = Path.create(px + ax, py + ay, ax, ay, false)
                    if (0 < path) then
                        call Stack.push(path)
                    endif
                else
                    set path = Path.create(xi + ox, yi + oy, ox, oy, true)
                    if (0 < path) then
                        call Stack.push(path)
                    endif
                    set path = Path.create(xi + ax, yi + ay, ax, ay, false)
                    if (0 < path) then
                        call Stack.push(path)
                    endif
                endif
            endif
        endmethod
        method branch takes integer ax, integer ay returns nothing
            local Path path = thistype.create(NormalizeComponent(this.xi) + ax, NormalizeComponent(this.yi) + ay, ax, ay, false)
            if (0 < path) then
                call Stack.push(path)
            endif
        endmethod
        method move takes nothing returns integer
            local boolean o0 = open0
            local boolean o90 = open90
            local boolean o180 = open180
            local boolean o270 = open270
            local boolean o = open
            
            local real angle
            local real nAngle
            
            local Path np
            
            set px = xi
            set py = yi
            
            if (o) then
                set xi = NormalizeComponent(x + ox)
                set yi = NormalizeComponent(y + oy)
            else
                set xi = xi + ax
                set yi = yi + ay
            endif
            
            if (Tile[xi][yi]) then
                return -1
            endif
            
            if (IsPathable(xi, yi, pt)) then
                set Tile[xi][yi] = true
                
                //      Test
                //call CreateUnit(Player(0), 'hfoo', xi, yi, 0)
                //      Test
                
                set open0 = IsPathable(xi + 32, yi, pt)
                set open90 = IsPathable(xi, yi + 32, pt)
                set open180 = IsPathable(xi - 32, yi, pt)
                set open270 = IsPathable(xi, yi - 32, pt)
                
                if (not o) then
                    set angle = CalculateAngleBetweenPoints(xi, yi, tx, ty)
                    set nAngle = NormalizeAngle(angle)
                    set ox = CalculateComponentX(angle)
                    set oy = CalculateComponentY(angle)
                    
                    call branchEx(o0, open0, 32, 0)
                    call branchEx(o90, open90, 0, 32)
                    call branchEx(o180, open180, -32, 0)
                    call branchEx(o270, open270, 0, -32)
                else
                    call branchEx2(o0, open0, 32, 0)
                    call branchEx2(o90, open90, 0, 32)
                    call branchEx2(o180, open180, -32, 0)
                    call branchEx2(o270, open270, 0, -32)
                endif
                
                if (o) then
                    set x = x + ox
                    set y = y + oy
                    set isBlocked = x + tr < tx or x - tr > tx or y + tr < ty or y - tr > ty
                else
                    set isBlocked = xi + tr < tx or xi - tr > tx or yi + tr < ty or yi - tr > ty
                endif
                
                return 1
            endif
            
            if (o) then
                set xi = NormalizeComponent(x)
                set yi = NormalizeComponent(y)
            else
                set xi = xi - ax
                set yi = yi - ay
            endif
            
            return 0
        endmethod
    endstruct
    
    static if DEBUG_MODE then
        private struct Thread extends array
            static constant integer OP_LIMIT = 200
            private static boolean finished = false
            
            static method start takes nothing returns nothing
                set finished = false
            endmethod
            static method finish takes nothing returns nothing
                set finished = true
            endmethod
            static method operator crashed takes nothing returns boolean
                return not finished
            endmethod
        endstruct
    endif
    
    private function ClearAll takes nothing returns nothing
        call Path.clear()
        call Stack.clear()
        call Tile.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 integer op = Thread.OP_LIMIT
            local Path path
            local integer move
            
            call Thread.start()
            loop
                set path = Stack.first
                
                exitwhen 0 == path or not path.isBlocked or 0 == op
                set op = op - 1
                
                set move = path.move()
                if (1 != move) then
                    call Stack.pop()
                    if (0 == path.move()) then
                        call path.branch(0, 32)
                        call path.branch(0, -32)
                        call path.branch(32, 0)
                        call path.branch(-32, 0)
                    endif
                    call path.destroy()
                endif
            endloop
            call Thread.finish()
            
            /*
            if ((not Path.isBlocked or 0 == Stack.first) and null != GetExpiredTimer()) then
                if (Path.isBlocked) 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 Path.isBlocked or 0 == Stack.first
        endmethod
        
        private static method initialize takes real originX, real originY, real targetX, real targetY, real targetRadius, integer pathingType returns boolean
            local Path o
            local Path origin
            local real angle
            local real ax
            local real ay
            local boolean init = false
            
            call ClearAll()
            
            call Path.initialize(targetX, targetY, targetRadius, pathingType)
            
            set angle = CalculateAngleBetweenPoints(originX, originY, targetX, targetY)
            set o = Path.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 = Path.create(originX + ax, originY + ay, ax, ay, false)
            if (0 != origin) then
                call Stack.push(origin)
                set init = true
            endif
            
            set angle = NormalizeAngle(angle + bj_PI/2)
            set ax = CalculateComponentX(angle)
            set ay = CalculateComponentY(angle)
            set origin = Path.create(originX + ax, originY + ay, ax, ay, false)
            if (0 != origin) then
                call Stack.push(origin)
                set init = true
            endif
            
            set angle = NormalizeAngle(angle + bj_PI/2)
            set ax = CalculateComponentX(angle)
            set ay = CalculateComponentY(angle)
            set origin = Path.create(originX + ax, originY + ay, ax, ay, false)
            if (0 != origin) then
                call Stack.push(origin)
                set init = true
            endif
            
            if (0 != o) then
                call Stack.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)
                    debug if (Thread.crashed) then
                        debug call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"IS PATH BLOCKED ERROR: THREAD CRASHED")
                        debug return true
                    debug endif
                endloop
                //call TimerStart(CreateTimer(), .025, true, function thistype.isPathBlocked)
            endif
            
            return Path.isBlocked
        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

 

[jim7777]

hmmm what kind of thing does this check?

The line between the source point and target point?
Or the area around the source point with an ending radius depending on the distance of the target point from the source point??

hmm
if it can check both, great LOL
and i think can be useful for detecting spells? Whether if the path between the two points are blocked or not

integer pathingType
any explanation??

 

[Dirac]

The line between the source point and target point?
Or the area around the source point with an ending radius depending on the distance of the target point from the source point??

No and no.
It checks if there's a way to walk from point A to point B using an algorithm similar to A* but less extensive (To only calculate posibility of path, not shortest path)
See the gifs that Mag posted above. Thats how the algorithm works.

Nes, it would be epic if you could develop a system (module to implement) that stores the points of axis of a path between two points into a stack, to move effects/units manually across the map without relying on w3's pathing systems, limited to 522 speed.

edit i think this could use some help from http://www.hiveworkshop.com/forums/...-code-snippets-40758/index46.html#post2054375

 

[Nestharus]

Dirac, it doesn't operate at all like mag's gifs now ; ). The algorithm is very, very different ; P.


It will check if the path between 2 points (point A and radius around point B) is open. It does this by going towards the point. Any time there is a change in environment (suddenly an obstruction somewhere), it branches towards that change and goes to the point if it isn't doing so already. Every time there is an obstruction in its path, it branches in all directions. What this means is that it'll end up tracing walls until it can get around them ^)^.

 

[Magtheridon96]

Spoiler

Don't call it Mag's gif D:
I got it off of Wikipedia D:

Anyway, Nes, that sounds great
Too bad it's still going to need a lot of iterations :/
(At least the number of iterations will be less though ^.^)

 

[Nestharus]

Ok... A* fills up the entire space if the path is blocked... this outlines the space... That's the area + perimeter vs the perimeter in iterations. The iterations might be 1000 rather large blocked off area vs 7000 for a rather large unblocked area with no obstructions ;o. Blocked might be like 40,000 or more.


This new algorithm is infinitely better for finding blocks ; ).

 

[jim7777]

Ohh
so it's just the same thought, difference is, walking?? LOL

Hurr what about boundaries? Are they detected as well??

 

[Nestharus]

Hurr what about boundaries? Are they detected as well??

Everything is detected, yes.

 

[Nestharus]

Updated ^)^. It's much faster than the one with the A*, but can still easily cause spikes. To remove these spikes, I could put it on a timer, but that'd make it harder to use + cause spikes with many instances anyways. Included is a demo map : ).


For TDs and TWs, this is how you should check if the path was blocked or not ^)^.
if(((IsRightBlocked(x, y) and IsLeftBlocked(x, y)) or (IsBottomBlocked(x, y) and IsTopBlocked(x, y))) and IsPathBlocked(x,y,targetX,targetY,radius,PATH_TYPE_WALKABILITY)) then

And here are the funcs

function IsRightBlocked takes integer x, integer y returns boolean
    return not (IsPathable(x+64, y+64, PATH_TYPE_WALKABILITY) and IsPathable(x+64, y, PATH_TYPE_WALKABILITY) and IsPathable(x+64, y-65, PATH_TYPE_WALKABILITY))
endfunction
function IsLeftBlocked takes integer x, integer y returns boolean
    return not (IsPathable(x-65, y+64, PATH_TYPE_WALKABILITY) and IsPathable(x-65, y, PATH_TYPE_WALKABILITY) and IsPathable(x-65, y-65, PATH_TYPE_WALKABILITY))
endfunction
function IsTopBlocked takes integer x, integer y returns boolean
    return not IsPathable(x, y+64, PATH_TYPE_WALKABILITY)
endfunction
function IsBottomBlocked takes integer x, integer y returns boolean
    return not IsPathable(x, y-65, PATH_TYPE_WALKABILITY)
endfunction

This is so that the algorithm only runs if it needs to : ).

 

[Bribe]

I recommend you make a wrapper which takes all those functions and turns them into one long function, that way the user doesn't have to remember all this stuff.

This seems buggy - what kind of collision size are you checking for? Cause I would definitely say, unless this unit has a collision size of 1, this is a blocked path:

 

[Nestharus]

On the last 2, it says blocked path does it not?

 

[Bribe]

This is where it wouldn't let me place the tower:

 

[Nestharus]

That's from the IsPathPossiblyBlocked or w/e. As I said, it was buggy, and demo map currently has it ; ), lol. I'll update demo map right now as I just fixed it.

edit
up : )

 

[Bribe]

Loving it.

 

[Nestharus]

It is now in my map as I have tested like every single possible scenario with the IsPathPossiblyBlocked thing, hehehe.

So, approved with 5 star for the first general purpose anti block lib? It'll be amazing for all tds and tws ;D.

edit
I know that it still freezes when it runs, but it's as fast as it's going to get and it only freezes on blocks ; p. Also, the freeze isn't nearly as bad as A* or breadth-first search. It's many times faster.

 

[Bribe]

I was thinking, since you know when pathing is going to be an issue (only when buildings are placed), to make a hashtable that remembers the playable grid by row and column, and to never let a single row (or column, depending on the orientation) get completely filled.

 

[Nestharus]

I was thinking, since you know when pathing is going to be an issue (only when buildings are placed), to make a hashtable that remembers the playable grid by row and column, and to never let a single row (or column, depending on the orientation) get completely filled.

not that simple >.>. Think of diag lines and curved lines and so on.

 

[Bribe]

True true.

Or at least to remember when a position was not pathable (in a hashtable)? Until a building gets destroyed... yeah maybe there are too many factors here.

The lag is not TOO bad, considering someone could build a system where someone trying to exploit it (multiple failed attempts just to cause trouble) would get kicked from the game.

Thinking about approving this, once I investigate the API and the requirements a bit more.

 

[Nestharus]

The spikes only occur when the algorithm runs ^)^. If you are using IsPathPossiblyBlocked, then that won't be too often ;D.

 

[Bribe]

Yeah I was getting 0 lag for all the regular towers I placed, I can see that picking up on a really high level for a pro-TD.

You want to go in with me and make one? Probably 4 players max, cause 8 player games take forever to get filled.

 

[Nestharus]

Yeah I was getting 0 lag for all the regular towers I placed, I can see that picking up on a really high level for a pro-TD.

You want to go in with me and make one? Probably 4 players max, cause 8 player games take forever to get filled.

I prefer tws.


Anyways, this script is pretty much as good as it's going to be. It's a very simple API (2 functions) ; ).

 

[Magtheridon96]

Sweet ^.^
The only thing I don't like is the second function
It's not about the functionality, it's about the name :/ (But that's just me)

Off-topic: Tower wars are way funner than Tower Defenses =D

 

[Laiev]

Off-topic: Tower wars are way funner than Tower Defenses =D

This.

 

[Nestharus]

Update:

Improved API
Speed Increase From Improved Algorithm
Couple of bug fixes




Now, I am starting to see a way to improve the algorithm to such an extent as to 100% remove the freeze during even worst case scenarios, but I am still working on it ; P. For now, here is an algorithm that will only freeze for big blocks.

Remember how the old one ran when you'd build towers in such a way as to have a potential block? Try building 3 vertically (2 and then 1 in the middle) to make the algorithm run (just anywhere). You will see that there will be no freeze! Yes, the algorithm did in fact run. Why is there no freeze? Because of the algorithm's improvement ; P.


Now, if I am able to somehow make it so that the algorithm does not trace absolutely everything when there is a block, I'll be gold.

edit
325 op limit -> 824 op limit thus far, meaning more than 2x faster. I am trying to make it not run across empty space. If I can manage that, I can get another major speed boost (from 1724 iterations to 1160 iterations).


edit
Working on a major algorithm improvement. Should be around 4x-6x faster. After that, I'll rewrite the algorithm to a new one, which'll be around 100x faster ;D.

 

[Nestharus]

Updated, freeze is now 100% removed ; ). It does significantly increase loading time of map based on map size (128x128, etc) as well as increase RAM usage, but it is very fast now : D.

0 Freeze Woo! Thing is ready to be approved ;D.


I was going to rewrite the algorithm to be something a bit better, but there are pros and cons to that possibly* better algorithm, so it might as well just stay as is.

 

[Magtheridon96]

Nes, feel free to post these results:

With:
- 3.06Ghz
- 2 cores
- 4GB of RAM

It took:
152 seconds with 160x160
59 seconds with 128x128
18 seconds with 96x96

^.^

 

[Nestharus]

Oh yes, for this... don't allow users to build in corners of your arena. Make the terrain unbuildable or something, otherwise the users will be able to make a huge brick ;o. If you have no corners, then you are fine (like ltw lanes), but if you do, block them off. For example, wmw maps contain 8 corners.

edit
actually, this could be problematic for checkpoints too (rects where creeps have to touch). Just make 1 tile in the rect unbuildable and all is good ; ).

edit
corners don't bug system

 

[Bribe]

I am no rocket scientist, are you trying to kill me with this?

First, what's with the bugs? That doesn't even make sense that those corners would block the map from functioning properly.

Second, great work on reducing the in-game lag. Totally worth it because the in-game result will be free of lag.

Third, why doesn't IsPathBlocked take any additional arguments any more? What unit is supposed to be passed as a parameter there?

 

[Dirac]

Bribe read the documentation.
In a TD all you have to do is IsPathBlocked(tower)
It checks if that "new" tower the user just built is blocking the way

And I agree, the fact that corners bug the system is unacceptable

 

[Nestharus]

And I agree, the fact that corners bug the system is unacceptable

actually if you read first post, corners don't bug system, you can just blanket rects that creeps have to touch with towers

 

[Bribe]

So what exaclty is wrong with building a huge brick, if it doesn't corrupt the pathing algorithm everything is still fine, right?

 

[Nestharus]

So what exaclty is wrong with building a huge brick, if it doesn't corrupt the pathing algorithm everything is still fine, right?

you can't build a huge brick from wall to wall... i was just thinking of blanketing rects specifically in my own wmw map, which would be a huge brick except for touching the opposite wall :\, so I was being silly in my super tired stupor of corners last night, lol. The instant you try to touch the other wall (an actual block), it'll detect it.


To prevent users from blanketing the rect, just make one of the tiles unbuildable (only 1 is needed). In my case, I would make the corners unbuildable since people never build at those anyways. Not sure what to do about the back checkpoints tho ;o.

 

[jim7777]

does this snippet check if the path or line between two points are blocked?

or just a radius around the unit is being checked?

 

[Nestharus]

does this snippet check if the path or line between two points are blocked?

or just a radius around the unit is being checked?

Path. It tries to get from one side of the tower to the other ^)^. If it can't make it to the other side, the path is blocked ;p.

2 sides chosen are based on a set of if statements to check what path through the tower was possibly blocked (left -> right, bottom -> top, right -> top, etc).

 

[Nestharus]

Fixed a bug with towers that are built 1 space apart from each other and a third tower built to possibly block the space in between. It would always read it as a block : ). Now it works properly.


Thanks to magtheridon96 for his wmw noobiness as that allowed him to find the bug ; ).

 

[Magtheridon96]

Thanks to magtheridon96 for his wmw noobiness as that allowed him to find the bug ; ).

I'm improving D:
And my score is pretty good compared to what you've seen other "pros" do D: