CocosLua3.10 A星算法(寻路算法)

参考文章：https://blog.csdn.net/zhulichen/article/details/78786493

主场景

local GameLayer = require('app.testFile.event.Key_5_Event_File.Layer.GameLayer')

local event = class('event', cc.Node)

function event:ctor()
    self:initValue()
    self:initLayer()
end

function event:initValue()
    self._GameLayer = nil
end

function event:initLayer()
    self._GameLayer = GameLayer:create()
    self:addChild(self._GameLayer)

    self._GameLayer:createLayer()
end

return event

创建界面

通过createModelData()方法，创建模板地图，标记的值为方块的类型
1.普通方块
2.障碍方块
3.起点
4.终点

这儿是由上至下的顺序，即左上角为(1,1)，然后根据方块的大小和定好的起始坐标来创建单个方块。

local GameNode = require('app.testFile.event.Key_5_Event_File.Node.GameNode')
local RoadCheck = require('app.testFile.event.Key_5_Event_File.Data.RoadCheck')
local Row = 12  -- 行
local Column = 8  -- 列
local Interval = 70  -- 区块间隔
local Start_Pos = cc.p(40, display.height)  --起始坐标
local TurnRound = 2  -- 限制转弯次数

local GameLayer = class('GameLayer', cc.Node)
function GameLayer:ctor()
    self:initValue()
    self:initData()
end

function GameLayer:initValue()
    self._modelTable = {}  -- 模板表(地图表)
    self._nodeTable = {}
    self._roadCheck = nil

    self._startPoint = cc.p(0, 0)
    self._endPoint = cc.p(0, 0)
end

function GameLayer:initData()
    self._roadCheck = RoadCheck:create(self, {Row = Row, Column = Column, TurnRound = TurnRound})
    self:addChild(self._roadCheck)
end

function GameLayer:createLayer()
    self._modelTable = self:createModelData()
    self:createNode()
    self._roadCheck:startCheck(self._startPoint, self._endPoint)
end

function GameLayer:createNode()
    if not self._modelTable or #self._modelTable <= 0 then
        return
    end

    for i, v in ipairs(self._modelTable) do
        local x = (i % Row == 0) and Row or i % Row
        local y = (i % Row == 0) and (i / Row) or math.floor(i / Row + 1)

        local data = {Value = v, Pos = cc.p(x, y)}
        local node = GameNode:create(data)
        self:addChild(node, 5)
        node:createNode()
        local str = string.format('%s_%s', x, y)
        self._nodeTable[str] = node

        if v == 3 then
            self._startPoint = cc.p(x, y)
        elseif v == 4 then
            self._endPoint = cc.p(x, y)
        end
    end
end

function GameLayer:getNodeByPos(_pos)
    local str = string.format('%s_%s', _pos.x, _pos.y)
    return self._nodeTable[str]
end

function GameLayer:createModelData()
    local temp = {
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
        1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 
        1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 
        1, 3, 1, 1, 1, 2, 1, 1, 1, 1, 4, 1, 
        1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 
        1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    }
    return temp
end

function GameLayer:getStartPos()
    return Start_Pos
end

function GameLayer:getInterval()
    return Interval
end
return GameLayer

单个方块

这儿将4种方块定为4种颜色，并另外新增两个颜色用于测试寻路和最终结果

--[[
    Value = (数值，方块的类型),
    Pos = (位置),
]]

local NodeSize = cc.size(60, 60)  -- 形块大小
local GameNode = class('GameNode', cc.Node)

local Color_Normal = cc.c3b(80, 80, 80)
local Color_Obstacle = cc.c3b(0, 0, 255)
local Color_Start = cc.c3b(255, 0, 0)
local Color_End = cc.c3b(0, 255, 0)

local Color_IsChecked = cc.c3b(255, 0, 0)
local Color_IsThroughed = cc.c3b(0, 255, 0)

local ColorTable = {
    Color_Normal,
    Color_Obstacle,
    Color_Start,
    Color_End,
}

function GameNode:ctor(data)
    self._data = data
    self:initValue()
end

function GameNode:initValue()
    self._layout = nil

    self._Value = self._data.Value or 1
    self._Pos = self._data.Pos or cc.p(0, 0)
    self._parentPos = cc.p(0, 0)

    self._text_F = nil
    self._text_G = nil
    self._text_H = nil

    self._value_G = 0
    self._value_H = 0
    self._value_F = self._value_G + self._value_H
