• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • It's time for the first HD Modeling Contest of 2024. Join the theme discussion for Hive's HD Modeling Contest #6! Click here to post your idea!

Bresenham Pathchecker

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
I was sick of not having a robust IsPathWalkable function that actually checks on a cell-by-cell basis, so I wrote my own based on the Bresenham algorithm of pixel graphics, which is a bit faster than one that uses trigonometry and lots of divisions and multiplications.

I think this should be the go-to for any missile or knockback system, simply because it doesn't care about the missile/unit movement speed and never skips a cell (also, it can be used to check a pathing before the unit actually starts moving, which greatly improves performance of these systems). As it always "centers" on every cell it checks, it also fixes some nasty problems with the IsTerrainWalkable resource when called on a coordinate way off the center of a cell.
Also, it returns a location of the closest pathable point.

If you want even higher accuracy (or use custom pathing maps that make use of the 32x32 grid), then you can reduce the cell size to 32.

JASS:
library IsPathWalkable initializer init uses TerrainPathability // v1.0
//get it here: [url]http://www.wc3c.net/showthread.php?t=103862[/url]

/*
 Description:
 This snippet uses the Bresenham algorithm of Pixelgraphics to check if the direct path between two cells (as a straight line) is walkable or not. It does so by looping through each cell between the two coordinates and checking their respective pathabilities.

 Note: This snippet will ignore the collision of units, but will consider all doodad, destructable or terrain pathing. If you want to consider unit collision aswell, simply swap out TerrainPathability for your desired resource and replace all IsTerrainWalkable calls in the script.


 Configurables:
 private constant boolean DIAGONAL_SAFETY
 - determines if on any diagonal step an adjacent cell is checked for extra safety (since units can not pass between two diagonally blocked cells). Default: enabled (true)
 private constant integer MIN_CELL_SIZE
 - determines the cell size for the Bresenham algorithm. As default pathing textures have a minimum cell size of 64, lowering this to 32 only makes sense if custom pathing textures are used. Default: 64.

 API:
 function IsPathWalkable takes real x1, real y1, real x2, real y2 returns boolean
 - returns true if the path between coordinates x1|y1 (start) and x2|y2 (end) is walkable

 function GetPathLastX takes nothing returns real
 function GetPathLastY takes nothing returns real
 - after using IsPathWalkable, these two functions will return the x and y coordinate of the last pathable cell between the start and end coordinate.

 */

globals
       private constant boolean DIAGONAL_SAFETY = true

       private constant integer MIN_CELL_SIZE = 64
       private constant integer CELL_CENTER_OFFSET = MIN_CELL_SIZE/2
   
       private real X = 0
       private real Y = 0
      
       private real WORLD_MIN_X = 0
       private real WORLD_MIN_Y = 0
endglobals

function IsPathWalkable takes real x1, real y1, real x2, real y2 returns boolean
       local integer xstart = R2I(x1-WORLD_MIN_X) / MIN_CELL_SIZE
       local integer xend = R2I(x2-WORLD_MIN_X) / MIN_CELL_SIZE
       local integer ystart = R2I(y1-WORLD_MIN_Y) / MIN_CELL_SIZE
       local integer yend = R2I(y2-WORLD_MIN_Y) / MIN_CELL_SIZE
       local integer dx = xend - xstart
       local integer dy = yend - ystart
       local integer adx = dx
       local integer ady = dy
       local integer sdx = 0
       local integer sdy = 0
       local integer pdx
       local integer pdy
       local integer ddx
       local integer ddy
       local integer es
       local integer el
       local integer error
       local integer x = xstart
       local integer y = ystart
       local integer i = 1
       set X = x1
       set Y = y1
       //calculate abs values and signs
       if adx < 0 then
           set adx = -adx
           set sdx = -1
       elseif adx > 0 then
           set sdx = 1
       endif
       if ady < 0 then
           set ady = -ady
           set sdy = -1
       elseif ady > 0 then
           set sdy = 1
       endif
       if adx > ady then
           set pdx = sdx
           set pdy = 0
           set es = ady
           set el = adx
       else
           set pdx = 0
           set pdy = sdy
           set es = adx
           set el = ady
       endif
       set ddx = sdx
       set ddy = sdy
   
       if not IsTerrainWalkable(x*MIN_CELL_SIZE+CELL_CENTER_OFFSET+WORLD_MIN_X, y*MIN_CELL_SIZE+CELL_CENTER_OFFSET+WORLD_MIN_Y) then
           return false
       endif
       set error = el/2
   
       loop
           exitwhen i > el
           set error = error - es
           if error < 0 then
               if DIAGONAL_SAFETY then
                   set dx = x+ddx-pdx
                   set dy = y+ddy-pdy
                   if IsTerrainWalkable(dx*MIN_CELL_SIZE+CELL_CENTER_OFFSET+WORLD_MIN_X, dy*MIN_CELL_SIZE+CELL_CENTER_OFFSET+WORLD_MIN_Y) then
                       set X = dx*MIN_CELL_SIZE+CELL_CENTER_OFFSET+WORLD_MIN_X
                       set Y = dy*MIN_CELL_SIZE+CELL_CENTER_OFFSET+WORLD_MIN_Y
                   else
                       return false
                   endif
               endif
               set error = error + el
               set x = x + ddx
               set y = y + ddy
           else
               set x = x + pdx
               set y = y + pdy
           endif
           if IsTerrainWalkable(x*MIN_CELL_SIZE+CELL_CENTER_OFFSET+WORLD_MIN_X, y*MIN_CELL_SIZE+CELL_CENTER_OFFSET+WORLD_MIN_Y) then
               set X = x*MIN_CELL_SIZE+CELL_CENTER_OFFSET+WORLD_MIN_X
               set Y = y*MIN_CELL_SIZE+CELL_CENTER_OFFSET+WORLD_MIN_Y
           else
               return false
           endif
           set i = i + 1
       endloop
       return true
endfunction

function GetPathLastX takes nothing returns real
     return X
endfunction
function GetPathLastY takes nothing returns real
     return Y
endfunction

private function init takes nothing returns nothing
    local rect r = GetWorldBounds()
    set WORLD_MIN_X = GetRectMinX(r)
    set WORLD_MIN_Y = GetRectMinY(r)
    set r = null
endfunction

endlibrary
 
Last edited:

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
I like your idea, man!
And what about also giving the cell size as parameter?
Wouldn't make much sense. Either you use custom pathing textures or you don't. ;)
It's not like you need to decide that dynamically.

EDIT: Also, a small wrapper for those that prefer entering angle and distance:
JASS:
function IsPathWalkableEx takes real x, real y, real rad, real distance returns loc
    return IsPathWalkable(x, y, x+Cos(rad)*distance, y+Sin(rad)*distance)
endfunction
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Sweet! But I might need to see a demo for some of the uses. It might be a bit hard to fit into missile and knockback logic if you're constrained to the cell grid.
Basicly, you can just use it once between the starting point and landing point on the launch method and know when the pathing is obstructed. In case of a missile that should not ignore pathing, of course. In case of a missile that only considers start and end pathing, it's pretty much useless (unless you want bounds safety no matter what flyheight the missile has, i.e. a missile not passing through walls; the cool thing is that you can have that as a simple toggle boolean as you just need to fire it once per launch, not periodically)
The cell grid is not a constraint, it's an advantage, as it increases accuracy of your pathing checks:
The current standard method of finding pathable cells (IsTerrainWalkable) uses an SetItemPosition() to find the closest pathable point, then measures the distance between the tested point and the point where the item ended up. This method is dangerous as it can return false positives when the checked point is too close to the boundary of a cell (so that the item is actually obstructed, but ends up within the treshold).
Also, using IsTerrainWalkable periodically every 0.03 seconds is a total waste of performance, especially for slow moving missiles, as you will end up checking the same cell multiple times.
This algorithm checks each cell only once and makes sure the cell is always tested in it's center to avoid false positives.


Is the returned location always on the path? Looking at the code, I assume it is on the path if it is pathable, else it'll go to a neighboring cell?
Yes, it always returns the last valid pathing cell of the path, not a random one around the blocked cell.
The location returned will always be at the center of this cell, not along the actual (exact) travelpath, because:
1) in case the pathing is blocked, you probably don't care about the original pathway anyway
2) cells are small enough so that it still looks neat
3) it calculates faster
4) you can always reduce the gridsize to 32 to have the same positioning accuracy that WC3 permits at most


However, I noticed that there is still one problem with this:
In case of a diagonal step, it does not check the adjacent parallel square aswell, so it is possible to pass through a diagonal pathing blocker (like the fence doodad).

diff.png


Basically, the current algorithm checks as displayed in the green example above. However, from a practical point of view, the blue one is safer in case of heavy use of diagonal-one-line pathing like the fence doodad.
I think I will implement the blue one as a flavour version aswell, so that the user can decide if he needs the extra safety (at the cost of higher runtime).
 
Last edited:
Thanks for the explanations!

Also, using IsTerrainWalkable periodically every 0.03 seconds is a total waste of performance, especially for slow moving missiles, as you will end up checking the same cell multiple times.
This algorithm checks each cell only once and makes sure the cell is always tested in it's center to avoid false positives.

I wouldn't say it is waste. Pathing changes all the time. If a unit suddenly walks in between a missile's path within the missile's duration, then the periodic check will account for that. However, if you only do the pathability calculation once at the missile launch, it'll just pass right through the unit.
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Thanks for the explanations!



I wouldn't say it is waste. Pathing changes all the time. If a unit suddenly walks in between a missile's path within the missile's duration, then the periodic check will account for that. However, if you only do the pathability calculation once at the missile launch, it'll just pass right through the unit.
IsTerrainWalkable does not check for units. That's the whole point. This is only to prevent units from jumping through walls.

If you want to check units, you should use this anyway, which solves the problem elegantly via build orders:
http://www.hiveworkshop.com/forums/...a-263230/?prev=search=pathability&d=list&r=20
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Updated the code in the TO; the algorithm now has a toggle for diagonal safety, which will basicly also check an adjacent parallel cell any time a diagonal step is made.
This will allow the algorithm to be fail-safe when using diagonal pathing blockers like the fence doodad.

