欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

A星寻路算法

程序员文章站 2022-07-12 15:11:00
...

        最近再弄cocos2d-x lua手游开发,我相信大家在开发手游时经常容易碰到寻路问题。寻路算法也挺多的,这里主要总结我在开发时使用的A satrt寻路算法。

       A星算法是基于启发式函数的一种寻路算法,A start的介绍就不重复了。主要是说明如何使用A start寻路算法。如图要从起点A移动到终点B,

地图中 A星寻路算法
            
    
    博客分类: 数据结构cocos2d A星寻路cocos2d-lua地图寻路最短路径  表示可行走的方块。


 
A星寻路算法
            
    
    博客分类: 数据结构cocos2d A星寻路cocos2d-lua地图寻路最短路径 

 

        该地图使用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星寻路算法
            
    
    博客分类: 数据结构cocos2d A星寻路cocos2d-lua地图寻路最短路径 
 

 

 

  • A星寻路算法
            
    
    博客分类: 数据结构cocos2d A星寻路cocos2d-lua地图寻路最短路径 
  • 大小: 907 Bytes
  • A星寻路算法
            
    
    博客分类: 数据结构cocos2d A星寻路cocos2d-lua地图寻路最短路径 
  • 大小: 64.8 KB
  • A星寻路算法
            
    
    博客分类: 数据结构cocos2d A星寻路cocos2d-lua地图寻路最短路径 
  • 大小: 77.8 KB