简单的走格子玩法可以试试嗷~。如果格子数量过于庞大，~~可以考虑下是不是设计不合理呢？~~可以考虑下其他方法~

构造一个堆

首先构造一个堆类（heap， AKA 优先队列/Priority Queue），这个数据结构会在计算时存储过程数据，文件命名为 heap.lua。

local floor = math.floor

local function f_min(a, b) return a < b end

local function new(template, comp_func)
  return setmetatable({
	  _heap = {},
    _sort = comp_func or f_min,
    _size = 0 },
  template)
end

---构造方法
---@type heap
local heap = setmetatable({}, {
  __call = function(self, ...)
    return new(self, ...)
  end })
heap.__index = heap

---添加一些基础的方法

function heap:empty()
  return (self._size == 0)
end

function heap:clear()
  self._heap = {}
  self._size = 0
  self._sort = self._sort or f_min
  return self
end

--- heap 中常用的 percolate up, percolae down, heapify 的 lua version
--- percolate up: 添加数据后的比较和排序
local function _percolate_up(heap, index)
  if index == 1 then return end
  local p_index
  if index <= 1 then return end
  if index % 2 == 0 then
    p_index = index / 2
  else p_index = (index - 1) / 2
  end
  if not heap._sort(heap._heap[p_index], heap._heap[index]) then
    heap._heap[p_index], heap._heap[index] = heap._heap[index], heap._heap[p_index]
    _percolate_up(heap, p_index)
  end
end

--- percolate down: 取出数据后的比较和排序
local function _percolate_down(heap, index)
  local l_index, r_index, min_index
  l_index = 2 * index
  r_index = l_index + 1
  if r_index > heap._size then
    if l_index > heap._size then return
    else min_index = l_index end
  else
    if heap._sort(heap._heap[l_index],heap._heap[r_index]) then
      min_index = l_index
    else
      min_index = r_index
    end
  end
  if not heap._sort(heap._heap[index], heap._heap[min_index]) then
    heap._heap[index], heap._heap[min_index] = heap._heap[min_index], heap._heap[index]
    _percolate_down(heap, min_index)
  end
end

--- 对 heap 进行整理
function heap:heapify(item)
  if self._size == 0 then return end
  if item then
    local idx = nil
    for i = 1, #self._heap do
      if self._heap[i] == item then idx = i end
    end
    if idx then
      percolate_down(self, idx)
      percolate_up(self, idx)
    end
    return
  end
  for i = floor(self._size / 2), 1, -1 do
    percolate_down(self, i)
  end
  return self
end

function heap:push(item)
  if item then
    self._size = self._size + 1
    self._heap[self._size] = item
    _percolate_up(self, self._size)
  end
  return self
end

function heap:pop()
  local root
  if self._size > 0 then
    root = self._heap[1]
    self._heap[1] = self._heap[self._size]
    self._heap[self._size] = nil
    self._size = self._size - 1
    if self._size > 1 then
      percolate_down(self, 1)
    end
  end
  return root
end

return heap

A* 算法的实现

A* 分四方向和八方向，所以两种都有定义：

local heap = require 'heap'
local min = math.min
local max = math.max
local abs = math.abs
local floor = math.floor

local function f_min(a,b) return a.f < b.f end

---四方向
local four_dir = {
  {1, 0},
  {0, 1},
  {0, -1},
  {-1, 0},
}

---八方向
local eight_dir = {
  {1, 1},
  {1, 0},
  {1, -1},
  {0, 1},
  {0, -1},
  {-1, 1},
  {-1, 0},
  {-1, -1}
}

