Lua深度优先：标记回溯的迷宫探索

flowchart TD
A[栈顶出当前格] --> B{四向有没走过的格}
B -- 有 --> C[标记入栈 前进一格]
C --> D{是出口}
D -- 是 --> E[栈即通路 结束]
D -- 否 --> A
B -- 无 --> F[出栈回溯一格]
F --> A

 fx-dfsmaze

-- @file DfsMaze.lua
-- 深度优先 —— 标记回溯的迷宫探索

local DfsMaze = {}

local CONST = {
    GRID_W        = 15,
    GRID_H        = 9,
    STEP_MAX      = 400,

    AUTOINC_BASE  = 1144000,
}

local _walls     = {}
local _visited   = {}
local _stack     = {}
local _done      = false
local _steps     = 0
local _exitC     = 0
local _exitR     = 0

local function KeyOf(c, r)
    return c .. "," .. r
end

local function ShowTip(msg)
    if msg and msg ~= "" then SL:ShowSystemTips(msg) end
end

function DfsMaze.SetMaze(wallTable, exitC, exitR)
    _walls = wallTable or {}
    _exitC = exitC
    _exitR = exitR
end

function DfsMaze.Reset(startC, startR)
    _visited = {}
    _stack = {}
    _done = false
    _steps = 0
    _visited[KeyOf(startC, startR)] = true
    _stack[#_stack + 1] = { startC, startR }
end

-- 试探回溯：单步推进，撞墙出栈
local DIRS = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }

function DfsMaze.Step()
    if _done or _steps >= CONST.STEP_MAX then
        return false
    end
    local cur = _stack[#_stack]
    if not cur then
        _done = true
        ShowTip("走投无路——回溯到头也没出口")
        return false
    end
    local c, r = cur[1], cur[2]
    if c == _exitC and r == _exitR then
        _done = true
        ShowTip("到出口了——栈就是走通的路")
        return true
    end
    _steps = _steps + 1
    for _, dir in ipairs(DIRS) do
        local nc = c + dir[1]
        local nr = r + dir[2]
        if nc >= 0 and nr >= 0
            and nc < CONST.GRID_W and nr < CONST.GRID_H
            and not _walls[KeyOf(nc, nr)]
            and not _visited[KeyOf(nc, nr)] then
            _visited[KeyOf(nc, nr)] = true
            _stack[#_stack + 1] = { nc, nr }
            return true
        end
    end
    _stack[#_stack] = nil
    return true
end

function DfsMaze.Path()
    return _stack
end

SL:ScheduleOnce(function()
    SL:BindDebugButton("走一步", function()
        DfsMaze.Step()
    end)
    ShowTip("技能已加载: 深度优先 (调试按钮触发)")
end, 1.0)

function DfsMaze.Unload()
    _walls = {}
    _visited = {}
    _stack = {}
    _done = false
end

return DfsMaze