- Joined
- Feb 4, 2009
- Messages
- 1,314
I tried to make a pathfinding system but I have a few issues with it:
1. it does not always find the shortest path
2. if I enable diagonal paths it will find weird paths
(probably could be fixed by checking up/down/left/right points but there might be a better solution)
3. sometimes it does not find a path at all
or if anyone got a better idea to find paths than this grid approach tell me and I'll try if it works
Alright, here's the code and the map
1. it does not always find the shortest path
2. if I enable diagonal paths it will find weird paths
(probably could be fixed by checking up/down/left/right points but there might be a better solution)
3. sometimes it does not find a path at all
or if anyone got a better idea to find paths than this grid approach tell me and I'll try if it works
Alright, here's the code and the map
JASS:
//Might find very small paths (even smaller than collision size of unit)
function FindPath_IsPathable takes real x, real y returns boolean
//Move items to point
call SetItemPosition(udg_Path_Item, x, y)
call SetItemPosition(udg_Path_Item2, x, y)
//If item1 is at the desired point the point is free
//If item2 is not at that point item1 didn't get stuck in cliffs or water
return GetWidgetX(udg_Path_Item)==x and GetWidgetY(udg_Path_Item)==y and GetWidgetX(udg_Path_Item2)!=x and GetWidgetY(udg_Path_Item2)!=y
endfunction
//Check point
function FindPath_Check takes integer x, integer y, integer c, integer i returns integer
//If point not checked yet
if not HaveSavedInteger(udg_Path, x, y) then
//Check pathing
if FindPath_IsPathable(x, y) then
//Save point
call SaveInteger(udg_Path, x, y, i)
call SaveInteger(udg_Path, c+1, 1, x)
call SaveInteger(udg_Path, c+1, 2, y)
return 1
endif
endif
return 0
endfunction
function FindPath_Run takes integer i, integer n returns integer
local integer x
local integer y
local integer xt = LoadInteger(udg_Path, StringHash("xt"), 0)
local integer yt = LoadInteger(udg_Path, StringHash("yt"), 0)
local integer r = LoadInteger(udg_Path, StringHash("r"), 0)
local integer c = n //Index for new points
local integer r2 = r*r //Detection radius
loop
//While there are points left to check
exitwhen i>n
//Load current point
set x = LoadInteger(udg_Path, i, 1)
set y = LoadInteger(udg_Path, i, 2)
//Check if target is close to current point
if (xt-x)*(xt-x)+(yt-y)*(yt-y)<=r2 then
return i
else
//Check left, right, up, down
set c = c + FindPath_Check(x+r, y, c, i)
set c = c + FindPath_Check(x-r, y, c, i)
set c = c + FindPath_Check(x, y+r, c, i)
set c = c + FindPath_Check(x, y-r, c, i)
//If I delete these it won't find diagonal paths at all
set c = c + FindPath_Check(x+r, y+r, c, i)
set c = c + FindPath_Check(x+r, y-r, c, i)
set c = c + FindPath_Check(x-r, y+r, c, i)
set c = c + FindPath_Check(x-r, y-r, c, i)
//Internal opperation limit
//Higher number might be possible
//But things might become unstable under certain conditions
//Better don't increase it much more
if c-n>100 then
exitwhen true
endif
endif
//Next point
set i = i + 1
endloop
//Target not found yet, start next circle
if c>n then
if n<LoadInteger(udg_Path, StringHash("limit"), 0) then
//Workaround to bypass operation limit
call SaveInteger(udg_Path, StringHash("i"), 0, i)
call SaveInteger(udg_Path, StringHash("c"), 0, c)
call TriggerExecute(gg_trg_Path)
return LoadInteger(udg_Path, StringHash("result"), 0)
endif
return -2
endif
return -3
endfunction
function FindPath_ItemFilter takes nothing returns boolean
//Hide item and add it to array to reveal it later
if IsItemVisible(GetFilterItem()) then
set udg_Path_ItemArray[udg_Path_Count] = GetFilterItem()
call SetItemVisible(udg_Path_ItemArray[udg_Path_Count], false)
set udg_Path_Count = udg_Path_Count + 1
endif
return false
endfunction
//Prepare pathfinding
function FindPath takes real x, real y, real x2, real y2 returns integer
//Distance between points
local integer r = 128
local integer result = -1
//Clear path
call FlushParentHashtable(udg_Path)
set udg_Path = InitHashtable()
//Create items for pathchecking
if udg_Path_Item==null then
set udg_Path_Item = CreateItem('ches', 0.00, 0.00)
set udg_Path_Item2 = CreateItem('ches', 0.00, 0.00)
call SetItemVisible(udg_Path_Item , false)
call SetItemVisible(udg_Path_Item2, false)
endif
//Hide items so they won't fuck up our pathchecking
set udg_Path_Count = 0
call EnumItemsInRect(bj_mapInitialPlayableArea, Condition(function FindPath_ItemFilter ), null)
//Set starting point for pathfinding
call SaveInteger(udg_Path, 0, 1, R2I(x))
call SaveInteger(udg_Path, 0, 2, R2I(y))
call SaveInteger(udg_Path, StringHash("xt"), 0, R2I(x2))
call SaveInteger(udg_Path, StringHash("yt"), 0, R2I(y2))
call SaveInteger(udg_Path, StringHash("r"), 0, r)
call SaveInteger(udg_Path, StringHash("limit"), 0, 12345)
//Begin pathfinding
//Parameters:
//1. index of first uprocessed point
//2. index of last point
set result = FindPath_Run(0, 0)
//Hide pathcheck items (moving unhides them)
call SetItemVisible(udg_Path_Item, false)
call SetItemVisible(udg_Path_Item2, false)
//Show previously hidden items
loop
exitwhen udg_Path_Count<=0
set udg_Path_Count = udg_Path_Count - 1
call SetItemVisible(udg_Path_ItemArray[udg_Path_Count], true)
endloop
return result
endfunction-
Path
-
Events
-
Conditions
-
Actions
-
Custom script: local integer i = LoadInteger(udg_Path, StringHash("i"), 0)
-
Custom script: local integer c = LoadInteger(udg_Path, StringHash("c"), 0)
-
Custom script: call SaveInteger(udg_Path, StringHash("result"), 0, FindPath_Run( i, c))
-
-
-
FindPath
-
Events
-
Unit - A unit Is issued an order targeting a point
-
-
Conditions
-
Actions
-
Custom script: local integer result = -1
-
Custom script: local integer x
-
Custom script: local integer y
-
Custom script: local integer x2
-
Custom script: local integer y2
-
Custom script: set result = FindPath(GetUnitX(GetTriggerUnit()), GetUnitY(GetTriggerUnit()), GetOrderPointX(), GetOrderPointY())
-
For each (Integer A) from 1 to Lightning_Count, do (Actions)
-
Loop - Actions
-
Lightning - Destroy Lightning[(Integer A)]
-
-
-
Set Lightning_Count = 0
-
Custom script: loop
-
Custom script: set x = LoadInteger(udg_Path, result, 1)
-
Custom script: set y = LoadInteger(udg_Path, result, 2)
-
Custom script: exitwhen result<=0
-
Custom script: set result = LoadInteger(udg_Path, x, y)
-
Custom script: set x2 = LoadInteger(udg_Path, result, 1)
-
Custom script: set y2 = LoadInteger(udg_Path, result, 2)
-
Set Lightning_Count = (Lightning_Count + 1)
-
Custom script: set udg_Lightning[udg_Lightning_Count] = AddLightning("DRAL", false, x, y, x2, y2)
-
Custom script: endloop
-
-
