开发文章

cocos2d-x lua A星寻路算法

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

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

地图中  表示可行走的方块。

cocos2d-x lua A星寻路算法

该地图使用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

    }

 查找成功

  

代码实现

      首先定义一个节点类

       

复制内容到剪贴板
  1. ----定义节点类   
  2. local  node= class("node")   
  3. --创建节点,x,y是map的item   
  4. function node.create(x,y,map)   
  5.    local myNode={}   
  6.    -- 节点在tmx的位置   
  7.    myNode.x = x;   
  8.    myNode.y = y;   
  9.    ---A start参数   
  10.    myNode.g = 0;  --当前节点到起始点的代价   
  11.    myNode.h = 0;  --当前点的终点的估价   
  12.    myNode.f = 0;  --f=g+h   
  13.    myNode.moveable = tiled.getMoveable(map,cc.p(x,y))  --该节点是否可行走   
  14.       
  15.    myNode.father={} -- 记录父节点,用来回溯路径     
  16.    return myNode   
  17. end   
  18.   
  19. return node  

有了node类,我们就可方便书写A start 算法主要逻辑

复制内容到剪贴板
  1. ----A start寻路算法   
  2.   
  3. local  A_start= class("A_start")   
  4.   
  5. local node = require("src/model/node")   
  6.   
  7. local cost_stargiht =1 ; --直线移动花费   
  8.   
  9. local cost_diag=1.414; --对角线移动花费   
  10.   
  11. local MapY = 59 --地图y坐标最大值   
  12.   
  13. local MapX = 89 --地图x坐标最大值   
  14.      
  15. local _open = {}; --代考察表   
  16.   
  17. local _close = {}; --以考察表   
  18.   
  19. --计算某点的估值函数,可以多种实现   
  20. local function  calculateH(point,endPoint)   
  21.     print(endPoint.x , point.x)   
  22.     ----计算两个点的距离   
  23.     local x = math.floor(endPoint.x - point.x)  --获取该点x到终点x的距离   
  24.     local y = math.floor(endPoint.y - point.y)  --获取该点y到终点y的距离   
  25.     local dis =math.abs(x)+math.abs(y)   
  26.     --local dis = math.sqrt(math.pow(x,2)+math.pow(y,2))       
  27.     return dis   
  28. end   
  29.   
  30. ---判断某点是否在close表内   
  31. local function isClose(point)   
  32.     for key, var in ipairs(_close) do  
  33.         if(var.x == point.x and var.y == point.y )then   
  34.            return true  
  35.         end   
  36.     end   
  37.        
  38.     return false  
  39. end   
  40.   
  41. ---判断某点是否在open表内   
  42. local function isOpen(point)   
  43.     for key, var in ipairs(_open) do  
  44.         if(var.x == point.x and var.y == point.y )then   
  45.            return true  
  46.         end   
  47.     end   
  48.        
  49.     return false  
  50. end   
  51.   
  52. ---寻路住逻辑,startPoint起始点,endPoint为终点,map为地图   
  53. function A_start.findPath(startPoint, endPoint, map)   
  54.       
  55.   _open = {}; --初始化   
  56.   
  57.   _close = {}; --初始化   
  58.        
  59.   --起始点   
  60.   local point = node.create(startPoint.x,startPoint.y,map)   
  61.   point.g = 0     
  62.   point.h = calculateH(point,endPoint)   
  63.   point.f = point.g + point.h   
  64.       
  65.   --当前节点不等于终点   
  66.   while(not(point.x == endPoint.x and point.y == endPoint.y))do     
  67.         ----获取其上下左右四点   
  68.         local around={}   
  69.         if(point.y > 0)then --上   
  70.             table.insert(around,node.create(point.x,point.y-1,map))   
  71.         end   
  72.         if(point.y < MapY)then --下   
  73.             table.insert(around,node.create(point.x,point.y+1,map))   
  74.         end   
  75.         if(point.x > 0)then --左   
  76.             table.insert(around,node.create(point.x-1,point.y,map))   
  77.         end   
  78.         if(point.x < MapX)then --右   
  79.             table.insert(around,node.create(point.x+1,point.y,map))   
  80.         end   
  81.                 
  82.         --检查周围点   
  83.         for key, var in pairs(around) do  
  84.                
  85.             --如果不可行走或已在close表,忽略此点   
  86.             if(isClose(var) or (not var.moveable))then   
  87.                  --print("忽略该点" .. var.x .. "  " .. var.y)             
  88.             else  
  89.                  --计算此点的代价   
  90.                  local g = cost_stargiht+ point.g    -- G值等同于上一步的G值 + 从上一步到这里的成本             
  91.                  local h = calculateH(var,endPoint)   
  92.                  local f = g + h   
  93.                   --该点不在open列表内   
  94.                  if(not isOpen(var))then   
  95.                     var.g = g;   
  96.                     var.h = h;   
  97.                     var.f = f   
  98.                     var.father = point --指向父节点   
  99.                     table.insert(_open,var) -- 添加到open表   
  100.                      
  101.                     --如果在open表,进行f比较   
  102.                  else  
  103.                       for key1, var1 in ipairs(_open) do  
  104.                            if(var1.x == var.x and var1.y == var.y)then    
  105.                                --if(var1.f>f)then---两个版本,// 检查G值还是F值   
  106.                               if(var1.g>g)then   
  107.                                    var1.f = f   
  108.                                    var1.g = g   
  109.                                    var1.h = h   
  110.                                    var1.parent = point    
  111.                                end   
  112.                                break  
  113.                            end   
  114.                       end   
  115.                   end   
  116.              end   
  117.          end   
  118.            
  119.         ----当前节点找完一遍添加到——close表   
  120.         table.insert(_close,point)   
  121.         --open为空,则查找失败   
  122.         if(table.getn(_open)== 0)then   
  123.            return 0 ---查找失败返回0   
  124.         end   
  125.   
  126.         ---从open表去除最小的f点,并从open表移除   
  127.         local max=99999   
  128.         local myKey   
  129.         for key2, var2 in ipairs(_open) do  
  130.             if(var2.f<max)then   
  131.                 max = var2.f   
  132.                 myKey = key2   
  133.             end   
  134.         end   
  135.         --从_open表移除并取出最小f的点最为起始点   
  136.         point = table.remove(_open,myKey)      
  137.                
  138.    end   
  139.    return point.father; -- 返回路径   
  140. end   
  141. return A_start  

