Hosted Project GR
- Joined
- Sep 17, 2009
- Messages
- 7,234
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.
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:
