Python Roguelike游戏：如何生成无重叠的程序化地牢房间

Hey there! Let's work through your problem of generating multiple non-overlapping rooms in your roguelike dungeon. We'll fix your overlap check, avoid infinite loops, clean up your code, and add efficiency improvements along the way.

First, Let's Fix the Core Issues in Your Current Code #

Your existing code has a few small bugs and design choices that make it hard to scale to multiple rooms:

• Overuse of global variables: This makes it hard to track room state and reuse logic for multiple rooms.
• Broken overlap check: Your check_if_space_taken function has incorrect loop logic (you're reusing the each_row variable, and not checking the specific room area).
• No boundary checks: Rooms can spawn outside the 50x50 grid, causing index errors.
• No guard against infinite loops: Without a maximum retry limit, your code could get stuck trying to find a valid spot forever.

Step 1: Refactor to Use Room Data Structures #

Instead of scattering room parameters across global variables, let's encapsulate them in a simple class. This makes it easier to track multiple rooms and pass data between functions.

Here's a basic Room class we can use:

class Room:
    def __init__(self, row, col, height, length):
        self.row = row
        self.col = col
        self.height = height
        self.length = length
        # Calculate room boundaries for easier overlap checks
        self.max_row = row + height
        self.max_col = col + length

Step 2: Build a Proper Space Check Function #

We need two critical checks for a new room:

1. Does it fit entirely within the 50x50 grid?
2. Does it overlap with any existing rooms?

Here's a robust, efficient check function:

def is_room_valid(new_room, grid, existing_rooms):
    # First, check if the room stays within grid boundaries
    if (new_room.max_row > len(grid) or 
        new_room.max_col > len(grid[0]) or
        new_room.row < 0 or new_room.col < 0):
        return False
    
    # Use axis-aligned bounding box (AABB) check for fast overlap detection
    for room in existing_rooms:
        # If the rooms don't overlap on either axis, they're safe
        if not (new_room.max_row <= room.row or
                new_room.row >= room.max_row or
                new_room.max_col <= room.col or
                new_room.col >= room.max_col):
            return False
    
    # Optional double-check: Verify the grid cells themselves (in case of manual edits)
    for r in range(new_room.row, new_room.max_row):
        for c in range(new_room.col, new_room.max_col):
            if grid[r][c] == 1:
                return False
    
    return True

The AABB check avoids iterating every grid cell for overlap—it just compares room boundaries, which saves a ton of time as the dungeon fills up.

Step 3: Generate Multiple Rooms Safely #

To avoid infinite loops, we'll set a maximum number of attempts per room. If we can't find a valid spot after that many tries, we'll stop (since the dungeon is likely full). We'll also track all existing rooms to check against.

Here's the updated room generation logic:

import random

GRID_SIZE = 50
MIN_ROOM_SIZE = 7
MAX_ROOM_SIZE = 15
MAX_ATTEMPTS_PER_ROOM = 100
TARGET_ROOM_COUNT = 10  # Adjust this to your desired number of rooms

def create_grid(size):
    return [[0 for _ in range(size)] for _ in range(size)]

def generate_random_room(grid_size):
    # Spawn rooms far enough from edges to fit minimum size
    row = random.randint(0, grid_size - MIN_ROOM_SIZE)
    col = random.randint(0, grid_size - MIN_ROOM_SIZE)
    height = random.randint(MIN_ROOM_SIZE, MAX_ROOM_SIZE)
    length = random.randint(MIN_ROOM_SIZE, MAX_ROOM_SIZE)
    # Clamp size to ensure room doesn't go out of bounds
    height = min(height, grid_size - row)
    length = min(length, grid_size - col)
    return Room(row, col, height, length)

def add_room_to_grid(grid, room):
    for r in range(room.row, room.max_row):
        for c in range(room.col, room.max_col):
            grid[r][c] = 1

Step 4: Put It All Together with a Dungeon Generator #

This function ties everything together: it creates the grid, tries to place rooms, and stops when it hits the target count or can't place more rooms.

def generate_dungeon():
    grid = create_grid(GRID_SIZE)
    existing_rooms = []
    
    for _ in range(TARGET_ROOM_COUNT):
        attempts = 0
        placed = False
        
        while attempts < MAX_ATTEMPTS_PER_ROOM and not placed:
            new_room = generate_random_room(GRID_SIZE)
            if is_room_valid(new_room, grid, existing_rooms):
                add_room_to_grid(grid, new_room)
                existing_rooms.append(new_room)
                print(f"Placed room at ({new_room.row}, {new_room.col}) with size {new_room.height}x{new_room.length}")
                placed = True
            attempts += 1
        
        if not placed:
            print(f"Couldn't place room after {MAX_ATTEMPTS_PER_ROOM} attempts—dungeon is getting full!")
            break  # Stop trying if we can't find more space
    
    return grid, existing_rooms

Step 5: Efficiency Optimizations #

• AABB Overlap Check: As mentioned, this is way faster than checking every grid cell for overlap.
• Attempt Limits: MAX_ATTEMPTS_PER_ROOM prevents infinite loops when the dungeon is nearly full.
• Boundary Clamping: generate_random_room ensures rooms never spawn outside the grid, eliminating index errors.
• No Global Variables: Using local variables and passing data between functions makes the code cleaner and easier to debug.

Full Working Code #

Here's the complete, runnable code:

import random

class Room:
    def __init__(self, row, col, height, length):
        self.row = row
        self.col = col
        self.height = height
        self.length = length
        self.max_row = row + height
        self.max_col = col + length

GRID_SIZE = 50
MIN_ROOM_SIZE = 7
MAX_ROOM_SIZE = 15
MAX_ATTEMPTS_PER_ROOM = 100
TARGET_ROOM_COUNT = 10

def create_grid(size):
    return [[0 for _ in range(size)] for _ in range(size)]

def generate_random_room(grid_size):
    row = random.randint(0, grid_size - MIN_ROOM_SIZE)
    col = random.randint(0, grid_size - MIN_ROOM_SIZE)
    height = random.randint(MIN_ROOM_SIZE, MAX_ROOM_SIZE)
    length = random.randint(MIN_ROOM_SIZE, MAX_ROOM_SIZE)
    height = min(height, grid_size - row)
    length = min(length, grid_size - col)
    return Room(row, col, height, length)

def is_room_valid(new_room, grid, existing_rooms):
    if (new_room.max_row > len(grid) or 
        new_room.max_col > len(grid[0]) or
        new_room.row < 0 or new_room.col < 0):
        return False
    
    for room in existing_rooms:
        if not (new_room.max_row <= room.row or
                new_room.row >= room.max_row or
                new_room.max_col <= room.col or
                new_room.col >= room.max_col):
            return False
    
    for r in range(new_room.row, new_room.max_row):
        for c in range(new_room.col, new_room.max_col):
            if grid[r][c] == 1:
                return False
    
    return True

def add_room_to_grid(grid, room):
    for r in range(room.row, room.max_row):
        for c in range(room.col, room.max_col):
            grid[r][c] = 1

def print_grid(grid):
    for row in grid:
        print(" ".join(map(str, row)))

def generate_dungeon():
    grid = create_grid(GRID_SIZE)
    existing_rooms = []
    
    for _ in range(TARGET_ROOM_COUNT):
        attempts = 0
        placed = False
        
        while attempts < MAX_ATTEMPTS_PER_ROOM and not placed:
            new_room = generate_random_room(GRID_SIZE)
            if is_room_valid(new_room, grid, existing_rooms):
                add_room_to_grid(grid, new_room)
                existing_rooms.append(new_room)
                print(f"Placed room at ({new_room.row}, {new_room.col}) with size {new_room.height}x{new_room.length}")
                placed = True
            attempts += 1
        
        if not placed:
            print(f"Couldn't place room after {MAX_ATTEMPTS_PER_ROOM} attempts—dungeon is getting full!")
            break
    
    return grid, existing_rooms

# Run the dungeon generation
grid, rooms = generate_dungeon()
print("\nFinal Dungeon Grid:")
print_grid(grid)

Extra Tips for Your Roguelike #

• Add Corridors: Once you have non-overlapping rooms, connect them with corridors (e.g., find the closest points between rooms and draw a straight or L-shaped path).
• BSP Tree Generation: For more structured dungeons, look into Binary Space Partitioning (BSP) trees—this splits the grid into regions first, then places rooms in each region, avoiding overlap entirely.
• Tweak Parameters: Adjust MIN_ROOM_SIZE, MAX_ROOM_SIZE, TARGET_ROOM_COUNT, and MAX_ATTEMPTS_PER_ROOM to get the dungeon density and size you want.

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