- Joined
- Jul 10, 2007
- Messages
- 6,306
Being Updated To A*
->http://www.hiveworkshop.com/forums/1956872-post2.html
->http://www.hiveworkshop.com/forums/1956872-post2.html
JASS:
library Path /* v1.0.0.2
*************************************************************************************
*
* This is able to determine if a path between two points is blocked as well
* as retrieve the shortest path between those two points in the form of a linked list.
*
************************************************************************************
*
* */uses/*
*
* */ IsPathable /* hiveworkshop.com/forums/submissions-414/snippet-ispathable-199131/
*
************************************************************************************
*
* struct Path extends array
*
* readonly thistype next
* - Retrieves the next node on the path. The first node is the path head.
* - Sentinel: 0
* readonly thistype prev
* - Retrieves the previous node on the path (previous of path head is last node).
* - Sentinel: 0
* readonly integer x
* - Retrieves x coordinate of node
* readonly integer y
* - Retrieves y coordinate of node
*
* static method create takes integer startX, integer startY, integer endX, integer endY, integer pathingType returns Path
* - Attempts to create a path between two points {startX,startY -> endX,endY}
* - In this case where there is no such path, the path returned is 0.
* - This will return the smallest path between the two points.
* - This is a very heavy operation.
* method destroy takes nothing returns nothing
* - Destroys a path. This is a very light operation.
*
* static method isBlocked takes integer startX, integer startY, integer endX, integer endY, integer pathingType returns boolean
* - Determines if a path is blocked or not.
*
************************************************************************************/
globals
private integer i=0 //instance count
private integer r=0 //recycler
endglobals
struct Path extends array
readonly thistype next //next node
readonly thistype prev //previous node
readonly integer x //x coord
readonly integer y //y coord
static method isBlocked takes integer x, integer y, integer x2, integer y2, integer pt returns boolean
local integer c=0 //instance count of local lists
local integer array n //list next
local integer array p //list previous
local integer array lx //point x
local integer array ly //point y
local integer array dx //direction x
local integer array dy //direction y
local thistype k=0 //current list
local thistype m=0 //new list
local hashtable ht //local hashtable for seeing if a coordinate was hit
local integer o //open paths
local boolean f=false //initially found path already?
//have to work in a 32x32 grid, so format the coordinates
set x=(x+32)/32*32
set y=(y+32)/32*32
set x2=(x2+32)/32*32
set y2=(y2+32)/32*32
//if the start and end points are pathable, continue
if (IsPathable(x,y,pt) and IsPathable(x2,y2,pt)) then
set ht=InitHashtable()
call SaveBoolean(ht,x,y,true) //mark start point as hit
//create first 4 path nodes branching out in 4 directions like a cross
//from start point
//! runtextmacro INI_PATH_NODE("32","0")
//! runtextmacro INI_PATH_NODE("-32","0")
//! runtextmacro INI_PATH_NODE("0","32")
//! runtextmacro INI_PATH_NODE("0","-32")
//if none of the path nodes were the end point, then continue
if (not f) then
//if none of the path nodes were valid, end
set k=n[0]
if (0==k) then
call FlushParentHashtable(ht)
set ht=null
return true
endif
//loop through each open path node and branch them out
loop
//reset the open paths. If this hits 0, path ended up being
//a dead end
set o=4
//branch out
//! runtextmacro ALLOCATE_PATH_NODE_2("0","32")
//! runtextmacro ALLOCATE_PATH_NODE_2("0","-32")
//! runtextmacro ALLOCATE_PATH_NODE_2("32","0")
//! runtextmacro ALLOCATE_PATH_NODE_2("-32","0")
//dead end
if (0==o) then
set n[p[k]]=n[k]
set p[n[k]]=p[k]
endif
set k=n[k]
//if k is at 0, then it's at the head
if (0==k) then
set k=n[k]
//if thee are no more lists, return blocked
if (0==k) then
call FlushParentHashtable(ht)
set ht=null
return true
endif
//flip pathing
//goes between going straight and branching
set f=not f
endif
endloop
endif
call FlushParentHashtable(ht)
set ht=null
//not blocked if at this point
return false
endif
//blocked if at this point
return true
endmethod
static method create takes integer x, integer y, integer x2, integer y2, integer pt returns thistype
local integer c=0 //list instance count
local integer array n //list next
local integer array p //list previous
local integer array pa //parent list
local integer array px //parent x
local integer array py //parent y
local integer array lx //point x
local integer array ly //point y
local integer array dx //direction x
local integer array dy //direction y
local thistype k=0 //current list
local thistype m=0 //new list
local thistype l=0 //list
local hashtable ht
local integer o //open paths
local boolean f=false
//format to 32x32 grid
set x=(x+32)/32*32
set y=(y+32)/32*32
set x2=(x2+32)/32*32
set y2=(y2+32)/32*32
//make sure start and end are pathable
if (IsPathable(x,y,pt) and IsPathable(x2,y2,pt)) then
set ht=InitHashtable()
call SaveBoolean(ht,x,y,true) //mark start as hit
//branch
//! runtextmacro INI_PATH_NODE("32","0")
//! runtextmacro INI_PATH_NODE("-32","0")
//! runtextmacro INI_PATH_NODE("0","32")
//! runtextmacro INI_PATH_NODE("0","-32")
//if not hit end, go on
if (not f) then
set k=n[0]
//if no branches, start is blocked off, return 0
if (0==k) then
call FlushParentHashtable(ht)
set ht=null
return 0
endif
//loop through each branch and branch them
loop
set o=4 //open paths
//! runtextmacro ALLOCATE_PATH_NODE("0","32")
//! runtextmacro ALLOCATE_PATH_NODE("0","-32")
//! runtextmacro ALLOCATE_PATH_NODE("32","0")
//! runtextmacro ALLOCATE_PATH_NODE("-32","0")
//dead end
if (0==o) then
set n[p[k]]=n[k]
set p[n[k]]=p[k]
endif
set k=n[k]
//if hit head, flip pathing
if (0==k) then
set k=n[k]
//no lists left, all hit dead ends, path is blocked
if (0==k) then
call FlushParentHashtable(ht)
set ht=null
return 0
endif
set f=not f //alternate between straight and branch
endif
endloop
endif
call FlushParentHashtable(ht)
set ht=null
set k=m //correct path node (goal) is in m
//allocate head and set it's coordinate to start point
if (0==r) then
set l=i+1
set i=l
else
set l=r
set r=l.next
endif
set l.x=x
set l.y=y
//allocate first node on path
if (0==r) then
set m=i+1
set i=m
else
set m=r
set r=m.next
endif
set m.x=lx[k]
set m.y=ly[k]
//add it to head
set m.next=l
set m.prev=l
set l.next=m
set l.prev=m
loop
exitwhen 0==pa[k] //exitwhen there are no more nodes on the path
//this goes from the end back to the start
//each node has a parent that it branched from
//as well as a parent coodinate, which is where
//it branched from the parent (since parents
//move). This just loops up through the parents.
//allocate
if (0==r) then
set m=i+1
set i=m
else
set m=r
set r=m.next
endif
//add
set l.prev.next=m
set m.prev=l.prev
set m.next=l
set l.prev=m
//store coord
set m.x=px[k]
set m.y=py[k]
//go to next parent
set k=pa[k]
endloop
//allocate last node
if (0==r) then
set m=i+1
set i=m
else
set m=r
set r=m.next
endif
set m.x=x2
set m.y=y2
//add
set l.prev.next=m
set m.prev=l.prev
set m.next=l
set l.prev=m
//set ends of list to 0
set l.prev.next=0
set l.next.prev=0
return l
endif
return 0
endmethod
method destroy takes nothing returns nothing
//recycles entire list
//last node points to recycler
//recycler is set to first node
//the list is essentially shifted in front of the recycler
set prev.next=r
set r=this
endmethod
endstruct
//this is for initializing the first branching nodes
//! textmacro INI_PATH_NODE takes DX,DY
//if no branch nodes have hit the end
//and the branch point is pathable
if not f and IsPathable(x+$DX$,y+$DY$,pt) then
//mark as hit
call SaveBoolean(ht,x+$DX$,y+$DY$,true)
//allocate
set k=c+1
set c=k
//store point
set lx[k]=x+$DX$
set ly[k]=y+$DY$
//add to branch list
set p[n[0]]=k
set n[k]=n[0]
set n[0]=k
//store direction*
set dx[k]=$DX$
set dy[k]=$DY$
//if the branch point was the goal, mark as goal
if lx[k]==x2 and ly[k]==y2 then
set m=k //store k to m
set f=true //mark (ini nodes only)
endif
endif
//! endtextmacro
//! textmacro ALLOCATE_PATH_NODE takes DX,DY
//if the branched point was hit or the point wasn't pathable, mark as dead end
if (HaveSavedBoolean(ht,lx[k]+$DX$,ly[k]+$DY$) or not IsPathable(lx[k]+$DX$,ly[k]+$DY$,pt)) then
set o=o-1 //dead end counter
else
//if a branch (not in same direction as current node)
if ($DX$!=dx[k] or $DY$!=dy[k]) then
//only branch if the branching flag is marked true
//this is to give priority to straight paths so that
//the shortest path doesn't end up being a spiraling mess
if (f) then
//mark branch point as hit
call SaveBoolean(ht,lx[k]+$DX$,ly[k]+$DY$,true)
//allocate
set m=c+1
set c=m
//store point of parent node as parent node coordinate
//remember that parent nodes move around!
set px[m]=lx[k]
set py[m]=ly[k]
//add to branch list
set p[n[0]]=m
set n[m]=n[0]
set n[0]=m
//store direction
set dx[m]=$DX$
set dy[m]=$DY$
//store coordinate
set lx[m]=lx[k]+$DX$
set ly[m]=ly[k]+$DY$
//store parent node
set pa[m]=k
//if this node hit the goal, exit loop
exitwhen lx[m]==x2 and ly[m]==y2
endif
//else if the path was straight, enter if flagged for straight paths
elseif (not f) then
//mark point as hit
call SaveBoolean(ht,lx[k]+$DX$,ly[k]+$DY$,true)
//set m to k in case this node was the goal
set m=k
//move the node forward
set lx[k]=lx[k]+$DX$
set ly[k]=ly[k]+$DY$
//if the node hit the goal, exit loop
exitwhen lx[k]==x2 and ly[k]==y2
endif
endif
//! endtextmacro
//! textmacro ALLOCATE_PATH_NODE_2 takes DX,DY
//if the branched point was hit or the point wasn't pathable, mark as dead end
if (HaveSavedBoolean(ht,lx[k]+$DX$,ly[k]+$DY$) or not IsPathable(lx[k]+$DX$,ly[k]+$DY$,pt)) then
set o=o-1 //dead end counter
else
//if a branch (not in same direction as current node)
if ($DX$!=dx[k] or $DY$!=dy[k]) then
//only branch if the branching flag is marked true
//this is to give priority to straight paths so that
//the shortest path doesn't end up being a spiraling mess
if (f) then
//mark branch point as hit
call SaveBoolean(ht,lx[k]+$DX$,ly[k]+$DY$,true)
//allocate
set m=c+1
set c=m
//add to branch list
set p[n[0]]=m
set n[m]=n[0]
set n[0]=m
//store direction
set dx[m]=$DX$
set dy[m]=$DY$
//store coordinate
set lx[m]=lx[k]+$DX$
set ly[m]=ly[k]+$DY$
//if this node hit the goal, exit loop
exitwhen lx[m]==x2 and ly[m]==y2
endif
//else if the path was straight, enter if flagged for straight paths
elseif (not f) then
//mark point as hit
call SaveBoolean(ht,lx[k]+$DX$,ly[k]+$DY$,true)
//move the node forward
set lx[k]=lx[k]+$DX$
set ly[k]=ly[k]+$DY$
//if the node hit the goal, exit loop
exitwhen lx[k]==x2 and ly[k]==y2
endif
endif
//! endtextmacro
endlibrary
Last edited by a moderator:
