TD Blockage system, any suggestions?

[Strilanc]

That's why a simple runner referee is better.

I can juke the runner referee just as well as the rest of the runners. Remember: I haven't walled at any point, I just keep moving the exit. Something like this:

(R is runner, x are walls, <>v^ are runner direction)

Runner heading to right-side exit.
xxx x
x x x
x x x
x x x
x x x
x R>x
xxxxx

Open left-side exit
x x x
x x x
x x^x
x xRx
x x x
x   x
xxxxx

Close right-side exit. Haha.
x xxx
x xRx
x xvx
x x x
x x x
x   x
xxxxx

Repeat.
x xxx
x x x
x x x
x x x
x x x
x<R x
xxxxx

Units in warcraft 3 are perfectly happy to keep running back and forth in a maze like that. Just don't wait too long to close off the exit.

 

[Sevion]

That's why you give referees no model/really small models or somehow make them invisible

 

[Strilanc]

That's why you give referees no model/really small models or somehow make them invisible

Hmm, that could work. The main downsides would be blocking building placement by accident or false-positives on players re-mazing a part the runners had already passed through.

 

[Sevion]

True. But none of these systems could be perfect with the ability to remaze.

 

[Strilanc]

True. But none of these systems could be perfect with the ability to remaze.

Have you ever played power towers (by me)? It allows remazing and uses backtrack detection to prevent pathing abuse. It's not perfect, but surprisingly hard to beat (especially reliably).

 

[Sevion]

Actually, yes. It happens to be one of my favorite TD maps in WC3. I still believe that an invisible referee is easiest. Besides, you could give him some really fast walk speed and just stop worrying about it. If people decide to abuse the system, they can abuse it... if they can figure out where the referee is.

But if you want to, you can make some extremely complicated pathing detection system.

 

[Inflicted]

lol i dont really mind if players "juggle"/"maze" the creeps.

and yes i had an invisible runner but there are a few problems with it.
also the problem of you cant build on the position of the runner, u get that red square? its iritating..
id rather find a different method.

and Strilanc weldone, great map
could you please tell me how you did ur mazing/backtrack system?

 

[Rushhour]

Hi there. As I promised I wrote an algorithm to check for the pathing

The amazing thing is that it worked immediately! I only had one obvious bug, and that was solved easily That's an amazing feeling, just wanted to let you know.

If you want to know how it works, feel free to ask. I don't have a good documentation in the code and I'm pretty sure it's unclear if you don't see the concept.

I didn't use the basic ant algorith since that needed to many equations; I needed to store too much stuff and it took too much time.

This one is 100% accurate if you set the OFFSET values right. It builds a 'square' around the start point.

___________
|        t |
|          |
|     s    |
|          |
|_________|
s=start
t=target
DIRECTION_OFFSET_X_RIGHT is from s to the right line, 
DIRECTION_OFFSET_Y_UP is from s to the top line,
  .
  .
  .

So if 't' isn't within the square, the size will increase automatically. (depending on the maze this could still be too small, but it's only in case you forgot).

For your maze, there shouldn't be any problem at all, since it is pretty small, straight and not any stuff like cliffs inside.
Remember that this algorith will work for any terrain, rocks,... .

The equation will need some seconds. If you know that the total X-OFFSET is pretty small you can increase the PAUSE_THREAD_EVERY_X_ROWS. But this will mainly be trial and error.
Right now it needs 1-2 seconds for a pretty big maze, the fps will drop if you build some towers at once and if the maze is big, but there are no 'leaks' .

This doesn't cause problems if two (or more) towers are built at the same time. It could only happen that both get destroyed even if one wouldn't block if the first one wasn't built!

Do you know (v)Jass? You need JassNewGenPack to use this (JassHelper compiles it to normal Jass)

Check the bottom of the script. In the function 'StartCheckingThePath' , which is called by the event "a construction finishes", you see how I check if there is a path between the coords S(-1000,-1000) and T(-500,-500) . If there is one, I create a special effect, if not I destroy the building.

