首页 > 代码库 > A*寻路算法的lua实现

A*寻路算法的lua实现

2024-07-26 20:51:14   225人阅读

一、问题概述

游 戏中有敌我双方，有四十个方格，当轮到我方武将行动的时候，要先显示出我方武将可以行动的方位，这个就涉及到我方武将的行动力的大小来决定，预先做出路径 的预算。这里还要考虑敌方以及地标(例如:炸弹、势头)的阻挡，以及特殊方格对武将行动力的消耗以及敌方的间隔阻挡规则。
当 碰到这个问题的时候，问老大选择用什么寻路算法，他推荐的是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*还是不会有太大的效率影响

A*寻路算法的lua实现


联系
我们