It is not exactly as posted in the image above. I thought that always having a "double cell" line would be undesirable, so I only checked two squares if a diagonal step was made, not every time.

Also, the function now returns a boolean as suggested by the name.
There is now a seperate function to return the last valid location instead.
 
Last edited:

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Sorry for doubleposting, but as I need help, I want this to be visible:

It seems that there are two problems with this resource:

1) the location returned for some reason does not work. I suppose that is because the location is initialized in globals? Don't know, I really have no explanation for this.

2) IsTerrainWalkable (from Cokemonkey) seems to return false positives for destructable pathing blockers. This is really annoying and I don't have an idea on how to fix this. Is there really no good resource that checks walkability without also considering units?
 

Bribe

Code Moderator
Level 50
Joined
Sep 26, 2009
Messages
9,456
In Knockback 2D, I use a custom inferno ability which uses a dummy to cast and determines pathing based on if IssuePointOrderById returns true (pathable) or false. It goes through trees, though. I have a theory that a dummy-blink ability would fix those issues, and after testing I will switch inferno for blink if that's the case. You can try it if you want to.
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Global initialization should be fine. Is it returning the center of the map? (is it null?) Or is it returning a weird location that doesn't seem to be correct?
I think it actually crashes the thread when I want to get GetLocationX from the returned location. Extremely weird. But I think I will have a global X and Y coordinate to access directly anyway. Locations suck.

In Knockback 2D, I use a custom inferno ability which uses a dummy to cast and determines pathing based on if IssuePointOrderById returns true (pathable) or false. It goes through trees, though. I have a theory that a dummy-blink ability would fix those issues, and after testing I will switch inferno for blink if that's the case. You can try it if you want to.
So Inferno is as unreliable then as any other method to detect pathing. Figures.

My problem is that I want to detect all possible ways to block walkability except units.
Especially destructables and SetTerrainPathable seem to have huge issues with the current methods to detect pathing (like moving an item).

I make heavy use of SetTerrainPathable for performance reasons (enumerating and removing all destructable pathing blockers on map init and replacing them via SetTerrainPathable), but no method I tested so far managed to return reliable true negatives for pathability set via this method.
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Just tested it - blink is no good for this unless you wait 1 second for the unit to land and see where it got displaced to. Maybe combine with windealk?
I'm starting to think that it might possibly be easier to just use the build order solution from pathinglib and just temporarily hide all units inside the checked cell.

Btw, has anyone experimented with CreateDestructableZ? What happens if a cell is blocked by something and the created destructable has a pathing texture? Does it still get placed properly?
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Zwieb, why not use an item to check for pathing? It's lighter to hide items than units, and if you need bigger than 16 collision size then just offset the item by 45 degrees right and 45 degrees left by 16 length for 32 collision, for example.
You think I haven't tried that already? I even mentioned the IsTerrainWalkable resource in the requirements; it does exactly that.

However, it seems to return false positives for SetTerrainPathable(x, y, false). Even if a spot is made unpathable with that method, the item ends up exactly where it is attempted to be placed, wronging the distance check.

Maybe if I combine it with IsTerrainPathable I can implement an additional safety for that. I'm not sure if this native successfully retrieves manual meddling with the pathing map on runtime via code. The name suggests that it works as kind of a counter to the previously mentioned native. Maybe it works, but I suppose not, since it also ignores destructables.
 

Bribe

Code Moderator
Level 50
Joined
Sep 26, 2009
Messages
9,456
I've never used that pathability library - sorry wasn't aware of it using an item but I guess it should've been obvious.

About the item position - really the item shouldn't even slightly move. I always do a direct == comparison between item X and destination X and it never lets me down. Are you certain it's not being offset even a little?
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
I've never used that pathability library - sorry wasn't aware of it using an item but I guess it should've been obvious.

About the item position - really the item shouldn't even slightly move. I always do a direct == comparison between item X and destination X and it never lets me down. Are you certain it's not being offset even a little?
Nope, the offset is exactly zero. Which is the problem. The item basicly gets placed on invalid terrain.

But I found this, which does exactly as I suggested: comparing the return value of the usual item reposition with an IsTerrainPathable check to find the cases of pathing that get not properly calculated by just the item placement variant alone:

http://www.wc3c.net/showthread.php?t=103862

It seems that this method does indeed catch the cornercase of SetTerrainPathable which is not tracked by the item placement thing alone. Magnificent stuff, albeit a bit heavy on operations.


Anyway, this is issue solved. I updated the main post with the final version.

@Mods: Please move this thread into the resource submission section!
 

Bribe

Code Moderator
Level 50
Joined
Sep 26, 2009
Messages
9,456
I've done a lot of experimenting in Knockback 2.5D and have found some pretty useful information. I'd like to corroborate with you on finding the best possible method.

1) Inferno order checks for simple pathing and is light enough to be cast without performance issues.

2) I check for possible blocking structures at the beginning of the knockback, and implement an enumeration periodically if they are found so units don't get knocked back through buildings. I don't like this method but it keeps things quite lightweight.

