So before in Fields I was using a pretty standard A* routine for pathing. The problem with this routine was that it was getting kind of slow (50-100 ms for each path, and I wasn't even close to the map sizes I wanted).
I realized this was largely due to the fact that even in the large, open spaces of Fields, each A* node was a small 10x10 box, and when pathing, each unit had to go through large grids of these little boxes even if there weren't any obstacles around. So, I started trying to create a faster pathing routine that would also allow me to abandon the grid completely and allow buildings to be placed entirely freeform - any postion, any angle.
I got stuck on this a few months ago, hence the few months of silence.
But last week I had a great idea that lead to this demo:
`Fields Pathfinding
`by BMacZero
sync on : sync rate 60
type VertType
X as float
Y as float
endtype
type LineType
V1 as integer
V2 as integer
endtype
type AStarNode
F as integer
G as integer
H as integer
Open as boolean
Closed as boolean
Parent as integer
endtype
type Connection
N1 as integer
N2 as integer
Distance as integer
endtype
DIM Lines(0) as LineType
DIM Verts(0) as VertType
`Allow the user to draw in some lines:
repeat
`Display the lines drawn so far
cls
DrawLines()
text 10,10,"Click and drag to draw lines."
text 10,20,"Space when done."
`Some circles to help the user lock onto existing vertices
ink rgb(150,0,0)
for c=1 to array count(Verts(0))
circle Verts(c).X,Verts(c).Y,10
next c
if mouseclick()=1
`Start drawing a line on mouseclick
if clicked=0
clicked=1
tstartvert=0
`Check if any verts are close enough to lock to
for c=1 to array count(Verts(0))
if SQRT((Verts(c).X-mousex())^2+(Verts(c).Y-mousey())^2)<=10 then tstartvert=c
next c
if tstartvert>0
startvert=tstartvert
startx=Verts(startvert).X
starty=Verts(startvert).Y
else
startvert=0
startx=mousex()
starty=mousey()
endif
else
`Keep drawing a line
`See if it can be locked to an existing vertice
tendvert=0
for c=1 to array count(Verts(0))
if SQRT((Verts(c).X-mousex())^2+(Verts(c).Y-mousey())^2)<=10 then tendvert=c
next c
if tendvert>0
endvert=tendvert
endx=Verts(endvert).X
endy=Verts(endvert).Y
else
endvert=0
endx=mousex()
endy=mousey()
endif
`Draw the line in progress
ink rgb(255,0,0),0
line startx,starty,endx,endy
endif
else
`Complete a line
if clicked=1
clicked=0
`If the line is valid..
if SQRT((startx-endx)^2+(starty-endy)^2)>10
`Make any verts needed for it:
if startvert=0
array insert at bottom Verts(0)
Verts(array count(Verts(0))).X=startx
Verts(array count(Verts(0))).Y=starty
startvert=array count(Verts(0))
endif
if endvert=0
array insert at bottom Verts(0)
Verts(array count(Verts(0))).X=endx
Verts(array count(Verts(0))).Y=endy
endvert=array count(Verts(0))
endif
`And draw a line between them:
array insert at bottom Lines(0)
Lines(array count(Lines(0))).V1=startvert
Lines(array count(Lines(0))).V2=endvert
endif
startvert=0
endvert=0
startx=0
starty=0
endx=0
endy=0
endif
endif
sync
`Done Drawing
until spacekey()=1
pressed=1
`============================ BEGIN PATH PREPROCESSING ====================================
`Process distances
DIM Connections(0) as Connection
DIM Connectiondels(0) as boolean
for c=1 to array count(Verts(0))
for d=c+1 to array count(Verts(0))
if Raycast(Verts(c).X,Verts(c).Y,Verts(d).X,Verts(d).Y,0,0)=0
array insert at top Connections(0)
array insert at top Connectiondels(0)
Connections(1).N1=c
Connections(1).N2=d
Connections(1).Distance=SQRT((Verts(c).X-Verts(c).Y)^2+(Verts(c).Y-Verts(d).Y)^2)
endif
next d
next c
`Remove interior ones
for c=1 to array count(Connections(0))
next c
`Delete
for c=array count(Connections(0)) to 1 step -1
if Connectiondels(c)=1 then array delete element Connections(0),c
next c
UNDIM Connectondels(0)
`==========================================================================================
UnitRadius#=10
DIM Paths(0) as VertType
MoveSpeed#=1
`sprite
ink rgb(255,255,255)
circle UnitRadius#,UnitRadius#,UnitRadius#
get image 1,0,0,(UnitRadius#*2)+1,(UnitRadius#*2)+1,1
sprite 1,100,100,1
offset sprite 1,UnitRadius#,UnitRadius#
DO
cls
text 10,10,str$(time)+" ms"
DrawLines()
text 10,20,"Click to path."
if mouseclick()=1 and clicked=0
clicked=1
start=timer()
UNDIM Paths(0)
DIM Paths(0) as VertType
Path(sprite x(1),sprite y(1),mousex(),mousey())
time=timer()-start
endif
if mouseclick()=0 then clicked=0
if array count(Paths(0))>0
pointsprite(1,Paths(1).X,Paths(1).Y)
move sprite 1,MoveSpeed#
if near(sprite x(1),Paths(1).X) and near(sprite y(1),Paths(1).Y) then array delete element Paths(0),1
endif
for c=1 to array count(Paths(0))
text Paths(c).X,Paths(c).Y,"X"
next c
SYNC
LOOP
function Path(StartX,StartY,EndX,EndY)
UNDIM TempNodes(0)
DIM TempNodes(array count(Verts(0))) as AStarNode
`Open nodes to start
for c=1 to array count(Verts(0))
if Raycast(StartX,StartY,Verts(c).X,Verts(c).Y,0,0)=0
TempNodes(c).Open=1
TempNodes(c).Parent=0
TempNodes(c).G=SQRT((StartX-Verts(c).X)^2+(StartY-Verts(c).y)^2)
TempNodes(c).H=abs(StartX-Verts(c).X)+abs(StartY-Verts(c).y)
TempNodes(c).F=TempNodes(c).G+TempNodes(c).H
endif
next c
while Raycast(Verts(winner).X,Verts(winner).Y,EndX,EndY,0,0)=1 or winner=0
score=99999
winner=0
for c=1 to array count(TempNodes(0))
if TempNodes(c).Open=1 and TempNodes(c).Closed=0
if TempNodes(c).F<score
winner=c
score=TempNodes(c).F
endif
endif
next c
if winner=0 then exitfunction
TempNodes(winner).Closed=1
for c=1 to array count(Connections(0))
temp=0
if Connections(c).N1=winner then temp=Connections(c).N2
if Connections(c).N2=winner then temp=Connections(c).N1
if temp>0 and TempNodes(temp).Closed=0
if TempNodes(temp).Open=0
TempNodes(temp).Open=1
TempNodes(temp).Parent=winner
TempNodes(temp).G=TempNodes(winner).G+Connections(c).Distance
TempNodes(temp).H=abs(Verts(winner).X-Verts(temp).X)+abs(Verts(winner).Y-Verts(temp).y)
TempNodes(temp).F=TempNodes(temp).G+TempNodes(temp).H
else
if TempNodes(temp).G>TempNodes(winner).G+Connections(c).Distance
TempNodes(temp).Parent=winner
TempNodes(temp).G=TempNodes(winner).G+Connections(c).Distance
TempNodes(temp).F=TempNodes(temp).G+TempNodes(temp).H
endif
endif
endif
next c
`Debug
if 0
cls
DrawLines()
for d=1 to array count(Verts(0))
if TempNodes(d).Open=1
if d=winner
text Verts(d).X,Verts(d).Y,str$(d)+"X"
else
text Verts(d).X,Verts(d).Y,str$(d)
endif
text Verts(d).X,Verts(d).Y+15,str$(TempNodes(d).Parent)
endif
next d
sync
wait key
endif
endwhile
`Backtrack to find path
if winner>0
repeat
array insert at top Paths(0)
Paths(1).X=Verts(winner).X
Paths(1).Y=Verts(winner).Y
winner=TempNodes(winner).Parent
until winner=0
endif
array insert at bottom Paths(0)
Paths(array count(Paths(0))).X=EndX
Paths(array count(Paths(0))).Y=EndY
endfunction
function Raycast(X1 as integer,Y1 as integer,X2 as integer,Y2 as integer,NL1,NL2)
for c=1 to array count(Lines(0))
if c<>NL1 and c<>NL2
if FastLineIntersection(X1,Y1,X2,Y2,Verts(Lines(c).V1).X,Verts(Lines(c).V1).Y,Verts(Lines(c).V2).X,Verts(Lines(c).V2).Y) then exitfunction 1
endif
next c
endfunction 0
`by DavidT
function pointsprite(s,x,y)
dx = sprite x(s) - x
dy = sprite y(s) - y
ang# = wrapvalue(atanfull(dx,dy)*-1)
rotate sprite s,ang#
endfunction
`by IanM
function FastLineIntersection(Ax as float,Ay as float,Bx as float,By as float,Cx as float,Cy as float,Dx as float,Dy as float)
local r as float : local s as float : local d as float : local n as float
n = ((Ay - Cy) * (Dx - Cx)) - ((Ax - Cx) * (Dy - Cy))
d = ((Bx - Ax) * (Dy - Cy)) - ((By - Ay) * (Dx - Cx))
if d = 0 then exitfunction 0
r = n / d
s = ( ((Ay-Cy)*(Bx-Ax))-((Ax-Cx)*(By-Ay)) ) / d
if r <= 0 then exitfunction 0
if r >= 1 then exitfunction 0
if s <= 0 then exitfunction 0
if s >= 1 then exitfunction 0
endfunction 1
function near(a#,b#)
temp#=1
if a#+temp#>b# and a#-temp#<b# or b#+temp#>a# and b#-temp#<a# then exitfunction 1
endfunction 0
function DrawLines()
`Verts
ink rgb(255,255,255)
for c=1 to array count(Verts(0))
`text Verts(c).X,Verts(c).Y,str$(c)
next c
`Connection
ink rgb(100,100,100)
for c=1 to array count(Connections(0))
line Verts(Connections(c).N1).X,Verts(Connections(c).N1).Y,Verts(Connections(c).N2).X,Verts(Connections(c).N2).Y
text (Verts(Connections(c).N1).X+Verts(Connections(c).N2).X)/2,(Verts(Connections(c).N1).Y+Verts(Connections(c).N2).Y)/2,str$(Connections(c).Distance)
next c
`Draw lines
ink rgb(255,0,0),0
for c=1 to array count(Lines(0))
line Verts(Lines(c).V1).X,Verts(Lines(c).V1).Y,Verts(Lines(c).V2).X,Verts(Lines(c).V2).Y
next c
endfunction
It's similar to A*, but instead of a grid it uses the corners of each obstactle as nodes. The unit moves from corner to corner to get where it's going - after all, that's the fastest way. (It's also the fastest I've had processing-wise - less than 0.5 ms for anything you can draw on this demo.)
It has a few glitches (for example, the unit will walk straight through anything more complex than triangles and squares), but hopefully I'll be working those out soon.
Questions, comments, and advice would be great (that's why I posted it
).
