pathfinding demo - GameCreators Forum

Author

Message

Daemon

18

Years of Service

User Offline

Joined: 16th Dec 2005

Location: Everywhere

Posted: 28th Oct 2006 01:09

Link

Yes, I know people have written path finding functions. I tried to make one myself before here.
I have managed to fit pathfinding into 20 lines and it is capable of multiple paths at once. Change the "width" and "height" variables to change the width and height of the world.

Controls:
Left-click: Draw walls
Right-click: Draw beginning/end point
Enter(once drawn even number of points): begin to path find.

It will take a second to find the paths, especially with large worlds and many paths.

Also, don't make impossible situations. It doesn't check for that, so you will be stuck in a loop.

Compressed-

randomize timer() : sync on : sync rate 0 : autocam off : width=100 : height=100 : depth=32 : maxpoints=20
type node
g as integer : h as integer : pdx as integer : pdy as integer : state as integer
endtype
global dim blocks(maxpoints/2,width,height) as node
type position
x as integer : y as integer
endtype
dim pos(maxpoints,2) as position : make memblock 1,width*height*depth*4+12 : write memblock dword 1,0,width : write memblock dword 1,4,height : write memblock dword 1,8,depth
for x=1 to width-2 : for y=1 to height-2 : write memblock dword 1,(y*width+x)*4+12,rgb(100,200,0) : next y : next x : for x=0 to width-1 : write memblock dword 1,x*4+12,rgb(20,100,40) : write memblock dword 1,((height-1)*width+x)*4+12,rgb(20,100,40) : next x : for y=0 to height-1 : write memblock dword 1,y*width*4+12,rgb(20,100,40) : write memblock dword 1,(y*width+width-1)*4+12,rgb(20,100,40) : next y : make image from memblock 1,1 : sprite 1,0,0,1 : size sprite 1,screen width(),screen height() : repeat : sync : mclick=mouseclick() : px=x : py=y : x=mousex()*(width+0.0)/screen width() : y=mousey()*(height+0.0)/screen height() : if mclick=1 : if clicking=1
if px<>x : m#=(py-y+0.0)/(px-x+0.0) : if px>x : lowx=x : highx=px : else : lowx=px : highx=x : endif : for ix=lowx to highx : iy=m#*(ix-x)+y : write memblock dword 1,(iy*width+ix)*4+12,rgb(20,100,40) : next ix : else : if py<>y : m#=(px-x+0.0)/(py-y+0.0) : if py>y : lowy=y : highy=py : else : lowy=py : highy=y : endif : for iy=lowy to highy : ix=m#*(iy-y)+x
write memblock dword 1,(iy*width+ix)*4+12,rgb(20,100,40) : next ix : endif : endif : else : write memblock dword 1,(y*width+x)*4+12,rgb(20,100,40) : endif : clicking=1 : endif : if mclick=2 and clicking=0 : if checks/2=checks/2.0 : write memblock dword 1,(y*width+x)*4+12,rgb(0,0,100) : inc p : pos(p,1).x=x : pos(p,1).y=y : else : write memblock dword 1,(y*width+x)*4+12,rgb(0,255,0) : pos(p,2).x=x : pos(p,2).y=y : endif : inc checks : clicking=2 : endif : if mclick=0 : clicking=0
endif : make image from memblock 1,1 : if escapekey()=1 : end : endif : until returnkey()=1 and checks=>2 and checks/2.0=checks/2 : for x=0 to width-1 : for y=0 to height-1 : for i=1 to p : if memblock dword (1,(y*width+x)*4+12)=rgb(20,100,40) : blocks(i,x,y).state=1 : else : blocks(i,x,y).state=-1 : endif : next i : next y : next x : for i=1 to p : find_path(i,pos(i,1).x,pos(i,1).y,pos(i,2).x,pos(i,2).y,width,height) : next i : for x=0 to width-1 : for y=0 to height-1 : for i=1 to p : if blocks(i,x,y).state=2 : write memblock dword 1,(y*width+x)*4+12,rgb(0,255,255)
endif : next i : next y : next x : make image from memblock 1,1 : sync : wait key : end
function find_path(pathnum,startx,starty,endx,endy,width,height)
blocks(pathnum,startx,starty).state=0 : blocks(pathnum,startx,starty).g=0 : blocks(pathnum,startx,starty).h=(abs(startx-endx)+abs(starty-endy))*10 : blocks(pathnum,startx,starty).pdx=0 : blocks(pathnum,startx,starty).pdy=0 : repeat : lowestf=999999 : fx=0 : fy=0 : for x=1 to width : for y=1 to height : if blocks(pathnum,x,y).state=0 : if blocks(pathnum,x,y).g+blocks(pathnum,x,y).h<lowestf : lowestf=blocks(pathnum,x,y).g+blocks(pathnum,x,y).h : fx=x : fy=y
endif : endif : next y : next x : for a=-1 to 1 : for b=-1 to 1 : if abs(a)+abs(b)=0 : diagonal=2 : endif : if abs(a)+abs(b)=1 : diagonal=0 : mv=10 : endif : if abs(a)+abs(b)=2 : diagonal=1 : mv=14 : endif : possible=1 : if fx+a>-1 and fy+b>-1 and fx+a<width and fy+b<height : if (blocks(pathnum,fx+a,fy+b).state=1)+(blocks(pathnum,fx+a,fy+b).state=0 and blocks(pathnum,fx+a,fy+b).g<blocks(pathnum,fx,fy).g+mv)+(diagonal=1 and blocks(pathnum,fx+a,fy).state=1)+(diagonal=1 and blocks(pathnum,fx+a,fy).state=1 or blocks(pathnum,fx,fy+b).state=1)=0 : blocks(pathnum,fx+a,fy+b).state=0 : blocks(pathnum,fx+a,fy+b).h=(abs(fx+a-endx)+abs(fy+b-endy))*10
blocks(pathnum,fx+a,fy+b).g=blocks(pathnum,fx,fy).g+mv : blocks(pathnum,fx+a,fy+b).pdx=a : blocks(pathnum,fx+a,fy+b).pdy=b : endif : endif : next b : next a : blocks(pathnum,fx,fy).state=1 : until blocks(pathnum,endx,endy).state=0 : nx=endx : ny=endy : repeat : blocks(pathnum,nx,ny).state=2 : nx=nx-blocks(pathnum,nx,ny).pdx : ny=ny-blocks(pathnum,nx,ny).pdy : until nx=startx and ny=starty
endfunction