3) If the inferno ID was false, I added another check to see if the user wants to move the unit over deep water and have a naga unit sample the pathing via SetUnitPosition. This is the most interesting approach and I may expand on it to cover more use-cases. How it works:

  • Naga is hidden to avoid it being enumerated during the game or its HP bar showing.
  • Naga cannot have locust ability due to it never being displaced during SetUnitPosition.
  • Naga cannot be placed in the correct position with the knocked back unit being in the way. Units must be enumerated and moved to a different spot to only permit legal displacement during SetUnitPosition.
  • Enumerated units cannot be temporarily hidden due as they cause any physical attacks directed towards them to reset (attacker treats unit as having done a phase shift and targets a different unit).
  • I don't like the way I displace units to check for this. I will ultimately probably just change that check to an IsTerrainDeepWater check.

I think the solution for pathing blockers, buildings and setterrainpathable alike is to displace all non-structure units in the path by moving them to a "safe point" (defined by the user on a per-map basis) which avoids triggering unnecessary region events. Then, to account for collision size, have 4 different structures the unit can build (16x16, 32x32, 48x48, 64x64). Do you think this would work? I'll test it out tonight.

Edit: not sure I like the structure method due to it needing to follow the grid. Perhaps sticking to the SetUnitPosition on the dummy will work best. The dummy is paused, so the function call is lightweight.
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
I've done a lot of experimenting in Knockback 2.5D and have found some pretty useful information. I'd like to corroborate with you on finding the best possible method.

1) Inferno order checks for simple pathing and is light enough to be cast without performance issues.

2) I check for possible blocking structures at the beginning of the knockback, and implement an enumeration periodically if they are found so units don't get knocked back through buildings. I don't like this method but it keeps things quite lightweight.

3) If the inferno ID was false, I added another check to see if the user wants to move the unit over deep water and have a naga unit sample the pathing via SetUnitPosition. This is the most interesting approach and I may expand on it to cover more use-cases. How it works:

  • Naga is hidden to avoid it being enumerated during the game or its HP bar showing.
  • Naga cannot have locust ability due to it never being displaced during SetUnitPosition.
  • Naga cannot be placed in the correct position with the knocked back unit being in the way. Units must be enumerated and moved to a different spot to only permit legal displacement during SetUnitPosition.
  • Enumerated units cannot be temporarily hidden due as they cause any physical attacks directed towards them to reset (attacker treats unit as having done a phase shift and targets a different unit).
  • I don't like the way I displace units to check for this. I will ultimately probably just change that check to an IsTerrainDeepWater check.

I think the solution for pathing blockers, buildings and setterrainpathable alike is to displace all non-structure units in the path by moving them to a "safe point" (defined by the user on a per-map basis) which avoids triggering unnecessary region events. Then, to account for collision size, have 4 different structures the unit can build (16x16, 32x32, 48x48, 64x64). Do you think this would work? I'll test it out tonight.

Edit: not sure I like the structure method due to it needing to follow the grid. Perhaps sticking to the SetUnitPosition on the dummy will work best. The dummy is paused, so the function call is lightweight.
All this would be HEAVY on operations.

The beauty about the item method is that it is pretty lightweight, since items don't trigger a lot of events.
Anyway, moving units out of the way is a terrible practice, as it triggers enter region events when the unit is moved back to it's original position.
If you locust or hide these units before moving, I am pretty sure that this will break a lot of spell effects or cause graphical glitches.

Tbh, I don't think it gets any better than this.
It solves all corner cases at the expense of moving some items around. Imho the only acceptable tradeoff so far.

I recommend you use my system for your knockback. It was basicly designed for that purpose. Following the grid is a blessing, not a curse, as units will ultimately move by grid anyway.
 

Bribe

Code Moderator
Level 50
Joined
Sep 26, 2009
Messages
9,456
Well, you should inline that item function since you check the same area repeatedly, right? This resource should just make a rect with the knockback path and hide all items in there. When your check is completed, move them back.

Why I dislike the item method is because they all have a collision size of 16. But with this system, you can cover fringe cases by permitting a collision size to be passed. A unit with 16 collision can go through much tighter areas than one with 64 collision.

I would really like to use this for Knockback 2.5D, but I don't see how it would work with bouncing units. I'd have to use extra variables to track how long until the next bounce, then run the checker again when it's time to bounce. BUT - the trigger must then assess if it should bounce from a different angle (if your check before the loop starts, returning false).

For this to work with Knockback 2.5D, I'd need to code this in vanilla JASS anyway. In the version I'd use, this function would return an integer instead of a boolean. I also would need it to not approximate anything (that IsTerrainWalkable resource would need to be re-implemented with 0 tolerance).

So, having IsTerrainWalkable inlined into your script, returning an integer instead of a boolean, and you've got a system which I could use.

Edit: Returning a real variable for the distance traveled would also be superior to returning an integer or boolean.
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Well, you should inline that item function since you check the same area repeatedly, right? This resource should just make a rect with the knockback path and hide all items in there. When your check is completed, move them back.
This could indeed be a minor speed optimization; but I don't like it for the simple reason that I just don't like code duplicates and people might want to use that library for other purposes aswell.
The speed difference should be negligible anyway.

