Hi there, i wrote this A* like pathfinding system recently and it features a simple system that reduces the amount of waypoints by removing unnecessary ones. its pretty fast and has a modifier that defines how fast or slow (unnaccurate vs accurate) the function will run. the demo needs a2plugin and maybe matrix plugin. it works with very big and convoluted maps assuming you dont have the detail setting too low (lower number = more accurate )
sync on : sync rate 60
a2setblendmode 2,2,1 : hide mouse : a2setlineaa 0
global density# = 16.0
a = screen width()/density# : b = screen height()/density#
dim n(a,b) as UDTnode
dim open(10000) as UDTastar
dim path(10000) as UDTastar
gosub _chaos:
dd# = 1.5
do
mx# = mousex() : my# = mousey()
mi = (mx#+density#/2)/density# : mj =(my#+density#/2)/density# : md# = boxdist(targeti,targetj,mi,mj)
text mx#+density#,my#+denisty#,str$(int(open(n(mi,mj).n).cost#*10))
for i = 0 to a : for j = 0 to b
a2line (i+0.5)*density#,(j+0.5)*density#,(i+0.5)*density#,(j-0.5)*density#,rgb(30,60,160)
a2line (i+0.5)*density#,(j+0.5)*density#,(i-0.5)*density#,(j+0.5)*density#,rgb(30,60,160)
if n(i,j).w = 0 then a2fillbox (i+0.5)*density#-1,(j+0.5)*density#-1,(i-0.5)*density#+2,(j-0.5)*density#+2,rgb(7,15+15*n(i,j).v#,40+40*n(i,j).v#)
if n(i,j).w = 1 then a2fillbox (i+0.5)*density#-1,(j+0.5)*density#-1,(i-0.5)*density#+2,(j-0.5)*density#+2,rgb(80,30,15)
if i = mi and j = mj
if mouseclick() = 1 then starti = i : startj = j : n(i,j).w = 0 : done = 0
if mouseclick() = 2 then targeti = i : targetj = j : n(i,j).w = 0 : done = 0
a2fillbox (i+0.5)*density#-1,(j+0.5)*density#-1,(i-0.5)*density#+2,(j-0.5)*density#+2,rgb(30,30,30)
endif
if i = starti and j = startj then a2fillbox (i+0.5)*density#-1,(j+0.5)*density#-1,(i-0.5)*density#+2,(j-0.5)*density#+2,rgb(100,200,30)
if i = targeti and j = targetj then a2fillbox (i+0.5)*density#-1,(j+0.5)*density#-1,(i-0.5)*density#+2,(j-0.5)*density#+2,rgb(200,100,30)
NEXT : next
if starti > 0 and targeti > 0 and done = 0
k = ASTAR(a,b,targeti,targetj,starti,startj,dd#,10000)
done = 1
ENDIF
for i = 1 to k
a2line path(i-1).i*density#,path(i-1).j*density#,path(i).i*density#,path(i).j*density# ,rgb(255,0,0)
v# = sqrt((path(i).i-path(i-1).i)^2+(path(i).j-path(i-1).j)^2)*0.25
a2line path(i).i*density#+(path(i).j-path(i-1).j)/v#,path(i).j*density#-(path(i).i-path(i-1).i)/v#,path(i).i*density#-(path(i).j-path(i-1).j)/v#,path(i).j*density#+(path(i).i-path(i-1).i)/v#,rgb(255,0,0)
NEXT
print k
dd# = dd#+mousemovez()/1800.0
print dd#
sync
cls
LOOP
function ASTAR(grid_width,grid_height,targeti,targetj,starti,startj,detail#,maxloops)
t# = hitimer(10000)
for i = 0 to grid_width : for j = 0 to grid_height
n(i,j).closed = 0 : n(i,j).open = 0
NEXT : next
for i = 0 to 1000 : open(i).closed = 0 : open(i).i = 0 : open(i).j = 0 : open(i).cost# = 0 : open(i).dist# = 0 : next
si = starti : sj = startj : n(si,sj).closed = 1
repeat
mincost# = 1000000000
_start:
for i = si-1 to si+1 : for j = sj-1 to sj+1
if n(i,j).w = 0 and n(i,j).closed = 0 and n(i,j).open = 0
if abs(i-si)+abs(j-sj) = 2 then cost# = 1.415 else cost# = 1
cost# = cost#
open(n).i = i : open(n).j = j : open(n).dist# = boxdist(targeti,targetj,i,j)*detail#
open(n).cost# = scost#+cost# : n(i,j).p_i = si : n(i,j).p_j = sj : n(i,j).n = n
n(i,j).open = 1 : inc n
else
if n(i,j).open = 1
tn = n(i,j).n
if abs(i-si)+abs(j-sj) = 2 then cost# = 1.415 else cost# = 1
tcost# = open(tn).cost#+cost#
if scost#+cost# < open(tn).cost#
n(open(tn).i,open(tn).j).p_i = si : n(open(tn).i,open(tn).j).p_j = sj : open(tn).cost# = scost#+cost# : goto _start:
endif
if tcost# < scost#
n(si,sj).p_i = i : n(si,sj).p_j = j : scost# = tcost# : goto _start:
endif
endif
endif
NEXT : next
for i = 0 to n-1
if open(i).dist#+open(i).cost# < mincost# and open(i).closed = 0 then mini = i : mincost# = open(i).dist#+open(i).cost#
NEXT
si = open(mini).i : sj = open(mini).j : open(mini).closed = 1 : scost# = open(mini).cost# : n(si,sj).closed = 1
if si = targeti and sj = targetj
path(k).i = si : path(k).j = sj
repeat
opathvi = pathvi : opathvj = pathvj : inc k
path(k).i = n(path(k-1).i,path(k-1).j).p_i : path(k).j = n(path(k-1).i,path(k-1).j).p_j
if path(k).i = starti and path(k).j = startj then done = 1
pathvi = path(k).i-path(k-1).i : pathvj = path(k).j-path(k-1).j
if pathvi = opathvi and pathvj = opathvj then dec k : path(k).i = path(k+1).i : path(k).j = path(k+1).j
if abs(pathvi)+abs(pathvj) = 2 then cost# = 1.415 else cost# = 1
inc pathcost#,cost#
until done = 1
endif
inc loops
until done = 1 or loops > maxloops
for i = 0 to n
a2line open(i).i*density#,open(i).j*density#,n(open(i).i,open(i).j).p_i*density#,n(open(i).i,open(i).j).p_j*density#,rgb(255,255,255),rgb(0,0,0)
NEXT
lapse# = (hitimer(10000)-t#)/10.0
text 0,100,"cost:"+str$(pathcost#)
text 0,115,"n:"+str$(n)+" time:"+str$(lapse#)
ENDFUNCTION k
_chaos:
for i = 1 to a-1 : for j = 1 to b-1
if i = 1 or j = 1 or i = a-1 or j = b-1 then n(i,j).w = 1
if random() < 0.06
for m = i-1 to i+1 : for n = j-1 to j+1
n(m,n).w = 1
next : next
endif
n(i,j).v# = (sin(i)*cos(j*i)+1)/2.0
next : next
return
type UDTastar
i : j
cost# : dist#
closed
endtype
type UDTnode
v# ` velocity percentage
w ` wall 1/0
p_i : p_j `parent
closed : open : n
endtype
function boxdist(x1#,y1#,x2#,y2#)
dx# = abs(x1#-x2#) : dy# = abs(y1#-y2#)
d# = abs(dx#-dy#)+1.415*min(dx#,dy#)
ENDFUNCTION d#
function squaredist(x1#,y1#,x2#,y2#)
d# = (x1#-x2#)^2+(y1#-y2#)^2
ENDFUNCTION d#
real A-star is probably faster and more accurate but this is what i came up with (based on previous knowledge of A-star)
[edit]
improved the code substantially, it now reports the true fastest route very often and quite quickly. The grid in the image is a 160x120 grid and it has very unusual and quite A* unfriendly geometry. the path took 2.2ms to find and it is the fastest possible one in that grid. suboptimal paths (2% slower) can be found at 1.8ms. the path spans a length of 206 units (diagonals count as 1.415) while it only consists of 66 waypoints.
