Sorry your browser is not supported!

global mapHeight
global mapWidth
global aStarPointer

mapHeight=500
mapWidth=500

type aStar
   moveCost
   parentX
   parentZ
   G
   H
   F
   list
endtype

dim aiMap(mapWidth,mapHeight) as aStar
remstart
   A* Data Type Definition
   .moveCost         Cost in 'action points' to enter this area
   .parentX          Knowing who your parents are is important in life, why should A*
   .parentZ             be any different?
   .g                A*G : Journey time so far
   .h                A*H : Heuristical value
   .f                A*F : Total of Journey & Heuristic
   .list             set to 1 for open list and 2 for closed list
remend


type tile
   x as integer
   y as integer
   f as integer
endtype
global dim lowF(1)
global dim start(1)
global dim target(1)
global dim openlist(map_width * map_height) as tile : rem openlist
global dim path(10000,1)



function clear(x,y)
   for Cx = 0 to x
      for Cy = 0 to y
         aiMap(cx,cy).parentX=0
         aiMap(cx,cy).parentZ=0
         aiMap(cx,cy).g=0
         aiMap(cx,cy).h=0
         aiMap(cx,cy).f=0
         aiMap(cx,cy).list=0
      next cy
   next cx
endfunction
function fill_aiMap()
   cls
   for x = 0 to map_width
      for y = 0 to map_height
         if aiMap(x,y).moveCost = 1 then ink RGB(47,221,60),0
         if aiMap(x,y).moveCost = 2 then ink RGB(114,134,141),0
         if aiMap(x,y).moveCost >0 then dot x,y
      next y
   next x
   ink RGB(47,156,198),0
   dot start(0),start(1)
   ink RGB(255,0,0),0
   dot target(0),target(1)
endfunction
Function A_star()
   st = timer()
   REM ADD START TILE TO OPENLIST
   aStarPointer =1
   openlist(1).x = start(0) : openlist(1).y = start(1)
   openlist(1).f = H(start(0),start(1))
   aiMap(start(0),start(1)).f=aiMap(start(0),start(1)).h
   aiMap(start(0),start(1)).g= 0
   aiMap(start(0),start(1)).list= 1 : rem flag it
   aiMap(start(0),start(1)).parentX = start(0)
   aiMap(start(0),start(1)).parentZ = start(1)
   lowf(0) = 0 : lowf(1) = 0
   Finished = 0 : rem NOT DONE YET

   repeat
      Rem check for the lowest F
      if getlowestF() = 0 then exit
      Rem Add it to closed list
      aiMap(lowf(0),lowf(1)).list = 2
      REM Check 8 adjacent tiles
      for X = -1 to 1
         for Y = -1 to 1
            if  (x = 0) and (y = 0) = 1
            else
               cuX = lowf(0)
               cuY = lowf(1)
               adX = lowf(0) + X
               adY = lowf(1) + Y
               rem check if walkable/notclosed if 1 then move on
            `  if is_walkable_and_not_closed(adX,adY) = 1
               if adx = -1 or ady = -1 or adx = 65 or ady = 49
               else
                  if aiMap(adx,ady).moveCost = 0 : rem is walkable
                     if aiMap(adx,ady).list <> 2: rem is not closed
                        rem check if not opened
                        if aiMap(adX,adY).list = 0
                           aiMap(adx,ady).list = 1
                           aiMap(adX,adY).parentX = cuX:rem set parent X
                           aiMap(adX,adY).parentZ = cuY:rem set parent Y
                           aiMap(adX,adY).g = aiMap(cuX,cuY).g + movecost(X,Y) :rem set G (Nicely done!)
                           aiMap(adX,adY).h = H(adX,adY) : rem set H
                           if aiMap(adX,adY).h = 0 then FINISHED = 2
                           aiMap(adX,adY).f = aiMap(adX,adY).g + aiMap(adX,adY).h: rem set F
                           add2open(adX,adY,aiMap(adx,ady).f) : rem add to open list
                        else : rem this means that it is already opened
                            if aiMap(adX,adY).list=1
                              if aiMap(adX,adY).g > aiMap(cuX,cuY).g + movecost(X,Y)
                                 aiMap(adX,adY).parentX = cuX :rem set new parent X
                                 aiMap(adX,adY).parentZ = cuY :rem set new parent Y
                                 aiMap(adX,adY).g = aiMap(cuX,cuY).g + movecost(X,Y) :rem set G (Nicely done!)
                                 aiMap(adX,adY).f = aiMap(adX,adY).g + aiMap(adX,adY).h: rem set F
                              endif
                           endif : rem  if G is better
                        endif : rem if not opened
                     endif : rem is walkabe & not closed
                  endif
               endif
            endif
         next Y
      next X
      REM QUIT WHEN DONE
      `if FINISHED = 1 then exit
   until finished > 0
   if finished = 2
      print "path found in "; timer() - st ; "ms"
      tx = target(0)
      ty = target(1)
      t=0
      repeat
         inc t
         path(t,0) = aiMap(tx,ty).parentX
         path(t,1) = aiMap(tx,ty).parentZ
         tx = path(t,0)
         ty = path(t,1)
         dot tx+,ty
      until tx = start(0) and ty = start(1)
      steps = t
   else
      print "path not found in "; timer() -st;"ms"
      steps = 0
   endif
endfunction steps
function add2open(adX,adY,f)
   inc aStarPointer
   openlist(aStarPointer).x = adx
   openlist(aStarPointer).y = ady
   openlist(aStarPointer).f = f
endfunction
function H(x,y)
   rem deltas based on goal tile
   distance = (abs(x - target(0))+ abs(y - target(1)))*10
endfunction distance
function movecost(X,y)
   cost = 14
   if X * Y = 0 then cost = 10
endfunction cost
function getlowestF()
   final =999999
   rem aStarPointer = array count(openlist(0))
   for t = 1 to aStarPointer
      if openlist(t).f < final then final = openlist(t).f :finalt = t
   next t
   lowf(0) = openlist(finalt).x
   lowf(1) = openlist(finalt).y
   if final = 999999 then result = 0 else result =1
   openlist(finalt).f = 999999
endfunction result