library ANTS initializer Init

globals
    //function: PathExists takes real fromx, real fromy, real targetx, real targety returns boolean
    //function: PathExistsLoc takes location fromloc, location targetloc returns boolean
    
    
    private constant real OFFSET=65.
    //distance between each check-point. 65 should be a great deal even for the smallest towers
    private constant real DIRECTION_OFFSET_X_LEFT=1500. 
    private constant real DIRECTION_OFFSET_X_RIGHT=1500. 
    private constant real DIRECTION_OFFSET_Y_UP=1500. 
    private constant real DIRECTION_OFFSET_Y_DOWN=1500.
    //Distance of the check-square centered on the startlocation of the check. Make smaller to increase check speed, higher to increase accuracy
    
    private constant boolean SAFER_PATHING_CHECK=false 
    //if there are items lying on the floor, this will make sure they don't count as unwalkable. 'false' is recommended for speed reasons
endglobals


    //RATHER DO NOT TOUCH THIS:
globals    
    //thanks to vexorian once again for his pathability-checking trick; modified
    private constant integer PAUSE_THREAD_EVERY_X_ROWS=10 //lower number = slower but less chance of function and thread stopping
    private constant real ADDITIONAL_OFFSET=500. //this offset is added when the standard offset wasn't enough and the distance between target and start is set as offset
    private constant integer UNPATHABLE_INDEX=1337 //random high number
    private item it
    private boolean bool
endglobals

private function CheckPathabilityTrickGet takes nothing returns nothing
    set bool = bool or (GetEnumItem()!=bj_itemRandomCurrentPick)
endfunction

private function CheckPathabilityTrick takes item p, real x, real y returns boolean
    local integer i=60
    local rect r
    if ((Pow(GetItemX(p)-x,2)+Pow(GetItemY(p)-y,2))<=100) then
        return true
    endif
    static if SAFER_PATHING_CHECK then
        set r=Rect(x-i,y-i,x+i,y+i)
        set bj_itemRandomCurrentPick=p
        set bool=false
        call EnumItemsInRect(r,null,function CheckPathabilityTrickGet)
        call RemoveRect(r)
        set r=null
        return bool
    else
        return false
    endif
endfunction

private function CheckPathability takes real x, real y returns boolean
    local boolean b=false
    local real itemx
    local real itemy
    call SetItemVisible(it,true)
    call SetItemPosition(it,x,y)
    static if SAFER_PATHING_CHECK then
        set b= CheckPathabilityTrick(it,x,y)
    else
        set itemx=GetItemX(it)-x
        set itemy=GetItemY(it)-y
        if ((itemx*itemx+itemy*itemy)<=100) then
            set b= true
        endif
    endif
    call SetItemVisible(it,false)
    return b
endfunction



function PathExists takes real fromX, real fromY, real toX, real toY returns boolean
local integer array PointIndex
local integer CurrIndexHolder=1
local integer CurrPointIndex
local integer arrayInd
local integer arrayIndBelow
local integer PointCount
local integer TempPointCount

local integer TargetIndex=0
local integer FromIndex=0

local real DirectionOffsetXRight
local real DirectionOffsetXLeft
local real DirectionOffsetYUp
local real DirectionOffsetYDown
local integer ROW_MAX_CELLS
local integer row


local real baseY
local real baseX
local real currX
local real currY

local real maxMapX=GetRectMaxX(bj_mapInitialPlayableArea)
local real maxMapY=GetRectMaxY(bj_mapInitialPlayableArea)
//Safety checks:
//Break if the target or start location isn't even walkable.
if CheckPathability(fromX,fromY) == false then
    debug call BJDebugMsg("Startlocation isn't walkable!")
    return false
endif
if CheckPathability(toX,toY) == false then
    debug call BJDebugMsg("Targetlocation isn't walkable!")
    return false