+ Code Snippet

randomize timer() : sync on : sync rate 0 : autocam off : width=100 : height=100 : depth=32 : maxpoints=20
type node
g as integer : h as integer : pdx as integer : pdy as integer : state as integer
endtype
global dim blocks(maxpoints/2,width,height) as node
type position
x as integer : y as integer
endtype
dim pos(maxpoints,2) as position : make memblock 1,width*height*depth*4+12 : write memblock dword 1,0,width : write memblock dword 1,4,height : write memblock dword 1,8,depth
for x=1 to width-2 : for y=1 to height-2 : write memblock dword 1,(y*width+x)*4+12,rgb(100,200,0) : next y : next x : for x=0 to width-1 : write memblock dword 1,x*4+12,rgb(20,100,40) : write memblock dword 1,((height-1)*width+x)*4+12,rgb(20,100,40) : next x : for y=0 to height-1 : write memblock dword 1,y*width*4+12,rgb(20,100,40) : write memblock dword 1,(y*width+width-1)*4+12,rgb(20,100,40) : next y : make image from memblock 1,1 : sprite 1,0,0,1 : size sprite 1,screen width(),screen height() : repeat : sync : mclick=mouseclick() : px=x : py=y : x=mousex()*(width+0.0)/screen width() : y=mousey()*(height+0.0)/screen height() : if mclick=1 : if clicking=1
if px<>x : m#=(py-y+0.0)/(px-x+0.0) : if px>x : lowx=x : highx=px : else : lowx=px : highx=x : endif : for ix=lowx to highx : iy=m#*(ix-x)+y : write memblock dword 1,(iy*width+ix)*4+12,rgb(20,100,40) : next ix : else : if py<>y : m#=(px-x+0.0)/(py-y+0.0) : if py>y : lowy=y : highy=py : else : lowy=py : highy=y : endif : for iy=lowy to highy : ix=m#*(iy-y)+x
write memblock dword 1,(iy*width+ix)*4+12,rgb(20,100,40) : next ix : endif : endif : else : write memblock dword 1,(y*width+x)*4+12,rgb(20,100,40) : endif : clicking=1 : endif : if mclick=2 and clicking=0 : if checks/2=checks/2.0 : write memblock dword 1,(y*width+x)*4+12,rgb(0,0,100) : inc p : pos(p,1).x=x : pos(p,1).y=y : else : write memblock dword 1,(y*width+x)*4+12,rgb(0,255,0) : pos(p,2).x=x : pos(p,2).y=y : endif : inc checks : clicking=2 : endif : if mclick=0 : clicking=0
endif : make image from memblock 1,1 : if escapekey()=1 : end : endif : until returnkey()=1 and checks=>2 and checks/2.0=checks/2 : for x=0 to width-1 : for y=0 to height-1 : for i=1 to p : if memblock dword (1,(y*width+x)*4+12)=rgb(20,100,40) : blocks(i,x,y).state=1 : else : blocks(i,x,y).state=-1 : endif : next i : next y : next x : for i=1 to p : find_path(i,pos(i,1).x,pos(i,1).y,pos(i,2).x,pos(i,2).y,width,height) : next i : for x=0 to width-1 : for y=0 to height-1 : for i=1 to p : if blocks(i,x,y).state=2 : write memblock dword 1,(y*width+x)*4+12,rgb(0,255,255)
endif : next i : next y : next x : make image from memblock 1,1 : sync : wait key : end
function find_path(pathnum,startx,starty,endx,endy,width,height)
blocks(pathnum,startx,starty).state=0 : blocks(pathnum,startx,starty).g=0 : blocks(pathnum,startx,starty).h=(abs(startx-endx)+abs(starty-endy))*10 : blocks(pathnum,startx,starty).pdx=0 : blocks(pathnum,startx,starty).pdy=0 : repeat : lowestf=999999 : fx=0 : fy=0 : for x=1 to width : for y=1 to height : if blocks(pathnum,x,y).state=0 : if blocks(pathnum,x,y).g+blocks(pathnum,x,y).h<lowestf : lowestf=blocks(pathnum,x,y).g+blocks(pathnum,x,y).h : fx=x : fy=y
endif : endif : next y : next x : for a=-1 to 1 : for b=-1 to 1 : if abs(a)+abs(b)=0 : diagonal=2 : endif : if abs(a)+abs(b)=1 : diagonal=0 : mv=10 : endif : if abs(a)+abs(b)=2 : diagonal=1 : mv=14 : endif : possible=1 : if fx+a>-1 and fy+b>-1 and fx+a<width and fy+b<height : if (blocks(pathnum,fx+a,fy+b).state=1)+(blocks(pathnum,fx+a,fy+b).state=0 and blocks(pathnum,fx+a,fy+b).g<blocks(pathnum,fx,fy).g+mv)+(diagonal=1 and blocks(pathnum,fx+a,fy).state=1)+(diagonal=1 and blocks(pathnum,fx+a,fy).state=1 or blocks(pathnum,fx,fy+b).state=1)=0 : blocks(pathnum,fx+a,fy+b).state=0 : blocks(pathnum,fx+a,fy+b).h=(abs(fx+a-endx)+abs(fy+b-endy))*10
blocks(pathnum,fx+a,fy+b).g=blocks(pathnum,fx,fy).g+mv : blocks(pathnum,fx+a,fy+b).pdx=a : blocks(pathnum,fx+a,fy+b).pdy=b : endif : endif : next b : next a : blocks(pathnum,fx,fy).state=1 : until blocks(pathnum,endx,endy).state=0 : nx=endx : ny=endy : repeat : blocks(pathnum,nx,ny).state=2 : nx=nx-blocks(pathnum,nx,ny).pdx : ny=ny-blocks(pathnum,nx,ny).pdy : until nx=startx and ny=starty
endfunction