local function astar_path_finding(map, is_four_dir)
  ---@type astar
  local self = {}

  -- init map
  ---@param map @二维数组，第一层是行，第二层是列
  ---@param is_four_dir boolean @true: 四方向; false: 八方向
  function self.init(map, is_four_dir)
    self.startPoint = { row = 0, col = 0 }
    self.endPoint   = { row = 0, col = 0 }
    self.map        = map
    self.cost       = 10 -- 四方向的开销定为10
    self.cost2      = 14 -- 对脚节点的开销取近似值14
    self.open_list  = heap(f_min)
    self.mapRows    = #map
    self.mapCols    = #map[1]
    self.four_dir   = is_four_dir

    self.nodes = {}
    for i = 1, self.mapRows do
      for j = 1, self.mapCols do
        table.insert(self.nodes,
        {
          father = nil,
          row = i,
          col = j,
          g = 0,
          h = 0,
          f = 0,
          state = 0,   -- 0: 1:open 2:closed
        })
      end
    end
  end

  -- begin with 1
  function self.get_index(row, col)
    return (row - 1) * self.mapCols + col
  end

  -- begin with 1
  function self.get_row_col_by_index(index)
    local row = floor((index - 1) / self.mapCols)
    return row + 1, index - row * self.mapCols
  end

  function self.get_path(startRow, startCol, endRow, endCol)
    self.startPoint.row = endRow
    self.startPoint.col = endCol
    self.endPoint.row = startRow
    self.endPoint.col = startCol
    return self.search_path()
  end

  function self.search_path()
    -- if the end point is invalid then get empty
    if self.map[self.endPoint.row][self.endPoint.col] ~= 0 then
      print('error: can not reach end point!')
      return nil
    end

    -- inclue the first node
    local idx = self.get_index(self.startPoint.row, self.startPoint.col)
    self.open_list:push(self.nodes[idx])

    -- check boundary and validity
    local check = function(row, col)
      if 1 <= row and row <= self.mapRows
      and 1 <= col and col <= self.mapCols then
        if self.map[row][col] == 0
        or (row == self.endPoint.row and col == self.endPoint.col) then
          return true
        end
      end

      return false
    end

    local dir = self.four_dir and four_dir or eight_dir
    while not self.open_list:empty() do
      -- check
      local node = self.open_list:pop()
      node.state = 2

      if node.row == self.endPoint.row and node.col == self.endPoint.col then
        -- find the path
        return self.build_path(node)
      end

      for i = 1, #dir do
        local row = node.row + dir[i][1]
        local col = node.col + dir[i][2]
        local idx = self.get_index(row, col)

        if check(row, col) then
          local g, h, f = self.get_cost(node, row, col,
	          row ~= node.row and col ~= node.col)
          local newNode = self.nodes[idx]

          if newNode.state == 0 then
            -- add new node
            newNode.father = node
            newNode.g = g
            newNode.h = h
            newNode.f = f
            newNode.state = 1
            self.open_list:push(newNode)
          elseif newNode.state == 1 then
            -- alreay in openlist
            if newNode.f > f then
              -- a better way then update
              newNode.father = node
              newNode.g = g
              newNode.h = h
              newNode.f = f
            end
          else
            -- in closelist
          end
        end
      end
    end

    -- no path
    print('no available path')
    return nil
  end

  function self.get_cost(father, row, col, isdiag)
    local g, h

    if isdiag then
      g = father.g + self.cost2
    else
      g = father.g + self.cost
    end

    -- calc H value
    if self.four_dir then
      h = self.manhattan(row, col)
    else
      h = self.diagonal(row, col)
    end

    return g, h, (g + h)
  end

  -- calc path
  function self.build_path(node)
    local path = {}
    local sumCost = node.f -- total cost
    while node do
      path[#path + 1] = { x = node.row, y = node.col }
      node = node.father
    end

    return path, sumCost
  end

  ---四方向计算曼哈顿距离
  function self.manhattan(row, col)
    local h = abs(row - self.endPoint.row) + abs(col - self.endPoint.col)
    return h * self.cost
  end

  -- 八方向计算欧式距离直到与终点垂直或平行
  function self.diagonal(row, col)
    local dx = abs(row - self.endPoint.row)
    local dy = abs(col - self.endPoint.col)
    local minD = min(dx, dy)
    return minD * self.cost2 + (dx + dy - 2 * minD) * self.cost
  end

  self.init(map, four_dir)
  return self
end

return astar_path_finding

使用方法

非常简单，require 之后直接调用 init 方法构造数据，然后调用 get_path 方法就可以获得路线了~