这样就完成了A start算法,下面我们来进行测试一下

复制内容到剪贴板
  1.  --精灵移动方法,cocos2d 方法   
  2. local function Noderun(var,node)   
  3.     if(node.moveNum< table.getn(node.path))then   
  4.         node.moveNum = node.moveNum +1 ;                  
  5.         node.layer:getChildByTag(100):runAction(cc.Sequence:create(   
  6.             cc.MoveTo:create(Soldier.speed,node.path[node.moveNum]),cc.CallFunc:create(Noderun,node)))                                   
  7.     else      
  8.         node.moveNum = 0;   
  9.     end   
  10. end        
  11.   
  12.   
  13.   
  14. local startItem = { x = 5,y = 57}      
  15. --终点   
  16.  local endItem = { x = 20,y = 49}   
  17. --A_start寻路,调用寻路方法   
  18.  local result = require("src/util/A_start").findPath(startItem,endItem,map)   
  19. ---路径查找到   
  20.  if(result ~= 0)then   
  21.      var.path = {} --path{}先清零   
  22.      table.insert(var.path,1,coordinate.getPoint(map,endItem)) -- 插入终点   
  23.      --位置数组   
  24.      --这里重要,是查找到的路径,还记的在node定义的father变量吗,路径就得靠它,每一个结点的   
  25.      --father属性都指向下一个结点,所以可以回溯出路径   
  26.      while(result.x)do  
  27.          local item = {x =result.x, y=result.y}   --把所有item连起来解释路径   
  28.          --coordinate.getPoint()是转换为cocos2d的坐标,用于精灵移动                 
  29.          table.insert(var.path ,  1 , coordinate.getPoint(map,item))   
  30.          result=result.father   
  31.      end    
  32.      --节点移动,这里是cocos2d-x 的结点移动,不会的不影响   
  33.      Noderun("",var)    
  34.  --路径 没找到   
  35.   else  
  36.      print("查找失败")   
  37.   end  

运行结果:

cocos2d-x lua A星寻路算法1

感谢 hm4123660 支持 磐实编程网 原文地址:
longpo.iteye.com/blog/2232330

文章信息

发布时间:2015-08-03

作者:hm4123660

发布者:aquwcw

浏览次数: