4x4网格游戏中L型棋子合法移动检测技术问询

这个问题在网格类游戏里很常见，核心是要快速验证L型棋子平移/旋转后的位置是否满足不越界、不与其他棋子重叠两个条件。结合你现有的代码，我给你一套清晰高效的实现方案：

核心思路 #

1. 用集合存储已占用单元格：集合的in操作是O(1)，比列表遍历高效得多，适合快速判断某个位置是否被硬币或其他L型占据。
2. 预定义L型的所有旋转形态：L型有4种基础旋转形态（0°、90°、180°、270°），提前定义它们的相对坐标（以某个锚点为原点），避免每次旋转都重新计算。
3. 遍历所有可能的锚点位置：对每种旋转形态，根据形态的大小限制锚点的可移动范围，计算所有绝对坐标后验证合法性。

具体实现步骤 #

1. 优化已占用单元格的收集 #

首先修改你的Grid类，添加一个方法来快速获取所有已占用的单元格，同时优化update方法的效率：

class Grid():
    def __init__(self):
        self.cells = np.zeros((SIZE, SIZE, 3), dtype=np.uint8)
        self.free_cells = []
    
    def get_occupied_cells(self, coins, l_shapes):
        """获取所有被占用的单元格集合"""
        occupied = set()
        # 添加所有硬币位置
        for coin in coins:
            occupied.add((coin.x, coin.y))
        # 添加所有L型棋子的位置
        for l in l_shapes:
            for coord in l.coords:
                occupied.add(tuple(coord))
        return occupied
    
    def update(self, coins, l_shapes):
        self.reset()
        occupied = self.get_occupied_cells(coins, l_shapes)
        # 绘制硬币
        for coin in coins:
            self.cells[coin.x][coin.y] = COIN_COL
        # 绘制L型
        for l in l_shapes:
            for coord in l.coords:
                self.cells[coord[0]][coord[1]] = L_COL
        # 计算空闲单元格（用集合判断更高效）
        self.free_cells = [(i,j) for i in range(SIZE) for j in range(SIZE) if (i,j) not in occupied]
    
    # 保留你现有的reset、show方法...

2. 预定义L型的所有旋转形态 #

在Grid类中添加L型的4种基础旋转形态（以形态的最小x/y点为锚点的相对坐标）：

# 在Grid类内部或者外部定义都可以，建议放在类内部作为类属性
class Grid():
    # 类属性：L型的4种旋转形态（相对锚点的坐标）
    L_SHAPE_FORMS = [
        # 0°：竖3格 + 右侧1格
        [(0, 0), (1, 0), (2, 0), (2, 1)],
        # 90°：横3格 + 下方1格
        [(0, 0), (0, 1), (0, 2), (1, 2)],
        # 180°：竖3格 + 左侧1格
        [(0, 1), (1, 1), (2, 1), (2, 0)],
        # 270°：横3格 + 上方1格
        [(1, 0), (1, 1), (1, 2), (0, 2)]
    ]
    
    # 其他方法...

3. 实现合法L型位置的生成函数 #

添加一个方法，生成当前网格中所有合法的L型位置：

class Grid():
    # 其他方法...
    
    def get_valid_l_positions(self, coins, l_shapes):
        """生成所有合法的L型棋子位置"""
        occupied = self.get_occupied_cells(coins, l_shapes)
        valid_positions = []
        grid_size = SIZE
        
        for form in self.L_SHAPE_FORMS:
            # 计算当前形态所需的最大x/y偏移，确定锚点的可移动范围
            max_rel_x = max(x for x, y in form)
            max_rel_y = max(y for x, y in form)
            
            # 锚点的x范围：0 <= anchor_x <= grid_size - 1 - max_rel_x
            anchor_x_range = grid_size - max_rel_x
            # 锚点的y范围：0 <= anchor_y <= grid_size - 1 - max_rel_y
            anchor_y_range = grid_size - max_rel_y
            
            # 遍历所有可能的锚点
            for anchor_x in range(anchor_x_range + 1):  # range左闭右开，+1覆盖所有合法值
                for anchor_y in range(anchor_y_range + 1):
                    # 计算形态的绝对坐标
                    absolute_coords = [(anchor_x + x, anchor_y + y) for x, y in form]
                    # 验证所有坐标都未被占用且在网格内（锚点范围已保证在网格内，可省略边界检查）
                    if all(coord not in occupied for coord in absolute_coords):
                        valid_positions.append(np.array(absolute_coords, dtype=np.uint8))
        
        return valid_positions

4. 单个L型的移动/旋转合法性检查 #

如果需要单独检查某个L型旋转/平移后的位置是否合法，可以写一个辅助函数：

def is_l_position_valid(self, target_coords, coins, l_shapes):
    """检查给定的L型坐标是否合法"""
    occupied = self.get_occupied_cells(coins, l_shapes)
    # 检查所有坐标在网格内且未被占用
    for coord in target_coords:
        x, y = coord
        if x < 0 or x >= SIZE or y < 0 or y >= SIZE:
            return False
        if (x, y) in occupied:
            return False
    return True

使用示例 #

比如你要移动当前的L型棋子，可以先获取所有合法位置，然后选择其中一个更新：

# 假设你有硬币列表coins和L型列表l_shapes
grid = Grid()
valid_l_pos = grid.get_valid_l_positions(coins, l_shapes)
# 选择第一个合法位置作为新的L型位置
if valid_l_pos:
    new_l = LShape(valid_l_pos[0])
    # 更新网格
    grid.update(coins, [new_l])
    grid.show()

这种方案既优雅又高效：集合操作保证了占用检查的速度，预定义形态避免了重复计算旋转逻辑，锚点范围限制减少了不必要的遍历。

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