A*尋路算法的lua實現(xiàn)

一、問題概述

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

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

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

二、關(guān)于A*

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

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

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

三、尋路思想

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

2.尋找A點可到到的周圍四個點，這里可到達(dá)是指沒有阻擋并且已經(jīng)不再關(guān)閉列表中的節(jié)點，并把他們添加進(jìn)開啟列表，并設(shè)置他們的父節(jié)點為A

3.從開啟列表中刪除A點并添加進(jìn)關(guān)閉列表中，關(guān)閉列表就是存放的不需要檢測的方格節(jié)點

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

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

6.當(dāng)發(fā)現(xiàn)開啟列表中有終點目標(biāo)方格的時候則說明路徑已經(jīng)找到。

關(guān)于詳細(xì)的圖解可以參考其他網(wǎng)友的詳解，我這里就不詳細(xì)寫了。

四、找回路徑

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

五、數(shù)據(jù)結(jié)構(gòu)

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)結(jié)構(gòu)

[plain] view plaincopyprint?

1. --根據(jù)一個table創(chuàng)建一個地形  

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() --關(guān)閉列表  

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. -- --檢測能達(dá)到的點  

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

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

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值,如果比原來大,就什么都不做,否則設(shè)置他的父節(jié)點為當(dāng)前節(jié)點,并更新G和F  

134.                 foundPoint(tempStart,point)  

135.             else  

136.                 --如果他們不再開始列表里面,就加入,并設(shè)置父節(jié)點,并計算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. --根據(jù)一個table創(chuàng)建一個地形  

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() --關(guān)閉列表  

156.     maze.findPath = findPath  

157.     return maze  

158. end  

159.   

160.   

161. return Maze  

調(diào)用方法

[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)  

七、運行效果

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