Uncompressed [not as good colo(u)rs]-

`Basic Setup
randomize timer()
sync on
sync rate 0
autocam off

`Variables
width=200
height=200
depth=32
maxpoints=20

`Setup for path finding
type node
   g as integer
   h as integer
   pdx as integer
   pdy as integer
   state as integer
endtype
global dim blocks(maxpoints/2,width,height) as node

`Setup for storing positions
type position
   x as integer
   y as integer
endtype
dim pos(maxpoints,2) as position

`Setup for drawing
make memblock 1,width*height*depth*4+12
write memblock dword 1,0,width
write memblock dword 1,4,height
write memblock dword 1,8,depth
for x=1 to width-2
   for y=1 to height-2
      write memblock dword 1,(y*width+x)*4+12,rgb(255,255,255)
   next y
next x
for x=0 to width-1
   write memblock dword 1,x*4+12,rgb(0,0,0)
   write memblock dword 1,((height-1)*width+x)*4+12,rgb(0,0,0)
next x
for y=0 to height-1
   write memblock dword 1,y*width*4+12,rgb(0,0,0)
   write memblock dword 1,(y*width+width-1)*4+12,rgb(0,0,0)
next y
make image from memblock 1,1
sprite 1,0,0,1
size sprite 1,screen width(),screen height()

`Draw
repeat
   sync
   mclick=mouseclick()
   px=x
   py=y
   x=mousex()*(width+0.0)/screen width()
   y=mousey()*(height+0.0)/screen height()
   if mclick=1
      if clicking=1
         if px<>x
            m#=(py-y+0.0)/(px-x+0.0)
            if px>x
               lowx=x
               highx=px
            else
               lowx=px
               highx=x
            endif
            for ix=lowx to highx
               iy=m#*(ix-x)+y
               write memblock dword 1,(iy*width+ix)*4+12,rgb(0,0,0)
            next ix
         else
            if py<>y
               m#=(px-x+0.0)/(py-y+0.0)
               if py>y
                  lowy=y
                  highy=py
               else
                  lowy=py
                  highy=y
               endif
               for iy=lowy to highy
                  ix=m#*(iy-y)+x
                  write memblock dword 1,(iy*width+ix)*4+12,rgb(0,0,0)
               next ix
               endif
         endif
      else
         write memblock dword 1,(y*width+x)*4+12,rgb(0,0,0)
      endif
      clicking=1
   endif
   if mclick=2 and clicking=0
      if checks/2=checks/2.0
         write memblock dword 1,(y*width+x)*4+12,rgb(255,0,0)
         inc p
         pos(p,1).x=x
         pos(p,1).y=y
      else
         write memblock dword 1,(y*width+x)*4+12,rgb(0,255,0)
         pos(p,2).x=x
         pos(p,2).y=y
      endif
      inc checks
      clicking=2
   endif
   if mclick=0
      clicking=0
   endif
   make image from memblock 1,1
   if escapekey()=1
      end
   endif
until returnkey()=1 and checks=>2 and checks/2.0=checks/2

`Define world for path finding
for x=0 to width-1
   for y=0 to height-1
      for i=1 to p
         if memblock dword (1,(y*width+x)*4+12)=rgb(0,0,0)
            blocks(i,x,y).state=1
         else
            blocks(i,x,y).state=-1
         endif
      next i
   next y
next x

`Find path
for i=1 to p
   find_path(i,pos(i,1).x,pos(i,1).y,pos(i,2).x,pos(i,2).y,width,height)