end

function GameNode:createNode()
    self._layout = self:initNode(false)
    self:resetPosition()

    if self._Value == 1 then
        -- self:setText(2, 2)
        -- self:showText()
    end
end

function GameNode:initNode(isShowText)
    local layout = ccui.Layout:create()
    layout:setAnchorPoint(cc.p(0.5, 0.5))
    layout:setContentSize(NodeSize)
    layout:setBackGroundColorType(ccui.LayoutBackGroundColorType.solid) --设置颜色
    layout:setBackGroundColor(ColorTable[self._Value])
    self:addChild(layout)

    if isShowText then
        local text = ccui.Text:create()
        text:setString(string.format('%s', self._Value))
        text:setFontSize(32)
        self:addChild(text, 2)
    end

    return layout
end

function GameNode:setPosition(pos)
    if not pos or not pos.x or not pos.y then
        return
    end

    self._Pos = pos 
end

function GameNode:getPosition()
    return self._Pos
end

function GameNode:resetPosition()
    self:setPositionX(self:getParent():getStartPos().x + self:getParent():getInterval() * self._Pos.x)
    self:setPositionY(self:getParent():getStartPos().y - self:getParent():getInterval() * self._Pos.y)
end

function GameNode:showTextF(str)
    if not self._text_F then
        self._text_F = ccui.Text:create()
        self._text_F:setFontSize(18)
        self._text_F:setPosition(-self._layout:getContentSize().width/2 + 6, self._layout:getContentSize().height/2 - 8)
        self:addChild(self._text_F)
    end

    self._text_F:setString(string.format('%s', str))
end

function GameNode:showTextG(str)
    if not self._text_G then
        self._text_G = ccui.Text:create()
        self._text_G:setFontSize(18)
        self._text_G:setPosition(-self._layout:getContentSize().width/2 + 6, -self._layout:getContentSize().height/2 + 8)
        self:addChild(self._text_G)
    end

    self._text_G:setString(string.format('%s', str))
end

function GameNode:showTextH(str)
    if not self._text_H then
        self._text_H = ccui.Text:create()
        self._text_H:setFontSize(18)
        self._text_H:setPosition(self._layout:getContentSize().width/2 - 6, -self._layout:getContentSize().height/2 + 8)
        self:addChild(self._text_H)
    end

    self._text_H:setString(string.format('%s', str))
end

function GameNode:showText()
    self:showTextG(self._value_G)
    self:showTextH(self._value_H)
    self:showTextF(self._value_F)
end

function GameNode:setText(_g, _h)
    self._value_G, self._value_H, self._value_F = _g, _h, _g+_h
    self:showText()
end

function GameNode:getFValue()
    return self._value_F
end

function GameNode:getGValue()
    return self._value_G
end

-- 是否可以经过该点(即这个是不是障碍)
function GameNode:getIsCanMove()
    return self._Value == 1 or self._Value == 3 or self._Value == 4
end

function GameNode:setIsCheckedColor()
    self._layout:setBackGroundColor(Color_IsChecked)
end

function GameNode:setIsThroughedColor()
    self._layout:setBackGroundColor(Color_IsThroughed)
end

function GameNode:setParentPos(pos)
    self._parentPos = pos
end

function GameNode:getParentPos()
    return self._parentPos
end

return GameNode

寻路算法

OneRoadValue即方块间的权值，这里恒定为10。这儿只搜寻上下左右方向，不考虑斜线行走。

自我理解：获得当前的点，将定好的周围的点放于待查列表中(openList)(这里需要判断之前是否处于openList，有额外的特殊处理)，设置好父节点，并将当前点放于不需要查的列表中(closeList)，每次完成上面顺序后，获得当前openList最小的F值，并递归此方法，参数为最小的F值对应的节点(这里运用的是点，因人而异)。之后，如果将终点放置于openList中，则认为已获得结果。最后从终点依次获得父节点，得到终点->起点的顺序。

local OneRoadValue = 10

local RoadCheck = class('RoadCheck', cc.Node)

function RoadCheck:ctor(delegate, data)
    self._delegate = delegate
    self._startPos = nil
    self._endPos = nil

    self._openList = {}
    self._closeList = {}
end

function RoadCheck:startCheck(_startPos, _endPos)
    self._startPos = _startPos
    self._endPos = _endPos

    self:checkDiretion(self._startPos)
end