endif
//Check if the offset is too small to even reach from start to target, set to minimum+ADDITIONAL_OFFSET
if toX-fromX >DIRECTION_OFFSET_X_RIGHT  then
    set DirectionOffsetXRight=toX-fromX+ADDITIONAL_OFFSET
else
    set DirectionOffsetXRight=DIRECTION_OFFSET_X_RIGHT
endif
if (fromX-toX) > DIRECTION_OFFSET_X_LEFT  then
    set DirectionOffsetXLeft=fromX-toX+ADDITIONAL_OFFSET
else
    set DirectionOffsetXLeft=DIRECTION_OFFSET_X_LEFT
endif
if (toY-fromY) > DIRECTION_OFFSET_Y_UP  then
    set DirectionOffsetYUp=toY-fromY+ADDITIONAL_OFFSET
else
    set DirectionOffsetYUp=DIRECTION_OFFSET_Y_UP
endif
if (fromY-toY) > DIRECTION_OFFSET_Y_DOWN  then
    set DirectionOffsetYDown=fromY-toY+ADDITIONAL_OFFSET
else
    set DirectionOffsetYDown=DIRECTION_OFFSET_Y_DOWN
endif

//when the start would be out of the map with the current offset, set it to the edge of the map

set baseX=fromX-DirectionOffsetXLeft
if baseX <GetRectMinX(bj_mapInitialPlayableArea) then
    set baseX=GetRectMinX(bj_mapInitialPlayableArea)
endif
set baseY=fromY-DirectionOffsetYDown
if baseY <GetRectMinY(bj_mapInitialPlayableArea) then
    set baseY=GetRectMinY(bj_mapInitialPlayableArea)
endif
set ROW_MAX_CELLS=R2I(((DirectionOffsetXRight+RAbsBJ(fromX-baseX))/OFFSET)+5.)


set row=1
set currX=baseX
set currY=baseY+(row-1)*OFFSET

set CurrPointIndex=CurrIndexHolder
set PointCount=1
set arrayInd=0
set arrayIndBelow=1
loop //the first row, at the left hand bottom of the offset square centered at the startpoint
    if CheckPathability(currX,currY) then
        set PointIndex[arrayInd*ROW_MAX_CELLS+PointCount]=CurrPointIndex
    else
        set PointIndex[arrayInd*ROW_MAX_CELLS+PointCount]=UNPATHABLE_INDEX
        set CurrIndexHolder=CurrIndexHolder+1
        set CurrPointIndex=CurrIndexHolder
    endif
    set PointCount=PointCount+1
    set currX=currX+OFFSET 
    exitwhen currX>fromX+DirectionOffsetXRight or currX >=maxMapX
endloop