next i
for x=0 to width-1
   for y=0 to height-1
      for i=1 to p
         if blocks(i,x,y).state=2
            write memblock dword 1,(y*width+x)*4+12,rgb(0,255,255)
         endif
      next i
   next y
next x
make image from memblock 1,1
sync
wait key
end
function find_path(pathnum,startx,starty,endx,endy,width,height)
blocks(pathnum,startx,starty).state=0
blocks(pathnum,startx,starty).g=0
blocks(pathnum,startx,starty).h=(abs(startx-endx)+abs(starty-endy))*10
blocks(pathnum,startx,starty).pdx=0
blocks(pathnum,startx,starty).pdy=0
repeat
   lowestf=999999
   fx=0
   fy=0
   for x=1 to width
      for y=1 to height
         if blocks(pathnum,x,y).state=0
            if blocks(pathnum,x,y).g+blocks(pathnum,x,y).h<lowestf
               lowestf=blocks(pathnum,x,y).g+blocks(pathnum,x,y).h
               fx=x
               fy=y
            endif
         endif
      next y
   next x
   for a=-1 to 1
      for b=-1 to 1
         n=abs(a)+abs(b)
         select n
            case 0
               diagonal=2
            endcase
            case 1
               diagonal=0
               mv=10
            endcase
            case 2
               diagonal=1
               mv=14
            endcase
         endselect
         possible=1
         if fx+a>-1 and fy+b>-1 and fx+a<width and fy+b<height
            if (blocks(pathnum,fx+a,fy+b).state=1)+(blocks(pathnum,fx+a,fy+b).state=0 and blocks(pathnum,fx+a,fy+b).g<blocks(pathnum,fx,fy).g+mv)+(diagonal=1 and blocks(pathnum,fx+a,fy).state=1)+(diagonal=1 and blocks(pathnum,fx+a,fy).state=1 or blocks(pathnum,fx,fy+b).state=1)=0
               blocks(pathnum,fx+a,fy+b).state=0
               blocks(pathnum,fx+a,fy+b).h=(abs(fx+a-endx)+abs(fy+b-endy))*10
               blocks(pathnum,fx+a,fy+b).g=blocks(pathnum,fx,fy).g+mv
               blocks(pathnum,fx+a,fy+b).pdx=a
               blocks(pathnum,fx+a,fy+b).pdy=b
            endif
         endif
      next b
   next a
   blocks(pathnum,fx,fy).state=1
   until blocks(pathnum,endx,endy).state=0
   nx=endx
   ny=endy
   repeat
   blocks(pathnum,nx,ny).state=2
   nx=nx-blocks(pathnum,nx,ny).pdx
   ny=ny-blocks(pathnum,nx,ny).pdy
until nx=startx and ny=starty
endfunction

+ Code Snippet

`Basic Setup
randomize timer()
sync on
sync rate 0
autocam off

`Variables
width=200
height=200
depth=32
maxpoints=20

`Setup for path finding
type node
   g as integer
   h as integer
   pdx as integer
   pdy as integer
   state as integer
endtype
global dim blocks(maxpoints/2,width,height) as node

`Setup for storing positions
type position
   x as integer
   y as integer
endtype
dim pos(maxpoints,2) as position

`Setup for drawing
make memblock 1,width*height*depth*4+12
write memblock dword 1,0,width
write memblock dword 1,4,height
write memblock dword 1,8,depth
for x=1 to width-2
   for y=1 to height-2
      write memblock dword 1,(y*width+x)*4+12,rgb(255,255,255)
   next y
next x
for x=0 to width-1
   write memblock dword 1,x*4+12,rgb(0,0,0)
   write memblock dword 1,((height-1)*width+x)*4+12,rgb(0,0,0)
next x
for y=0 to height-1
   write memblock dword 1,y*width*4+12,rgb(0,0,0)
   write memblock dword 1,(y*width+width-1)*4+12,rgb(0,0,0)
next y
make image from memblock 1,1
sprite 1,0,0,1
size sprite 1,screen width(),screen height()

`Draw
repeat
   sync
   mclick=mouseclick()
   px=x
   py=y
   x=mousex()*(width+0.0)/screen width()
   y=mousey()*(height+0.0)/screen height()
   if mclick=1
      if clicking=1
         if px<>x
            m#=(py-y+0.0)/(px-x+0.0)
            if px>x
               lowx=x
               highx=px
            else
               lowx=px
               highx=x
            endif
            for ix=lowx to highx
               iy=m#*(ix-x)+y
               write memblock dword 1,(iy*width+ix)*4+12,rgb(0,0,0)
            next ix
         else
            if py<>y
               m#=(px-x+0.0)/(py-y+0.0)
               if py>y
                  lowy=y
                  highy=py
               else
                  lowy=py
                  highy=y
               endif
               for iy=lowy to highy
                  ix=m#*(iy-y)+x
                  write memblock dword 1,(iy*width+ix)*4+12,rgb(0,0,0)
               next ix
               endif
         endif
      else
         write memblock dword 1,(y*width+x)*4+12,rgb(0,0,0)
      endif
      clicking=1
   endif
   if mclick=2 and clicking=0
      if checks/2=checks/2.0
         write memblock dword 1,(y*width+x)*4+12,rgb(255,0,0)
         inc p
         pos(p,1).x=x
         pos(p,1).y=y
      else
         write memblock dword 1,(y*width+x)*4+12,rgb(0,255,0)
         pos(p,2).x=x
         pos(p,2).y=y
      endif
      inc checks
      clicking=2
   endif
   if mclick=0
      clicking=0
   endif
   make image from memblock 1,1
   if escapekey()=1
      end
   endif
