A*

A*

--# Main
-- Main

function setup()
    parameter.integer("Size",10,100,25)
    parameter.action("Create",createMaze)
    parameter.action("Solve",SolveMaze)
    offset={x=50,y=50} --offset of maze from bottom left corner
end

function createMaze()
    w,h=Size,Size
    m=Maze(w,h) --create maze
    z=m.maze --get resulting maze
    --calculate size of squares that fit on screen, not greater than 40
    local sx=(WIDTH-offset.x*2)/w
    local sy=(HEIGHT-offset.y*2)/h
    s=math.min(sx,sy,40)
    path=nil --solution
end

function draw()
    background(40, 40, 50)
    strokeWidth(1)
    stroke(255)
    if s==nil then return end
    
    pushStyle()
    pushMatrix()
    --move drawing start position to bottom left of maze
    --then all future code can assume maze starts at 0,0
    --the only tricky thing is our maze cells have 1,1 at top left
    --but our screen has 0,0 at bottom left, ie y is upside down
    translate(offset.x,offset.y)
    topy=s*h --top of maze
    for i=1,w do
        for j=1,h do
            local x,y=(i-1)*s,topy-(j-1)*s
            --each cell has info about all its walls but if we draw them all
            --we would draw most of them twice because they belong to two cells
            --the most efficient is just to draw the top and left walls of each cell
            --which only leaves out the very bottom row and extreme right hand column
            --which we can deal with afterwards
            if z[i][j][1]==1 then line(x,y,x+s,y) end
            if z[i][j][2]==1 then line(x,y,x,y-s) end
        end
    end
    --now do bottom row
    for i=1,w do
        if z[i][h][4]==1 then 
            local x,y=(i-1)*s,topy-h*s
            line(x,y,x+s,y) 
        end
    end
    --and right hand column
    for j=1,h do
        if z[w][j][3]==1 then 
            local x,y=w*s,topy-(j-1)*s
            line(x,y,x,y-s) 
        end
    end
    --draw solution if available
    strokeWidth(2)
    stroke(255,0,0)
    if path~=nil then
        for i=2,#path do
            x1,y1=(path[i-1].x-.5)*s,topy-(path[i-1].y-.5)*s
            x2,y2=(path[i].x-.5)*s,topy-(path[i].y-.5)*s
            line(x1,y1,x2,y2)
        end 
    end
    popMatrix()
    popStyle()
end

function SolveMaze()
    astar=Astar()
    path=astar:CalcPath(astar:CalcMoves(z,1,1,w,h))
    if path==nil then
       print("No path found") 
    end
end
--# Maze
Maze=class()

--[[ 
Creating a maze with this class
m = Maze(n,m,rnd) ----m is not the maze, you need the next line as well, see below
where 
    n=width,
    m(optional, defaults to n)=height,
    rnd(optional, see under)=random seed
        if you provide rnd, then you will get the same maze every time, 
        but if you omit it, it will be different every time

z=m.maze --this returns the maze
  this is a 3D table, n wide x m high x 4 values (for walls)
  1,1 is top left cell, so z[3][5][3] refers to wall 3 of the cell in column 3, row 5
  The walls are numbered 1=top, 2=left, 3=right, 4=bottom, and their value is 1=wall, 0=gap
  so this tests if the top wall of cell 4,8 is a gap: z[4][8][1]==0

The maze itself is so called "perfect", in that there is only one path between any two cells
This is how it works
1) Start at a random cell in the grid.  
2) Look for a random neighbor cell you haven't been to yet.  
3) If you find one, move there, knocking down the wall between the cells. If you don't find one, back up to the previous cell.  
4) Repeat steps 2 and 3 until you've been to every cell in the grid.
--]]

