A星寻路算法
最近再弄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
运行结果：
上一篇： 无聊猜想：高并发，更新要求高的解决思路 lucene数据结构Blog
下一篇： 如何选择中文分词