until returnkey()=1 and checks=>2 and checks/2.0=checks/2

`Define world for path finding
for x=0 to width-1
   for y=0 to height-1
      for i=1 to p
         if memblock dword (1,(y*width+x)*4+12)=rgb(0,0,0)
            blocks(i,x,y).state=1
         else
            blocks(i,x,y).state=-1
         endif
      next i
   next y
next x

`Find path
for i=1 to p
   find_path(i,pos(i,1).x,pos(i,1).y,pos(i,2).x,pos(i,2).y,width,height)
next i
for x=0 to width-1
   for y=0 to height-1
      for i=1 to p
         if blocks(i,x,y).state=2
            write memblock dword 1,(y*width+x)*4+12,rgb(0,255,255)
         endif
      next i
   next y
next x
make image from memblock 1,1
sync
wait key
end
function find_path(pathnum,startx,starty,endx,endy,width,height)
blocks(pathnum,startx,starty).state=0
blocks(pathnum,startx,starty).g=0
blocks(pathnum,startx,starty).h=(abs(startx-endx)+abs(starty-endy))*10
blocks(pathnum,startx,starty).pdx=0
blocks(pathnum,startx,starty).pdy=0
repeat
   lowestf=999999
   fx=0
   fy=0
   for x=1 to width
      for y=1 to height
         if blocks(pathnum,x,y).state=0
            if blocks(pathnum,x,y).g+blocks(pathnum,x,y).h<lowestf
               lowestf=blocks(pathnum,x,y).g+blocks(pathnum,x,y).h
               fx=x
               fy=y
            endif
         endif
      next y
   next x
   for a=-1 to 1
      for b=-1 to 1
         n=abs(a)+abs(b)
         select n
            case 0
               diagonal=2
            endcase
            case 1
               diagonal=0
               mv=10
            endcase
            case 2
               diagonal=1
               mv=14
            endcase
         endselect
         possible=1
         if fx+a>-1 and fy+b>-1 and fx+a<width and fy+b<height
            if (blocks(pathnum,fx+a,fy+b).state=1)+(blocks(pathnum,fx+a,fy+b).state=0 and blocks(pathnum,fx+a,fy+b).g<blocks(pathnum,fx,fy).g+mv)+(diagonal=1 and blocks(pathnum,fx+a,fy).state=1)+(diagonal=1 and blocks(pathnum,fx+a,fy).state=1 or blocks(pathnum,fx,fy+b).state=1)=0
               blocks(pathnum,fx+a,fy+b).state=0
               blocks(pathnum,fx+a,fy+b).h=(abs(fx+a-endx)+abs(fy+b-endy))*10
               blocks(pathnum,fx+a,fy+b).g=blocks(pathnum,fx,fy).g+mv
               blocks(pathnum,fx+a,fy+b).pdx=a
               blocks(pathnum,fx+a,fy+b).pdy=b
            endif
         endif
      next b
   next a
   blocks(pathnum,fx,fy).state=1
   until blocks(pathnum,endx,endy).state=0
   nx=endx
   ny=endy
   repeat
   blocks(pathnum,nx,ny).state=2
   nx=nx-blocks(pathnum,nx,ny).pdx
   ny=ny-blocks(pathnum,nx,ny).pdy
until nx=startx and ny=starty
endfunction

Insanity is just a state of mind.

Back to top

Profile PM Website

sadsack

20

Years of Service

User Offline

Joined: 27th Nov 2003

Location: here

Posted: 28th Oct 2006 01:27

Link

Hi Daemon,
I like your code, it is slow, Do you mind is I email you if I find a part of it that I don't understand. I would like to make it faster.
renny

Back to top

Profile PM Email Website

Daemon

18

Years of Service

User Offline

Joined: 16th Dec 2005

Location: Everywhere

Posted: 28th Oct 2006 02:27 Edited at: 29th Oct 2006 05:21

Link

It would be great if you could make it faster.

If you don't understand something in it email me at:
Jake(I hate spam)Stoth(a with circle around it)yahoo(dot)hotmail(dot)com

Take out (I hate spam), put @ for (a with circle around it) and put a . for (dot)

Edit: I have updated my code, but it doesn't fit into 20 lines any more. One difference is that each path has it's own color. Also, if you hit space when drawing the world a maze will be generated, that way you don't have to take the time to draw out really complex test worlds. The width and height should both be odd numbers if you want to generate a maze.

O, and I did change how the a* function works a little.

`Basic Setup
randomize timer()
sync on
sync rate 0
autocam off

`Variables
width=101
height=101
depth=32
maxpoints=20

`Setup for path finding
type node
   g as integer
   h as integer
   pdx as integer
   pdy as integer
   state as integer
endtype
global dim blocks(maxpoints/2,width,height) as node

`Setup for storing positions
type position
   x as integer
   y as integer
endtype
dim pos(maxpoints,2) as position