Why I dislike the item method is because they all have a collision size of 16. But with this system, you can cover fringe cases by permitting a collision size to be passed. A unit with 16 collision can go through much tighter areas than one with 64 collision.
First of: this pathchecker checks 64x64 cells by default, even though it can be configured to check 32x32 cells, doubling the resolution.
This is because 64x64 is the smallest default pathing texture size for doodads/destructables.
So, by definition, any unit with a collision size of 0-31 is already fully covered by this system.
If you want to check for larger units, all you need to do is run the algorithm twice with an offset of 64 coordinate units in X or Y direction (depending on the direction of the knockback*).

This will cover all remaining collision sizes (32-63). Remember that collision size is capped at a radius of 64 anyway, so there are only these two possibilities.

*if knockback angle is between 315 and 45 degrees (= moving east) or between 135 and 225 (= moving west), offset by x.
Otherwise offset by y.

I could implement that directly into the system (as a function wrapper), if it is needed.


I would really like to use this for Knockback 2.5D, but I don't see how it would work with bouncing units. I'd have to use extra variables to track how long until the next bounce, then run the checker again when it's time to bounce. BUT - the trigger must then assess if it should bounce from a different angle (if your check before the loop starts, returning false).
I don't know how your bounces will work, but I don't see a problem with just running the algorithm again each time the unit bounces.

For this to work with Knockback 2.5D, I'd need to code this in vanilla JASS anyway. In the version I'd use, this function would return an integer instead of a boolean. I also would need it to not approximate anything (that IsTerrainWalkable resource would need to be re-implemented with 0 tolerance).
What would that integer possibly refer to then?
This does not approximate anything. The resource I use as a requirement approximates item displacement, yes, but since my system places items exactly by grid, all cases in which the aproximation would yield false results can never happen.
In fact, this was part of the reason why I even wrote this.

So, having IsTerrainWalkable inlined into your script, returning an integer instead of a boolean, and you've got a system which I could use.

Edit: Returning a real variable for the distance traveled would also be superior to returning an integer or boolean.
What should the integer value be? Also, why would I return the distance traveled when I don't actually move anything? This would be part of your knockback, not part of a pathchecker. You can retrieve the coordinates of the last walkable grid cell on the path; it is easy to calculate the distance between that and your origin.
 

Kazeon

Hosted Project: EC
Level 33
Joined
Oct 12, 2011
Messages
3,449
IsTerrainWalkable becomes quite a noticeably costy operation when you use it so frequently. As you are hiding, unhiding, and re-hiding items over and over again (as item enumeration actually iterates all items in the map, as DSG said). In extreme usage scenario like in my Glideon map, my fps dropped to ~5 when using Rising_Dusk's walkability checker library. But it was miraculously improved to 40~ fps when using the PathingLib. It's just for comparison how heavy Rising_Dusk's walkability checker library is. But for the best solution I can think of is to create a built-in walkability checker for this system so at least you are not re-hiding items inefficiently too much.
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
I didn't experience any FPS drops at all, but I also don't have lots of items in my map at the same time.

So yes, might be possible that the item approach is not a good idea in theory. However, it's the only solution we have so far that does not consider units.

If you are fine with units also blocking your path, just replace IsTerrainWalkable with PathingLib.

what is the state of this?
Tested and working. I am using it since months without an issue.
 

Kazeon

Hosted Project: EC
Level 33
Joined
Oct 12, 2011
Messages
3,449
Even if you use rect, actually it still iterates all items in map in order to check which items are within the rect. But yep that's probably still better than iterating though all items yourself.

@Zwei:
My map doesn't use item at all, yet still that was the result. Maybe because my PC was significantly weaker than yours. I have bought new one tho :D
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Even if you use rect, actually it still iterates all items in map in order to check which items are within the rect. But yep that's probably still better than iterating though all items yourself.

@Zwei:
My map doesn't use item at all, yet still that was the result. Maybe because my PC was significantly weaker than yours. I have bought new one tho :D
Something is fishy there then... there is no way this could be so bad in performance since I basicly use this on all knockbacks and several 32 fps checks in Gaias... and nobody ever complained about performance there.

What did you use in grid size? How long was the distance you were checking?
 

Kazeon

Hosted Project: EC
Level 33
Joined
Oct 12, 2011
Messages
3,449
Something is fishy there then... there is no way this could be so bad in performance since I basicly use this on all knockbacks and several 32 fps checks in Gaias... and nobody ever complained about performance there.

What did you use in grid size? How long was the distance you were checking?

I'm not sure since the issue was at very early stage of development. But I remember of using IsTerrainWalkable less often than your system does.
I really think IsTerrainWalkable is only a little heavier than SetUnitPosition. The system need to check which spot is free from pathing blocker to place the moved item/unit afterwards. And the larger the area it checks, the heavier the process will be.

Okay, maybe the improvement of using PathingLib was not that significant and perhaps I was just hyping it. Since it was long time ago and I don't remember it clearly.

And in the end, my main point was actually, like what Bribe pointed out, to only hide and unhide items before and after your system checks. If you use other walkablility checker library, you will ended up re-hiding and re-unhiding items over and over again everytime you call IsTerrainWalkable. The item approach issue only happens in certain scenario and using it is totally fine to me.
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
This is as straightforward as straightforward can be. What exactly is missing here in terms of a description?

