Python Sokoban关卡生成器无限挂起，无法输出关卡求助

问题核心原因 #

1. 可解性判断完全错误
   当前is_solvable仅检查玩家能否走到箱子和目标点，但推箱子的可解性要求是箱子能被玩家推到目标点，不是玩家单纯能到达箱子位置。更糟的是，is_reachable把箱子($)列为障碍物，导致连"玩家能走到箱子旁边"这个基础条件都无法满足，加上size=10的地图有效区域仅8x8=64格，20堵墙+4个箱子+4个目标+1个玩家几乎占满空间，几乎没有生成符合当前错误判断的"可解"关卡的可能，直接导致generate_level里的死循环。

2. 元素放置的死循环风险
   当num_walls设置过大时，有效区域的空格被墙壁占满，后续放置玩家、箱子、目标时，while True循环会无限寻找空格，永远无法退出。

3. 可达性判断逻辑错误
   is_reachable中把箱子($)视为完全不可进入的区域，但推箱子时玩家需要走到箱子相邻的位置才能推动，当前逻辑完全忽略了这一点。

修复建议与修正代码 #

关键修复点 #

• 重新实现可解性判断：检查每个箱子是否存在至少一个目标点，且玩家能到达箱子的可推动位置，同时箱子能被推到目标点（简化版先保证箱子和目标点都在玩家可达的连通区域内）。
• 添加元素数量校验：确保墙壁、玩家、箱子、目标的总数不超过有效区域的空格数，避免放置元素时的死循环。
• 修复可达性判断：允许玩家走到箱子的相邻格（但不能穿过箱子），同时调整可解性判断的逻辑。
• 添加生成尝试次数限制：避免无限循环，超过次数则提示参数不合理。

修正后的代码 #

import numpy as np

class LevelGenerator:
    def __init__(self, size, num_walls):
        self.size = size
        # 计算有效区域最大可放置元素数，预留足够空格保证连通性
        max_allowed_walls = (size-2)**2 - 1 - 2*((size-2)//2)  # 玩家 + 箱子 + 目标
        self.num_walls = min(num_walls, max_allowed_walls - 10)  # 预留10个空格
        self.level = np.full((size, size), ' ')
        self.generate_level()

    def place_borders(self):
        self.level[0, :] = '#'
        self.level[:, 0] = '#'
        self.level[-1, :] = '#'
        self.level[:, -1] = '#'

    def place_walls(self):
        available_positions = []
        for x in range(1, self.size-1):
            for y in range(1, self.size-1):
                available_positions.append((x, y))
        # 随机选择墙壁位置，避免死循环
        wall_positions = np.random.choice(len(available_positions), self.num_walls, replace=False)
        for idx in wall_positions:
            x, y = available_positions[idx]
            self.level[x, y] = '#'

    def place_player(self):
        available_positions = []
        for x in range(1, self.size-1):
            for y in range(1, self.size-1):
                if self.level[x, y] == ' ':
                    available_positions.append((x, y))
        if not available_positions:
            raise ValueError("No space left for player")
        x, y = available_positions[np.random.randint(len(available_positions))]
        self.level[x, y] = '@'
        self.player_pos = (x, y)

    def place_boxes_and_goals(self):
        num_boxes = (self.size - 2) // 2
        self.boxes = []
        self.goals = []
        available_positions = []
        for x in range(1, self.size-1):
            for y in range(1, self.size-1):
                if self.level[x, y] == ' ':
                    available_positions.append((x, y))
        if len(available_positions) < num_boxes * 2:
            raise ValueError("No enough space for boxes and goals")
        # 先选箱子位置
        box_indices = np.random.choice(len(available_positions), num_boxes, replace=False)
        for idx in box_indices:
            x, y = available_positions[idx]
            self.level[x, y] = '$'
            self.boxes.append((x, y))
            available_positions.pop(idx)
        # 再选目标位置
        goal_indices = np.random.choice(len(available_positions), num_boxes, replace=False)
        for idx in goal_indices:
            x, y = available_positions[idx]
            self.level[x, y] = '.'
            self.goals.append((x, y))

    def get_connected_area(self, start_pos):
        """获取玩家可达的连通区域（包括箱子的相邻格）"""
        visited = set()
        stack = [start_pos]
        visited.add(start_pos)
        while stack:
            cx, cy = stack.pop()
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nx, ny = cx + dx, cy + dy
                if 0 <= nx < self.size and 0 <= ny < self.size:
                    cell = self.level[nx, ny]
                    # 允许走到空格、目标点，或者箱子的相邻格（箱子本身不能走）
                    if (cell in [' ', '.'] or (cell == '$' and (cx, cy) not in self.boxes)) and (nx, ny) not in visited:
                        visited.add((nx, ny))
                        stack.append((nx, ny))
        return visited

    def is_solvable(self):
        # 第一步：获取玩家可达的区域
        connected_area = self.get_connected_area(self.player_pos)
        # 第二步：检查所有箱子都有至少一个相邻格在玩家可达区域内（可推动）
        for box_pos in self.boxes:
            x, y = box_pos
            has_access = False
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nx, ny = x + dx, y + dy
                if (nx, ny) in connected_area:
                    has_access = True
                    break
            if not has_access:
                return False
        # 第三步：检查所有目标点都在连通区域内
        for goal_pos in self.goals:
            if goal_pos not in connected_area:
                return False
        return True

    def generate_level(self):
        max_attempts = 1000
        attempts = 0
        while attempts < max_attempts:
            attempts += 1
            self.level.fill(' ')
            try:
                self.place_borders()
                self.place_walls()
                self.place_player()
                self.place_boxes_and_goals()
                if self.is_solvable():
                    print(f"Generated level in {attempts} attempts")
                    return
            except ValueError as e:
                print(f"Attempt {attempts} failed: {e}")
                continue
        raise RuntimeError(f"Failed to generate solvable level after {max_attempts} attempts. Try reducing num_walls or increasing size.")

    def get_level(self):
        return self.level

# Example usage
print("Generating Sokoban level...")
size = 10
num_walls = 20
generator = LevelGenerator(size, num_walls)
level = generator.get_level()
print("\n".join("".join(row) for row in level))

修复说明 #

1. 元素放置优化：不再用while True随机找位置，而是先收集所有可用位置再随机选择，彻底避免放置时的死循环。
2. 墙壁数量限制：自动计算最大允许的墙壁数量，预留足够空格保证连通性。
3. 可解性判断修正：通过连通区域检查，确保玩家能到达箱子的可推动位置，且目标点在可达区域内（简化版可解性判断，进阶可实现完整的推箱子路径搜索）。
4. 生成次数限制：设置最大尝试次数，超过则提示参数问题，避免无限挂起。

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