反向 BFS 生成关卡是推箱子里最聪明的做法。正向出题没法保证可解,随手画的布局可能没解法。反向 BFS 从「所有箱子都在目标上」的胜利状态出发,反向执行拉箱子操作,走 N 步后停下来,当前局面就是保证可解的关卡。

    为什么保证可解?每一步都是从可解状态退回,退出来的局面有一条回到胜利状态的路径,就是退回去的步骤反过来。理论最少步数也顺带得到,就是 N。

    let state = solvedState;
    for (let i = 0; i < N; i++) {
      state = pullRandom(state);
    }
    return state;
    

    pull 是 push 的逆:玩家在箱子旁,把箱子朝自己方向拉。随机选合法方向走若干步就是成品关卡。N 控制难度。

    生成的关卡解法往往不直观,因为退路径随机。想要更有设计感,可在反向时加偏好,比如优先朝空旷区域退,但效果一般,不如纯随机再手工筛选。