require("math") Pathfinder = {} -- cost to move from one node to another Pathfinder.COST = 1 function Pathfinder:new(o) o = o or {} setmetatable(o, self) self.__index = self return o end --[[ map is a bitmap of solid (1) and empty (0) tiles stride is the width of the map in tiles ]]-- function Pathfinder:setMap(map, stride) self.map = map self.stride = stride end --[[ from and to are pairs of x/y coordinates on the map we search for a path from "to" to "from", so that we can follow the path ]]-- function Pathfinder:findPath(from, to) local path = {x=from.x, y=from.y, cost=0, toTarget=0} local last = nil self.open = {} self.closed = {} self.target = to -- add starting node self.closed[1] = path self:addNeighbors(path) while not last do -- move cheapest node to closed list local node = self:removeCheapestNode() if node then self.closed[#self.closed + 1] = node -- check if we have reached our target if node.x == self.target.x and node.y == self.target.y then last = node else self:addNeighbors(node) end else -- no path found return nil end end -- build up path while last.prev do last.prev.next = last last = last.prev end return path end function Pathfinder:removeCheapestNode() if #self.open == 0 then return nil end local idx = 1 local cost = self.open[1].toTarget for i = 2, #self.open do if cost > self.open[i].toTarget then idx = i cost = self.open[i].toTarget end end return table.remove(self.open, idx) end function Pathfinder:addOpenNode(x, y, parent) local nodeCost = Pathfinder.COST if parent then -- skip nodes already in closed list for i = 1, #self.closed do if self.closed[i].x == x and self.closed[i].y == y then return end end -- replace node if already in open list with higher cost nodeCost = nodeCost + parent.cost for i = 1, #self.open do local test = self.open[i] if test.x == x and test.y == y then if test.cost > nodeCost then test.cost = nodeCost test.prev = parent end return end end end -- otherwise, add node to open list local toTarget = Pathfinder.COST * (math.abs(self.target.x - x) + math.abs(self.target.y - y)) local node = {x= x, y= y, cost= nodeCost, toTarget= toTarget, prev= parent} self.open[#self.open + 1] = node end function Pathfinder:addNeighbors(node) local idx = node.x + (node.y - 1) * self.stride -- Bottom if node.y > 1 and not self.map[idx - self.stride] then self:addOpenNode(node.x, node.y - 1, node) end -- Right if node.x < self.stride and not self.map[idx + 1] then self:addOpenNode(node.x + 1, node.y, node) end -- Top if idx + self.stride <= #self.map and not self.map[idx + self.stride] then self:addOpenNode(node.x, node.y + 1, node) end -- Left if node.x > 1 and not self.map[idx - 1] then self:addOpenNode(node.x - 1, node.y, node) end end