A*尋路算法的lua實現

一、問題概述

游戲中有敵我雙方，有四十個方格，當輪到我方武將行動的時候，要先顯示出我方武將可以行動的方位，這個就涉及到我方武將的行動力的大小來決定，預先做出路徑的預算。這里還要考慮敵方以及地標(例如:×××、勢頭)的阻擋，以及特殊方格對武將行動力的消耗以及敵方的間隔阻擋規則。

當碰到這個問題的時候，問老大選擇用什么尋路算法，他推薦的是Dijstra算法，但我看了之后感覺還不是很適合我的需求，第一：我覺得Dijstra算法是有向圖的最佳路徑選擇，節點之間路徑長度必須先知曉，但我這里四十個方格如果要兩兩制定感覺稍微復雜，而且隨著武將的移動，地圖還是時時變化的，感覺更復雜。第二：Distra算法沒有阻擋考慮，當然也可以記錄若干路徑然后考慮阻擋選擇最優路徑，我感覺也稍復雜。

然而我的第一反應該需求A*算法挺接近的，然后咨詢老大，老大說A*方格之間距離必須要均等不然比較復雜。然后再咨詢公司其他稍有經驗同事，當然各有個的說法，什么深度、廣度遍歷，感覺沒一個確定的說法。讓我選擇就糾結了一天，不敢輕易選擇，如果稍有考慮不慎，說不定就要做幾天白用工，但最后我還是堅持自己的想法用A*來實現。

二、關于A*

A*通用的計算公式F=G+H

G:表示從起點A移動到網格上指定方格的移動耗費(我這里沒考慮斜方向移動),也可理解為節點的權重

H:表示從制定方格移動到終點B的預計耗費,這里一般就是計算距離*系數

三、尋路思想

1.從起點A開始，把它添加到"開啟列表"

2.尋找A點可到到的周圍四個點，這里可到達是指沒有阻擋并且已經不再關閉列表中的節點，并把他們添加進開啟列表，并設置他們的父節點為A

3.從開啟列表中刪除A點并添加進關閉列表中，關閉列表就是存放的不需要檢測的方格節點

4.檢查它所有相鄰并且合一到達的方格，如果這些方格還不再開啟列表里的話就把他們加入開啟列表，計算這些方格的GHF值并設置它的父節點

5.如果某個相鄰方格 D 已經在 "開啟列表" 里了, 檢查如果用新的路徑 (就是經過C 的路徑) 到達它的話, G值是否會更低一些, 如果新的G值更低, 那就把它的 "父方格" 改為目前選中的方格 C, 然后重新計算它的 F 值和 G 值 (H 值不需要重新計算, 因為對于每個方塊, H 值是不變的). 如果新的 G 值比較高, 就說明經過 C 再到達 D 不是一個明智的選擇, 因為它需要更遠的路, 這時我們什么也不做

6.當發現開啟列表中有終點目標方格的時候則說明路徑已經找到。

關于詳細的圖解可以參考其他網友的詳解，我這里就不詳細寫了。

四、找回路徑

我們找到最后一個點的時候然后層層往之前找到他的父節點迭代到最后不為空結束

五、數據結構

Point類

[plain] view plaincopyprint?

1. module('Point', package.seeall)  

2. -- require("script/battle/BattleCommon")  

3. --計算F值  

4. function CalcF( point )  

5.     point.F = point.G + point.H  

6. end  

7.   

8. function create( posId )  

9.     local point = {}  

10.     point.parentPoint = {}  

11.     point.step = 1 --用于計算h值  

12.     local x,y = BattleCommon.convertPosIdToCoord(posId)  

13.     point.F = 0  

14.     point.G = 0  

15.     point.H = 0  

16.     point.X = y            --point.X范圍[1,5]  

17.     point.Y = x            --point.Y范圍[1,8]  

18.     point.posId = posId  

19.     point.CalcF = CalcF  

20.       

21.     return point  

22. end  