function RoadCheck:addToOpenTable(pos)
    local str = string.format('%s_%s', pos.x, pos.y)
    self._openList[str] = pos
end

function RoadCheck:checkIsInOpenTable(pos)
    local str = string.format('%s_%s', pos.x, pos.y)
    return self._openList[str]
end

function RoadCheck:removeInOpenTable(pos)
    local str = string.format('%s_%s', pos.x, pos.y)
    self._openList[str] = nil
end

function RoadCheck:addToCloseTable(pos)
    local str = string.format('%s_%s', pos.x, pos.y)
    self._closeList[str] = true
end

function RoadCheck:checkIsInCloseTable(pos)
    local str = string.format('%s_%s', pos.x, pos.y)
    return self._closeList[str]
end

-- 找到open表中最小的f值
function RoadCheck:getMinFPosInOpenTable()
    if table.nums(self._openList) == 0 then
        return false
    end

    local minPos = cc.p(0, 0)
    local minF = 99999
    for i, v in pairs(self._openList) do
        local node = self._delegate:getNodeByPos(v)
        if node:getFValue() < minF then
            minF = node:getFValue()
            minPos = v
        end
    end

    return minPos
end

-- 获得当前node的g值，根据当前寻路的节点获得
function RoadCheck:getGValueInThroughRoad(pPos)
    local gValue = OneRoadValue
    local node = self._delegate:getNodeByPos(pPos)
    gValue = gValue + node:getGValue()

    return gValue
end

function RoadCheck:isInEnd()
    return self:checkIsInOpenTable(self._endPos)
end

function RoadCheck:showRoad()
    local pos = self._endPos
    local action = nil
    local function fun()
        local node = self._delegate:getNodeByPos(pos)
        local pPos = node:getParentPos()
        local pNode = self._delegate:getNodeByPos(pPos)
        pNode:setIsThroughedColor()

        if pPos.x == self._startPos.x and pPos.y == self._startPos.y then
            if action then
                self:stopAction(action)
            end

            return
        end
        pos = pNode:getPosition()

        -- 不带延迟调用
        -- fun()        
    end

    -- 带延迟调用
    action = schedule(self, fun, 0.2)

    -- 不带延迟调用
    -- fun()
end

-- 添加到open表内
function RoadCheck:checkDiretion(currentPos)
    if self:isInEnd() then  -- 如果到达了终点
        self:showRoad()
        return
    end

    -- 添加到closeList，在openList中移除，插入到遍历表中
    self:addToCloseTable(currentPos)
    self:removeInOpenTable(currentPos)

    -- 改变当前的颜色
    local cNode = self._delegate:getNodeByPos(currentPos)
    cNode:setIsCheckedColor()

    local x, y = currentPos.x, currentPos.y
    local temp = {cc.p(x, y+1), cc.p(x, y-1), cc.p(x-1, y), cc.p(x+1, y)}  -- 上下左右

    for i, v in ipairs(temp) do
        local node = self._delegate:getNodeByPos(v)
        if node and node:getIsCanMove() and not self:checkIsInCloseTable(v) then  -- 如果有这个节点，并且可经过，并且不处于closelist里面，则放到openlist里面
            -- 检查是否在openlist中
            if self:checkIsInOpenTable(v) then
                if self:getGValueInThroughRoad(currentPos) < node:getGValue() then  -- 如果现在经过的点，比之前经过的点，G值还小，重新设置父节点和FGH值
                    node:setParentPos(currentPos)
                    local g = self:getGValueInThroughRoad(currentPos)
                    local h = (math.abs(v.x - self._endPos.x) + math.abs(v.y - self._endPos.y)) * OneRoadValue
                    node:setText(g, h)                  
                end
            else
                self:addToOpenTable(v)
                node:setParentPos(currentPos)
                local g = self:getGValueInThroughRoad(currentPos)
                local h = (math.abs(v.x - self._endPos.x) + math.abs(v.y - self._endPos.y)) * OneRoadValue
                node:setText(g, h)
            end
        end
    end

    local pos = self:getMinFPosInOpenTable()
    if not pos then
        return 
    end

    -- 带延迟调用
    -- local function fun()
    --  self:checkDiretion(pos)
    -- end

    -- performWithDelay(self, fun, 2)

    -- 不带延迟调用
    self:checkDiretion(pos)
end


return RoadCheck

A星.png

ε≡٩(๑>₃<)۶ 请大家多多评论一起讨论讨论