CocosLua3.10 连连看(深度算法和A星算法)

参考文章：泰课消消乐详解：https://www.taikr.com/article/1967
参考文章：A星算法：https://blog.csdn.net/zhulichen/article/details/78786493

主界面：

用于添加地图，游戏逻辑，处理连线，转消息和数据等。
ps. 连线这里运用的是改变layout的size，也可以用进度条或者动画等

local InvisibleWall = true  -- 隐藏墙,经过的路(测试用)

local MapLayer = require('app.testFile.event.Key_4_Event_File.Layer.MapLayer')
local RoadCheckByDepth = require('app.testFile.event.Key_4_Event_File.Data.RoadCheckByDepth')
local RoadCheckByAStar = require('app.testFile.event.Key_4_Event_File.Data.RoadCheckByAStar')

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

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

function event:initValue()
    self._MapLayer = nil
    self._roadCheck = nil
end

function event:initLayer()
    self._MapLayer = MapLayer:create(self)
    self:addChild(self._MapLayer)

    self._MapLayer:createMap()
end

function event:initData()
    -- self._roadCheck = RoadCheckByDepth:create(self, {Row = self._MapLayer:getRow(), Column = self._MapLayer:getColumn(), TurnTotalCount = self._MapLayer:getTurnTotalCount()})  -- 深度算法
    self._roadCheck = RoadCheckByAStar:create(self, {Row = self._MapLayer:getRow(), Column = self._MapLayer:getColumn(), TurnTotalCount = self._MapLayer:getTurnTotalCount()})  -- A星算法
    self:addChild(self._roadCheck)
end

function event:getNode(_x, _y)
    return self._MapLayer:getNode(_x, _y)
end

function event:getNodeByPos(_pos)
    return self._MapLayer:getNodeByPos(_pos)
end

function event:getNodeValeByPos(_pos)
    return self._MapLayer:getNodeValeByPos(_pos)
end

function event:getNodeValue(_x, _y)
    return self._MapLayer:getNodeValue(_x, _y)
end

-- 检查是否连
function event:checkIsLink(lastPos, currentPos)
    if not lastPos or not currentPos then
        self:linkReturn(false, currentPos)
        return
    end

    local isLink = false
    dump(lastPos, 'lastpos..')
    dump(currentPos, 'currentPos..')
    print('Click..')

    self._roadCheck:startRoadCheck(lastPos, currentPos)
end

-- 查询返回
function event:linkReturn(_value, cPos)
    self._MapLayer:resetToWall(self._MapLayer:getLastPos(), cPos)
    if _value then
        self:doRemoveTrueReset(cPos)
    else
        self._MapLayer:doClickCurrentNode(cPos)
    end
end

function event:doRemoveTrueReset(cPos)
    self:removeNode(self._MapLayer:getLastPos(), cPos)
end

function event:removeNode(pos1, pos2)
    local function endCallback()
        local node1 = self._MapLayer:getNode(pos1.x, pos1.y)
        local node2 = self._MapLayer:getNode(pos2.x, pos2.y)

        self._MapLayer:setNodeValue(pos1.x , pos1.y, false)
        self._MapLayer:setNodeValue(pos2.x , pos2.y, false)

        if node1 then
            node1:resetToWall()
            node1:setVisible(not InvisibleWall and true or false)
        end

        if node2 then
            node2:resetToWall()
            node2:setVisible(not InvisibleWall and true or false)
        end

        self:setDefaultState()
    end

    dump(self._roadCheck:getLineTable(), 'lineTable')
    self:drawLine(endCallback)
end

-- 画线
function event:drawLine(endFunc)
    local lineTable = self._roadCheck:getLineTable()
    if not lineTable or #lineTable <= 1 then
        return
    end

    local idx = 1
    local temp = {}
    local function draw(t1, t2)
        local layout = ccui.Layout:create()
        layout:setAnchorPoint(cc.p(0, 0.5))
        layout:setPosition(self._MapLayer:getInterval() * lineTable[t1].x + self._MapLayer:getStartPos().x, self._MapLayer:getInterval() * lineTable[t1].y + self._MapLayer:getStartPos().y)

        layout:setContentSize(cc.size(0, 4))
        layout:setBackGroundColorType(ccui.LayoutBackGroundColorType.solid) --设置颜色
        layout:setBackGroundColor(cc.c3b(255, 255, 255))
        layout.progress = 0

        self:addChild(layout, 10)
        table.insert(temp, layout)

        local r = self:getAngleByPos(lineTable[t1], lineTable[t2])
        layout:setRotation(-r)

        local time = 0.002
        local seq = cc.Sequence:create(
            -- cc.DelayTime:create(time),
            cc.CallFunc:create(function()
                layout.progress = layout.progress + 25
                layout:setContentSize(cc.size(layout.progress * 0.01 * self._MapLayer:getInterval(), 4))

                if layout.progress == 100 then
                    layout:stopAllActions()

                    idx = idx + 1
                    if idx ~= #lineTable then
                        draw(idx, idx+1)
                    else
                        for i, v in ipairs(temp) do
                            v:removeFromParent()
                            temp = {}
                        end

                        if endFunc then
                            endFunc()
                        end
                    end
                end
            end)
        )
        local action = cc.RepeatForever:create(seq)
        layout:runAction(action)
    end

    draw(idx, idx+1)