23.   

24. return Point  

地形(Maze)結構

[plain] view plaincopyprint?

1. --根據一個table創建一個地形  

2. function create( tb )  

3.     local maze = {}  

4.     maze.step = 1 --格子與格子的基本距離,用于計算H值  

5.     maze.mazeArray = tb  

6.     maze.openList = TabledArray.create() --開啟列表  

7.     maze.closeList = TabledArray.create() --關閉列表  

8.     maze.findPath = findPath  

9.     return maze  

10. end  

六、主要代碼

[plain] view plaincopyprint?

1. module('Maze', package.seeall)  

2. require("script/battle/TabledArray")  

3. require("script/battle/BattleCommon")  

4. require ("script/battle/Point")  

5.   

6. -- --獲取列表中F值最小的點  

7. function getMinPoint( pointsList )  

8.     local minPoint = pointsList.tbl[1]  

9.     for i = 1,pointsList:getSize() do  

10.         if minPoint.F > pointsList.tbl[i].F then  

11.             minPoint = pointsList.tbl[i]  

12.         end  

13.     end  

14.     return minPoint  

15. end  

16.   

17. -- --檢測是否有阻擋,沒有阻擋為true  

18. function checkBlock( maze,x,y,roleFlag)              --x范圍[1,5]  y范圍[1,8]  

19.     if roleFlag == BattleCommon.BATTLE_GROUP_ALLIES then --我方陣營  

20.         if maze.mazeArray[x][y][1] == 0 or maze.mazeArray[x][y][1] == 1 then  

21.             return true  --沒有阻擋  

22.         else  

23.             return false     

24.         end  

25.     elseif roleFlag == BattleCommon.BATTLE_GROUP_ENEMY then  

26.         if maze.mazeArray[x][y][1] == 0 or maze.mazeArray[x][y][1] == 2 then  

27.             return true  --沒有阻擋  

28.         else  

29.             return false     

30.         end  

31.     end  

32. end  

33.   

34. -- --列表中是否包含x,y的點  

35. function existsXY( list,x,y )  

36.     if list:getSize()>0 then  

37.         for i,point in pairs(list.tbl) do  

38.             if point.X == x and point.Y == y then  

39.                 return true  

40.             end  

41.         end  

42.     end  

43.     return false  

44. end  

45.   

46. --列表中是否包含某個點  

47. function existsPoint( list,point )  

48.     for i, p in pairs(list.tbl) do  

49.         if (p.X == point.X) and (p.Y == point.Y) then  

50.             return true  

51.         end  

52.     end  

53.     return false  

54. end  

55.   

56.   

57. -- --檢測能達到的點  

58. function canReach( maze,startPoint,x,y,roleFlag)  

59.     if (not checkBlock(maze,x,y,roleFlag)) or  existsXY(maze.closeList,x,y) then --關閉列表中包含這個點或者有阻擋  

60.         return false  

61.     else  

62.         if (math.abs(x-startPoint.X)+math.abs(y-startPoint.Y) == 1 ) then  

63.             return true  

64.         end  

65.     end  

66. end  

67.   

68. -- --獲取相鄰的點  

69. function getSurroundPoints( maze,point,roleFlag )  

70.     local surroundPoints = TabledArray.create()  

71.     for i = point.X - 1 ,point.X + 1 do  

72.         for j=point.Y - 1,point.Y + 1 do  

73.             if i>0 and i<6 and j > 0 and j < 9 then  --排除超過表姐  

74.                 if BattleCommon.distanceFromTo(point.posId,BattleCommon.convertToPositionId(j-1,i-1)) < 2 then  

75.                     if canReach(maze,point,i,j,roleFlag) then  

76.                         surroundPoints:append(maze.mazeArray[i][j][2])  

77.                     end  

78.                 end  

79.             end  

80.         end  

81.     end  

82.     return surroundPoints   --返回point點的集合  

83. end  

84.   

85. -- --計算G值  

