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

主場(chǎng)景

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

創(chuàng)建界面

通過createModelData()方法，創(chuàng)建模板地圖，標(biāo)記的值為方塊的類型
1.普通方塊
2.障礙方塊
3.起點(diǎn)
4.終點(diǎn)

這兒是由上至下的順序，即左上角為(1,1)，然后根據(jù)方塊的大小和定好的起始坐標(biāo)來創(chuàng)建單個(gè)方塊。

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  -- 區(qū)塊間隔
local Start_Pos = cc.p(40, display.height)  --起始坐標(biāo)
local TurnRound = 2  -- 限制轉(zhuǎn)彎次數(shù)

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

單個(gè)方塊

這兒將4種方塊定為4種顏色，并另外新增兩個(gè)顏色用于測(cè)試尋路和最終結(jié)果

--[[
    Value = (數(shù)值，方塊的類型),
    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) --設(shè)置顏色
    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

-- 是否可以經(jīng)過該點(diǎn)(即這個(gè)是不是障礙)
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即方塊間的權(quán)值，這里恒定為10。這兒只搜尋上下左右方向，不考慮斜線行走。

自我理解：獲得當(dāng)前的點(diǎn)，將定好的周圍的點(diǎn)放于待查列表中(openList)(這里需要判斷之前是否處于openList，有額外的特殊處理)，設(shè)置好父節(jié)點(diǎn)，并將當(dāng)前點(diǎn)放于不需要查的列表中(closeList)，每次完成上面順序后，獲得當(dāng)前openList最小的F值，并遞歸此方法，參數(shù)為最小的F值對(duì)應(yīng)的節(jié)點(diǎn)(這里運(yùn)用的是點(diǎn)，因人而異)。之后，如果將終點(diǎn)放置于openList中，則認(rèn)為已獲得結(jié)果。最后從終點(diǎn)依次獲得父節(jié)點(diǎn)，得到終點(diǎn)->起點(diǎn)的順序。

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

-- 獲得當(dāng)前node的g值，根據(jù)當(dāng)前尋路的節(jié)點(diǎn)獲得
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()

        -- 不帶延遲調(diào)用
        -- fun()        
    end

    -- 帶延遲調(diào)用
    action = schedule(self, fun, 0.2)

    -- 不帶延遲調(diào)用
    -- fun()
end

-- 添加到open表內(nèi)
function RoadCheck:checkDiretion(currentPos)
    if self:isInEnd() then  -- 如果到達(dá)了終點(diǎn)
        self:showRoad()
        return
    end

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

    -- 改變當(dāng)前的顏色
    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  -- 如果有這個(gè)節(jié)點(diǎn)，并且可經(jīng)過，并且不處于closelist里面，則放到openlist里面
            -- 檢查是否在openlist中
            if self:checkIsInOpenTable(v) then
                if self:getGValueInThroughRoad(currentPos) < node:getGValue() then  -- 如果現(xiàn)在經(jīng)過的點(diǎn)，比之前經(jīng)過的點(diǎn)，G值還小，重新設(shè)置父節(jié)點(diǎn)和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

    -- 帶延遲調(diào)用
    -- local function fun()
    --  self:checkDiretion(pos)
    -- end

    -- performWithDelay(self, fun, 2)

    -- 不帶延遲調(diào)用
    self:checkDiretion(pos)
end


return RoadCheck

A星.png

ε≡?(?>?<)? 請(qǐng)大家多多評(píng)論一起討論討論