? ? ? ? 最近再弄cocos2d-x lua手游开发，我相信大家在开发手游时经常容易碰到寻路问题。寻路算法也挺多的，这里主要总结我在开发时使用的A satrt寻路算法。
? ? ? ?A星算法是基于启发式函数的一种寻路算法，A start的介绍就不重复了。主要是说明如何使用A start寻路算法。如图要从起点A移动到终点B，
地图中?
?表示可行走的方块。
?
?
? ? ? ? 该地图使用Tiled绘制的，每个方块都有自己的坐标，起点A为（5,27），终点B为（20,49）（这地图的原点（0,0）在地图左上角，图中地图只是原地图的部分，所以坐标不是0,0开始）。下面就来具体实现A start在这地图的寻路算法
? ? ?
?A start ?伪代码（结合代码便于理解）
? ? ? point ?= 起点
? ? ? while(point ！= 终点）
? ? {
? ? ? ? ? list = point相邻的点放到list里
? ? ? ? ? for（list）循环周围的点
? ? ? ? ? {?
? ? ? ? ? ? ? ?temp = list[index] 在list取出一个点
? ? ? ? ? ? ? ?if（temp在close表里 || temp不可行走)
? ? ? ? ? ? ? ? ? ? ? ?continue ? ?忽然该点，不作处理
? ? ? ? ? ? ? ?else
? ? ? ? ? ? ? ? ? ? ?计算temp的 g , h, f的值
? ? ? ? ? ? ? ? ? ? ?if(temp 不在open表内）
? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?把temp放入open表
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?把temp的father指向point
? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ?else ?temp在open内
? ? ? ? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 设open[i]为temp点
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if（temp.g < open[i].g)当前的temp的g小于已存在open表内的该点的g时
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 更新open[i]的g,h,f的值为temp的值
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 把open[i]的father指向point? ??
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? }
?
? ? ? ? ?一遍遍历完后把point插入close表
? ? ? ? ? if（size（open[]) ==0)
? ? ? ? ? ? ? ? ?查找失败，停止查找
? ? ? ? ? 从open表取出f值最小的点min
? ? ? ? ? point ?= ?min
? ? }
?
? ?查找成功
??
代码实现
? ? ? 首先定义一个节点类
? ? ? ?
----定义节点类
local node= class("node")
--创建节点,x,y是map的item
function node.create(x,y,map)
local myNode={}
-- 节点在tmx的位置
myNode.x = x;
myNode.y = y;
---A start参数
myNode.g = 0; --当前节点到起始点的代价
myNode.h = 0; --当前点的终点的估价
myNode.f = 0; --f=g+h
myNode.moveable = tiled.getMoveable(map,cc.p(x,y)) --该节点是否可行走
myNode.father={} -- 记录父节点,用来回溯路径
return myNode
end
return node
?
?
? ?有了node类，我们就可方便书写A start 算法主要逻辑
?
----A start寻路算法
local A_start= class("A_start")
local node = require("src/model/node")
local cost_stargiht =1 ; --直线移动花费
local cost_diag=1.414; --对角线移动花费
local MapY = 59 --地图y坐标最大值
local MapX = 89 --地图x坐标最大值
local _open = {}; --代考察表
local _close = {}; --以考察表
--计算某点的估值函数，可以多种实现
local function calculateH(point,endPoint)
print(endPoint.x , point.x)
----计算两个点的距离
local x = math.floor(endPoint.x - point.x) --获取该点x到终点x的距离
local y = math.floor(endPoint.y - point.y) --获取该点y到终点y的距离
local dis =math.abs(x)+math.abs(y)
--local dis = math.sqrt(math.pow(x,2)+math.pow(y,2))
return dis
end
---判断某点是否在close表内
local function isClose(point)
for key, var in ipairs(_close) do
if(var.x == point.x and var.y == point.y )then
return true
end
end
return false
end
---判断某点是否在open表内
local function isOpen(point)
for key, var in ipairs(_open) do
if(var.x == point.x and var.y == point.y )then
return true
end
end
return false
end
---寻路住逻辑，startPoint起始点，endPoint为终点，map为地图
function A_start.findPath(startPoint, endPoint, map)
_open = {}; --初始化
_close = {}; --初始化
--起始点
local point = node.create(startPoint.x,startPoint.y,map)
point.g = 0
point.h = calculateH(point,endPoint)
point.f = point.g + point.h
--当前节点不等于终点
while(not(point.x == endPoint.x and point.y == endPoint.y))do
----获取其上下左右四点
local around={}
if(point.y > 0)then --上
table.insert(around,node.create(point.x,point.y-1,map))
end
if(point.y < MapY)then --下
table.insert(around,node.create(point.x,point.y+1,map))
end
if(point.x > 0)then --左
table.insert(around,node.create(point.x-1,point.y,map))
end
if(point.x < MapX)then --右
table.insert(around,node.create(point.x+1,point.y,map))
end
--检查周围点
for key, var in pairs(around) do
--如果不可行走或已在close表，忽略此点
if(isClose(var) or (not var.moveable))then
--print("忽略该点" .. var.x .. " " .. var.y)
else
--计算此点的代价
local g = cost_stargiht+ point.g -- G值等同于上一步的G值 + 从上一步到这里的成本
local h = calculateH(var,endPoint)
local f = g + h
--该点不在open列表内
if(not isOpen(var))then
var.g = g;
var.h = h;
var.f = f
var.father = point --指向父节点
table.insert(_open,var) -- 添加到open表
--如果在open表，进行f比较
else
for key1, var1 in ipairs(_open) do
if(var1.x == var.x and var1.y == var.y)then
--if(var1.f>f)then---两个版本，// 检查G值还是F值
if(var1.g>g)then
var1.f = f
var1.g = g
var1.h = h
var1.parent = point
end
break
end
end
end
end
end
----当前节点找完一遍添加到——close表
table.insert(_close,point)
--open为空，则查找失败
if(table.getn(_open)== 0)then
return 0 ---查找失败返回0
end
---从open表去除最小的f点,并从open表移除
local max=99999
local myKey
for key2, var2 in ipairs(_open) do
if(var2.f<max)then
max = var2.f
myKey = key2
end
end
--从_open表移除并取出最小f的点最为起始点
point = table.remove(_open,myKey)
end
return point.father; -- 返回路径
end
return A_start
? ?
?
? ? 这样就完成了A start算法，下面我们来进行测试一下
?
--精灵移动方法，cocos2d 方法
local function Noderun(var,node)
if(node.moveNum< table.getn(node.path))then
node.moveNum = node.moveNum +1 ;
node.layer:getChildByTag(100):runAction(cc.Sequence:create(
cc.MoveTo:create(Soldier.speed,node.path[node.moveNum]),cc.CallFunc:create(Noderun,node)))
else
node.moveNum = 0;
end
end
local startItem = { x = 5,y = 57}
--终点
local endItem = { x = 20,y = 49}
--A_start寻路，调用寻路方法
local result = require("src/util/A_start").findPath(startItem,endItem,map)
---路径查找到
if(result ~= 0)then
var.path = {} --path{}先清零
table.insert(var.path,1,coordinate.getPoint(map,endItem)) -- 插入终点
--位置数组
--这里重要，是查找到的路径，还记的在node定义的father变量吗，路径就得靠它，每一个结点的
--father属性都指向下一个结点，所以可以回溯出路径
while(result.x)do
local item = {x =result.x, y=result.y} --把所有item连起来解释路径
--coordinate.getPoint()是转换为cocos2d的坐标，用于精灵移动
table.insert(var.path , 1 , coordinate.getPoint(map,item))
result=result.father
end
--节点移动，这里是cocos2d-x 的结点移动，不会的不影响
Noderun("",var)
--路径 没找到
else
print("查找失败")
end
?
运行结果：
?
?
?
原文：http://longpo.iteye.com/blog/2232330