Also, I don't see why I need an API for "IsPathWalkable". The name itself is self-explanatory.


Plus, I don't see why I am "not responding". I never received a PM about this. Sorry for not checking all my threads constantly.
 
The path checking seems to work nicely, but there's a little issue with last x/y.
As you work with the cell points, the checked points are not really "onPath" from x1/y1 - x2/y2,
and one can see in the demo that then the returned LastX/Y of the PathChecker will return the x/y of the last valid cell-checkpoint,
and not always the x/y that were actually on the real path.

Edit: the map terrain is from PathingLib v1.5.
 

Attachments

  • Pathing Checker.w3x
    37.4 KB · Views: 83
Last edited:

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
The path checking seems to work nicely, but there's a little issue with last x/y.
As you work with the cell points, the checked points are not really "onPath" from x1/y1 - x2/y2,
and one can see in the demo that then the returned LastX/Y of the PathChecker will return the x/y of the last valid cell-checkpoint,
and not always the x/y that were actually on the real path.

Edit: the map terrain is from PathingLib v1.5.
This is correct and intended (for performance reasons).

In practice, there is almost no visible difference anyway, as all normal unit pathing will apply to the minimum size pathing logic of units (32 units) anyway.

If you need the extra precision, you can simply switch to 32 unit resolution via the snippet's constants. Any higher precision would have no impact on gameplay, as this is the minimum the default unit pathing algorithm of WC3 allows.
 
Hm, with the lightning one definitly could see the offset at some places.
For normal unit movement you're probably right that it doesn't matter though.
Still, idk, I maybe would personaly prefer a path x/y. I made an example, if you want you can use it, and the lightnings also looks a bit better.

JASS:
library IsPathWalkable uses TerrainPathability
//get it here: [url]http://www.wc3c.net/showthread.php?t=103862[/url]

/*
Description:
This snippet uses the Bresenham algorithm of Pixelgraphics to check if the direct path between two cells (as a straight line) is walkable or not. It does so by looping through each cell between the two coordinates and checking their respective pathabilities.

Note: This snippet will ignore the collision of units, but will consider all doodad, destructable or terrain pathing. If you want to consider unit collision aswell, simply swap out TerrainPathability for your desired resource and replace all IsTerrainWalkable calls in the script.


Configurables:
private constant boolean DIAGONAL_SAFETY
- determines if on any diagonal step an adjacent cell is checked for extra safety (since units can not pass between two diagonally blocked cells). Default: enabled (true)
private constant integer MIN_CELL_SIZE
- determines the cell size for the Bresenham algorithm. As default pathing textures have a minimum cell size of 64, lowering this to 32 only makes sense if custom pathing textures are used. Default: 64.

API:
function IsPathWalkable takes real x1, real y1, real x2, real y2 returns boolean
- returns true if the path between coordinates x1|y1 (start) and x2|y2 (end) is walkable

function GetPathLastX takes nothing returns real
function GetPathLastY takes nothing returns real
- after using IsPathWalkable, these two functions will return the x and y coordinate of the last pathable cell between the start and end coordinate.

*/

globals
      private constant boolean DIAGONAL_SAFETY = true

      private constant integer MIN_CELL_SIZE = 64
      private constant integer CELL_CENTER_OFFSET = MIN_CELL_SIZE/2
  
      private real X = 0
      private real Y = 0
    
      private real LastX
      private real LastY
endglobals

//! textmacro Pathing_GetLastXY_Get

    if pathable then
        set LastX = x2
        set LastY = y2
        return true
    endif

    set angle1 = Atan2(y2 - y1, x2 - x1)
    set angle2 = Atan2(Y - y1, X - x1)
    set theta = (angle2 - angle1)*-1
      
    // rotate last x/y of cell checkpoint back to the path
    set LastX = (X-x1)*Cos(theta) - (Y-y1)*Sin(theta) + x1
    set LastY = (X-x1)*Sin(theta) + (Y-y1)*Cos(theta) + y1

    set offset_default = SquareRoot((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1))
    set offset_current = SquareRoot((X-x1) * (X-x1) + (Y-y1) * (Y-y1))
  
    // fix distance if it's bigger
    if (offset_default < offset_current) then
        set LastX = x2
        set LastY = y2
    endif
    return false

//! endtextmacro

//! textmacro Pathing_GetLastXY_Locals
    local real angle1
    local real angle2
    local real theta
    local real offset_default
    local real offset_current
    local boolean pathable
//! endtextmacro

