AWall - Wall Detection System

[Strilanc]

Summary
A very common problem for tower defense games is detecting when a player is taking advantage of unit pathing. The typical solution involves hoping units attack if they are walled and is very easy to defeat. AWall detects when units have been walled.

The system currently uses HAIL and SUEL [included in the example map], and requires vJass. The example map includes a GUI extension for people who can't write JASS.

Explanation
AWall does various checks to runners that have been added to the system. It periodically checks if runners are stopped, attacking, or stuck, it drops 'breadcrumb' rects behind runners to see if they backtrack, it catches runners attacking towers, etc.

When you create a runner you want wall detection on, add it to the system using AWall_AddRunner. When a player builders a tower use AWall_AddTower on it [only necessary if you use attack prevention]. When a runner reaches a waypoint, use AWall_ResetRunner [backtracking is possible after waypoints, this removes the currently dropped bread crumbs for that unit].

When it detects that a runner has been walled, it runs callbacks registered using AWall_RegisterForWalled. It sets the globals AWall_unit to the runner, and AWall_reason to the reason it believes the unit was walled. For example, if the unit was attacking, reason will be set to AWALL_REASON_ATTACKING. It is the maps job to punish the player, save the unit or whatever else the maker wants. AWall only does detection.

If a unit is/was recently snared or stunned, the wall detection will still activate, but it will have a reason set to AWALL_REASON_PREVENT. When you get PREVENT, you should usually not punish the player, but simply re-order the unit [it may have just been released and started attacking].

Code

JASS:

///////////////////////////////////////////////////////
/// Strilanc's Anti Wall Library
/// Last Updated: July 15, 2008
/// Version: Beta-4
///////////////////////////////////////////////////////
/// Description:
///  - This library attempts to detect when players try to abuse unit pathing in TDs. The main advantage over
///  other techniques is the backtrack detection, which prevents juggling. It also detects attacking, stopping and
///  not moving. It also isn't fooled by units being stunned or snared.
///
/// Explanation:
///  - Units in the system have rects (bread crumbs) placed behind them as they walk around. If they are juggled
///  they will backtrack and re-enter those rects, firing an event. Juggling without causing backtracking is difficult.
///  - If CATCH_STOPPED is set, stopped units are caught when they try to drop crumbs.
///  - If CATCH_ATTACKING is set, attacking units are caught when they attack or try to drop crumbs.
///  - If CATCH_STUCK is set, units who haven't move a lot for awhile are caught.
///  - If a unit was recently stunned or snared and the system detects that it was walled, the callback still runs but
///    the reason is set to AWALL_REASON_PREVENT.
///
/// Usage:
///  - When runners hit waypoints, reset them using AWall_ResetRunner [so they don't fire backtrack detection]
///  - Add runners using AWall_AddRunner(unit), remove runners using AWall_RemoveRunner(unit)
///  - Add towers using AWall_AddTower(unit) [for attack detection]
///  - Add callbacks using AWall_RegisterForWalled(code)
///  - The global values AWall_unit and AWall_reason contain the arguments for the callback.
///  - Possible reasons are AWALL_REASON_BACK_TRACKED, AWALL_REASON_STOPPED, AWALL_REASON_STUCK, 
///    AWALL_REASON_ATTACKING and AWALL_REASON_PREVENT.
///  - If you get AWALL_REASON_PREVENT the unit is not walled, but you should re-order it to its destination.
///
/// Notes:
///  - This system is meant for less than a hundred runners. More runners will tend to interfere with
///  each other and set of the various detectors.
///////////////////////////////////////////////////////
library AWall initializer initAWall requires HAIL, SUEL
    ///=== Settings ============================================================
    globals
        private constant boolean SHOW_DEBUG_MESSAGES = true //show debug messages? (only in debug mode)
        private constant boolean SHOW_ERROR_MESSAGES = true //show serious error messages?
        private constant boolean REMOVE_ON_DEATH = true //auto remove runners when they die?
        private constant boolean CATCH_STOPPED = true //periodically check for stopped runners?
        private constant boolean CATCH_ATTACKING = true //catch attacking runners?
        private constant boolean CATCH_STUCK = true //check for runners trying to move but not progressing for awhile?
    endglobals
    ///=== Global Arguments ============================================================
    globals
        constant integer AWALL_REASON_PREVENT = 0 //the unit set off a check, but was very recently stunned/entangled/etc
        constant integer AWALL_REASON_BACK_TRACKED = 1 //the unit backtracked
        constant integer AWALL_REASON_STOPPED = 2 //the unit is stopped
        constant integer AWALL_REASON_ATTACKING = 3 //the unit is attacking
        constant integer AWALL_REASON_STUCK = 4 //the unit hasn't moved far for awhile

        //callback arguments
        unit AWall_unit = null //walled unit
        integer AWall_reason = 0 //reason the system thinks the unit was walled
    endglobals
    
    ///===================================================================================
    ///===================================================================================
    ///===================================================================================
    
    globals
        private constant real TICK_PERIOD = 1.0 //seconds between dropping crumbs and performing checks
        private constant real CRUMB_SIZE = 32.0 //width and height of a crumb rect
        private constant integer MIN_CRUMB_DISTANCE = 256 //minimum distance a runner must travel to drop a new crumb
        private constant integer MAX_STUCK_COUNT = 8 //a runner is stuck if it fails to move the min distance this many times
        private constant integer NUM_CRUMBS = 4 //number of crumbs per runner
        
        private SpreadUnitEvent eventTowerAttacked = 0
        private trigger callBackTrigger = CreateTrigger() //stores the walled callbacks
        private group runners = CreateGroup() //units in the system
    endglobals
    
    private keyword Runner
    //=== HAIL DEPENDENCE
    //! runtextmacro HAIL_CreateProperty("Runner", "Runner", "private")
    //=== END HAIL DEPENDENCE
        
    private struct Runner
        readonly unit u
        private trigger t = CreateTrigger() //enters region event
        private region bread = CreateRegion()
        private rect array crumbs[NUM_CRUMBS]
        private integer crumbIndex = 0
        private boolean wasHeld = false
        private boolean isHeld = false
        private integer stuckCount = 0
        private real lastX = 0
        private real lastY = 0

        ///Removes a runner's crumbs and resets its stuck count
        public method reset takes nothing returns nothing
            local integer i = 0
            loop
                exitwhen i >= NUM_CRUMBS
                call RegionClearRect(.bread, .crumbs[i])
                call RemoveRect(.crumbs[i])
                set .crumbs[i] = null
                set i = i + 1
            endloop
            set .stuckCount = 0
        endmethod

        ///Fires the walled callback trigger
        public method report takes integer reason, string reasonName returns nothing
            if .wasHeld or .isHeld and reason != AWALL_REASON_PREVENT then
                call .report(AWALL_REASON_PREVENT, reasonName + "(prevented)")
                return
            endif
            call .reset() //avoid double-catch
            debug if SHOW_DEBUG_MESSAGES then
            debug     call BJDebugMsg("AWall caught a " + GetUnitName(.u) + " " + reasonName + ".")
            debug endif
            set AWall_unit = .u
            set AWall_reason = reason
            call TriggerExecute(callBackTrigger)
        endmethod
        
        ///Checks the runner and drops a bread crumb
        public method tick takes nothing returns nothing
            local unit u = .u
            local real x = GetUnitX(u)
            local real y = GetUnitY(u)
            local integer oid = GetUnitCurrentOrder(u)
            set .wasHeld = .isHeld
            set .isHeld = IsUnitType(u,UNIT_TYPE_STUNNED) or IsUnitType(u,UNIT_TYPE_SNARED) // or IsUnitPaused(u) or IsUnitHidden(u) or GetUnitState(u,UNIT_STATE_LIFE)<=0

            //=== Check state
            if CATCH_STOPPED and oid == 0 then
                call .report(AWALL_REASON_STOPPED, "stopped")
            elseif CATCH_ATTACKING and oid == OrderId("attack") then
                call .report(AWALL_REASON_ATTACKING, "attack-moving")
            elseif CATCH_STUCK and RAbsBJ(x-.lastX)+RAbsBJ(y-.lastY) < MIN_CRUMB_DISTANCE then
                if not .isHeld and not .wasHeld then
                    set .stuckCount = .stuckCount + 1
                    if .stuckCount >= MAX_STUCK_COUNT then
                        call .report(AWALL_REASON_STUCK, "stuck")
                    else
                        //don't drop a crumb so close to the last one
                        set u = null
                        return
                    endif
                endif
            else
                set .stuckCount = 0
                set .lastX = x
                set .lastY = y
            endif
            set u = null

            //=== Drop a crumb
            //add previous crumb to bread
            call RegionAddRect(.bread, .crumbs[.crumbIndex])
            //create new crumb
            set .crumbIndex = .crumbIndex + 1
            if .crumbIndex + 1 >= NUM_CRUMBS then
                set .crumbIndex = 0
            endif
            //replace oldest crumb
            if .crumbs[.crumbIndex] == null then
                set .crumbs[.crumbIndex] = Rect(0,0,CRUMB_SIZE,CRUMB_SIZE)
            endif
            call RegionClearRect(.bread, .crumbs[.crumbIndex])
            call MoveRectTo(.crumbs[.crumbIndex], x, y)
        endmethod
        
        ///Catches units treading over bread crumbs
        private static method catchEnterRegion takes nothing returns nothing
            //check that this is a runner entering its own region
            local Runner this = GetRunner(GetTriggerUnit())
            if this == 0 or not IsUnitInRegion(.bread, .u) then
                return
            endif
            
            //report the runner
            call .report(AWALL_REASON_BACK_TRACKED, "backtracking")
        endmethod

        ///Create a Runner for the given unit
        public static method create takes unit u returns Runner
            local Runner r
            local integer i
            if u == null then
                return 0
            endif

            //check for double-create
            set r = GetRunner(u)
            if r != 0 then
                return r
            endif
                        
            //allocate
            set r = Runner.allocate()
            if r == 0 then
                if SHOW_ERROR_MESSAGES then
                    call BJDebugMsg("Map Error: Failed to allocate a Runner. (AWall:Runner.create)")
                endif
                return 0
            endif
            
            //init
            set r.u = u
            call GroupAddUnit(runners, u)
            call SetRunner(u, r)
            call TriggerAddAction(r.t, function Runner.catchEnterRegion)
            call TriggerRegisterEnterRegion(r.t, r.bread, null)
            debug if SHOW_DEBUG_MESSAGES then
            debug     call BJDebugMsg("AWall added a " + GetUnitName(u) + ".")
            debug endif
            return r
        endmethod

        ///Cleanup the Runner
        private method onDestroy takes nothing returns nothing
            call .reset()
            call RemoveRegion(.bread)
            call DestroyTrigger(.t)
            set .bread = null
            set .t = null
            call GroupRemoveUnit(runners, .u)            
            debug if SHOW_DEBUG_MESSAGES then
            debug     call BJDebugMsg("AWall removed a " + GetUnitName(.u) + ".")
            debug endif
            call ResetRunner(.u)
            set .u = null
        endmethod
    endstruct

    ///Ticks all runners in the system
    private function enumTick takes nothing returns nothing
        call GetRunner(GetEnumUnit()).tick()
    endfunction
    private function tick takes nothing returns nothing
        call ForGroup(runners, function enumTick)
    endfunction
    
    ///Catches runners when they attack towers
    private function catchAttacker takes nothing returns nothing
        local Runner r = GetRunner(GetAttacker())
        if r != 0 then
            call r.report(AWALL_REASON_ATTACKING, "attacking")
        endif
    endfunction

    ///Removes runners from the system when they die
    private function catchDyingUnit takes nothing returns nothing
        local Runner r = GetRunner(GetTriggerUnit())
        if r != 0 then
            call r.destroy()
        endif
    endfunction

    ///=== Interface ============================================================
    function AWall_AddRunner takes unit u returns nothing
        call Runner.create(u)
    endfunction
    function AWall_RemoveRunner takes unit u returns nothing
        local Runner r = GetRunner(u)
        if r != 0 then
            call r.destroy()
        endif        
    endfunction
    function AWall_ResetRunner takes unit u returns nothing
        local Runner r = GetRunner(u)
        if r != 0 then
            call r.reset()
            debug if SHOW_DEBUG_MESSAGES then
            debug     call BJDebugMsg("AWall reset a " + GetUnitName(r.u) + ".")
            debug endif
        endif
    endfunction
    function AWall_RegisterForWalled takes code c returns nothing
        call TriggerAddAction(callBackTrigger, c)
    endfunction
    function AWall_AddTower takes unit u returns nothing
        if CATCH_ATTACKING then
            call eventTowerAttacked.addUnit(u)
        endif
    endfunction
    function AWall_NumRunners takes nothing returns integer
        return CountUnitsInGroup(runners)
    endfunction

    ///=== Init ============================================================
    private function initAWall takes nothing returns nothing
        local trigger t
        
        set t = CreateTrigger()
        call TriggerRegisterTimerEvent(t, TICK_PERIOD, true)
        call TriggerAddAction(t, function tick)

        if REMOVE_ON_DEATH then
            set t = CreateTrigger()
            call TriggerRegisterAnyUnitEventBJ(t, EVENT_PLAYER_UNIT_DEATH)
            call TriggerAddAction(t, function catchDyingUnit)
        endif

        if CATCH_ATTACKING then
            set eventTowerAttacked = SpreadUnitEvent.create(EVENT_UNIT_ATTACKED)
            call eventTowerAttacked.register(function catchAttacker)
        endif
        
        debug if SHOW_DEBUG_MESSAGES then
        debug     call BJDebugMsg("Initialized AWall with SHOW_DEBUG_MESSAGES")
        debug endif
    endfunction
