程序化生成迷宫中的回溯算法问题求助

你的回溯逻辑存在几个关键问题，导致回溯时无法正确找到可用路径：

1. 栈操作逻辑混乱 #

你用table.insert(history, 1, curr)把当前节点插入栈顶（数组头部），但在backtrack中移除栈顶后，找到有效方向时没有正确维护栈的状态，导致重复插入节点，最终栈结构混乱，只能回到起点。

2. 回溯时的节点处理错误 #

当找到历史节点有可用方向时，你直接返回该节点，但此时该节点已经被从栈中移除，后续step函数会再次将其插入栈顶，造成栈内节点重复，破坏路径记录。

3. 访问标记时机错误 #

step函数中，你在返回当前位置前标记visited，但实际上应该在移动到新位置后标记新位置为已访问，否则初始位置和后续节点的访问状态会出现混乱。

修复后的核心代码 #

修改backtrack函数 #

function backtrack()
  -- 循环直到找到有可用方向的节点，或回到起点
  while #history > 1 do
    -- 弹出当前无路可走的节点
    table.remove(history, 1)
    local prev = history[1]
    
    -- 检查四个方向的有效性（北、东、南、西）
    local valid = {
      (prev[2] < 21) and not visited[prev[1]][prev[2] + 1],
      (prev[1] < 21) and not visited[prev[1] + 1][prev[2]],
      (prev[2] > 1) and not visited[prev[1]][prev[2] - 1],
      (prev[1] > 1) and not visited[prev[1] - 1][prev[2]]
    }
    
    -- 遍历寻找第一个有效方向
    for i = 1, 4 do
      if valid[i] then
        -- 返回找到的节点和方向，此时节点仍在栈中
        return prev, i
      end
    end
  end
  -- 回到起点且无可用方向，返回nil
  return nil, nil
end

修改step函数 #

function step(position)
  local curr = position
  local dir = pickDir(curr)
  
  -- 若无有效方向，触发回溯
  if not dir then
    curr, dir = backtrack()
    -- 若回溯到起点仍无方向，说明迷宫已生成完成
    if not curr then return nil end
  end
  
  -- 根据方向计算新位置
  local newPos = {curr[1], curr[2]}
  if dir == 1 then newPos[2] = newPos[2] + 1 -- 北
  elseif dir == 2 then newPos[1] = newPos[1] + 1 -- 东
  elseif dir == 3 then newPos[2] = newPos[2] - 1 -- 南
  elseif dir == 4 then newPos[1] = newPos[1] - 1 -- 西
  end
  
  -- 开凿墙壁（补充你的墙壁开凿逻辑，连接curr和newPos）
  -- (... 开凿墙壁的代码 ...)
  
  -- 标记新位置为已访问
  visited[newPos[1]][newPos[2]] = true
  -- 将新位置入栈顶
  table.insert(history, 1, newPos)
  
  -- 返回新位置，继续下一步
  return newPos
end

额外注意事项 #

• 初始化时，需要将起点位置标记为已访问，并加入history栈：

  local startPos = {1, 1} -- 可根据需求调整起点
  visited[startPos[1]][startPos[2]] = true
  table.insert(history, 1, startPos)
  

• 建议将方向有效性判断抽成独立函数，避免pickDir和backtrack重复代码：

  function getValidDirs(pos)
    return {
      (pos[2] < 21) and not visited[pos[1]][pos[2] + 1],
      (pos[1] < 21) and not visited[pos[1] + 1][pos[2]],
      (pos[2] > 1) and not visited[pos[1]][pos[2] - 1],
      (pos[1] > 1) and not visited[pos[1] - 1][pos[2]]
    }
  end
  

内容的提问来源于stack exchange，提问作者snow