A星lua实现

A星的大致流程：

每走下一步前，评估所有可走下一步的移动量，然后从中选择最佳步骤；不断重复这个过程，直到到达目的地。

  1 local Astar = {}
  2 
  3 function Astar.new()
  4     local inst = {}
  5     inst.__index = Astar
  6     setmetatable(inst, inst)
  7     inst:ctor()
  8     return inst
  9 end
 10 
 11 function Astar:ctor()
 12     self.tiles = nil
 13     self.cachedStepInfos = nil
 14 end
 15 
 16 function Astar:SetTiles(tiles)
 17     self.tiles = tiles
 18     self.cachedStepInfos = nil
 19 end
 20 
 21 function Astar:CheckOutOfRange(x, y)
 22     local row = self.tiles[y]
 23     if nil == row then return true end
 24     if nil == row[x] then return true end
 25     return false
 26 end
 27 
 28 function Astar:ResetStepInfos()
 29     if nil ~= self.cachedStepInfos then
 30         for k_rowIndex, v_rowStepInfos in pairs(self.cachedStepInfos) do
 31             for k_colIndex, v_stepInfo in pairs(v_rowStepInfos) do
 32                 v_stepInfo.g = 0
 33                 v_stepInfo.h = 0
 34                 v_stepInfo.f = 0
 35                 v_stepInfo.used = false
 36             end
 37         end
 38     end
 39 end
 40 
 41 function Astar:GetStepInfo(x, y)
 42     if nil == self.cachedStepInfos then
 43         self.cachedStepInfos = {}
 44     end
 45     local row = self.cachedStepInfos[y]
 46     if nil == row then
 47         row = {}
 48         self.cachedStepInfos[y] = row
 49     end
 50     local stepInfo = row[x]
 51     if nil == stepInfo then
 52         stepInfo = {
 53             loc = { x=x, y=y },
 54         }
 55         row[x] = stepInfo
 56     end
 57     return stepInfo
 58 end
 59 
 60 ---获取2个点之间的最佳路径
 61 function Astar:FindPath(startLoc, toLoc)
 62     if startLoc.x == toLoc.x and startLoc.y == toLoc.y then
 63         return false
 64     end
 65 
 66     if self:CheckOutOfRange(startLoc.x, startLoc.y) then return false end
 67     if self:CheckOutOfRange(toLoc.x, toLoc.y) then return false end
 68 
 69     self:ResetStepInfos()
 70 
 71     self.open = {}
 72     self.closed = {}
 73     self.startLoc = startLoc
 74     self.toLoc = toLoc
 75     self:GetStepInfo(startLoc.x, startLoc.y).used = true
 76 
 77     local curLoc = startLoc
 78     while true do
 79         local oldCount = #self.open
 80         if not self:NextStepByRule(curLoc) then
 81             return true
 82         end
 83         if #self.open > oldCount then
 84             local best = self:FindBest()
 85             if nil == best then
 86                 return false
 87             end
 88             curLoc = best.loc
 89             table.insert(self.closed, curLoc)
 90         else
 91             return false
 92         end
 93     end
 94     return true
 95 end
 96 
 97 ---按下一步规则执行下一步
 98 function Astar:NextStepByRule(curLoc)
 99     --这边下一步的规则是右,上,左,下四个方向
100     local notReachDst = self:CheckNextStep(curLoc.x+1, curLoc.y) --right
101             and self:CheckNextStep(curLoc.x, curLoc.y-1) --top
102             and self:CheckNextStep(curLoc.x-1, curLoc.y) --left
103             and self:CheckNextStep(curLoc.x, curLoc.y+1) --bottom
104     return notReachDst
105 end
106 
107 ---检查下一步, 如果符合条件的则放入open列表
108 ---@return "是否未到达终点"
109 function Astar:CheckNextStep(x, y)
110     local toLoc = self.toLoc
111     if x == toLoc.x and y == toLoc.y then --到达终点
112         table.insert(self.closed, toLoc)
113         return false
114     end
115 
116     if nil ~= self.tiles[y] and 0 == self.tiles[y][x] then
117         local stepInfo = self:GetStepInfo(x, y)
118         if not stepInfo.used then
119             stepInfo.g = #self.closed + 1
120             stepInfo.h = math.abs(x - toLoc.x) + math.abs(y - toLoc.y)
121             stepInfo.f = stepInfo.g + stepInfo.h
122             stepInfo.used = true
123             table.insert(self.open, stepInfo)
124         end
125     end
126     return true
127 end
128 
129 function Astar:FindBest()
130     local best = nil
131     local index = 0
132     --print("----- open")
133     for i=1,#self.open do
134         local stepInfo = self.open[i]
135         --print(string.format("-----: %s, %s, %s", stepInfo.loc.y, stepInfo.loc.x, stepInfo.f))
136         if nil == best then
137             best = stepInfo
138             index = i
139         elseif stepInfo.f <= best.f then
140             best = stepInfo
141             index = i
142         end
143     end
144     --print("-----: " .. index)
145     if index > 0 then
146         table.remove(self.open, index)
147     end
148     return best
149 end

测试代码

 1 local a = Astar.new()
 2 local tiles = {}
 3 tiles[1] = { 0, 0, 0, 0, 0, 0, 0 }
 4 tiles[2] = { 0, 0, 0, 1, 0, 0, 0 }
 5 tiles[3] = { 0, 0, 0, 1, 0, 0, 0 }
 6 tiles[4] = { 0, 0, 0, 1, 0, 0, 0 }
 7 tiles[5] = { 0, 1, 0, 1, 0, 0, 0 }
 8 tiles[6] = { 0, 0, 0, 0, 0, 0, 0 }
 9 a:SetTiles(tiles)
10 if a:FindPath({x=2, y=4}, {x=6, y=5}) then
11 
12 end
13 local closed = a.closed
14 for i=1,#closed do
15     local loc = closed[i]
16     print(string.format("y=%s, x=%s", loc.y, loc.x))
17 end

【A星原理参考】

 A星寻路算法 - 简书 (jianshu.com)