lua实现a寻路算法

A*寻路算法是一种常用的路径规划算法，可以在复杂的地图中快速找到最短路径。下面是一个简单的Lua实现：

-- 定义节点类 local Node = {} Node.__index = Node

function Node.new(x, y) local self = setmetatable({}, Node) self.x = x self.y = y self.g = 0 self.h = 0 self.f = 0 self.parent = nil return self end

-- 计算节点到目标节点的距离 function Node:heuristic(target) return math.abs(self.x - target.x) + math.abs(self.y - target.y) end

-- 定义地图类 local Map = {} Map.__index = Map

function Map.new(width, height) local self = setmetatable({}, Map) self.width = width self.height = height self.grid = {} for x = 1, width do self.grid[x] = {} for y = 1, height do self.grid[x][y] = 0 end end return self end

-- 设置障碍物 function Map:set_obstacle(x, y) self.grid[x][y] = 1 end

-- 判断是否为障碍物 function Map:is_obstacle(x, y) return self.grid[x][y] == 1 end

-- 获取周围节点 function Map:get_neighbors(node) local neighbors = {} for dx = -1, 1 do for dy = -1, 1 do if dx ~= 0 or dy ~= 0 then local x = node.x + dx local y = node.y + dy if x >= 1 and x <= self.width and y >= 1 and y <= self.height and not self:is_obstacle(x, y) then table.insert(neighbors, Node.new(x, y)) end end end end return neighbors end

-- A*算法 function Map:a_star(start, target) local open_set = {start} local closed_set = {} while #open_set > 0 do -- 选取f值最小的节点 local current = open_set[1] for i = 2, #open_set do if open_set[i].f < current.f then current = open_set[i] end end -- 到达目标节点 if current == target then local path = {} while current do table.insert(path, 1, current) current = current.parent end return path end -- 移动当前节点到closed集合 for i = 1, #open_set do if open_set[i] == current then table.remove(open_set, i) break end end table.insert(closed_set, current) -- 扩展周围节点 local neighbors = self:get_neighbors(current) for i = 1, #neighbors do local neighbor = neighbors[i] -- 跳过已经在closed集合中的节点 if not table.contains(closed_set, neighbor) then local new_g = current.g + 1 -- 如果节点已经在open集合中，更新g值 local found = false for j = 1, #open_set do if open_set[j] == neighbor then found = true if new_g < neighbor.g then neighbor.g = new_g neighbor.f = neighbor.g + neighbor.h neighbor.parent = current end break end end -- 如果节点不在open集合中，加入open集合 if not found then neighbor.g = new_g neighbor.h = neighbor:heuristic(target) neighbor.f = neighbor.g + neighbor.h neighbor.parent = current table.insert(open_set, neighbor) end end end end return nil end

-- 测试 local map = Map.new(5, 5) map:set_obstacle(2, 2) map:set_obstacle(3, 2) map:set_obstacle(4, 2) local start = Node.new(1, 1) local target = Node.new(5, 5) local path = map:a_star(start, target) if path then for i = 1, #path do print(path[i].x, path[i].y) end else print("No path found") end