end

function event:getAngleByPos(pos1, pos2)
    if not pos1 or not pos2 then
        return 0
    end

    local p = {}  
    p.x = pos2.x - pos1.x  
    p.y = pos2.y - pos1.y  

    local r = math.atan2(p.y, p.x) * 180 / math.pi
    return r
end

function event:setDefaultState()
    self._MapLayer:setDefaultState()
    self._roadCheck:setDefaultState()
end

function event:getRoadCheck()
    return self._roadCheck
end

function event:getInvisibleWall()
    return InvisibleWall
end
return event

地图：

创建游戏行*列个地图节点，创建外部围墙，和可点击事件

local GameNode = require('app.testFile.event.Key_4_Event_File.Node.GameNode')

local Row = 8  -- 行
local Column = 8  -- 列
local TypeCount = 6  -- 类型种数
local Interval = 70  -- 区块间隔
local Start_Pos = cc.p(160, 0)  --起始坐标
local TurnTotalCount = 2  -- 限制转弯次数

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

function MapLayer:initValue()
    self._isCheck = false  -- 可检查(点击完第一个变为true)
    self._lastPos = nil  -- 上个坐标

    self._modelTable = {}  -- 模板表(地图表)
    self._nodeTable = {}  -- 可点击的所有节点表
    self._nodeValueTable = {}  -- 记录位置是否有值
    self._currentClickNode = nil  -- 点击的点(独一个)

    self._wallTable = {}  -- 外墙
end

function MapLayer:initData()

end

function MapLayer:createMap()
    if not self:isCanBeModelMap() then
        print('行列需要组成偶数才行喔xD 重新配吧')
        return
    end

    self:createNormalLayer()
    self._modelTable = self:createModelData()
    self:createNode()
    self:createCurrentClickNode()
end

function MapLayer:createNormalLayer()
    local layout = ccui.Layout:create()
    layout:setContentSize(cc.size(display.width, display.height))
    layout:setTouchEnabled(true)
    self:addChild(layout, 1)

    local function callback(sender, eventType)
        if eventType == ccui.TouchEventType.ended then
            self._delegate:setDefaultState()
        end
    end
        
    layout:addTouchEventListener(callback)
end

function MapLayer:setDefaultState()
    self._lastPos = nil
    self._isCheck = false
    self._currentClickNode:setVisible(false)
end

function MapLayer:isCanBeModelMap()
    return (Row * Column) % 2 == 0
end

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

    -- 围墙
    for x = 0, Row+1 do
        for y = 0, Column+1 do
            if x == 0 or x == Row+1 or y == 0 or y == Column+1 then
                local data = {Value = 0, Pos = cc.p(x, y)}
                local node = GameNode:create(data)
                self:addChild(node, 5)
                node:createWallNode()
                self:setNode(x, y, node)
                table.insert(self._wallTable, node)
                node:setVisible(not self._delegate:getInvisibleWall() and true or false)
            end
        end
    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)

        if v ~= -1 then
            node:createNormalNode()
            self:setNode(x, y, node)
            self:setNodeValue(x, y, true)
        else
            node:createWallNode()
            self:setNode(x, y, node)            
        end
    end
end

function MapLayer:setNode(_x, _y, _node)
    if not _x or not _y or not _node then
        return
    end

    local str = string.format('%s_%s', _x, _y)
    self._nodeTable[str] = _node
end

function MapLayer:getNode(_x, _y)
    if not _x or not _y then
        return
    end

    local str = string.format('%s_%s', _x, _y)
    return self._nodeTable[str]
end

function MapLayer:getNodeByPos(_pos)
    return self:getNode(_pos.x, _pos.y)
end

function MapLayer:setNodeValue(_x, _y, _value)
    if not _x or not _y then
        return
    end

    local str = string.format('%s_%s', _x, _y)
    self._nodeValueTable[str] = _value or false
end

function MapLayer:getNodeValeByPos(_pos)
    return self:getNodeValue(_pos.x, _pos.y)
end

function MapLayer:getNodeValue(_x, _y)
    if not _x or not _y then
        return
    end

    local str = string.format('%s_%s', _x, _y)
    return self._nodeValueTable[str] and true or false
end