86. function CalcG( point )  

87.     local G = point.G  

88.     local parentG = 0  

89.     if point.parentPoint then  

90.         parentG = point.parentPoint.G  

91.     end  

92.     return G + parentG  

93. end  

94.   

95. function foundPoint( tempStart,point )  

96.     local G = CalcG(point)  

97.     if G < point.G then  

98.         point.parentPoint = tempStart  

99.         point.G = G  

100.         point:CalcF()  

101.     end  

102. end  

103.   

104.   

105. function notFoundPoint( maze,tempStart,point )  

106.     point.parentPoint = tempStart  

107.     point.G = CalcG(point)  

108.     point:CalcF()  

109.     maze.openList:append(point)  

110. end  

111.   

112. function getPoint( list,data )  

113.     for i,point in pairs(list.tbl) do  

114.         if point.posId == data.posId then  

115.             return point  

116.         end  

117.     end  

118.     return nil  

119. end  

120.   

121. -- --尋找路徑(起始路徑)  

122. local function findPath( maze,startPoint,endPoint,roleFlag)  

123.     maze.openList:append(startPoint)  

124.     while maze.openList:getSize() ~= 0 do  

125.         --找出F的最小值  

126.         local tempStart = getMinPoint(maze.openList)  

127.         maze.openList:removeById(1)  

128.         maze.closeList:append(tempStart)  

129.         --找出它相鄰的點  

130.         local surroundPoints = getSurroundPoints(maze,tempStart,roleFlag)  

131.         for i,point in pairs(surroundPoints.tbl) do  

132.             if existsPoint(maze.openList,point) then  

133.                 --計算G值,如果比原來大,就什么都不做,否則設置他的父節點為當前節點,并更新G和F  

134.                 foundPoint(tempStart,point)  

135.             else  

136.                 --如果他們不再開始列表里面,就加入,并設置父節點,并計算GHF  

137.                 notFoundPoint(maze,tempStart,point)  

138.             end  

139.         end  

140.         --如果最后一個存在則返回  

141.         if getPoint(maze.openList,endPoint) then  

142.             return getPoint(maze.openList,endPoint)  

143.         end  

144.     end  

145.     return getPoint(maze.openList,endPoint)  

146. end  

147.   

148.   

149. --根據一個table創建一個地形  

150. function create( tb )  

151.     local maze = {}  

152.     maze.step = 1 --格子與格子的基本距離,用于計算H值  

153.     maze.mazeArray = tb  

154.     maze.openList = TabledArray.create() --開啟列表  

155.     maze.closeList = TabledArray.create() --關閉列表  

156.     maze.findPath = findPath  

157.     return maze  

158. end  

159.   

160.   

161. return Maze  

調用方法

[plain] view plaincopyprint?

1. function printPath( presentPoint )  

2.     local pathArray = TabledArray.create()  

3.     while presentPoint do  

4.         pathArray:preppend(presentPoint.posId)  

5.         presentPoint = presentPoint.parentPoint  

6.     end  

7.     local startPoint = pathArray:get(2)  

8.     local endPoint = pathArray:getLast()  

9.       

10.     cclog(startPoint)  

11.     cclog(endPoint)  

12.     cclog("從"..startPoint.."到"..endPoint.."的路徑是:")  

13.     for i,p in pairs(pathArray.tbl) do  

14.         cclog(p)  

15.     end  

16. end  

[plain] view plaincopyprint?

1. local array = battleBoard:createBoxPoints(cRole:getFlag(),40)  

2. local maze = Maze.create(array)  

3. local startPoint = Point.create(cRole:getPositionId())  

4. local endPoint = Point.create(40)  

5. local presentPoint = maze:findPath(startPoint,endPoint,cRole:getFlag())  

6. printPath(presentPoint)  

七、運行效果

手機測試效果還可以，貌似在255*255規模的方格規模上采用A*還是不會有太大的效率影響。如果需要交流歡迎聯系。