`Setup for drawing
make memblock 1,width*height*depth*4+12
write memblock dword 1,0,width
write memblock dword 1,4,height
write memblock dword 1,8,depth
for x=1 to width-2
   for y=1 to height-2
      write memblock dword 1,(y*width+x)*4+12,rgb(255,255,255)
   next y
next x
for x=0 to width-1
   write memblock dword 1,x*4+12,rgb(0,0,0)
   write memblock dword 1,((height-1)*width+x)*4+12,rgb(0,0,0)
next x
for y=0 to height-1
   write memblock dword 1,y*width*4+12,rgb(0,0,0)
   write memblock dword 1,(y*width+width-1)*4+12,rgb(0,0,0)
next y
make image from memblock 1,1
sprite 1,0,0,1
size sprite 1,screen width(),screen height()

`Draw
repeat
   sync
   mclick=mouseclick()
   px=x
   py=y
   x=mousex()*(width+0.0)/screen width()
   y=mousey()*(height+0.0)/screen height()
   if mclick=1
      if clicking=1
         if (py-y+0.0)/(px-x+0.0)=<1
            m#=(py-y+0.0)/(px-x+0.0)
            if px>x
               lowx=x
               highx=px
            else
               lowx=px
               highx=x
            endif
            for ix=lowx to highx
               iy=m#*(ix-x)+y
               write memblock dword 1,(iy*width+ix)*4+12,rgb(0,0,0)
            next ix
         else
            if py<>y
               m#=(px-x+0.0)/(py-y+0.0)
               if py>y
                  lowy=y
                  highy=py
               else
                  lowy=py
                  highy=y
               endif
               for iy=lowy to highy
                  ix=m#*(iy-y)+x
                  write memblock dword 1,(iy*width+ix)*4+12,rgb(0,0,0)
               next ix
               endif
         endif
      else
         write memblock dword 1,(y*width+x)*4+12,rgb(0,0,0)
      endif
      clicking=1
   endif
   if mclick=2 and clicking=0
      if checks/2=checks/2.0
         write memblock dword 1,(y*width+x)*4+12,rgb(255,0,0)
         inc p
         pos(p,1).x=x
         pos(p,1).y=y
      else
         write memblock dword 1,(y*width+x)*4+12,rgb(0,255,0)
         pos(p,2).x=x
         pos(p,2).y=y
      endif
      inc checks
      clicking=2
   endif
   if mclick=0
      clicking=0
   endif
   if spacekey()=1 and mazemade=0
      create_maze(width,height)
      mazemade=1
   endif
   make image from memblock 1,1
   if escapekey()=1
      end
   endif
until returnkey()=1 and checks=>2 and checks/2.0=checks/2

`Define world for path finding
for x=0 to width-1
   for y=0 to height-1
      if memblock dword (1,(y*width+x)*4+12)=rgb(0,0,0)
         blocks(0,x,y).state=1
      else
         blocks(0,x,y).state=-1
      endif
   next y
next x

`Find path
for i=1 to p
   find_path(i,pos(i,1).x,pos(i,1).y,pos(i,2).x,pos(i,2).y,width,height)
next i

`Draw path
color as dword
for i=1 to p
   color=rgb(rnd(255),rnd(255),rnd(255))
   for x=0 to width-1
      for y=0 to height-1
         if blocks(i,x,y).state=2
            write memblock dword 1,(y*width+x)*4+12,color
         endif
      next y
   next x
next i
make image from memblock 1,1
sync
wait key
end
function find_path(pathnum,startx,starty,endx,endy,width,height)
for x=1 to width
   for y=1 to width
      blocks(pathnum,x,y).state=blocks(0,x,y).state
   next y
next x
blocks(pathnum,startx,starty).state=0
blocks(pathnum,startx,starty).g=0
blocks(pathnum,startx,starty).h=(abs(startx-endx)+abs(starty-endy))*10
blocks(pathnum,startx,starty).pdx=0
blocks(pathnum,startx,starty).pdy=0
repeat
   lowestf=999999
   fx=0
   fy=0
   for x=1 to width
      for y=1 to height
         if blocks(pathnum,x,y).state=0
            if blocks(pathnum,x,y).g+blocks(pathnum,x,y).h<lowestf
               lowestf=blocks(pathnum,x,y).g+blocks(pathnum,x,y).h
               fx=x
               fy=y
            endif
         endif
      next y
   next x
   for a=-1 to 1
      for b=-1 to 1
         n=abs(a)+abs(b)
         diagonal=int(n/2)
         if n=1
            mv=10
         endif
         if n=2
            mv=14
         endif
         if fx+a>-1 and fy+b>-1 and fx+a<width and fy+b<height
            if (blocks(pathnum,fx+a,fy+b).state=1)+(blocks(pathnum,fx+a,fy+b).state=0 and blocks(pathnum,fx+a,fy+b).g<blocks(pathnum,fx,fy).g+mv)+(diagonal=1 and blocks(pathnum,fx+a,fy).state=1)+(diagonal=1 and blocks(pathnum,fx+a,fy).state=1 or blocks(pathnum,fx,fy+b).state=1)=0
               blocks(pathnum,fx+a,fy+b).state=0
               blocks(pathnum,fx+a,fy+b).h=(abs(fx+a-endx)+abs(fy+b-endy))*10
               blocks(pathnum,fx+a,fy+b).g=blocks(pathnum,fx,fy).g+mv
               blocks(pathnum,fx+a,fy+b).pdx=a
               blocks(pathnum,fx+a,fy+b).pdy=b
            endif
         endif
      next b
   next a
   blocks(pathnum,fx,fy).state=1
until blocks(pathnum,endx,endy).state=0
nx=endx
ny=endy
repeat
   blocks(pathnum,nx,ny).state=2
   nx=nx-blocks(pathnum,nx,ny).pdx
   ny=ny-blocks(pathnum,nx,ny).pdy
until nx=startx and ny=starty or escapekey()=1
endfunction

`For those with short attention spans
function create_maze(xtiles,ytiles)
max=(xtiles*ytiles)-((xtiles-2)*(ytiles-2)-((xtiles-3)/2)*(ytiles-3))+2
local dim maze(xtiles,ytiles) as boolean
for x=1 to xtiles
   maze(x,1)=1
   maze(x,ytiles)=1
