cocos2dxforluaA*寻路算法实现2

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› LUA›LUA教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

关于A＊算法的实现过程，简单来说就是一个计算权限的过程。

首先，创建一个地图节点类，"MapNode.lua"

 local MapNode = class("MapNode")
 
function MapNode:ctor()
    self._row = 0--行
    self._col = 0--列
    self._parent = nil--父节点
    self._f = 0--当前节点的总开销
    self._g = 0--当前节点的累计开销
    self._h = 0--启发因子
end

return MapNode

"AStar.lua"逻辑实现

local Direction = {}--方向
Direction.Right = 0
Direction.Right_Down = 1
Direction.Down = 2
Direction.Left_Down = 3
Direction.Left = 4
Direction.Left_Up = 5
Direction.Up = 6
Direction.Right_Up = 7

local MapNode = require "app.views.MapNode"

AStar = {}
AStar.__index = AStar

function AStar.create()
    local temp = {}
    setmetatable(temp, AStar)
    return temp
end

--mapData：二维数组，存放底图数据，0是可行走格子，1是有障碍格子
function AStar:init(mapData)
    self._mapData = mapData--地图数据
    
    self._map = {}
    self._lPath = {}--收集的路径
    self._bFind = false
    
    local mapRow = #mapData
    local mapCol = #mapData[1]

    for i = 0, mapRow -1 do
        self._map[i] = {}
        for j = 0, mapCol -1 do
            local mapNode = MapNode.new()
            mapNode._row = i
            mapNode._col = j
            self._map[i][j] = mapNode
        end
    end
end

--开始寻路
--from:开始格子位置（非坐标）
--to:目标格子位置
function AStar:getSearchPath(from, to)
    self:processAStar(from, to)--收集路径到_lPath
    return self._lPath
end

function AStar:canPass(row,col)--判断是否能够通过
    if self._mapData[col][row] == 0 then
        return true
    end
    return false
end
 
function AStar:getAdjacent(currentPos,dir)--根据方向获取相邻格子的位置
if dir == Direction.Right then
        return cc.p(currentPos.x + 1,currentPos.y)
    elseif dir == Direction.Right_Down then
        return cc.p(currentPos.x + 1,currentPos.y - 1)
    elseif dir == Direction.Down then
        return cc.p(currentPos.x,currentPos.y - 1)
    elseif dir == Direction.Left_Down then
        return cc.p(currentPos.x - 1,currentPos.y - 1)
    elseif dir == Direction.Left then
        return cc.p(currentPos.x - 1,currentPos.y)
    elseif dir == Direction.Left_Up then
        return cc.p(currentPos.x - 1,currentPos.y + 1)
    elseif dir == Direction.Up then
        return cc.p(currentPos.x,currentPos.y + 1)
    elseif dir == Direction.Right_Up then
        return cc.p(currentPos.x + 1,currentPos.y + 1)
end
end
 
function AStar:AStarCore(fromPos,toPos)--算法核心代码
    local open = {}
    local close = {}
    
    local targetNode = self._map[toPos.y][toPos.x]
    local fromNode = self._map[fromPos.y][fromPos.x]
    
    local f,g,h;
    fromNode._g = 0
    fromNode._h = math.abs(fromPos.x - toPos.x) +  math.abs(fromPos.y - toPos.y)
    fromNode._f = fromNode._h
    
    open[#open + 1] = fromNode
    while #open > 0 do
    local mapNode = open[1]
        table.remove(open,1)
    
    if mapNode._row == toPos.x and mapNode._col == toPos.y then
       return true
    end
    
    close[#close + 1]  = mapNode
    local parentPos = cc.p(mapNode._col,mapNode._row)
    local adjacentPos = nil
    local adjacentNode = nil
    
    for i = 0,7 do
            adjacentPos = self:getAdjacent(parentPos,i)
            if adjacentPos.x >= 0 and adjacentPos.x < mapCol and adjacentPos.y >= 0 and adjacentPos.y < mapRow then     
                adjacentNode = self._map[adjacentPos.y][adjacentPos.x]
                if self:canPass(adjacentPos.y,adjacentPos.x) == true and self:isContain(close,adjacentNode) == false and 
                    self:isContain(open,adjacentNode) == false then
                    if i % 2 == 0 then
                        g = adjacentNode._g + 1
                    else
                        g = adjacentNode._g + 1.4
                    end
                    h = math.abs(adjacentPos.x -toPos.x) + math.abs(adjacentPos.y - toPos.y)
                    f = g + h
                    
                    adjacentNode._parent = mapNode
                    adjacentNode._f = f
                    adjacentNode._g = g
                    adjacentNode._h = h
                    open[#open + 1] = adjacentNode
                end
            end
    end
    table.sort(open,function(a,b)
       return a._f < b._f
    end)
    end
    return false
end
 
function AStar:processAStar(from,to)--执行A*算法
    local f = self:AStarCore(from,to)
    if f ==  true then
        self:collectRoute(from,to)
        return true
    end
    return false
end
 
function AStar:collectRoute(from, to)--收集路线
    self._lPath = {}
    local mapNode = self._map[to.y][to.x]
    self._lPath[#self._lPath + 1] = mapNode
    while mapNode._col ~= from.x or mapNode._row ~= from.y do
        mapNode = mapNode._parent
        self._lPath[#self._lPath + 1] = mapNode
    end
end
 
function AStar:isContain(tbl,cell) --在table中是否包含某个单元
    for k,v in pairs(tbl) do
        if tbl[k] == cell then
            return true
        end
    end
    return false
end

测试一下：

TestScene.lua

require "AStar.lua"
local TestScene = class("TestScene",cc.load("mvc").ViewBase)

function TestScene:ctor()
    local mapData = {
    {0, 0, 0, 0, 0, 0, 0, 0}
    {0, 0, 0, 0, 0, 0, 0, 0}
    {0, 0, 1, 1, 0, 0, 0, 0}
    {0, 0, 1, 0, 1, 0, 0, 0}
    {0, 0, 0, 1, 0, 1, 0, 0}
    {0, 0, 0, 0, 0, 0, 0, 0}
    {0, 0, 0, 0, 0, 0, 0, 0}
    {0, 0, 0, 0, 0, 0, 0, 0}
    }--地图数据
 
    self.mapData = mapData
    for i = 1, #mapData do--创建地图快图片
        for j = 1, #mapData[1] do
            local tileSp = cc.Sprite:create("tilemap.png")
            self:addChild(tileSp)
            tileSp:setPosition(i * tileWidth-(tileWidth * 0.5), j * tileHeight - (tileWidth * 0.5))
        end
    end
    
    local from = cc.p(0,0)--起点
    local to = cc.p(7,8)--目标点
    local sp1 = display.newSprite("qizi.png",to.x *tileWidth+(tileWidth*0.5),to.y *tileHeight+(tileWidth*0.5))--目标点图片
    self:addChild(sp1)
    
    local sp2 = display.newSprite("qizi.png",from.x *tileWidth+(tileWidth*0.5),from.y *tileHeight+(tileWidth*0.5))--起点图片
    self:addChild(sp2)
    
    self:setCollisionSp()
    
    self._sprite = sp.SkeletonAnimation:create("spine/116_m_fks/116_m_fks.json","spine/116_m_fks/116_m_fks.atlas",0.08)
    self._sprite:setAnimation(0,"stanby_1",true)--创建角色
    self._sprite:setScale(-1,1)
    self._sprite:setPosition(from.x *tileWidth+(tileWidth*0.5),from.y *tileHeight)
    self:addChild(self._sprite)
    
    local astar_logic = AStar.create()
    astar_logic:init(mapData)
    self._lPath = astar_logic:getSearchPath(from, to)
    self:drawPathNode()
    self._posIndex = #self._lPath
    self:moveSprite()
end

function TestScene:setCollisionSp()--设置障碍物
    for k, v in pairs(self.mapData) do
        for m, n in pairs(v) do
            if n == 1 then--障碍物
                local sp = display.newSprite("collision.png",i*tileWidth+(tileWidth*0.5),j*tileHeight+(tileWidth*0.5))
                self:addChild(sp)
            end
        end
    end
end

function TestScene:moveSprite()--移动精灵
    local x = self._lPath[self._posIndex]._col *tileWidth+(tileWidth*0.5)
    local y = self._lPath[self._posIndex]._row *tileWidth+(tileWidth*0.5)
    transition.moveTo(self._sprite,{x = x,y = y,time = 1,onComplete = function() 
        self._posIndex = self._posIndex - 1
        if self._posIndex == 0 then
            return
        end
        self:moveSprite()
    end})
end

function TestScene:drawPathNode()--画路径图片
    for k,v in pairs(self._lPath) do
        local sp3 = display.newSprite("redPoint.png",v._col *tileWidth+(tileWidth*0.5),v._row  *tileWidth+(tileWidth*0.5))
        self:addChild(sp3)
    end
end