endlibrary

History
None

[DioD]

native IssuePointOrder takes unit whichUnit, string order, real x, real y returns boolean

Code:

if not IssuePointOrder(Unit,SomeRB("move"),x,y) then
call Echo("Unit cannot complete this order")
endif

[Strilanc]

Originally Posted by DioD

native IssuePointOrder takes unit whichUnit, string order, real x, real y returns boolean

Code:

if not IssuePointOrder(Unit,SomeRB("move"),x,y) then
call Echo("Unit cannot complete this order")
endif

I'm not exactly sure what your point is. Do you think IssuePointOrder will detect walls? It won't.

- Even if a unit can't reach the destination it will move to a closer point, so the order still succeeds [tested and confirmed, please don't state things like this unless you've tested them].
- Even if the order returned false if the destination wasn't reachable, units can be walled after they are ordered.
- Even if you could detect the destination becoming unreachable, juggling units only requires switching maze exits back and forth (never closing both, therefore the end is always reachable).

You _need_ backtrack detection if you want to stop juggling [*without severely interfering with players like blocking building during rounds].

[moyack]

This system is simply elegant. I must confess that at the beginning I didn't understand its purpose but now that I tested it it looks great and useful, not only for Tower defense.

One thing that I noticed is this:

JASS:

function AWall_AddRunner takes unit u returns nothing
    call Runner.create(u)
