[vJASS] [Snippet] IsPathBlockerInBetween

[MoCo]

Hey everyone,

this is a small library that provides a function that checks if there is a pathing blocker (default ground) between 2 coordinate points (x1,y1) and (x2,y2).

This detection function requires a library for pathability detection. I'm using Rising Dusk's TerrainPathability here, but you could also use any other library.

library IsPathBlockerInBetween initializer Init requires TerrainPathability
//**************************************************************************
//*  ============================
//*  IsPathBlockerInBetween  1.00   (by MoCo)
//*  ============================
//*
//*  This library provides a function to check if there is a pathing blocker (default ground) between 2 coordinate points, given by x and y.   
//*
//*  This system requires a library for pathability detection.
//*  I'm using Rising Dusk's library here, but you could also use any other library.
//*  Using another library means that you might need to change the call of the IsTerrainWalkable function 
//*  to the name of whatever function the other pathability library is providing.
//*  You could also change the IsTerrainWalkable function call to something like IsTerrainFlyable if you need.
//* 
//*  Setup:
//*  ======
//*
//*    1. Copy this library and the TerrainPathability library to your map.
//*
//*    2. Adjust the MAX_DISTANCE constant
//*
//*       Set this constant to the maximum distance between 2 points, you need to detect a pathing blocker in between within your map
//*        
//*       - A higher value means higher accuracy of detection; 
//*         the higher the distance between the 2 points, the higher the accuracy needed by the function to return proper results 
//*   
//*       - A higher value means lower performance;
//*         if you only need the detection function for low distances, 
//*         like for line of sight systems where sight range is limited and, for example, you won't need the function for longer distances anyway,
//*         you should use a lower value to improve performance
//* 
//*       - Note that performance usually won't be an issue at all.
//*         So if you plan to use this function only a few times, you wouldn't need to bother about performance. 
//*         However, for exmaple, if you are using this function with an AI system and need to call it multiple times a second for about 50-100 units,
//*         you probably want to optimize performance. 
//*
//*       - Technically, a higher values means more checkup steps in the line between the 2 points
//*         If you know what you're doing, you can also manually set the number of these steps 
//*         by setting the Steps variable to the number of steps you would like to have
//*
//*       - If you find that in some situations the function doesn't deliver proper results, increase the MAX_DISTANCE variable or set Steps to a higher number
//*
//*  Usage:
//*  ======
//*
//*  Call the function PathBlockerInBetween(real x1, real y1, real x2, real y2)
//*
//*    The function returns true, if a pathing blocker (default ground) is between the two coordinates, and false if not.
//*
//**************************************************************************
globals 

    private constant real MAX_DISTANCE = 1024  // Do set this value to the maximum distance (or slightly higher),
                                              // you need the path detection function to work properly
    
    private integer Steps = 0      // If you know what you're doing, you can manually define 
                                   // the number of the checkup steps in the line between the 2 points.
                                   // Else just leave this value as it is
endglobals

function PathBlockerInBetween takes real x1, real y1, real x2, real y2 returns boolean
    local real incX = (x2-x1)/Steps
    local real incY = (y2-y1)/Steps
    local real x = x1
    local real y = y1
    local integer i = 0
    local boolean check = false
    
    loop
        exitwhen i > Steps or check
        if IsTerrainWalkable(x,y) == false then     // You may want to change this function,
            set check = true                        // if you are using a different library for pathability checking
        endif
        set x = x + incX
        set y = y + incY
        set i = i + 1
    endloop

    return check
endfunction

private function Init takes nothing returns nothing
    if Steps == 0 then // if no manual override of steps count, calculate number based on given MAX_DISTANCE
        set Steps = R2I(MAX_DISTANCE / 32.)
    endif
endfunction

endlibrary

I've attached a small testmap.

If you know ways to improve the script, i.e. some way of performance optimization or better approaches for the detection algorithm, please let me know and I will update it.

 

[Nestharus]

This isn't particularly useful. What's more useful is determining whether the footman can be seen or not. For example, there may be a pathing blocker, but you may be on elevated terrain.

Another thing that is more useful is determining if there is a path at all or not.

However, this can be used for making the first resource =).

The algorithm for doing your check can be improved to use something like a binary search.

 

[MoCo]

I think this actually is useful.

One use case might be a jump spell that needs to detect if something is in the way which cannot be over-jumped.

A second use case, the one I recently needed this for, is the following:
I've started working on a stealth game, where I need to detect if vampires are in the line of sight of villagers.

Therefore, I needed to check 2 things:

1. Is a vampire within the field of view of a villager? (http://www.hiveworkshop.com/forums/...sunitinsight-isunitbehind-261347/#post2638064)

2. Is there something (like a house) that blocks the line of sight between the villager and the vampire?
So I needed a way to implement a line of sight system. Thus, I use pathing blockers with Fat Line of Sight set to true. This way, pathing blockers (houses) block vision of units. Then, I needed a way to detect if these blockers are in the line of sight between 2 particular units (note that I cannot just use IsUnitVisible here). That's when I needed the above function.


As it concerns the technical approach / implementation, however, I'd be happy if you can provide a better approach, especially if it helps to improve performance.

 

[Nestharus]

My bad, a binary search would be pointless.

function PathBlockerInBetween takes real x1, real y1, real x2, real y2 returns boolean
    local real distance = SquareRoot((y2 - y1)*(y2 - y1) + (x2 - x1)*(x2 - x1))
    local real angleBetweenPoints = Atan2((y2 - y1), (x2 - x1))
    local real deltaX = Cos(angleBetweenPoints)*32
    local real deltaY = Sin(angleBetweenPoints)*32
    local real traveled = 0
    
    loop
        exitwhen traveled >= distance or not IsTerrainWalkable(x, y)
        
        set x = x + deltaX
        set y = y + deltaY

        set traveled = traveled + 32
    endloop

    return traveled < distance
endfunction

Also, as mentioned before, you also need to account for terrain height. This is useless by itself. The two examples you mentioned would break with varying terrain height. You can be in field of view of something with a pathing blocker in the way.

 

[MoCo]

I do not want to argue on the usefulness. In fact, I need this in exactly this way and I can imagine that others may need such function too. If there is significant terrain deformation, sure, terrain is an aspect that could be considered too if implementing a vision system, but that would require a completely different approach. But let's focus on what this is about: checking for a path blocker between two points, nothing more, nothing less.

Thank you for your code suggestion.
But are you sure your code really is faster?
For my needs, the focus is on low distances only, nothing higher than 512.
I just thought that the choice of the algorithm might be different, depending on if focus is on either lower distances, or higher distances? I dunno..

 

[Nestharus]

You're arguing for a map specific resource as a general resource submission... I hope you see the problem with this.

 

[MoCo]

I thought detecting path blockers between 2 points could be a generally useful thing, but I have no problem with this being graveyarded if you think it's too specific. Maybe one more opinion would be fine though.

 

[chobibo]

If you can somehow make the filtering condition configurable, I guess this would be fine. Right now, it's hard-coded to check for obstructions considered by Dusk's pathing library. Some people might want to only pick unit obstructions, destructable obstructions (dash spells could use that), etc.

 

[Kazeon]

Try this method:
Use a unit (both ground and flying), create it at (x1, y1), should face the target location. Then order it to move to (x2, y2). Return "unit's facing != angle from x1, y1 to x2, y2", it indicates there is/are blocker in the way. <= Dunno is this accurate or not.

 

[MoCo]

While I understand that this should be more generic, unfortunately, being honest, I probably won't find time and motivation to further work on this to turn it into a generic detection library that detects multiple types of widgets (at least not so soon).

So I suggest to just put it to graveyard. If someone needs exactly this function, he will probably find it with the search function and can decide for using either the top function or the one proposed by Nes. I'm still not sure which one is faster; might be even depending on distances. The most interesting question in this context for me is to find the fastest algorithm for such "Is something in the line" detections.

@Dalvengyr: Interesting idea, but I'm afraid SetUnitFacing is not fast enough for this as it does not work at instant speed if I remember correctly.

 

[PurgeandFire]

@Dalvengyr: Neat idea, but it would require a timer delay, and if the points are far enough--it might not be 100% accurate.

@MoCo: I disagree with graveyarding it. I think it is useful.

As for the script, I think it is a bit awkward to have a maximum distance. You should just iterate every 32 units (unless the user specifies otherwise) towards the angle between the points--it'll cover all cases.

 

[Kazeon]

Yeah, defend your resources dude. Even if everybody dislikes. Prove'em your resource's approve worthy.

 

[MoCo]

Hmm, well, ok. I'll spend some more thoughts on this.
My primary goal is to make the function as fast as possible, so I'd like to avoid those heavy angle and distance calculations.

While Nes function is more generic, a predefined STEPS value has the charme of being faster if a mapper knows that he would only need the function for specific ranges so he can set the STEPS without fearing accuracy problems. Maybe a library should provide the generic way by default, but also include an option to choose predefined steps to improve speed if desired? For example, most spells work with very limited casting ranges were this approach can be efficient.

 

[maddeem]

Shouldn't MAX_DISTANCE be an integer? That way you can just avoid the R2I. I find this resource useful. +rep

 

[MoCo]

Thanks for rep!

Yepp, I think it could just be changed to integer.

 

[Zwiebelchen]

It works fine and we don't have this yet. I don't see a reason why it shouldn't be approved.

However, two suggestions to improve convenience for the end-user:

1) make the TerrainPathability optional and add IsTerrainPathable as another optional resource; then use a constant boolean to determine which is used by static if; this allows users to chose which pathing lib they use without having to mess around with the code
2) remove the MAX_DISTANCE constant. Just let the user define STEPS and be done with it. There's no reason to have a constant that is basicly just for calculating another. In fact, MAX_DISTANCE is more or less an arbitrary magic number, whereas "steps" has an actual meaning. Imho, what "steps" does can be explained far easier than what "MAX_DISTANCE" is for.

 