function IsPathWalkable takes real x1, real y1, real x2, real y2 returns boolean
    
      //! runtextmacro Pathing_GetLastXY_Locals()

      local integer xstart = R2I(x1) / MIN_CELL_SIZE
      local integer xend = R2I(x2) / MIN_CELL_SIZE
      local integer ystart = R2I(y1) / MIN_CELL_SIZE
      local integer yend = R2I(y2) / MIN_CELL_SIZE
      local integer dx = xend - xstart
      local integer dy = yend - ystart
      local integer adx = dx
      local integer ady = dy
      local integer sdx = 0
      local integer sdy = 0
      local integer pdx
      local integer pdy
      local integer ddx
      local integer ddy
      local integer es
      local integer el
      local integer error
      local integer x = xstart
      local integer y = ystart
      local integer i = 1
      set X = x1
      set Y = y1
      //calculate abs values and signs
      if adx < 0 then
          set adx = -adx
          set sdx = -1
      elseif adx > 0 then
          set sdx = 1
      endif
      if ady < 0 then
          set ady = -ady
          set sdy = -1
      elseif ady > 0 then
          set sdy = 1
      endif
      if adx > ady then
          set pdx = sdx
          set pdy = 0
          set es = ady
          set el = adx
      else
          set pdx = 0
          set pdy = sdy
          set es = adx
          set el = ady
      endif
      set ddx = sdx
      set ddy = sdy
  
      if not IsTerrainWalkable(x*MIN_CELL_SIZE+CELL_CENTER_OFFSET, y*MIN_CELL_SIZE+CELL_CENTER_OFFSET) then
          return false
      endif
      set error = el/2
  
      loop
          exitwhen i > el
          set error = error - es
          if error < 0 then
              if DIAGONAL_SAFETY then
                  set dx = x+ddx-pdx
                  set dy = y+ddy-pdy
                  if IsTerrainWalkable(dx*MIN_CELL_SIZE+CELL_CENTER_OFFSET, dy*MIN_CELL_SIZE+CELL_CENTER_OFFSET) then
                      set X = dx*MIN_CELL_SIZE+CELL_CENTER_OFFSET
                      set Y = dy*MIN_CELL_SIZE+CELL_CENTER_OFFSET
                  else
                      set pathable = false
                      //! runtextmacro Pathing_GetLastXY_Get()
                  endif
              endif
              set error = error + el
              set x = x + ddx
              set y = y + ddy
          else
              set x = x + pdx
              set y = y + pdy
          endif
          if IsTerrainWalkable(x*MIN_CELL_SIZE+CELL_CENTER_OFFSET, y*MIN_CELL_SIZE+CELL_CENTER_OFFSET) then
              set X = x*MIN_CELL_SIZE+CELL_CENTER_OFFSET
              set Y = y*MIN_CELL_SIZE+CELL_CENTER_OFFSET
          else
              set pathable = false
              //! runtextmacro Pathing_GetLastXY_Get()
          endif
          set i = i + 1
      endloop
    
      set pathable = true
      //! runtextmacro Pathing_GetLastXY_Get()
endfunction

function GetPathLastX takes nothing returns real
    return LastX
endfunction
function GetPathLastY takes nothing returns real
    return LastY
endfunction

endlibrary

Hm.. but see the image below. When I go a bit more left (to center of farm), then it says not pathable, but at this it says "pathable" even there is clearly the farm.

Edit:

The actual path is not pathable, but seems like the path to cell checkpoint (on the right) is pathable, which results in something unwanted.

 

Attachments

  • Pathing Checker.w3x
    38.5 KB · Views: 82
  • pathable.PNG
    pathable.PNG
    658.3 KB · Views: 141
Last edited:

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
The thing you reported is not an issue, it's intended. The pathchecker will by default ignore unit (and thus also building) collision. This is also mentioned in the API.

If you want to change that, you just have to use a different IsTerrainPathable library. I recommend the one here on hive that uses build orders; it is very lightweight and registers all pathing obstructions, including units and buildings.


The adjustments you made to get the "correct" coordinate of the last pathable point are heavy burden on processing power (using Square Roots and trigonometry) and thus defeat the purpose of the snippet.

I made this with maximum performance in mind for exactly one purpose: checking if a direct line between two points is pathable (for example, for knockback systems or blink-type spells). The returned last position is just a bonus.

If exact pathing precision is important for your use, you should use a different snippet that uses trigonometry instead of cell-based checking. There is no point in using the Bresenham algorithm then. This is not for art applications, this is for quick pathing checks.
 
Last edited:
Right, it was mentioned for units, it was my fault. Anyways, buildings have also a pathing map that is not walkable (magenta ; 6.1) "war3mapPath.tga" The Image Path -- W3M and W3X Files Format) , and it should be considered as not pathable. It actually happens, for example when I place an other farm on the right of the test farm, then it properly says "not pathable". But look at the image, here it's clearly at the magenta, but it says pathable.

My guess:
The actual path is not pathable, but seems like the path to cell checkpoint (on the right) is pathable, which results in something unwanted.

The adjustments you made to get the "correct" coordinate of the last pathable point are heavy burden on processing power (using Square Roots and trigonometry) and thus defeat the purpose of the snippet.
In case it's pathable, there is almost no overhead. In case it's not pathable there are some function calls, but you get correct values. It's not necessarily about aesthetics, but about correct formulas. The lightning is just used to visualisize the result.
I honestly doubt that you will have major fps difference with it, in the end it's still only some function calls, and there are much heavier algorithms out there, like some polygon operations.
You're acting like calculating correct values could destroy the map gameplay, or so. And the "last return values" bonus may be good for some rough concepts, but it's mathematicaly just false, and it's a pretty important info.
 