next x
for y=1 to ytiles
   maze(1,y)=1
   maze(xtiles,y)=1
next y
counter=2*xtiles+2*ytiles-2
while counter<max and escapekey()=0
   x=rnd(xtiles-2)+1
   y=rnd(ytiles-2)+1
   if maze(x-1,y-1)=1 and maze(x-1,y)+maze(x,y-1)=0 or maze(x-1,y+1)=1 and maze(x-1,y)+maze(x,y+1)=0 or maze(x+1,y-1)=1 and maze(x+1,y)+maze(x,y-1)=0 or maze(x+1,y+1)=1 and maze(x+1,y)+maze(x,y+1)=0 or maze(x,y)=1 or x/2.0=x/2 and y/2.0=y/2 or maze(x-1,y)+maze(x+1,y)+maze(x,y-1)+maze(x,y+1)<>1
   else
      maze(x,y)=1
      inc counter
   endif
endwhile
for x=0 to xtiles-1
   for y=0 to ytiles-1
      if maze(x+1,y+1)=1
         write memblock dword 1,(y*xtiles+x)*4+12,rgb(0,0,0)
      endif
   next y
next x
undim maze(0)
endfunction

+ Code Snippet

`Basic Setup
randomize timer()
sync on
sync rate 0
autocam off

`Variables
width=101
height=101
depth=32
maxpoints=20

`Setup for path finding
type node
   g as integer
   h as integer
   pdx as integer
   pdy as integer
   state as integer
endtype
global dim blocks(maxpoints/2,width,height) as node

`Setup for storing positions
type position
   x as integer
   y as integer
endtype
dim pos(maxpoints,2) as position

`Setup for drawing
make memblock 1,width*height*depth*4+12
write memblock dword 1,0,width
write memblock dword 1,4,height
write memblock dword 1,8,depth
for x=1 to width-2
   for y=1 to height-2
      write memblock dword 1,(y*width+x)*4+12,rgb(255,255,255)
   next y
next x
for x=0 to width-1
   write memblock dword 1,x*4+12,rgb(0,0,0)
   write memblock dword 1,((height-1)*width+x)*4+12,rgb(0,0,0)
next x
for y=0 to height-1
   write memblock dword 1,y*width*4+12,rgb(0,0,0)
   write memblock dword 1,(y*width+width-1)*4+12,rgb(0,0,0)
next y
make image from memblock 1,1
sprite 1,0,0,1
size sprite 1,screen width(),screen height()

`Draw
repeat
   sync
   mclick=mouseclick()
   px=x
   py=y
   x=mousex()*(width+0.0)/screen width()
   y=mousey()*(height+0.0)/screen height()
   if mclick=1
      if clicking=1
         if (py-y+0.0)/(px-x+0.0)=<1
            m#=(py-y+0.0)/(px-x+0.0)
            if px>x
               lowx=x
               highx=px
            else
               lowx=px
               highx=x
            endif
            for ix=lowx to highx
               iy=m#*(ix-x)+y
               write memblock dword 1,(iy*width+ix)*4+12,rgb(0,0,0)
            next ix
         else
            if py<>y
               m#=(px-x+0.0)/(py-y+0.0)
               if py>y
                  lowy=y
                  highy=py
               else
                  lowy=py
                  highy=y
               endif
               for iy=lowy to highy
                  ix=m#*(iy-y)+x
                  write memblock dword 1,(iy*width+ix)*4+12,rgb(0,0,0)
               next ix
               endif
         endif
      else
         write memblock dword 1,(y*width+x)*4+12,rgb(0,0,0)
      endif
      clicking=1
   endif
   if mclick=2 and clicking=0
      if checks/2=checks/2.0
         write memblock dword 1,(y*width+x)*4+12,rgb(255,0,0)
         inc p
         pos(p,1).x=x
         pos(p,1).y=y
      else
         write memblock dword 1,(y*width+x)*4+12,rgb(0,255,0)
         pos(p,2).x=x
         pos(p,2).y=y
      endif
      inc checks
      clicking=2
   endif
   if mclick=0
      clicking=0
   endif
   if spacekey()=1 and mazemade=0
      create_maze(width,height)
      mazemade=1
   endif
   make image from memblock 1,1
   if escapekey()=1
      end
   endif
until returnkey()=1 and checks=>2 and checks/2.0=checks/2