[MoCo]

Thanks, good points. I'll update the code in the next days.

 

[Zwiebelchen]

Also, another thing that you probably should implement:

You calculate your dX and dY variables just by the initial X and Y distance between the target points. This means you are performing your walkable checks across a completely linear trajectory. There's a problem with that though, which is related to how IsTerrainWalkable detects walkability: it moves an item to the checked spot and tests if it moves. When doing the check, it applies a certain precision treshold to correct rounding errors when placing the item.

This affects your system, as it can create a false positive if your check position is very close to the edge of a tile, especially if an area is blocked diagonally (for example, by the fence doodad). In this case, the system thinks the line between those two points is pathable, while it isn't (the minimum collision diameter of units is 16).

To correct this, you might want to offset your checked points by X=X+ModuloInteger(x, 32)-16. You also need to perform another check on the neighboring tile at X=X-32

I'll illustrate the problem to you:

The grey tiles have a pathing blocker (for example, the diagonal fence doodad), the white tiles don't.
You check the pathing between point A and point C.
At point A and C; no problems. But at point B, you are exactly on the edge of two blocked tiles. If you use IsTerrainWalkable here, the function will return a false positive, as the item will move slightly, but not out of the precision treshold.

To combat this, you must displace your measuring points A,B and C always to the center of a 32x32 tile (which are at 16,16; 16,48; 48,16 and 48,48 in this example, hence why you need to subtract 16 after adding the modulo) and also check the adjacent tile.

So, instead of only checking point B, your algorithm should check all four cells around point B.

 

[MoCo]

Yeah, you are right of course. I guess I even thought about this issue before.
Fact is, the addition of the adjacent tiles checkup increases the amount of function calls of the pathchecker by factor 3, which is quite a lot.

I could argue that pathing situations like above are rare and that it might be acceptable, to have inaccurate results here. On the other hand, it can be easily argued against if such situations are necessary in the map design.

Well, for a generic resource, it might be a good compromise to offer two alternative flavors, like Vexorian did it with TimerUtils back in the days.

Red flavor: uses the old, fast approach and does not check adjacent tiles; The mapper decides if situations like the one above are crucial in the map or not; the mapper may also decide to avoid such situations by design in order to use the speed advantages.

Blue flavor: is slower, but takes care of situations like above and can be used, if reliable results are necessary for above pathing situations

 

[Zwiebelchen]

I think you are underestimating the importance of this problem. Not only does it happen on diagonal blockers like the fence doodad, but it also happens whenever two pathing blockers connect with each other diagonally. So unless the mapper always pays special attention to "fill the gaps", I think this snipped *should* account for this situation by applying the aforementioned extra checks.

Plus, remember that any stationary objects in the game will always be "centered" in the cells, greatly increasing the likelyhood for "just on the edge"-checks. So the accuracy of your snippet will go down significantly if f.ex. you check pathing blockers between towers (to check missile collision).

The precise checking should be the default, not the optional feature. Turning this off should be optional (in case the user uses a pathability resource that already accounts for this).

And let's face it: modern day CPUs are strong enough for this.

 

[Kazeon]

set Steps = R2I(MAX_DISTANCE / 32.)

32 should be added to configuration constant. Since defaultly, minimum pathing (both for building and destructables) is 64 px wide. While the smaller size (32 px) can only be achieved if user import their own pathing image (very rare case). So it's a good idea to leave it configurable for user, as the iteration:

    loop
        exitwhen traveled >= distance or not @IsTerrainWalkable(x, y)@
        
        set x = x + deltaX
        set y = y + deltaY

        set traveled = traveled + 32
    endloop

is quite heavy and maybe is supposed to be used a lot of times, we should tend to have the lowest accuracy as possible, to avoid any performance issue. Which at this case, 64 is the best. But again, there is possibility for user to have 32x32 pathing so it's the best to leave it configurable.

And "accuracy" (real) seems better than "steps". If user set the step very low (such as 10) there is a big big chance that the iteration would miss a small pathing blocker. Take this example, the "distance" is 1000, and the "steps" set to 10. There is ((100-64)/100 = 0.36) or 36% that the iteration will miss a 64x64 pathing blocker (the small one) that's a bad accuracy.

That distance it self should be dynamic: based on distance between (x1, y1) to (x2, y2). Not constant. What if the distance is >1024? It could probably fails to detect.

The summary is: change steps to accuracy (real) and remove the max distance thingy. Please consider.

 

[BPower]

I have to test in-game if this is working as describe, but according to the comments I have a good feeling

IsTerrainWalkable(x,y) == false comparision for false conditions should be written this way: not IsTerrainWalkable(x,y)

Instead of setting check to true, you can directly return true. It will also stop the loop.
If the thread runs without positive result, return false in the end ( no local boolean required )

If you wish, you can add a configurable accuracity like Quilnez pointed out ( 64 instead of 32 )

You can set Steps directly to R2I(DISTANCE/32) instead of using an initializer. I tell you this, because otherwise I would summon you to write a module initializer!

I like this snippet.

Going deeper into what Zwiebelchen said:
Yes diagonal pathing blockers are the core problem. Especially if you wish to implement this into an AI system.
In that case you wish to have accurate results, otherwise AI controlled units may get stupid orders by their controlling system.
For detecting a center of a Tile, you can use TileDefinition by IcemanBo.

I think there is discussion material, how to solve the problem in a good way.

 

[Zwiebelchen]

For detecting a center of a Tile, you can use TileDefinition by IcemanBo.

... or he could just apply the very simple maths I pointed out.

 

[BPower]

Oh, I didn't saw that

 

[Bribe]

Just looking at the code, I wanted to insta-approve this. However, Zwieb pointed out some pretty serious risks. BPower mentioned some optimizations I also endorse. It's been months. I'll graveyard this until you're ready to release a stable version.

 

[maxodors]

I think you are underestimating the importance of this problem. Not only does it happen on diagonal blockers like the fence doodad, but it also happens whenever two pathing blockers connect with each other diagonally. So unless the mapper always pays special attention to "fill the gaps", I think this snipped should account for this situation by applying the aforementioned extra checks.

Plus, remember that any stationary objects in the game will always be "centered" in the cells, greatly increasing the likelyhood for "just on the edge"-checks. So the accuracy of your snippet will go down significantly if f.ex. you check pathing blockers between towers (to check missile collision).

The precise checking should be the default, not the optional feature. Turning this off should be optional (in case the user uses a pathability resource that already accounts for this).

And let's face it: modern day CPUs are strong enough for this.

I tried to do a system based on this system and your comment. The idea of the system is to check whether the remaining moving distance of the unit or missile is more than the unpathable object. xMove and yMove are coordinates where the unit will move. Others are obvious. However, it does not work properly. I would really appreciate some feedback.

library IsPathBlockerInBetween /*


    */uses /*
    
    */TerrainPathability
    
    
    globals
    
        private integer ACCURACY = 64
        
    endglobals
    
    function PathBlockerInBetween takes real xMove, real yMove, real angle, real speed, real distLeft returns boolean 
        local real deltaX 
        local real deltaY 
        local real traveled 
        local real x 
        local real y 
        local real x1 = xMove + ModuloReal(xMove, ACCURACY)- ACCURACY/2
        local real x2
        if xMove > x1 then
            set x2 = x1 + ACCURACY
        else
            set x2 = x1 - ACCURACY
        endif
        
        if not IsTerrainWalkable(xMove, yMove) and not IsTerrainWalkable(x1, yMove) and not IsTerrainWalkable(x2, yMove) then
            set deltaX = Cos(angle * bj_DEGTORAD) * ACCURACY
            set deltaY = Sin(angle * bj_DEGTORAD) * ACCURACY
            set traveled = speed
            set x = xMove
            set y = yMove
            
            loop
                exitwhen traveled >= distLeft or (IsTerrainWalkable(x, y) and IsTerrainWalkable(x1, y) and IsTerrainWalkable(x2, y))
                
                set x = x + deltaX
                set y = y + deltaY
                set x1 = x + ModuloReal(x, ACCURACY)- ACCURACY/2
                if xMove > x1 then
                    set x2 = x1 + ACCURACY
                else
                    set x2 = x1 - ACCURACY
                endif

                set traveled = traveled + ACCURACY
            endloop
            
            debug call BJDebugMsg("[Shunpo] Distance Remaning" + R2S(distLeft))
            debug call BJDebugMsg("[Shunpo] Traveled Distance " + R2S(traveled))
            
            return traveled >= distLeft
        endif
        
        return false
    endfunction
    
endlibrary