Attachments

  • aa.PNG
    aa.PNG
    183.2 KB · Views: 136
  • Pathing Checker (1).w3x
    38.5 KB · Views: 94

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
I designed this for the purpose of calculating the last pathable position for unit placement. And in this case I specifically don't want the exact location on the path.

I attached an image displaying the problem. The algorithm I implemented will always return the center of one of the green cells for the last pathable point from A to B.
Your modified algorithm will always return a position on the red line, which can actually be on a non-pathable cell, as you can see below.

It's fine as an optional feature though.


As for your farm problem, I suppose its an issue with your IsTerrainPathable function. Which one did you use? Remember that if you use one that is based on item placement, you might get weird effects such as this on buildings. Have you tried the same with a doodad?


EDIT:
I just checked out your demomap with my unmodified algorithm and visualized all the cells checked with a special effect; it seems that my algorithm always checks the cell right from the actual current cell for some reason. Nice find!

EDIT2:
Okay, the problem is the classic truncated vs. floored division problem. For some reason I assumed that blizzard implemented integer division in the same (smart) way it is implemented in Python, which is: 48/64 = 0 and -48/64 = -1.
However, the way it works in JASS is 48/64 = 0 and -48/64 = 0, which shifts the cell numbers if x or y are negative.
In practice, this means that the algorithm above only works in the first quadrant of the map and will result in shifted positions on all other quadrants. I'll fix this asap.
 

Attachments

  • Bresenham.jpg
    Bresenham.jpg
    17.9 KB · Views: 103
Last edited:

Submission:
Bresehnham Pathchecker v1.0

Date:
22 Feb 2017

Status:
Approved
Note:

The fix works good.
Your argumentation makes actually sense too, that in normal cases it matters if the path-line is pathable, and not the 100% correct line, at least for normal movement. Therefore it works as intended.

I took freedom to add a "1.0" version number, because it may be useful when they are updates. Approved.
 
Level 1
Joined
Apr 8, 2020
Messages
110
You can do the following - I created 3 variables:
Two Point variables: TempLoc_1 and TempLoc_2
One Boolean variable: IsPathWalkable

  • CheckPath
    • Events
    • Conditions
    • Actions
      • Custom script: set udg_IsPathWalkable = IsPathWalkable(GetLocationX(udg_TempLoc_1), GetLocationY(udg_TempLoc_1), GetLocationX(udg_TempLoc_2), GetLocationY(udg_TempLoc_2))
  • Example
    • Events
      • Unit - A unit enters (Playable map area)
    • Conditions
    • Actions
      • Set TempLoc_1 = (Position of (Triggering unit))
      • Set TempLoc_2 = (Random point in (Playable map area))
      • Trigger - Run CheckPath <gen> (ignoring conditions)
      • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
        • If - Conditions
          • IsPathWalkable Equal to True
        • Then - Actions
          • Unit - Order (Triggering unit) to Move To TempLoc_2
        • Else - Actions
Alternative Systems: Check Walkability (GUI) and PathingLib
 
Level 11
Joined
Jul 17, 2013
Messages
544
You can do the following - I created 3 variables:
Two Point variables: TempLoc_1 and TempLoc_2
One Boolean variable: IsPathWalkable

  • CheckPath
    • Events
    • Conditions
    • Actions
      • Custom script: set udg_IsPathWalkable = IsPathWalkable(GetLocationX(udg_TempLoc_1), GetLocationY(udg_TempLoc_1), GetLocationX(udg_TempLoc_2), GetLocationY(udg_TempLoc_2))
  • Example
    • Events
      • Unit - A unit enters (Playable map area)
    • Conditions
    • Actions
      • Set TempLoc_1 = (Position of (Triggering unit))
      • Set TempLoc_2 = (Random point in (Playable map area))
      • Trigger - Run CheckPath <gen> (ignoring conditions)
      • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
        • If - Conditions
          • IsPathWalkable Equal to True
        • Then - Actions
          • Unit - Order (Triggering unit) to Move To TempLoc_2
        • Else - Actions
Alternative Systems: Check Walkability (GUI) and PathingLib


Why temploc 2 must exit? Isn't IT better for it to be same region all the time? Like region 2

Idk if gamę wouldnt lag if IT checks all of my big map and takes random point

I need walkability check for knockback btw

Is the GUI system fine? I have Heard Someone saying its leakly
 
Level 1
Joined
Apr 8, 2020
Messages
110
@emil23 This resource checks the path between two points, not just a single point. If you want to check only a single point, you can use the IsTerrainWalkable or the GUI variant, Check Walkability, library directly.

A knockback system, as you might understand it this way, moves a unit from one point to another, so it is similarly about a path between two points like this resource.

I highly doubt setting a point variable to a random point in playable map area will cause lag. Besides, that was just an example. You can set it to anything that you desire.

About the leaks, I would have thought someone would have reported in the thread by now ever since the system's incarnation. I mean like so many years have passed with so many using it (Ok, I admit 622 downloads is not much, but the download count does not consider the myriad of other sources peeps obtain this resource from) that I would think any leaks would have been known by this time.
 
Last edited:
Top