`Define world for path finding
for x=0 to width-1
   for y=0 to height-1
      if memblock dword (1,(y*width+x)*4+12)=rgb(0,0,0)
         blocks(0,x,y).state=1
      else
         blocks(0,x,y).state=-1
      endif
   next y
next x

`Find path
for i=1 to p
   find_path(i,pos(i,1).x,pos(i,1).y,pos(i,2).x,pos(i,2).y,width,height)
next i

`Draw path
color as dword
for i=1 to p
   color=rgb(rnd(255),rnd(255),rnd(255))
   for x=0 to width-1
      for y=0 to height-1
         if blocks(i,x,y).state=2
            write memblock dword 1,(y*width+x)*4+12,color
         endif
      next y
   next x
next i
make image from memblock 1,1
sync
wait key
end
function find_path(pathnum,startx,starty,endx,endy,width,height)
for x=1 to width
   for y=1 to width
      blocks(pathnum,x,y).state=blocks(0,x,y).state
   next y
next x
blocks(pathnum,startx,starty).state=0
blocks(pathnum,startx,starty).g=0
blocks(pathnum,startx,starty).h=(abs(startx-endx)+abs(starty-endy))*10
blocks(pathnum,startx,starty).pdx=0
blocks(pathnum,startx,starty).pdy=0
repeat
   lowestf=999999
   fx=0
   fy=0
   for x=1 to width
      for y=1 to height
         if blocks(pathnum,x,y).state=0
            if blocks(pathnum,x,y).g+blocks(pathnum,x,y).h<lowestf
               lowestf=blocks(pathnum,x,y).g+blocks(pathnum,x,y).h
               fx=x
               fy=y
            endif
         endif
      next y
   next x
   for a=-1 to 1
      for b=-1 to 1
         n=abs(a)+abs(b)
         diagonal=int(n/2)
         if n=1
            mv=10
         endif
         if n=2
            mv=14
         endif
         if fx+a>-1 and fy+b>-1 and fx+a<width and fy+b<height
            if (blocks(pathnum,fx+a,fy+b).state=1)+(blocks(pathnum,fx+a,fy+b).state=0 and blocks(pathnum,fx+a,fy+b).g<blocks(pathnum,fx,fy).g+mv)+(diagonal=1 and blocks(pathnum,fx+a,fy).state=1)+(diagonal=1 and blocks(pathnum,fx+a,fy).state=1 or blocks(pathnum,fx,fy+b).state=1)=0
               blocks(pathnum,fx+a,fy+b).state=0
               blocks(pathnum,fx+a,fy+b).h=(abs(fx+a-endx)+abs(fy+b-endy))*10
               blocks(pathnum,fx+a,fy+b).g=blocks(pathnum,fx,fy).g+mv
               blocks(pathnum,fx+a,fy+b).pdx=a
               blocks(pathnum,fx+a,fy+b).pdy=b
            endif
         endif
      next b
   next a
   blocks(pathnum,fx,fy).state=1
until blocks(pathnum,endx,endy).state=0
nx=endx
ny=endy
repeat
   blocks(pathnum,nx,ny).state=2
   nx=nx-blocks(pathnum,nx,ny).pdx
   ny=ny-blocks(pathnum,nx,ny).pdy
until nx=startx and ny=starty or escapekey()=1
endfunction

`For those with short attention spans
function create_maze(xtiles,ytiles)
max=(xtiles*ytiles)-((xtiles-2)*(ytiles-2)-((xtiles-3)/2)*(ytiles-3))+2
local dim maze(xtiles,ytiles) as boolean
for x=1 to xtiles
   maze(x,1)=1
   maze(x,ytiles)=1
next x
for y=1 to ytiles
   maze(1,y)=1
   maze(xtiles,y)=1
next y
counter=2*xtiles+2*ytiles-2
while counter<max and escapekey()=0
   x=rnd(xtiles-2)+1
   y=rnd(ytiles-2)+1
   if maze(x-1,y-1)=1 and maze(x-1,y)+maze(x,y-1)=0 or maze(x-1,y+1)=1 and maze(x-1,y)+maze(x,y+1)=0 or maze(x+1,y-1)=1 and maze(x+1,y)+maze(x,y-1)=0 or maze(x+1,y+1)=1 and maze(x+1,y)+maze(x,y+1)=0 or maze(x,y)=1 or x/2.0=x/2 and y/2.0=y/2 or maze(x-1,y)+maze(x+1,y)+maze(x,y-1)+maze(x,y+1)<>1
   else
      maze(x,y)=1
      inc counter
   endif
endwhile
for x=0 to xtiles-1
   for y=0 to ytiles-1
      if maze(x+1,y+1)=1
         write memblock dword 1,(y*xtiles+x)*4+12,rgb(0,0,0)
      endif
   next y
next x
undim maze(0)
endfunction

Insanity is just a state of mind.

Back to top

Profile PM Website

sadsack

20

Years of Service

User Offline

Joined: 27th Nov 2003

Location: here

Posted: 30th Oct 2006 02:16

Link

I want to work on that code, it is very good, but I just got LightWave 9 and I have to get some models out. So it will be a week or to befor I can get into it. Thanks for the ok on it.
Just email me and I will put your email in my address book

ufofinder2001@yahoo.com
rennyhampton@thegusworks.com

Back to top

Profile PM Email Website

Sorry your browser is not supported!

The 20 Line Challenge / pathfinding demo