endfunction

just set those functions as public and you won't need to set the prefix

JASS:

public function AddRunner takes unit u returns nothing
    call Runner.create(u)
endfunction

Do this and I'll put this submission in the right place.

[d07.RiV]

Also

JASS:

        public method report takes integer reason, string reasonName returns nothing
            if .wasHeld or .isHeld and reason != AWALL_REASON_PREVENT then
                call .report(AWALL_REASON_PREVENT, reasonName + "(prevented)")
                return
            endif
            call .reset() //avoid double-catch

can be changed to

JASS:

        public method report takes integer reason, string reasonName returns nothing
            if .wasHeld or .isHeld and reason != AWALL_REASON_PREVENT then
                set reason = AWALL_REASON_PREVENT
                set reasonName = reasonName + "(prevented)"
            endif
            call .reset() //avoid double-catch

Doesn't really affect performance, just a tip.

I'll try it if I ever make a map that involves any kind of runners/creeps (I suppose it can also be used for AoS with some modifications?)

[Strilanc]

It doesn't work if the runners are attackers.

[moyack]

meh.

my tip is just aesthetic, so moved to scripts systems.

[D.V.D]

Could this detect cliffs too?

[Strilanc]

It detects when a runner is walled, whether or not it's buildings doing it.

[Kam]

Could this be modified to stop submerged units from entering shallow water?

[Strilanc]

What exactly do you think the system does? It detects if a runner is acting like it was walled, it doesn't look at the terrain in any way.