function Maze:init(n,m,rnd)
    local m=m or n --set m=n if not provided
    local rnd=rnd or createRandomSeed()
    math.randomseed(rnd)
    t={} for i=1,n do t[i]={} end --create 2D maze
    local stack={} --holds visited cells
    local visitedCells=0
    local totalCells=n*m
    --set up little array to help with finding neighbours
    local nb={{x=0,y=-1},{x=-1,y=0},{x=1,y=0},{x=0,y=1}}
    --generate random starting cell
    local cell={x=math.random(1,n),y=math.random(1,m)}
    self.firstX,self.firstY=cell.x,cell.y
    t[cell.x][cell.y]={1,1,1,1} -- top, left, right, bottom (1=wall)
    visitedCells = visitedCells + 1
    --loop through
    while visitedCells<totalCells do
        local prevVisitedCells=visitedCells
        local r={1,2,3,4}
        while #r~=0 do
            --pick a random neighbour from the four directions
           local rr=math.random(1,#r)
           local s=r[rr]
           table.remove(r,rr)
           --work out x and y positions of neighbour
           local x,y=cell.x+nb[s].x,cell.y+nb[s].y
           --must be a valid cell that hasnt been visited
           if x>0 and x<=n and y>0 and y<=m and t[x][y]==nil then 
                t[x][y]={1,1,1,1} -- top, right,bottom,left (1=wall)
                t[cell.x][cell.y][s]=0 --break down wall in current cell
                t[x][y][5-s]=0 --and neighbour
                visitedCells = visitedCells + 1
                table.insert(stack,{x=cell.x,y=cell.y}) --add previous cell to stack in case we need it
                cell.x,cell.y=x,y --make neighbour the current cell
                break
           end
        end
        if prevVisitedCells==visitedCells then
            --no unvisited neighbours found, go back to previous cell from stack
            cell.x,cell.y=stack[#stack].x,stack[#stack].y
            table.remove(stack,#stack)
        end
    end 
    self.maze=t
end

--create a truly random seed using system accelerometers, what a kludge!
function createRandomSeed()
 return math.abs((UserAcceleration.x+UserAcceleration.y+RotationRate.x)/
            (RotationRate.y+Gravity.x+Gravity.y))*10000
end
--# Astar
Astar=class()
-- A* Path Finding Function
-- Based on the Algorithm posted at mobile.tutsplus.com
-- Corona SDK: Game Development Path Finding
-- Version 1.0
-- Modified by Reefwing Software (www.reefwing.com.au)
-- Modifications:
--     - Ported to Codea from Corona
--     - Changed isObstacle variable to a more general state variable

--Usage (you need both lines below)
--astar=Astar()
--path=astar:CalcPath(astar:CalcMoves(board,startX, startY, targetX, targetY)

-- where board is 2 D table containing info on obstacles in each cell
--specifically, whether moves are possible to the left,right, top and bottom 
--(diagonal moves aren't supported)

--IMPORTANT - you need to modify the lines between the asterisks below to suit the way you've stored your data

--the resulting path is a table of x,y values giving the solution from start to finish

function Astar:CalcMoves(board, startX, startY, targetX, targetY)

   local openlist = {}      -- Possible Moves
   local closedlist = {}    -- Checked Squares
   local listk = 1          -- open list counter
   local closedk = 0        -- Closedlist counter
   local tempH = math.abs(startX-targetX) + math.abs(startY-targetY)
   local tempG = 0

   openlist[1] = {x = startX, y = startY, g = 0, h = tempH, f = 0 + tempH ,par = 1}

   local xsize = table.getn(board[1])
   local ysize = table.getn(board)
   local curSquare = {}
   local curSquareIndex = 1     -- Index of current base

   while listk > 0 do
       local lowestF = openlist[listk].f
       curSquareIndex = listk
           for k = listk, 1, -1 do
               if openlist[k].f < lowestF then
                   lowestF = openlist[k].f
                   curSquareIndex = k
               end
           end

      closedk = closedk + 1
      table.insert(closedlist,closedk,openlist[curSquareIndex])

      curSquare = closedlist[closedk]    -- define current base from which to grow list

      local rightOK = true
      local leftOK = true                -- Booleans defining if they're OK to add
      local downOK = true                -- (must be reset for each while loop)
      local upOK = true

      -- Look through closedlist. Makes sure that the path doesn't double back

      if closedk > 0 then
          for k = 1, closedk do
              if closedlist[k].x == curSquare.x + 1 and closedlist[k].y == curSquare.y then
                  rightOK = false
              end
              if closedlist[k].x == curSquare.x-1 and closedlist[k].y == curSquare.y then
                  leftOK = false
              end
              if closedlist[k].x == curSquare.x and closedlist[k].y == curSquare.y + 1 then
                  downOK = false
              end
              if closedlist[k].x == curSquare.x and closedlist[k].y == curSquare.y - 1 then
                  upOK = false
              end
          end
      end

      -- Check if next points are on the map and within moving distance

      if curSquare.x + 1 > xsize then
          rightOK = false
      end
      if curSquare.x - 1 < 1 then
          leftOK = false
      end
      if curSquare.y + 1 > ysize then
          downOK = false
      end
      if curSquare.y - 1 < 1 then
          upOK = false
      end

      -- If it is on the map, check map for obstacles

      -- Lua returns an error if you try to access a table position
      -- that doesn't exist, so you can't combine it with above.

      -- *********** MODIFY THIS SECTION TO SUIT YOUR DATA ***************************
      --modify the 4 marked lines below
      --each line tells the program when it is NOT possible to move in one of the four directions shown
      --in the existing code below, each cell contains a table {x,x,x,x} where the 1st item=top wall, 
      -- 2nd=left,3rd=right, 4th=bottom, and they are set to 1 if there is a wall, else 0
      --so if board[3][5][2]=1 it means the left side of cell 3,5 has a wall
      --this is why the code below says moves are not ok if the value is 1

      if curSquare.x + 1 <= xsize and
          board[curSquare.x][curSquare.y][3] == 1 then  --modify   
              rightOK = false
      end
      if curSquare.x - 1 >= 1 and
          board[curSquare.x][curSquare.y][2] == 1 then  --modify
              leftOK = false
      end
      if curSquare.y + 1 <= ysize and
          board[curSquare.x][curSquare.y][4] == 1 then  --modify
              downOK = false
      end
      if curSquare.y - 1 >= 1 and
          board[curSquare.x][curSquare.y][1]== 1 then  --modify
              upOK = false
      end

      -- *********** END OF SECTION TO MODIFY ****************************************

      -- check if the move from the current base is shorter then from the former parent

      tempG = curSquare.g + 1
      for k = 1,listk do
          if rightOK and openlist[k].x==curSquare.x+1 and openlist[k].y==curSquare.y
              and openlist[k].g>tempG then
                  tempH=math.abs((curSquare.x+1)-targetX)+math.abs(curSquare.y-targetY)
                  table.insert(openlist,k,{x=curSquare.x+1, y=curSquare.y, g=tempG,
                               h=tempH, f=tempG+tempH, par=closedk})
          rightOK=false
          end

          if leftOK and openlist[k].x==curSquare.x-1 and openlist[k].y==curSquare.y
              and openlist[k].g>tempG then
                  tempH=math.abs((curSquare.x-1)-targetX)+math.abs(curSquare.y-targetY)
                  table.insert(openlist,k,{x=curSquare.x-1, y=curSquare.y, g=tempG,
                               h=tempH, f=tempG+tempH, par=closedk})
          leftOK=false
          end

          if downOK and openlist[k].x==curSquare.x and openlist[k].y==curSquare.y+1
              and openlist[k].g>tempG then
                  tempH=math.abs((curSquare.x)-targetX)+math.abs(curSquare.y+1-targetY)
                  table.insert(openlist,k,{x=curSquare.x, y=curSquare.y+1, g=tempG,
                               h=tempH, f=tempG+tempH, par=closedk})
          downOK=false
          end

          if upOK and openlist[k].x==curSquare.x and openlist[k].y==curSquare.y-1
              and openlist[k].g>tempG then
                  tempH=math.abs((curSquare.x)-targetX)+math.abs(curSquare.y-1-targetY)
                  table.insert(openlist,k,{x=curSquare.x, y=curSquare.y-1, g=tempG,
                               h=tempH, f=tempG+tempH, par=closedk})
          upOK=false
          end
         end

      -- Add points to openlist
      -- Add point to the right of current base point

      if rightOK then
          listk=listk+1
          tempH=math.abs((curSquare.x+1)-targetX)+math.abs(curSquare.y-targetY)
          table.insert(openlist,listk,{x=curSquare.x+1, y=curSquare.y, g=tempG,
              h=tempH, f=tempG+tempH, par=closedk})
      end

      -- Add point to the left of current base point

      if leftOK then
          listk=listk+1
          tempH=math.abs((curSquare.x-1)-targetX)+math.abs(curSquare.y-targetY)
          table.insert(openlist,listk,{x=curSquare.x-1, y=curSquare.y, g=tempG,
                       h=tempH, f=tempG+tempH, par=closedk})
      end

      -- Add point on the top of current base point

      if downOK then
          listk=listk+1
          tempH=math.abs(curSquare.x-targetX)+math.abs((curSquare.y+1)-targetY)
          table.insert(openlist,listk,{x=curSquare.x, y=curSquare.y+1, g=tempG,
                       h=tempH, f=tempG+tempH, par=closedk})
      end

      -- Add point on the bottom of current base point
      if upOK then
          listk=listk+1
          tempH=math.abs(curSquare.x-targetX)+math.abs((curSquare.y-1)-targetY)
          table.insert(openlist,listk,{x=curSquare.x, y=curSquare.y-1, g=tempG,
                       h=tempH, f=tempG+tempH, par=closedk})
      end

      table.remove(openlist,curSquareIndex)
      listk=listk-1

      if closedlist[closedk].x==targetX and closedlist[closedk].y==targetY then
          return closedlist
      end
  end

  return nil

end

function Astar:CalcPath(closedlist)

  if closedlist == nil then
      return nil
  end

  local path = {}
  local pathIndex = {}
  local last = table.getn(closedlist)

  table.insert(pathIndex, 1, last)

  local i = 1

  while pathIndex[i] > 1 do
      i = i + 1
      table.insert(pathIndex, i, closedlist[pathIndex[i - 1]].par)
  end

  for n = table.getn(pathIndex), 1, -1 do
      table.insert(path,{x=closedlist[pathIndex[n]].x, y=closedlist[pathIndex[n]].y})
  end

  closedlist = nil

  return path

end