function MapLayer:createModelData()
    local data = {}
    for i = 1, (Row * Column) / 2 do
        local random = math.random(1, TypeCount)
        table.insert(data, random)
        table.insert(data, random)
    end

    local newData = self:upsetData(data)
    return newData
end

function MapLayer:upsetData(_data)
    local temp = {}
    local idx = 1
    while (idx <= #_data and #temp <= #_data) do
        local random = math.random(1, #_data)
        table.insert(temp, _data[random])
        idx = idx + 1
    end

    return temp
end

function MapLayer:createCurrentClickNode()
    local data = {Value = -1, Pos = cc.p(0, 0)}
    self._currentClickNode = GameNode:create(data)
    self:addChild(self._currentClickNode, 5)
    self._currentClickNode:createCurrentNode()
end

function MapLayer:doClickEvent(cPos)
    self:resetCurrentClickPosition(cPos)
    self:checkIsTheSecondClick(cPos)
end

function MapLayer:checkIsTheSecondClick(cPos)
    if self._isCheck and self:checkIsTheSameValue(self._lastPos, cPos) then
        self._delegate:checkIsLink(self._lastPos, cPos)
    else
        -- 没选择前一个
        self:doClickCurrentNode(cPos)
    end
end

function MapLayer:checkIsTheSameValue(pos1, pos2)
    local node1 = self:getNode(pos1.x, pos1.y)
    local node2 = self:getNode(pos2.x, pos2.y)

    if not node1 or not node2 then
        return
    end

    return node1:getValue() == node2:getValue()
end

function MapLayer:resetCurrentClickPosition(cPos)
    if not self._currentClickNode then
        return
    end

    self._currentClickNode:setPos(cPos)
    self._currentClickNode:resetPos()
end

function MapLayer:resetIsCheck()
    self._isCheck = not self._isCheck
end


function MapLayer:doClickCurrentNode(cPos)
    if self._lastPos then
        self:getNodeByPos(self._lastPos):setIsTheNormalColor()
    end

    if cPos then
        self:getNodeByPos(cPos):setIsTheNormalColor()
    end

    self._currentClickNode:setVisible(true)
    self._lastPos = cPos
    self._isCheck = true
    self._delegate:getRoadCheck():setDefaultState()
end

-- 重置为可移动的点
function MapLayer:resetToWall(_lastPos, _currentPos)
    for i, v in ipairs(self._wallTable) do
        v:resetToWall()
    end

    if self._delegate:getRoadCheck().getOpenList then
        for i, v in pairs(self._delegate:getRoadCheck():getOpenList()) do
            self:getNodeByPos(v):resetToWall()
        end
    end

    if self._delegate:getRoadCheck().getCloseList then
        for i, v in pairs(self._delegate:getRoadCheck():getCloseList()) do
            if not (v.x == _lastPos.x and v.y == _lastPos.y) and not (v.x == _currentPos.x and v.y == _currentPos.y) then  -- 如果不是起点也不是终点
                self:getNodeByPos(v):resetToWall()
            end
        end
    end
end

function MapLayer:getStartPos()
    return Start_Pos
end

function MapLayer:getInterval()
    return Interval
end

function MapLayer:getRow()
    return Row
end

function MapLayer:getColumn()
    return Column
end

function MapLayer:getTurnTotalCount()
    return TurnTotalCount
end

function MapLayer:getLastPos()
    return self._lastPos
end

return MapLayer

单个节点

--[[
    Value = (数值),
    Pos = (位置),

    F = G + H + J (权值，3个数值相加。 获得下个计算点是通过最小的F值来获得)
    G (从起点经过父节点到该点的权值)
    H (该点到目标点的权值(估算值))
    J (获得该点的所有下一个移动点(openlist中)，如果可移动点与父节点到该点的方向不同，则++1)
]]

local NodeSize = cc.size(60, 60)  -- 形块大小

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

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

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 = nil

    self._text = nil
    self._text_F = nil
    self._text_G = nil
    self._text_H = nil
    self._text_J = nil

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

function GameNode:createNormalNode()
    self._layout = self:initNode(false, true)
    self:resetPos()
    self:bindEvent()
end

function GameNode:createWallNode()
    self._layout = self:initNode(true, false)
    self:resetPos()
end

function GameNode:initNode(isWall, isShowText)
    local layout = ccui.Layout:create()
    layout:setAnchorPoint(cc.p(0.5, 0.5))
    layout:setContentSize(isWall and cc.size(50, 50) or NodeSize)
    layout:setBackGroundColorType(ccui.LayoutBackGroundColorType.solid) --设置颜色
    layout:setBackGroundColor(isWall and cc.c3b(40, 40, 40) or cc.c3b(80, 80, 80))
    layout:setTouchEnabled(true)
    self:addChild(layout)

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

    return layout
end

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

    self._Pos = pos 
end

function GameNode:getPos()
    return self._Pos
end

function GameNode:resetPos()
    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:bindEvent()
    if not self._layout then
        return
    end

    local function callback(sender, eventType)
        if eventType == ccui.TouchEventType.ended then
            self:clickEvent()
        end
    end
        
    self._layout:addTouchEventListener(callback)  
end

function GameNode:clickEvent()
    self:getParent():doClickEvent(self._Pos)
end

function GameNode:createCurrentNode()
    self._layout = ccui.ImageView:create('res/frame.png')
    self:addChild(self._layout)
    self:setVisible(false)
end

function GameNode:getValue()
    return self._Value
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:setVisible(true)
    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:setVisible(true)
    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:setVisible(true)
    self._text_H:setString(string.format('%s', str))
end

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

    self._text_J:setVisible(true)
    self._text_J:setString(string.format('%s', str))
end

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

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

function GameNode:getFValue()
    return self._value_F
end

function GameNode:getGValue()
    return self._value_G
end

function GameNode:getJValue()
    return self._value_J
end

function GameNode:getAngleByPos(pos1, pos2)
    if not pos1 or not pos2 then
        return 0
    end

    local p = {}  
    p.x = pos2.x - pos1.x  
    p.y = pos2.y - pos1.y  

    local r = math.atan2(p.y, p.x) * 180 / math.pi
    return r
end

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

function GameNode:getParentPos()
    return self._parentPos
end

-- 测试用，设置为查找，红色(A星查找)
function GameNode:setIsCheckedColor()
    self._layout:setBackGroundColor(Color_IsChecked)
end

-- 测试用，设置为最终经过，绿色(A星查找)
function GameNode:setIsThroughedColor()
    self._layout:setBackGroundColor(Color_IsThroughed)
end

-- 设置为普通
function GameNode:setIsTheNormalColor()
    self._layout:setBackGroundColor(cc.c3b(80, 80, 80))
end

-- 改变为墙
function GameNode:resetToWall()
    self._layout:setBackGroundColor(cc.c3b(40, 40, 40))
    self._layout:setTouchEnabled(false)

    self._value_G, self._value_H, self._value_F = 0, 0, 0

    if self._text_F then
        self._text_F:setVisible(false)
    end
    if self._text_G then
        self._text_G:setVisible(false)
    end
    if self._text_H then
        self._text_H:setVisible(false)
    end
    if self._text_J then
        self._text_J:setVisible(false)
    end
    if self._text then
        self._text:setVisible(false)
    end

    if self._ptext then
        self._ptext:setVisible(false)
    end
end

-- 获得父节点到这个节点的方向
function GameNode:getDirInParentToHere()
    if not self._parentPos then
        return
    end

    if self._Pos.x - self._parentPos.x > 0 then
        return 'right'
    elseif self._Pos.x - self._parentPos.x < 0 then
        return 'left'
    elseif self._Pos.y - self._parentPos.y < 0 then
        return 'down'
    elseif self._Pos.y - self._parentPos.y > 0 then
        return 'up'
    end

    return
end

-- 显示指向父节点的text ui
function GameNode:showParentTag()
    if not self._ptext then
        self._ptext = ccui.Text:create()
        self._ptext:setString(string.format('个'))
        self._ptext:setFontSize(26)
        self:addChild(self._ptext, 2)
    end

    local angle = self:getAngleByPos(self._Pos, self._parentPos)
    self._ptext:setVisible(true)
    self._ptext:setRotation(-angle + 90)
end

return GameNode

算法相关

深度算法 查看checkRoadLink()方法：

深度算法是我使用的第一种写法，代码中包含两种写法。
1.一种是获得终点后，直接把经过的点(路，只记录最终经过的。途中经过的会被for给返回，不添加到currentVisit内)，然后直接赋值给self._lineTable，直接返回
2.另一种是找到终点后，递归返回添加到self._lineTable数据里面。

ps. xD因为第二种是我一开始写的，就一直保留着了，然后通过高人学习到第一种也可以。两种比较后，感觉第1种比较好理解。
ps+. 代码中有很多showPrint，showDump等测试代码，可以通过关闭开关ShowPrint，不打印这些测试日志。

local Row = 0
local Column = 0
local TurnTotalCount = 0
local ShowPrint = false  -- 打印，不用在意在意这个，其实就是print和dump，加个开关打印测试日志而已

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

function RoadCheckByDepth:ctor(delegate, data)
    self._delegate = delegate
    self._data = data
    self:initValue()
end

function RoadCheckByDepth:initValue()
    self._startPos = nil
    self._endPos = nil

    self._lineTable = {}
    self._currentStep = -1
    Row = self._data.Row or 0
    Column = self._data.Column or 0
    TurnTotalCount = self._data.TurnTotalCount or 0
end

function RoadCheckByDepth:startRoadCheck(lastPos, currentPos)
    self._startPos = lastPos
    self._endPos = currentPos
    self:checkRoadLink(lastPos, currentPos, 0, 1, 0)

    self._delegate:linkReturn(self._currentStep > 0, self._endPos)
end

-- 通过改变pos1，来找到是否与pos2匹配
--[[
    currentVisit = {
        visitPosTableInKey = {}  -- 记录保存过的坐标(放于key中，无序)
        visitPosTableInValue = {}   -- 记录保存过的坐标(放于Value中，有序)
    }
]]

-- 通过传的当前遍历顺序，直接遇到结果后直接插入(深度遍历算法)
function RoadCheckByDepth:checkRoadLink(pos1, pos2, count, direction, index, currentVisit)
    local x1, y1 = pos1.x, pos1.y
    local x2, y2 = pos2.x, pos2.y

    local dirText = {'左', '上', '右', '下'}
    self:showPrint('调用GameLayer:checkRoadLink 当前位置是', 'x='..x1, 'y='..y1, '当前弯数='..count, '当前方向='..dirText[direction], '当前步数='..index)

    if x1 < 0 or x1 > Row+1 or y1 < 0 or y1 > Column+1 then  -- 不允许超出界外两格检测
        self:showPrint('return false 超出界面 *****************************')
        return false
    end

    if count then
        if count > TurnTotalCount then
            self:showPrint('return false 超出转弯数 *****************************')
            return false
        end
    end

    if index then
        if self._currentStep ~= -1 and index >= self._currentStep then
            self:showPrint('return false 步数比上个太多 *****************************')
            return false
        end
    end

    -- 记录当前访问过的数据(这里只计划记录之前所保存的，而不是包括其他的时候，如果想把其他情况给记录，如果希望如此，则把下面的cVisit.visitPosTableInKey[keyStr] = nil注释掉即可)
    local cVisit = currentVisit and currentVisit or {visitPosTableInKey = {}, visitPosTableInValue = {}}
    local isStartPos = (self._startPos.x == x1 and self._startPos.y == y1)
    if not isStartPos and self._delegate:getNodeValue(x1, y1) then
        if x1 == x2 and y1 == y2 then
            self:showPrint('有节点 并且遇到最终目标')
            self:showPrint('return true 两值相等 *****************************',  '当前是', x1, y1)
            self:showPrint('清除所有self._lineTable !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!')
            self._lineTable = {}

            self:showPrint('添加数据', pos1.x, pos1.y,'++++++++++++++++++++++++++++++++==')

            table.insert(cVisit.visitPosTableInValue, pos1)
            self._lineTable = clone(cVisit.visitPosTableInValue)
            table.remove(cVisit.visitPosTableInValue, #cVisit.visitPosTableInValue)

            self._currentStep = index + 1
            self:showPrint('一共', self._currentStep, '步')

            self:showDump(cVisit, 'cVisit>>>>')

            return true
        end

        self:showPrint('有节点 没有遇到最终目标')
        return false
    end

    local keyStr = string.format('%s_%s', x1, y1)
    if cVisit.visitPosTableInKey[keyStr] then
        self:showPrint('return false 该节点访问过了 *******************************************************', keyStr)
        return false
    end
    cVisit.visitPosTableInKey[keyStr] = true
    table.insert(cVisit.visitPosTableInValue, pos1)

    local temp = {cc.p(x1-1, y1), cc.p(x1, y1+1), cc.p(x1+1, y1), cc.p(x1, y1-1)}   -- 左上右下
    for i, v in ipairs(temp) do
        self:showPrint('\n')
        self:showPrint('执行循环', i, '当前是', x1, y1)

        local keyStr = string.format('%s_%s', v.x, v.y)

        if not isStartPos then
            if direction ~= i then
                self:showPrint('direction是', direction, 'i是', i, '不相等 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')
                self:showPrint('index = ', index, '当前是', x1, y1)

                self:checkRoadLink(v, pos2, count+1, i, index + 1, cVisit)
            else
                self:showPrint('direction是', direction, 'i是', i, '相等 ==================================')
                self:showPrint('index = ', index, '当前是', x1, y1)
                self:checkRoadLink(v, pos2, count, i, index + 1, cVisit)
            end
        else
            self:checkRoadLink(v, pos2, count, i, index + 1, cVisit)
        end
    end

    cVisit.visitPosTableInKey[keyStr] = nil
    table.remove(cVisit.visitPosTableInValue, #cVisit.visitPosTableInValue)

    self:showPrint('检查完毕', self._currentStep > 0)
    return false
end

-- 通过isEnd来判断是否结束，添加数据
-- function RoadCheckByDepth:checkRoadLink(pos1, pos2, count, direction, index, currentVisit)
--  local x1, y1 = pos1.x, pos1.y
--  local x2, y2 = pos2.x, pos2.y

--  local dirText = {'左', '上', '右', '下'}
--  self:showPrint('调用GameLayer:checkRoadLink 当前位置是', 'x='..x1, 'y='..y1, '当前弯数='..count, '当前方向='..dirText[direction], '当前步数='..index)

--  if x1 < 0 or x1 > Row+1 or y1 < 0 or y1 > Column+1 then  -- 不允许超出界外两格检测
--      self:showPrint('return false 超出界面 *****************************')
--      return false
--  end

--  if count then
--      if count > TurnTotalCount then
--          self:showPrint('return false 超出转弯数 *****************************')
--          return false
--      end
--  end

--  if index then
--      if self._currentStep ~= -1 and index >= self._currentStep then
--          self:showPrint('return false 步数比上个太多 *****************************')
--          return false
--      end
--  end

--  local isStartPos = (self._startPos.x == x1 and self._startPos.y == y1)
--  if not isStartPos and self._delegate:getNodeValue(x1, y1) then
--      if x1 == x2 and y1 == y2 then
--          self:showPrint('有节点 并且遇到最终目标')
--          self:showPrint('return true 两值相等 *****************************',  '当前是', x1, y1)
--          self:showPrint('清除所有self._lineTable !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!')
--          self._lineTable = {}

--          self:showPrint('添加数据', pos1.x, pos1.y,'++++++++++++++++++++++++++++++++==')
--          table.insert(self._lineTable, 1, pos1)

--          self._currentStep = index + 1
--          self:showPrint('一共', self._currentStep, '步')

--          self:showDump(currentVisit, 'currentVisit>>>>')

--          return true
--      end

--      self:showPrint('有节点 没有遇到最终目标')
--      return false
--  end
    
--  -- 记录当前访问过的数据(这里只计划记录之前所保存的，而不是包括其他的时候，如果想把其他情况给记录，如果希望如此，则把下面的cVisit.visitPosTableInKey[keyStr] = nil注释掉即可)
--  local cVisit = currentVisit and currentVisit or {visitPosTableInKey = {}, visitPosTableInValue = {}}
--  local keyStr = string.format('%s_%s', x1, y1)
--  if cVisit.visitPosTableInKey[keyStr] then
--      self:showPrint('return false 该节点访问过了 *******************************************************', keyStr)
--      return false
--  end
--  cVisit.visitPosTableInKey[keyStr] = true
--  table.insert(cVisit.visitPosTableInValue, pos1)

--  local temp = {cc.p(x1-1, y1), cc.p(x1, y1+1), cc.p(x1+1, y1), cc.p(x1, y1-1)}   -- 左上右下
--  local isEnd = false
--  local tag = false

--  for i, v in ipairs(temp) do
--      self:showPrint('\n')
--      self:showPrint('执行循环', i, '当前是', x1, y1)

--      local keyStr = string.format('%s_%s', v.x, v.y)

--      if not isStartPos then
--          if direction ~= i then
--              self:showPrint('direction是', direction, 'i是', i, '不相等 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')
--              self:showPrint('index = ', index, '当前是', x1, y1)

--              tag = self:checkRoadLink(v, pos2, count+1, i, index + 1, cVisit)
--              isEnd = isEnd and isEnd or tag  -- 当isEnd为true就一直保持为true状态
--              self:showPrint('isEnd', isEnd)
--          else
--              self:showPrint('direction是', direction, 'i是', i, '相等 ==================================')
--              self:showPrint('index = ', index, '当前是', x1, y1)
--              tag = self:checkRoadLink(v, pos2, count, i, index + 1, cVisit)
--              isEnd = isEnd and isEnd or tag  -- 当isEnd为true就一直保持为true状态
--          end
--      else
--          tag = self:checkRoadLink(v, pos2, count, i, index + 1, cVisit)
--          isEnd = isEnd and isEnd or tag  -- 当isEnd为true就一直保持为true状态
--      end
--  end
    
--  if self._currentStep > 0 and isEnd then
--      self:showPrint('添加数据', pos1.x, pos1.y,'++++++++++++++++++++++++++++++++==')
--      table.insert(self._lineTable, 1, pos1)
--  end

--  cVisit.visitPosTableInKey[keyStr] = nil
--  table.remove(cVisit.visitPosTableInValue, #cVisit.visitPosTableInValue)

--  self:showPrint('检查完毕', self._currentStep > 0)
--  return isEnd, (self._currentStep > 0)
-- end


function RoadCheckByDepth:getLineTable()
    return self._lineTable
end

function RoadCheckByDepth:getCurrentStep()
    return self._currentStep
end

function RoadCheckByDepth:setDefaultState()
    self._lineTable = {}
    self._currentStep = -1
end

function RoadCheckByDepth:showPrint(...)
    if not ShowPrint then
        return
    end

    print(...)
end

function RoadCheckByDepth:showDump(...)
    if not ShowPrint then
        return
    end

    dump(...)
end
return RoadCheckByDepth

A星算法

ps.代码中有很多测试开关
1.ShowTest 打印一些测试区块，包括A星算法的寻找路线等。
2.UseDelay 运用延迟寻找，方便测试查看当前是到达哪个位置查找

local OneRoadValue = 10
local Row = 0
local Column = 0
local TurnTotalCount = 0

-- 测试相关
local ShowTest = false
local UseDelay = false  -- 是否启动延迟
local DelayTime = 3  -- 每一个移动的延迟(最好搭配开启showTest一起使用)

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

function RoadCheckByAStar:ctor(delegate, data)
    self._delegate = delegate
    self._data = data
    self:initValue()
end

function RoadCheckByAStar:initValue()
    self._startPos = nil
    self._endPos = nil

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

    self._lineTable = {}  -- 通过的表
    Row = self._data.Row or 0
    Column = self._data.Column or 0
    TurnTotalCount = self._data.TurnTotalCount or 0
end

function RoadCheckByAStar:startRoadCheck(_startPos, _endPos)
    self._startPos = _startPos
    self._endPos = _endPos

    self:checkRoadLink(self._startPos)
end

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

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

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

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

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

-- 找到open表中最小的f值
function RoadCheckByAStar: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 RoadCheckByAStar:getGValueInThroughRoad(pPos)
    local gValue = OneRoadValue
    local node = self._delegate:getNodeByPos(pPos)
    gValue = gValue + node:getGValue()

    return gValue
end

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

function RoadCheckByAStar:isEndPos(_pos)
    return self._endPos.x == _pos.x and self._endPos.y == _pos.y
end

function RoadCheckByAStar:setLineTable()
    local pos = self._endPos
    local endNode = self._delegate:getNodeByPos(pos)
    if ShowTest then
        endNode:setIsThroughedColor()
    end
    table.insert(self._lineTable, pos)  -- 添加终点进去
    -- 将终点从openlist中移除，移到closelist里面(方便主界面画线)
    self:addToCloseTable(pos)
    self:removeInOpenTable(pos) 

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

        if ShowTest then
            pNode:setIsThroughedColor()
        end
        table.insert(self._lineTable, pPos)

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

            -- 因为A星是从终点遍历到终点，所以需要倒序一下
            local temp = {}
            for i = #self._lineTable, 1, -1 do
                table.insert(temp, self._lineTable[i])
            end
            self._lineTable = temp

            self._delegate:linkReturn(#self._lineTable > 0, self._endPos)
            return true
        end

        pos = pNode:getPos()

        -- 不带延迟调用
        if not UseDelay then
            fun()
        end
    end

    -- 带延迟调用
    if UseDelay then
        action = schedule(self, fun, DelayTime)
    else
        -- 不带延迟调用
        fun()
    end
end

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

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

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

    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 then
            if (not self:checkIsInCloseTable(v)) and (self:isCanMoveInSpeicalRule(v, currentPos)) then  -- 如果不处于closelist里面，并且满足了特殊规则
                if not self._delegate:getNodeValeByPos(v) or self:isEndPos(v) then  -- 如果该路没有值(即非正常方块，或者是结束点)
                    -- 检查是否在openlist中
                    if self:checkIsInOpenTable(v) then
                        if self:getGValueInThroughRoad(currentPos) < node:getGValue() or self:getJValueInThroughRoad(currentPos, v) < node:getJValue() 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
                            local j = self:getJValueInThroughRoad(currentPos, v)
                            node:setText(g, h, j)
                            if ShowTest then
                                node:showText()
                                node:showParentTag()
                            end     
                        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
                        local j = self:getJValueInThroughRoad(currentPos, v)
                        node:setText(g, h, j)
                        if ShowTest then
                            node:showText()
                            node:showParentTag()
                        end                     
                    end
                end
            end
        end
    end

    local pos = self:getMinFPosInOpenTable()
    if not pos then
        self._delegate:linkReturn(#self._lineTable > 0, self._endPos)
        return 
    end

    -- 带延迟调用
    if UseDelay then
        local function fun()
            self:checkRoadLink(pos)
        end
        performWithDelay(self, fun, DelayTime)
    else
        -- 不带延迟调用
        self:checkRoadLink(pos)
    end
end

function RoadCheckByAStar:isCanMoveInSpeicalRule(_pos, _lastPos)
    if _pos.x < 0 or _pos.x > Row+1 or _pos.y < 0 or _pos.y > Column+1 then  -- 不允许超出界外两格检测
        return false
    end

    -- 不允许超出弯道n次(定为2次)
    if self:getTurnRoundCount(_pos, _lastPos) > TurnTotalCount then
        return false
    end

    return true
end

function RoadCheckByAStar:getTurnRoundCount(_pos, _lastPos)
    if _lastPos.x == self._startPos.x and _lastPos.y == self._startPos.y then
        return 0
    end

    local tCount = 0
    local rDir = nil
    local pos = _lastPos

    -- 检查当前与之前的位置
    local lNode = self._delegate:getNodeByPos(pos)
    local lDir = lNode:getDirInParentToHere()
    if lDir ~= self:getDirInPosToPos(_lastPos, _pos) then
        tCount = tCount + 1
    end

    local function fun()
        local node = self._delegate:getNodeByPos(pos)
        local dir = node:getDirInParentToHere()
        if not rDir then
            rDir = dir
        else
            if rDir ~= dir then
                tCount = tCount + 1
                rDir = dir
            end
        end

        local pPos = node:getParentPos()
        if pPos.x == self._startPos.x and pPos.y == self._startPos.y then
            return
        end

        pos = pPos
        fun()
    end

    fun()

    return tCount
end

function RoadCheckByAStar:getDirInPosToPos(_p1, _p2)
    if _p2.x - _p1.x > 0 then
        return 'right'
    elseif _p2.x - _p1.x < 0 then
        return 'left'
    elseif _p2.y - _p1.y < 0 then
        return 'down'
    elseif _p2.y - _p1.y > 0 then
        return 'up'
    end

    return
end

function RoadCheckByAStar:setDefaultState()
    self._lineTable = {}
    self._openList = {}
    self._closeList = {}
    self._startPos = nil
    self._endPos = nil  
end

function RoadCheckByAStar:getLineTable()
    return self._lineTable
end

function RoadCheckByAStar:getOpenList()
    return self._openList
end

function RoadCheckByAStar:getCloseList()
    return self._closeList
end

function RoadCheckByAStar:getJValueInThroughRoad(_lastPos, _pos)
    if _lastPos.x == self._startPos.x and _lastPos.y == self._startPos.y then
        return 0
    end

    local node = self._delegate:getNodeByPos(_pos)
    local lDir = node:getDirInParentToHere()  -- 获得父节点到这里的方向
    local jValue = 0
    local x, y = _pos.x, _pos.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
        if (not self:checkIsInCloseTable(v)) and (self:isCanMoveInSpeicalRule(v, _pos)) then  -- 如果不处于closelist里面，并且满足了特殊规则
            if not self._delegate:getNodeValeByPos(v) or self:isEndPos(v) then  -- 如果该路没有值(即非正常方块，或者是结束点)
                if lDir ~= self:getDirInPosToPos(_pos, v) then
                    jValue = jValue + 1
                end
            end
        end
    end
    return jValue
end

return RoadCheckByAStar

消消乐.png

一些代码后话：

一开始想用泰课中的分布计算，但是考虑在转2处理转1，并且转1还要处理转0会需要比较多的代码。然后还有考虑到可能连连看会有不一定为2转的情况，所以没有考虑这种写法了。( o(╥﹏╥)o 后面觉得好像不可能会有这种情况啊）
深度算法写起来比较容易理解
A星算法写起来需要注意点比较多：
1.因为A星算法是获得最短路径的算法，但是消消乐需要注意拐弯不能高于2次
2.A星算法是根据F值来获得并赋予父节点的，所以可能会遇到此情况。图中2,3方块的F值是相等，所以2,3方块谁先走的话，就会被认为为4方块的父节点。如果是2方块为父节点，则最终会找不到结果。

AStar_1.png

处理方法：
--- 1. 如果起点到终点找不到结果，反过来终点到起点试试(xD没测试过，盲猜)
--- 2. 在A星F = G + H 的基础上，更改为F = G + H + J，J表示该节点的下一个所有可移动点(非closelist中的)，获得这些点的移动方向，与父节点到该点的方向做比较。如果不一致，则++1。J为这个权值(就理解为之后可移动的方向，与父节点到这个点移动方向不一致的权值即可）。这样的话，得到的就会为：
图中点1出发，点2为(G10 H50 J1)，因为点2下一个为点4，点2到点4的方向与点1(父节点)到点2(该点)方向不一致)，点3为(G50 H50 J1)。此时点2和点3F值相同。假设他先经过了点2，那么会将点4放入openList，并点4的权值各值为(G20 H40 J2 F62(3项相加)，点2到点4方向为"右"，而点4到可移动点分别为，点5"上"，点3"下"，所以J为2)。然后从openlist获得下一个最小的F值，即点3。然后发现点4已经在openlist中，并且G值相同，所以则计算J值，该值为0，因为点4可移动的点只有点5，并且点4到点5的方向与点3到点4的方向相同，所以为0。然后经过比较后，把点4的父节点更改为点3，已达到目的。(这里运用的是这种)

3.或许还会有其他更好的办法。xD，所以还是希望先从深度算法开始写，理解一下消消乐的写法

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