如何在Pygame中生成无重叠的俄罗斯方块式随机障碍场？

我试图在Pygame中使用多种俄罗斯方块形状生成随机障碍场，需要用这些形状随机填充128×128的网格。目前已能通过pygame.draw.polygon生成并填充网格，但部分形状存在重叠问题，请问如何避免不同多边形对象之间的重叠？

附上当前代码：

import pygame

pygame.init()
import random

# 创建显示窗口
screen = pygame.display.set_mode((768 ,768))
total_cells = 128*128
# 颜色定义
blue = (0,0,255); red = (255,0,0); white = (255,255,255); black = (0, 0, 0); green = (0, 240, 100)

def getShape(start, width = 50):
    a = random.randint(1,8)
    RT = [start, (start[0] + 2*width, start[1]), (start[0] + 2*width, start[1] + width), (start[0] + width, start[1] + width), (start[0] + width, start[1] + 3*width), (start[0], start[1] + 3*width)]

    LT = [start, (start[0] - 2*width, start[1]), (start[0] - 2*width, start[1] + width), (start[0] - width, start[1] + width), (start[0] - width, start[1] + 3*width), (start[0], start[1] + 3*width)]

    RB = [start, (start[0] + width, start[1]), (start[0] + width, start[1] + 2*width), (start[0] + 2*width, start[1] + 2*width), (start[0] + 2*width, start[1] + 3*width), (start[0], start[1] + 3*width)]

    LB = [start, (start[0] - width, start[1]), (start[0] - width, start[1] + 2*width), (start[0] - 2*width, start[1] + 2*width), (start[0] - 2*width, start[1] + 3*width), (start[0], start[1] + 3*width)]

    if(a == 1):
        return LT
    elif(a == 2):
        return RT
    elif(a == 3):
        return LB
    elif(a == 4):
        return RB

def drawGrid():
    screen.fill(white)
    for i in range(0, 768, 6):
        pygame.draw.line(screen, black, (0, i), (768, i))
        pygame.draw.line(screen, black, (i, 0), (i, 768))

def generateObstacles(perc):
    fill_cells = round(total_cells*perc/100)
    fill_count = 0
    for i in range(0, fill_cells, 4):
        x1 = random.randint(2,126); y1 = random.randint(3,124)
        start = (6*x1, 6*y1)
        ob = getShape(start, 6)
        pygame.draw.polygon(screen, black, ob)
        fill_count += 4
        print('已填充单元格数量',fill_count)

def main():
    screen = pygame.display.set_mode((768 ,768))

    drawGrid()
    x1 = random.randint(2,126); y1 = random.randint(3,125)

    start = (6*x1, 6*y1)
    sp1 = getShape(start, 6)

    x1 = random.randint(1,24); y1 = random.randint(1,24)

    start = (6*x1, 6*y1)
    sp2 = getShape(start, 6)

    generateObstacles(50)

    pygame.display.flip()
    while pygame.event.wait().type != pygame.QUIT:
        pass
if __name__ == "__main__": 
    main()

要避免形状重叠，核心是跟踪已占用的网格单元格，生成新形状前先检查其覆盖区域是否合法（不越界、未被占用），只有符合条件才绘制。具体实现步骤如下：

• 创建网格状态标记数组：用128×128的二维数组记录每个单元格是否被占用，初始全为False。
• 定义形状的网格偏移：每种俄罗斯方块形状对应固定的网格坐标偏移，与像素绘制分离，方便碰撞检查。
• 合法性检查：生成形状时，先计算其覆盖的所有网格单元格，检查是否越界或已被占用。
• 优化填充逻辑：设置最大尝试次数，避免网格接近填满时陷入无限循环。

修改后的完整代码 #

import pygame
import random

pygame.init()

# 基础配置
screen = pygame.display.set_mode((768, 768))
GRID_SIZE = 128
CELL_SIZE = 6
total_cells = GRID_SIZE * GRID_SIZE

# 颜色定义
blue = (0, 0, 255); red = (255, 0, 0); white = (255, 255, 255); black = (0, 0, 0); green = (0, 240, 100)

# 定义每种形状对应的网格偏移（相对于起始网格坐标 (grid_x, grid_y)）
SHAPE_OFFSETS = {
    'LT': [(0, 0), (-2, 0), (-2, 1), (-1, 1), (-1, 3), (0, 3)],
    'RT': [(0, 0), (2, 0), (2, 1), (1, 1), (1, 3), (0, 3)],
    'LB': [(0, 0), (-1, 0), (-1, 2), (-2, 2), (-2, 3), (0, 3)],
    'RB': [(0, 0), (1, 0), (1, 2), (2, 2), (2, 3), (0, 3)]
}

def get_shape():
    # 随机选择一种形状
    shape_type = random.choice(list(SHAPE_OFFSETS.keys()))
    return shape_type, SHAPE_OFFSETS[shape_type]

def draw_grid():
    screen.fill(white)
    for i in range(0, 768, CELL_SIZE):
        pygame.draw.line(screen, black, (0, i), (768, i))
        pygame.draw.line(screen, black, (i, 0), (i, 768))

def generate_obstacles(perc):
    # 初始化网格占用状态
    grid_occupied = [[False for _ in range(GRID_SIZE)] for _ in range(GRID_SIZE)]
    fill_cells = round(total_cells * perc / 100)
    fill_count = 0
    max_attempts = 10000  # 最大尝试次数，防止死循环

    while fill_count < fill_cells and max_attempts > 0:
        max_attempts -= 1
        # 随机选择起始网格坐标（预留边界空间）
        grid_x = random.randint(2, GRID_SIZE - 3)
        grid_y = random.randint(3, GRID_SIZE - 4)
        
        shape_type, offsets = get_shape()
        shape_cells = []
        valid = True
        
        # 检查形状覆盖的单元格是否合法
        for dx, dy in offsets:
            x = grid_x + dx
            y = grid_y + dy
            # 越界检查
            if x < 0 or x >= GRID_SIZE or y < 0 or y >= GRID_SIZE:
                valid = False
                break
            # 占用检查
            if grid_occupied[y][x]:
                valid = False
                break
            shape_cells.append((x, y))
        
        if valid:
            # 标记单元格为已占用
            for x, y in shape_cells:
                grid_occupied[y][x] = True
            # 转换为像素坐标并绘制形状
            start_pixel = (grid_x * CELL_SIZE, grid_y * CELL_SIZE)
            shape_pixels = [(start_pixel[0] + dx * CELL_SIZE, start_pixel[1] + dy * CELL_SIZE) for dx, dy in offsets]
            pygame.draw.polygon(screen, black, shape_pixels)
            # 更新填充计数（去重统计）
            fill_count += len(set(shape_cells))
            print(f'已填充单元格数量: {fill_count}')

def main():
    draw_grid()
    generate_obstacles(50)
    pygame.display.flip()
    
    # 事件循环
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                pygame.quit()
                return

if __name__ == "__main__":
    main()

关键改进说明 #

1. 网格状态跟踪：grid_occupied数组实时记录单元格占用情况，从根源上避免重叠。
2. 形状偏移分离：将形状的网格逻辑与像素绘制分离，碰撞检查更直观、易维护。
3. 双重合法性验证：同时检查形状是否越界、是否与已存在形状重叠，确保绘制的形状完全合规。
4. 循环保护：最大尝试次数的设置，避免网格接近填满时程序陷入无限循环。

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