游戏中有敌我双方，有四十个方格，当轮到我方武将行动的时候，要先显示出我方武将可以行动的方位，这个就涉及到我方武将的行动力的大小来决定，预先做出路径的预算。这里还要考虑敌方以及地标(例如:×××、势头)的阻挡，以及特殊方格对武将行动力的消耗以及敌方的间隔阻挡规则。

当碰到这个问题的时候，问老大选择用什么寻路算法，他推荐的是Dijstra算法，但我看了之后感觉还不是很适合我的需求，第一：我觉得Dijstra算法是有向图的最佳路径选择，节点之间路径长度必须先知晓，但我这里四十个方格如果要两两制定感觉稍微复杂，而且随着武将的移动，地图还是时时变化的，感觉更复杂。第二：Distra算法没有阻挡考虑，当然也可以记录若干路径然后考虑阻挡选择最优路径，我感觉也稍复杂。

然而我的第一反应该需求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?

module('Point',package.seeall)

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

--计算F值

functionCalcF(point)

point.F=point.G+point.H

end

functioncreate(posId)

localpoint={}

point.parentPoint={}

point.step=1--用于计算h值

localx,y=BattleCommon.convertPosIdToCoord(posId)

point.F=0

point.G=0

point.H=0

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

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

point.posId=posId

point.CalcF=CalcF

returnpoint

end

returnPoint

地形(Maze)结构

[plain]view plaincopyprint?

--根据一个table创建一个地形

functioncreate(tb)

localmaze={}

maze.step=1--格子与格子的基本距离,用于计算H值

maze.mazeArray=tb

maze.openList=TabledArray.create()--开启列表

maze.closeList=TabledArray.create()--关闭列表

maze.findPath=findPath

returnmaze

end

[plain]view plaincopyprint?

module('Maze',package.seeall)

require("script/battle/TabledArray")

require("script/battle/BattleCommon")

require("script/battle/Point")

----获取列表中F值最小的点

functiongetMinPoint(pointsList)

localminPoint=pointsList.tbl[1]

fori=1,pointsList:getSize()do

ifminPoint.F>pointsList.tbl[i].Fthen

minPoint=pointsList.tbl[i]

end

end

returnminPoint

end

----检测是否有阻挡,没有阻挡为true

functioncheckBlock(maze,x,y,roleFlag)--x范围[1,5]y范围[1,8]

ifroleFlag==BattleCommon.BATTLE_GROUP_ALLIESthen--我方阵营

ifmaze.mazeArray[x][y][1]==0ormaze.mazeArray[x][y][1]==1then

returntrue--没有阻挡

else

returnfalse

end

elseifroleFlag==BattleCommon.BATTLE_GROUP_ENEMYthen

ifmaze.mazeArray[x][y][1]==0ormaze.mazeArray[x][y][1]==2then

returntrue--没有阻挡

else

returnfalse

end

end

end

----列表中是否包含x,y的点

functionexistsXY(list,x,y)

iflist:getSize()>0then

fori,pointinpairs(list.tbl)do

ifpoint.X==xandpoint.Y==ythen

returntrue

end

end

end

returnfalse

end

--列表中是否包含某个点

functionexistsPoint(list,point)

fori,pinpairs(list.tbl)do

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

returntrue

end

end

returnfalse

end

----检测能达到的点

functioncanReach(maze,startPoint,x,y,roleFlag)

if(notcheckBlock(maze,x,y,roleFlag))orexistsXY(maze.closeList,x,y)then--关闭列表中包含这个点或者有阻挡

returnfalse

else

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

returntrue

end

end

end

----获取相邻的点

functiongetSurroundPoints(maze,point,roleFlag)

localsurroundPoints=TabledArray.create()

fori=point.X-1,point.X+1do

forj=point.Y-1,point.Y+1do

ifi>0andi<6andj>0andj<9then--排除超过表姐

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

ifcanReach(maze,point,i,j,roleFlag)then

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

end

end

end

end

end

returnsurroundPoints--返回point点的集合

end

----计算G值

functionCalcG(point)

localG=point.G

localparentG=0

ifpoint.parentPointthen

parentG=point.parentPoint.G

end

returnG+parentG

end

functionfoundPoint(tempStart,point)

localG=CalcG(point)

ifG<point.Gthen

point.parentPoint=tempStart

point.G=G

point:CalcF()

end

end

functionnotFoundPoint(maze,tempStart,point)

point.parentPoint=tempStart

point.G=CalcG(point)

point:CalcF()

maze.openList:append(point)

end

functiongetPoint(list,data)

fori,pointinpairs(list.tbl)do

ifpoint.posId==data.posIdthen

returnpoint

end

end

returnnil

end

----寻找路径(起始路径)

localfunctionfindPath(maze,startPoint,endPoint,roleFlag)

maze.openList:append(startPoint)

whilemaze.openList:getSize()~=0do

--找出F的最小值

localtempStart=getMinPoint(maze.openList)

maze.openList:removeById(1)

maze.closeList:append(tempStart)

--找出它相邻的点

localsurroundPoints=getSurroundPoints(maze,tempStart,roleFlag)

fori,pointinpairs(surroundPoints.tbl)do

ifexistsPoint(maze.openList,point)then

--计算G值,如果比原来大,就什么都不做,否则设置他的父节点为当前节点,并更新G和F

foundPoint(tempStart,point)

else

--如果他们不再开始列表里面,就加入,并设置父节点,并计算GHF

notFoundPoint(maze,tempStart,point)

end

end

--如果最后一个存在则返回

ifgetPoint(maze.openList,endPoint)then

returngetPoint(maze.openList,endPoint)

end

end

returngetPoint(maze.openList,endPoint)

end

--根据一个table创建一个地形

functioncreate(tb)

localmaze={}

maze.step=1--格子与格子的基本距离,用于计算H值

maze.mazeArray=tb

maze.openList=TabledArray.create()--开启列表

maze.closeList=TabledArray.create()--关闭列表

maze.findPath=findPath

returnmaze

end

returnMaze

调用方法

[plain]view plaincopyprint?

functionprintPath(presentPoint)

localpathArray=TabledArray.create()

whilepresentPointdo

pathArray:preppend(presentPoint.posId)

presentPoint=presentPoint.parentPoint

end

localstartPoint=pathArray:get(2)

localendPoint=pathArray:getLast()

cclog(startPoint)

cclog(endPoint)

cclog("从"..startPoint.."到"..endPoint.."的路径是:")

fori,pinpairs(pathArray.tbl)do

cclog(p)

end

end

[plain]view plaincopyprint?

localarray=battleBoard:createBoxPoints(cRole:getFlag(),40)

localmaze=Maze.create(array)

localstartPoint=Point.create(cRole:getPositionId())

localendPoint=Point.create(40)

localpresentPoint=maze:findPath(startPoint,endPoint,cRole:getFlag())

printPath(presentPoint)

七、运行效果

手机测试效果还可以，貌似在255*255规模的方格规模上采用A*还是不会有太大的效率影响。如果需要交流欢迎联系。