lua实现寻路算法

Lua是一种轻量级、高效的脚本语言，适合用于游戏开发中的寻路算法实现。以下是一个简单的Lua代码实现：

-- 寻路算法的实现

local function pathfinding(start, goal, map)

-- 根据地图的情况，生成一个二维数组，记录每个点的状态 local nodes = {} for i = 1, #map do nodes[i] = {} for j = 1, #map[i] do nodes[i][j] = {x = i, y = j, g = math.huge, f = math.huge, parent = nil, state = map[i][j]} end end

-- 将起点的状态设置为"open"，g和f值设为0 nodes[start.x][start.y].state = "open" nodes[start.x][start.y].g = 0 nodes[start.x][start.y].f = 0

-- 定义open和closed列表，用于存储待访问和已访问的点 local open = {nodes[start.x][start.y]} local closed = {}

-- 定义一个函数，用于查找open列表中f值最小的点 local function getLowestF() local lowestF = math.huge local lowestNode = nil for _, node in ipairs(open) do if node.f < lowestF then lowestF = node.f lowestNode = node end end return lowestNode end

-- 开始寻路 while #open > 0 do local current = getLowestF() if current == nodes[goal.x][goal.y] then -- 到达目标点 local path = {} while current.parent do table.insert(path, 1, current) current = current.parent end return path end table.remove(open, current) -- 将当前点从open列表中移除 current.state = "closed" -- 将当前点的状态设置为"closed" table.insert(closed, current) -- 将当前点加入closed列表

-- 遍历当前点的邻居
for _, neighbor in ipairs(getNeighbors(current, nodes)) do
  if neighbor.state == "closed" then
    -- 如果邻居点已经在closed列表中，忽略它
  elseif neighbor.state == "open" then
    -- 如果邻居点已经在open列表中，检查是否通过当前点到达邻居点更优
    local newG = current.g + distance(current, neighbor)
    if newG < neighbor.g then
      neighbor.g = newG
      neighbor.f = neighbor.g + heuristic(neighbor, nodes[goal.x][goal.y])
      neighbor.parent = current
    end
  else -- 邻居点未被访问过
    neighbor.state = "open"
    neighbor.g = current.g + distance(current, neighbor)
    neighbor.f = neighbor.g + heuristic(neighbor, nodes[goal.x][goal.y])
    neighbor.parent = current
    table.insert(open, neighbor)
  end
end

end

return nil -- 如果无法到达目标点，返回nil end

-- 定义一个函数，用于获取一个点的所有邻居 function getNeighbors(node, nodes) local neighbors = {} local x, y = node.x, node.y if nodes[x - 1] and nodes[x - 1][y] then table.insert(neighbors, nodes[x - 1][y]) end -- 上 if nodes[x + 1] and nodes[x + 1][y] then table.insert(neighbors, nodes[x + 1][y]) end -- 下 if nodes[x][y - 1] then table.insert(neighbors, nodes[x][y - 1]) end -- 左 if nodes[x][y + 1] then table.insert(neighbors, nodes[x][y + 1]) end -- 右 return neighbors end

-- 定义一个函数，用于计算两个点的距离 function distance(node1, node2) local dx = math.abs(node1.x - node2.x) local dy = math.abs(node1.y - node2.y) if dx > dy then return 14 * dy + 10 * (dx - dy) else return 14 * dx + 10 * (dy - dx) end end

-- 定义一个函数，用于计算两个点之间的启发式距离 function heuristic(node1, node2) local dx = math.abs(node1.x - node2.x) local dy = math.abs(node1.y - node2.y) return 10 * (dx + dy) end

-- 测试代码 local map = { {1, 1, 1, 1, 1}, {1, 0, 0, 0, 1}, {1, 0, 1, 0, 1}, {1, 0, 0, 0, 1}, {1, 1, 1, 1, 1} }

local start = {x = 2, y = 2} local goal = {x = 4, y = 4}

local path = pathfinding(start, goal, map)

if path then print("Path found!") for _, node in ipairs(path) do print(node.x, node.y) end else print("No path found!") end

-- 输出结果： -- Path found! -- 2 2 -- 3 3 -- 4 4