A* algorithm demo in a MUSHclient plugin

findPathsAstar.lua

function findPathsAstar (startX, startY)

  statusMessage = "Starting"
  finalCost = 0
  
  print (string.format ("Starting at %d,%d", startX, startY))
  
  -- open list and closed list
  open, closed = {}, {}
 
  -- for display
  explored_rooms = {}
  
  -- add to open list
  function makeOpen (x, y, g, parentX, parentY)
    local scalar = xyToScalar (x, y)
    explored_rooms [scalar] = NODE_OPEN  -- open
    if open [scalar] then
      -- X, Y won't change because the location doesn't change
      -- update this if we got here with a lower G cost
       if (g + open [scalar].h) < open [scalar].f then
        -- print (string.format ("Amending %d,%d to have G = %0.3f rather than %0.3f (F = %0.3f rather than %0.3f) and new parents %d,%d", 
        --        x, y, g, open [scalar].g, g + open [scalar].h, open [scalar].f, parentX, parentY))
        open [scalar].g = g
        open [scalar].f = g + open [scalar].h
        open [scalar].parentX = parentX
        open [scalar].parentY = parentY
       end -- if
      return open [scalar].f
    end -- if already there
    
    
    -- add it, compute H (hyptonuse = sqrt (deltaX*deltaX + deltaY*deltaY)
    local h = math.sqrt (((x - destination_X) * (x - destination_X)) + ((y - destination_Y) * (y - destination_Y)))
    open [scalar] = { x = x, y = y, g = g, h = h , f = g + h, parentX = parentX, parentY = parentY}

    -- print (string.format ("Adding node %d,%d to the open list, g = %0.3f, h = %0.3f, f = %0.3f", x, y, g, h, g + h))
    
    return open [scalar].f
  end -- makeOpen

  function isOpen (x, y)
    local scalar = xyToScalar (x, y)
    return open [scalar]  
  end -- isOpen
  
    -- add to closed list
  function makeClosed (x, y)
    local scalar = xyToScalar (x, y)
    closed [scalar] = open [scalar] -- copy values 
    open [scalar] = nil -- not in open list any more
    explored_rooms [scalar] = NODE_CLOSED  -- closed
  end -- makeClosed

  function isClosed (x, y)
    local scalar = xyToScalar (x, y)
    return closed [scalar]  
  end -- isOpen
  
  function addNode (x, y, g, cost, parentX, parentY)

    if done then
      return
    end -- if done
    
    -- see if we reached end  
    if x == destination_X and y == destination_Y then
      done = true
      finalCost = g + (cost * getGrid (x, y))
      paths = { }
      repeat
        table.insert (paths, { x = parentX, y = parentY } )
        local parent = isClosed (parentX, parentY)  -- get parent of this node
        parentX, parentY = parent.parentX, parent.parentY
      until parentX == 0 or parentY == 0
      return
    end -- if
    
    if getGrid (x, y) == GRID_WALL then
      return  -- wall
    end -- if
   
    if isClosed (x, y) then
      return
    end -- closed 
    
    -- factor in land/water cost
  makeOpen (x, y, g + (cost * getGrid (x, y)), parentX, parentY)        
  end -- addNode

  
  local depth = 0
  local count = 0
  done = false
   
  -- found path goes here
  paths = {}

  -- create particle for the initial room
  addNode (startX, startY, 0, 0, 0, 0)  -- no g, no cost, no parent

  local total_time = 0
  
  while (not done) and next (open) and count < 2000 do

    -- print ""
    
    startTime = utils.timer ()
    count = count + 1
    
    -- find lowest scoring node in the open list
    local fMin = 999999999
    local gMin = 999999999
    local minNode = nil
    local openCount = 0
    local closedCount = 0
    for k, v in pairs (open) do
      openCount = openCount + 1
      if v.f < fMin then
        fMin = v.f
        minNode = v
        gMin = v.g  -- in case next one is equal, not less
      elseif v.f == fMin then  -- same f score, pick lower g score
        if v.g < gMin then
          gMin = v.g
          minNode = v
        end -- if
      end -- if lower or same F score
    end -- for    

    for k, v in pairs (closed) do
      closedCount = closedCount + 1
    end -- for    
      
    -- print (string.format ("%d nodes open, %d nodes closed", openCount, closedCount))
    
    x, y, g, h, f = minNode.x, minNode.y, minNode.g, minNode.h, minNode.f
    
     
    -- add this node to the closed list
    makeClosed (x, y)    
    
    -- print (string.rep ("-", 10))
    -- print (string.format ("Selected node %d,%d - put it on the closed list, g = %0.3f, h = %0.3f, f = %0.3f", x, y, g, h, f))
    -- print (string.rep ("-", 10))
    
    addNode (x - 1, y, g, 1, x, y)  -- W
    addNode (x + 1, y, g, 1, x, y)  -- E
    addNode (x, y - 1, g, 1, x, y)  -- N
    addNode (x, y + 1, g, 1, x, y)  -- S
    addNode (x - 1, y - 1, g, DIAGONAL_WEIGHT, x, y)  -- NW
    addNode (x - 1, y + 1, g, DIAGONAL_WEIGHT, x, y)  -- SW 
    addNode (x + 1, y - 1, g, DIAGONAL_WEIGHT, x, y)  -- NE
    addNode (x + 1, y + 1, g, DIAGONAL_WEIGHT, x, y)  -- SE
    
    total_time = total_time + (utils.timer () - startTime)
    statusMessage = string.format ("Iteration %d, cost = %0.1f", count, g)
    if count % 10 == 0 then
      drawGrid ()
      Repaint ()
    end -- if
  end   -- while more particles

    
  --[[
  
  -- print the final path (from back end)
  for k, v in ipairs (paths) do
    print (string.format ("%d,%d", v.x, v.y))
  end -- for
  --]]

  print "Route:"
  for i = #paths, 1, -1 do
    Tell (string.format (" [%d,%d]", paths [i].x, paths [i].y))
  end -- for
  print ""
    
  totalOpen, totalClosed = 0, 0
  
  for k, v in pairs (open) do
    totalOpen = totalOpen + 1
  end -- for
  for k, v in pairs (closed) do
    totalClosed = totalClosed + 1
  end -- for
  
  
  statusMessage =  string.format ("Time: %0.2f ms, %d squares in solution. Ended up with %d open nodes and %d closed nodes. Final cost = %0.1f.", 
                                  total_time * 1000, #paths, totalOpen, totalClosed, finalCost)

  print (string.format ("Ended up with %d open nodes and %d closed nodes", totalOpen, totalClosed))
  print (string.format ("Took %0.2f ms, squares in solution = %d", total_time * 1000, #paths))
  
  Redraw ()
  return paths, count, depth
end -- function findPathsAstar

findPathsBreadthFirst.lua

function findPathsBreadthFirst (x, y)

  statusMessage = "Running"

  local function make_particle (x, y, prev_path)
    local prev_path = prev_path or {}
    return {current_x=x, current_y = y, path=prev_path}
  end

  local function canExplore (x, y)
    if getGrid (x, y) == GRID_WALL then
      return false  -- wall
    end -- if
    if explored_rooms [xyToScalar (x, y)] then
      return false  -- already been there
    end -- if
    return true
  end -- canExplore
  
  function addNode (x, y)
    if canExplore (x, y) then 
      table.insert (exits, { x = x, y = y }) 
    end   -- to left
  end -- addNode
  
  local depth = 0
  local count = 0
  local done = false
  local found, reason
  explored_rooms, particles = {}, {}

  -- found path goes here
  paths = {}

  -- create particle for the initial room
  table.insert (particles, make_particle (x, y))

  local total_time = 0
  
  while (not done) and #particles > 0 and depth < DEPTH do

    startTime = utils.timer ()
    
    -- create a new generation of particles
    new_generation = {}
    depth = depth + 1

    SetStatus (string.format ("Scanning: %i/%i depth (%i rooms)", depth, DEPTH, count))

    -- process each active particle
    for i, part in ipairs (particles) do

      count = count + 1

      -- if room doesn't exist, forget it
      local x, y = part.current_x, part.current_y
      if xyValid (x, y) then
        -- get a list of exits from the current room
        exits = { }
        
        --[[  NOT AS GOOD (FAVOURS DIAGONALS)
        for xNew = x - 1, x + 1 do
          for yNew = y - 1, y + 1 do
            if not (xNew == x and yNew == y) then
              if canExplore (xNew, yNew) then 
                table.insert (exits, { x = xNew, y = yNew }) 
              end
            end -- not the square we are on
          end -- for yNew
        end -- for xNew
        --]]
        
        addNode (x - 1, y)  -- W
        addNode (x + 1, y)  -- E
        addNode (x, y - 1)  -- N
        addNode (x, y + 1)  -- S
        addNode (x - 1, y - 1)  -- NW
        addNode (x - 1, y + 1)  -- SW 
        addNode (x + 1, y + 1)  -- NE
        addNode (x + 1, y - 1)  -- SE
        
        
        -- create one new particle for each exit
        for dir, dest in pairs(exits) do

          -- if we've been in this room before, drop it
          if not explored_rooms[xyToScalar (dest.x, dest.y)] then
            explored_rooms[xyToScalar (dest.x, dest.y)] = NODE_EXPLORED
            new_path = copytable.deep (part.path)
            table.insert(new_path, { x = dest.x, y = dest.y } )

            if dest.x == destination_X and dest.y == destination_Y then
              done = true
              paths = new_path
            end -- if
            
            -- make a new particle in the new room
            table.insert(new_generation, make_particle(dest.x, dest.y, new_path))
          end -- not explored this room
          if done then
            break
          end

        end  -- for each exit

      end -- if room exists

      if done then
        break
      end
    end  -- for each particle

    particles = new_generation
    
    total_time = total_time + (utils.timer () - startTime)
    
    statusMessage =  string.format ("Iteration = %d", count)
    drawGrid ()
    Repaint ()
  end   -- while more particles

  SetStatus "Ready"
  print (string.format ("Took %0.2f ms, squares in solution = %d", total_time * 1000, #paths))
  
  statusMessage =  string.format ("Took %0.2f ms, squares in solution = %d", total_time * 1000, #paths)
  return paths, count, depth
end -- function findPathsBreadthFirst

Path_Finder.xml

<?xml version="1.0" encoding="iso-8859-1"?>
<!DOCTYPE muclient>

<muclient>
<plugin
   name="Path_Finder"
   author="Nick Gammon"
   id="fe137cf7827bb2eda19f4072"
   language="Lua"
   purpose="Testing path finding"
   save_state="y"
   date_written="2019-05-19 12:19:26"
   requires="5.06"
   version="1.0"
   >
<description>
Type "draw" to test path finding.
</description>

</plugin>

<aliases>
  <alias
   match="draw"
   enabled="y"
   send_to="12"
   sequence="100"
  >
  <send>OnPluginInstall ()</send>
  </alias>
</aliases>


<script>
<![CDATA[

require "copytable"

SHOW_LABELS = true
SHOW_MESSAGE = true

GRID_SIZE = 18
X_SIZE = 40
Y_SIZE = 40
OFFSET = 30

local RANDOM_SEED = os.time ()
--[[
 local FORCE_START_X = 8
 local FORCE_START_Y = 3
 local FORCE_DESTINATION_X = 59 -- 30
 local FORCE_DESTINATION_Y = 43 -- 52
 local RANDOM_SEED = 42
--]]

DIAGONAL_WEIGHT = math.sqrt (2)

DEPTH = 80
NODE_OPEN = 1
NODE_CLOSED = 2
NODE_EXPLORED = 3

GRID_LAND = 1
GRID_WATER = 3
GRID_WALL = 999

math.randomseed (RANDOM_SEED)

local grid = { }

function xyToScalar (x, y)
  return x * Y_SIZE + y  -- each X has to allow for a gap of Y
end -- xyToScalar

function xyValid (x, y)
  if x < 1 or y < 1 or x > X_SIZE or y > Y_SIZE then
    return false
  end -- if out of range
  return true
end --  xyValid

function getGrid (x, y)
  if not xyValid (x, y) then
    return GRID_WALL
  end -- if out of range
  return grid [xyToScalar (x, y)]
end -- getGrid

function setGrid (x, y, value)
  if not xyValid (x, y) then
    return
  end -- if out of range
  grid [xyToScalar (x, y)] = value
end -- setGrid

function positionToPixel (x, y)
  return OFFSET + (x - 1) * GRID_SIZE,
         OFFSET + (y - 1) * GRID_SIZE,
         OFFSET + (x) * GRID_SIZE,
         OFFSET + (y) * GRID_SIZE
end -- positionToPixel

function drawGrid ()
  WindowRectOp (win, miniwin.rect_fill, 0, 0, 0, 0, ColourNameToRGB("white"))

  for x = 1, X_SIZE do
    if SHOW_LABELS  then
      WindowText (win, "f", string.format ("%2d", x), OFFSET + (x - 1) * GRID_SIZE, 12, 0, 0, ColourNameToRGB "black")
    end -- if

    for y = 1, Y_SIZE do
      local x1, y1, x2, y2 = positionToPixel (x, y)
      local gridType = getGrid (x, y)

      if gridType == GRID_WALL then
        WindowRectOp (win, miniwin.rect_fill, x1, y1, x2, y2, ColourNameToRGB("black"))
      elseif gridType == GRID_LAND then
        WindowRectOp (win, miniwin.rect_fill, x1, y1, x2, y2, ColourNameToRGB("palegreen"))
      elseif gridType == GRID_WATER then
        WindowCircleOp (win, miniwin.circle_rectangle, -- rectangle
                         x1, y1, x2, y2,                -- Left, Top, Right, Bottom
                        ColourNameToRGB("blue"), miniwin.pen_null, 0,
                        ColourNameToRGB("powderblue"), miniwin.brush_waves_horizontal)-- brush

        --WindowRectOp (win, miniwin.rect_fill, x1, y1, x2, y2, ColourNameToRGB("powderblue"))
      end -- if

      if explored_rooms[xyToScalar (x, y)] == NODE_OPEN then
        WindowRectOp (win, miniwin.rect_fill, x1, y1, x2, y2, ColourNameToRGB("yellow"))
      elseif explored_rooms[xyToScalar (x, y)] == NODE_CLOSED then
        WindowRectOp (win, miniwin.rect_fill, x1, y1, x2, y2, ColourNameToRGB("salmon"))
      elseif explored_rooms[xyToScalar (x, y)] == NODE_EXPLORED then
        WindowRectOp (win, miniwin.rect_fill, x1, y1, x2, y2, ColourNameToRGB("khaki"))
      end -- if

      WindowRectOp (win, miniwin.rect_frame, x1, y1, x2, y2, ColourNameToRGB("lightblue"))

    end -- for y
  end -- for x

  if SHOW_LABELS  then
    for y = 1, Y_SIZE do
        WindowText (win, "f", string.format ("%2d", y), 10, OFFSET + (y - 1) * GRID_SIZE, 0, 0, ColourNameToRGB "black")
    end -- Y label
  end -- if

  -- show found path if any
  if next (paths) then
    for k, v in ipairs (paths) do
      local x1, y1, x2, y2 = positionToPixel (v.x, v.y)
      WindowRectOp (win, miniwin.rect_fill, x1, y1, x2, y2, ColourNameToRGB("royalblue"))
    end -- for
  end -- if path found

  -- show start
  local x1, y1, x2, y2 = positionToPixel (start_X, start_Y)
  WindowRectOp (win, miniwin.rect_fill, x1, y1, x2, y2, ColourNameToRGB("darkgreen"))

  -- show destination
  local x1, y1, x2, y2 = positionToPixel (destination_X, destination_Y)
  WindowRectOp (win, miniwin.rect_fill, x1, y1, x2, y2, ColourNameToRGB("darkred"))

  -- show messagae

  if SHOW_MESSAGE then
    WindowText (win, "f", statusMessage,
                OFFSET,  OFFSET + Y_SIZE * GRID_SIZE + 5, 0, 0, ColourNameToRGB "black")
  end -- if

end -- drawGrid


dofile (GetInfo (60) .. "findPathsBreadthFirst.lua")
dofile (GetInfo (60) .. "findPathsAstar.lua")

function OnPluginInstall ()

  print (string.rep ("-", 60))

  -- Initial stuff

  win = "test_" .. GetPluginID ()  -- get a unique name, ensure not empty if outside plugin
  WindowCreate (win, 0, 0,
                X_SIZE * GRID_SIZE + OFFSET * 2,
                Y_SIZE * GRID_SIZE + OFFSET * 2,
                miniwin.pos_bottom_right, 0, ColourNameToRGB("white"))  -- create window
  WindowShow (win,  true)  -- show it

  WindowFont (win, "f", "Dina", 8, false, false, false, false) -- define font

  -- fill grid with no walls
  for x = 1, X_SIZE do
     for y = 1, Y_SIZE do
       setGrid (x, y, GRID_LAND)
    end -- y
  end -- x

  -- put walls at edges

  -- left to right
  for x = 1, X_SIZE do
     setGrid (x, 1, GRID_WALL)  -- wall
     setGrid (x, Y_SIZE, GRID_WALL)  -- opposite wall
  end -- x

  -- top to bottom
  for y = 1, Y_SIZE do
    setGrid (1, y, GRID_WALL)
    setGrid (X_SIZE, y, GRID_WALL)
  end -- y

  -- draw some walls
  for i = 1, 20 do -- math.random (10, 20) do
     local x_size = math.random (10)
     local y_size = math.random (10)
     local x_start = math.random (X_SIZE)
     local y_start = math.random (Y_SIZE)
     for x = 1, x_size do
       for y = 1, y_size do
         setGrid (x_start + x, y + y_start, GRID_WALL)
       end -- for y
    end -- for x
  end -- for each random wall

  -- add some water

  for x = 22, 25 do
    for y = 20, 35 do
      setGrid (x, y, GRID_WATER)
    end -- for y
  end -- for x

  --[[
 for x = 22, 25 do
    for y = 40, 55 do
      setGrid (x, y, GRID_WATER)
    end -- for y
  end -- for x
  --]]

    -- find a start square
  if FORCE_START_X and FORCE_START_Y then
    start_X = FORCE_START_X
    start_Y = FORCE_START_Y
  else
    for i = 1, 1000 do
      start_X = math.random (X_SIZE)
      start_Y = math.random (Y_SIZE)
      if not getGrid (start_X, start_Y) == GRID_WALL then
        break  -- found one!
      end -- if
    end -- for
  end -- if

  -- find a destination square
  if FORCE_DESTINATION_X and FORCE_DESTINATION_Y then
    destination_X = FORCE_DESTINATION_X
    destination_Y = FORCE_DESTINATION_Y
  else
    for i = 1, 1000 do
      destination_X = math.random (X_SIZE)
      destination_Y = math.random (Y_SIZE)
      if getGrid (destination_X, destination_Y) ~= GRID_WALL and not (start_X == destination_X and start_Y == destination_Y) then
        break  -- found one!
      end -- if
    end -- for
  end -- if

  -- force start square to be land
  setGrid (start_X, start_Y, GRID_LAND)

  -- FIND THE PATH
  --  paths, count, depth = findPathsBreadthFirst (start_X, start_Y)    -- BREADTH FIRST
   paths, count, depth = findPathsAstar (start_X, start_Y)    -- A* ALGORITHM


  print ("Iterations =", count)

  drawGrid ()

end -- OnPluginInstall



]]>

</script>

</muclient>