最近再弄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
运行结果:
相关推荐
A星寻路算法(A* Search Algorithm)是计算机科学中用于在图或网格中寻找从起点到终点最短路径的一种高效算法。它结合了最佳优先搜索(如Dijkstra算法)和启发式搜索策略,通过估计从起点到目标点的最优成本来指导...
A星寻路算法(A* Search Algorithm)是一种广泛应用的路径搜索算法,主要用在游戏开发、图形界面编程、机器人导航等领域,用于寻找从起点到终点的最短路径。在这个MFC(Microsoft Foundation Classes)编写的动态演示...
基于javascript实现的a星寻路算法源码+项目说明.zip 基于javascript实现的a星寻路算法源码+项目说明.zip 基于javascript实现的a星寻路算法源码+项目说明.zip 基于javascript实现的a星寻路算法源码+项目说明.zip 基于...
在易语言中实现A星寻路算法,是为了解决游戏、地图导航等领域中的路径规划问题。A星(A*)算法是一种高效的启发式搜索算法,它结合了Dijkstra算法和最佳优先搜索,能够找到从起点到终点的最短路径。 A星算法的核心...
在这个压缩包文件中,"A星寻路"可能是包含MATLAB代码或者相关示例的文件,用于演示如何在具体的网格地图上实现A星寻路算法。通过学习和理解这些代码,你可以更好地掌握A星算法的细节,并可能扩展到其他应用领域。
VB 中的A星寻路算法 用了折半快速插入有序队列可以很快的添加结点数据 数组是以距离从大到小的一个有序队列 每次取数组中最后的数据,可以快速删除 例如:redim preserve A(ubound(A)-1)
A星(A*)寻路算法是计算机科学中用于路径搜索和图遍历的一种高效算法,尤其在游戏开发、导航系统、机器人路径规划等领域广泛应用。它结合了最佳优先搜索(如Dijkstra算法)和启发式搜索(如Greedy Best-First ...
`A星寻路.fla`可能是包含动画和交互的Flash项目,其中调用了`ARoad.as`和`Maps.as`中的类来实现动态寻路效果。 总结,Flash AS3中的A*寻路算法实现了智能路径规划,通过优化的数据结构和启发式搜索策略,有效地解决...
寻路,经典A星算法(A*): 1。采用静态内存方案,寻路过程不会出现动态内存分配,杜绝内存泄漏的可能 2。CloseList采用直接寻址方式实现 3。OpenList采用优化过的遍历查找插入算法,实现简单高效。如果哪位有二叉堆...
A星(A*)寻路算法是游戏开发中常用的一种路径规划算法,它在二维或三维空间中寻找从起点到终点的最短路径。Cocos是一个强大的跨平台2D游戏开发框架,支持多种编程语言,如C++, Lua和JavaScript。在这个课程作业中,你...
总之,这个项目提供了C++实现的A星和B星寻路算法,结合MFC创建了一个可视化环境,用户可以观察和比较不同算法的寻路效果。通过调试和优化,这些算法可以应用于各种需要寻找最短路径的问题中,比如游戏中的角色移动、...
A星寻路算法广泛应用于游戏开发、机器人路径规划、网络路由、物流配送等领域。MATLAB作为强大的科学计算和图形化工具,是实现和测试这种算法的理想平台。通过阅读和理解提供的MATLAB源码,你可以深入理解A星算法的...
本篇文章将深入探讨如何在VB环境中实现A星寻路算法。 A星算法是一种启发式搜索算法,它的核心思想是在广度优先搜索的基础上加入了一个评估函数,以更高效地找到从起点到终点的最短路径。这个评估函数通常由两部分...