//starting the main loop, looping throw each row
    loop
        set row=row+1
        set PointCount=1

        if arrayInd == 0 then
            set arrayInd=1
            set arrayIndBelow=0
        else
            set arrayInd=0
            set arrayIndBelow=1
        endif
        set currX=baseX
        set currY=baseY+(row-1)*OFFSET
        if (row/PAUSE_THREAD_EVERY_X_ROWS)*PAUSE_THREAD_EVERY_X_ROWS ==row then
            //pause regularly to avoid op-limit
            call TriggerSleepAction(0.)
        endif
        set CurrPointIndex=0
        loop
            if CheckPathability(currX,currY) then
            

                if CurrPointIndex !=0 then
                    if PointIndex[arrayIndBelow*ROW_MAX_CELLS+PointCount] != CurrPointIndex and PointIndex[arrayIndBelow*ROW_MAX_CELLS+PointCount] != UNPATHABLE_INDEX then
                        
                        if FromIndex==CurrPointIndex then
                            set FromIndex=PointIndex[arrayIndBelow*ROW_MAX_CELLS+PointCount]
                        endif
                        if TargetIndex == CurrPointIndex then
                            set TargetIndex=PointIndex[arrayIndBelow*ROW_MAX_CELLS+PointCount]
                        endif
                        set CurrPointIndex =PointIndex[arrayIndBelow*ROW_MAX_CELLS+PointCount]
                        set TempPointCount=PointCount

                         loop
                            set PointIndex[arrayInd*ROW_MAX_CELLS+TempPointCount]=CurrPointIndex
                            set TempPointCount=TempPointCount-1
                            exitwhen PointIndex[arrayInd*ROW_MAX_CELLS+TempPointCount] ==UNPATHABLE_INDEX or TempPointCount < 1
                        endloop
                    else                         
                        set PointIndex[arrayInd*ROW_MAX_CELLS+PointCount]=CurrPointIndex
                    endif
                 
                elseif PointIndex[arrayIndBelow*ROW_MAX_CELLS+PointCount] != UNPATHABLE_INDEX then
                    set CurrPointIndex=PointIndex[arrayIndBelow*ROW_MAX_CELLS+PointCount]
                    set PointIndex[arrayInd*ROW_MAX_CELLS+PointCount]=CurrPointIndex
                else
                    set CurrIndexHolder=CurrIndexHolder+1
                    set CurrPointIndex=CurrIndexHolder
                    set PointIndex[arrayInd*ROW_MAX_CELLS+PointCount]=CurrPointIndex
                endif

                if RAbsBJ(currX-fromX)<=OFFSET and RAbsBJ(currY-fromY)<=OFFSET then
                    set FromIndex=CurrPointIndex
                elseif RAbsBJ(currX-toX)<=OFFSET and RAbsBJ(currY-toY)<=OFFSET then
                    set TargetIndex=CurrPointIndex
                endif
                
            else
                set PointIndex[arrayInd*ROW_MAX_CELLS+PointCount]=UNPATHABLE_INDEX
                set CurrPointIndex=0
            endif
            
            
            set PointCount=PointCount+1
            set currX=currX+OFFSET 
        exitwhen currX >fromX+DirectionOffsetXRight or currX >= maxMapX
        endloop
        
    exitwhen currY >=fromY+DirectionOffsetYUp or (FromIndex != 0 and FromIndex ==TargetIndex) or currY >=maxMapY
    endloop

if FromIndex==TargetIndex and FromIndex !=0 then
    debug call BJDebugMsg("Found a path.")
    return true
else
    debug call BJDebugMsg("NO PATH!")
    return false
endif

endfunction

function PathExistsLoc takes location fromloc, location targetloc returns boolean
    return PathExists(GetLocationX(fromloc),GetLocationY(fromloc),GetLocationX(targetloc),GetLocationY(targetloc))
endfunction

function StartCheckingThePath takes nothing returns nothing
local unit u=GetConstructedStructure()
if PathExists(-1000.,-1000.,-500.,-500.) then
    call DestroyEffect(AddSpecialEffect("Abilities\\Spells\\Human\\Flare\\FlareCaster.mdl",GetUnitX(u),GetUnitY(u)))
else
    call KillUnit(u)
endif
set u=null
endfunction 

private function Init takes nothing returns nothing
local trigger t=CreateTrigger()
call TriggerRegisterAnyUnitEventBJ(t,EVENT_PLAYER_UNIT_CONSTRUCT_FINISH)
call TriggerAddAction(t,function StartCheckingThePath )

//Necessary for the system:
//-----------------------------
set it=CreateItem('ciri',0.,0.)
call SetItemVisible(it,false)
//-----------------------------
endfunction

endlibrary

 

[Inflicted]

ok wow that looks good, thanx alot. umm im not so good on Jass or vJass but il get the JassNewGenPack as u mentioned.

could i ask you a favor?

could you add a demo map with this in, and show where i must change the values? please and thank u

 

[Rushhour]

Here we go. You will need NewGen Editor to edit the map and/or the system.

Note the map is open source and NOT made by me. It was just the first unprotected map I found in my folder.