Розробка AI-системи процедурної генерації рівнів

AI-процедурна генерація рівнів для ігор

Процедурна генерація рівнів (PCG-levels) створює ігрові простори алгоритмічно: підземелля, рівні платформерів, відкриті світи, головоломки. AI-підходи додають семантичне розуміння: система знає, де повинен відбутися перший контакт з ворогом, де спрятаний секрет, якою є оптимальна крива складності.

Алгоритми генерації підземель

from dataclasses import dataclass, field
from enum import Enum
import random
import numpy as np
from collections import deque

class TileType(Enum):
    WALL = 0
    FLOOR = 1
    DOOR = 2
    CHEST = 3
    SPAWN = 4
    EXIT = 5
    TRAP = 6
    BOSS_ROOM = 7

@dataclass
class DungeonConfig:
    width: int = 64
    height: int = 64
    min_rooms: int = 8
    max_rooms: int = 15
    min_room_size: tuple = (4, 4)
    max_room_size: tuple = (12, 10)
    corridor_width: int = 1
    difficulty: float = 0.5    # 0.0 – 1.0, впливає на ворогів та пастки
    dungeon_type: str = "classic"  # classic, cave, maze, ruins

class BSPDungeonGenerator:
    """Binary Space Partitioning — класичний алгоритм для підземель"""

    def __init__(self, config: DungeonConfig):
        self.config = config
        self.grid = np.full((config.height, config.width), TileType.WALL.value)
        self.rooms = []
        self.rng = random.Random()

    def generate(self, seed: int = None) -> np.ndarray:
        if seed:
            self.rng.seed(seed)
            np.random.seed(seed)

        # 1. BSP-розбиття
        root = {"x": 1, "y": 1, "w": self.config.width - 2, "h": self.config.height - 2}
        leaves = self._split_bsp(root, depth=0, max_depth=4)

        # 2. Створення кімнат у листях
        for leaf in leaves:
            room = self._create_room_in_leaf(leaf)
            if room:
                self.rooms.append(room)
                self._carve_room(room)

        # 3. Сполучення кімнат коридорами
        for i in range(len(self.rooms) - 1):
            self._connect_rooms(self.rooms[i], self.rooms[i + 1])

        # 4. Розміщення спеціальних тайлів
        self._place_spawn_and_exit()
        self._place_interactive_elements()

        return self.grid

    def _split_bsp(self, node: dict, depth: int, max_depth: int) -> list:
        if depth >= max_depth or (node["w"] < 14 and node["h"] < 14):
            return [node]

        split_horizontal = self.rng.random() > 0.5
        if node["w"] > node["h"] * 1.25:
            split_horizontal = False
        elif node["h"] > node["w"] * 1.25:
            split_horizontal = True

        leaves = []
        if split_horizontal:
            split_pos = self.rng.randint(node["y"] + 6, node["y"] + node["h"] - 6)
            child_a = {"x": node["x"], "y": node["y"], "w": node["w"], "h": split_pos - node["y"]}
            child_b = {"x": node["x"], "y": split_pos, "w": node["w"], "h": node["y"] + node["h"] - split_pos}
        else:
            split_pos = self.rng.randint(node["x"] + 6, node["x"] + node["w"] - 6)
            child_a = {"x": node["x"], "y": node["y"], "w": split_pos - node["x"], "h": node["h"]}
            child_b = {"x": split_pos, "y": node["y"], "w": node["x"] + node["w"] - split_pos, "h": node["h"]}

        leaves.extend(self._split_bsp(child_a, depth + 1, max_depth))
        leaves.extend(self._split_bsp(child_b, depth + 1, max_depth))
        return leaves

    def _create_room_in_leaf(self, leaf: dict) -> dict | None:
        max_w = min(self.config.max_room_size[0], leaf["w"] - 2)
        max_h = min(self.config.max_room_size[1], leaf["h"] - 2)
        if max_w < self.config.min_room_size[0] or max_h < self.config.min_room_size[1]:
            return None
        w = self.rng.randint(self.config.min_room_size[0], max_w)
        h = self.rng.randint(self.config.min_room_size[1], max_h)
        x = leaf["x"] + self.rng.randint(1, leaf["w"] - w - 1)
        y = leaf["y"] + self.rng.randint(1, leaf["h"] - h - 1)
        return {"x": x, "y": y, "w": w, "h": h}

    def _carve_room(self, room: dict) -> None:
        for y in range(room["y"], room["y"] + room["h"]):
            for x in range(room["x"], room["x"] + room["w"]):
                self.grid[y][x] = TileType.FLOOR.value

    def _connect_rooms(self, room_a: dict, room_b: dict) -> None:
        """L-подібний коридор між центрами кімнат"""
        cx_a = room_a["x"] + room_a["w"] // 2
        cy_a = room_a["y"] + room_a["h"] // 2
        cx_b = room_b["x"] + room_b["w"] // 2
        cy_b = room_b["y"] + room_b["h"] // 2

        if self.rng.random() > 0.5:
            self._carve_horizontal(cy_a, min(cx_a, cx_b), max(cx_a, cx_b))
            self._carve_vertical(cx_b, min(cy_a, cy_b), max(cy_a, cy_b))
        else:
            self._carve_vertical(cx_a, min(cy_a, cy_b), max(cy_a, cy_b))
            self._carve_horizontal(cy_b, min(cx_a, cx_b), max(cx_a, cx_b))

    def _carve_horizontal(self, y: int, x1: int, x2: int) -> None:
        for x in range(x1, x2 + 1):
            self.grid[y][x] = TileType.FLOOR.value

    def _carve_vertical(self, x: int, y1: int, y2: int) -> None:
        for y in range(y1, y2 + 1):
            self.grid[y][x] = TileType.FLOOR.value

    def _place_spawn_and_exit(self) -> None:
        if self.rooms:
            spawn_room = self.rooms[0]
            self.grid[spawn_room["y"] + 1][spawn_room["x"] + 1] = TileType.SPAWN.value
            exit_room = self.rooms[-1]
            self.grid[exit_room["y"] + 1][exit_room["x"] + 1] = TileType.EXIT.value
            # Кімната босса — найбільша кімната
            boss_room = max(self.rooms, key=lambda r: r["w"] * r["h"])
            mid_y = boss_room["y"] + boss_room["h"] // 2
            mid_x = boss_room["x"] + boss_room["w"] // 2
            self.grid[mid_y][mid_x] = TileType.BOSS_ROOM.value

    def _place_interactive_elements(self) -> None:
        trap_count = int(len(self.rooms) * self.config.difficulty * 0.3)
        chest_count = max(1, int(len(self.rooms) * 0.4))

        for room in self.rng.sample(self.rooms[1:-1], min(trap_count, len(self.rooms) - 2)):
            x = self.rng.randint(room["x"] + 1, room["x"] + room["w"] - 2)
            y = self.rng.randint(room["y"] + 1, room["y"] + room["h"] - 2)
            self.grid[y][x] = TileType.TRAP.value

        for room in self.rng.sample(self.rooms, min(chest_count, len(self.rooms))):
            x = self.rng.randint(room["x"] + 1, room["x"] + room["w"] - 2)
            y = self.rng.randint(room["y"] + 1, room["y"] + room["h"] - 2)
            if self.grid[y][x] == TileType.FLOOR.value:
                self.grid[y][x] = TileType.CHEST.value

Wave Function Collapse для тайлових рівнів

class WaveFunctionCollapse:
    """
    WFC генерує рівні по зразку: аналізує паттерни в прикладі тайлової карти
    та генерує нові карти з тими ж локальними паттернами.
    Застосовується в платформерах, ізометричних RPG, головоломках.
    """

    def __init__(self, sample_grid: np.ndarray, pattern_size: int = 3):
        self.pattern_size = pattern_size
        self.patterns, self.weights = self._extract_patterns(sample_grid)
        self.adjacency = self._compute_adjacency()

    def _extract_patterns(self, grid: np.ndarray) -> tuple:
        patterns = {}
        h, w = grid.shape
        p = self.pattern_size

        for y in range(h - p + 1):
            for x in range(w - p + 1):
                pattern = tuple(grid[y:y+p, x:x+p].flatten())
                patterns[pattern] = patterns.get(pattern, 0) + 1

        all_patterns = list(patterns.keys())
        weights = [patterns[p] for p in all_patterns]
        return all_patterns, weights

    def _compute_adjacency(self) -> dict:
        """Для кожного паттерну визначаємо допустимих сусідів у 4 напрямах"""
        adjacency = {i: {d: set() for d in ["up", "down", "left", "right"]}
                     for i in range(len(self.patterns))}
        p = self.pattern_size

        for i, pat_a in enumerate(self.patterns):
            grid_a = np.array(pat_a).reshape(p, p)
            for j, pat_b in enumerate(self.patterns):
                grid_b = np.array(pat_b).reshape(p, p)
                # Перевіряємо сумісність накладання
                if np.array_equal(grid_a[1:, :], grid_b[:-1, :]):
                    adjacency[i]["down"].add(j)
                    adjacency[j]["up"].add(i)
                if np.array_equal(grid_a[:, 1:], grid_b[:, :-1]):
                    adjacency[i]["right"].add(j)
                    adjacency[j]["left"].add(i)

        return adjacency

    def generate(self, output_size: tuple) -> np.ndarray:
        h, w = output_size
        # Кожна клітка містить набір можливих паттернів
        wave = [[set(range(len(self.patterns))) for _ in range(w)] for _ in range(h)]
        result = np.zeros((h, w), dtype=int)

        while True:
            # Знаходимо клітку з мінімальною ентропією (не схопану)
            min_entropy = float("inf")
            min_cell = None
            for y in range(h):
                for x in range(w):
                    if len(wave[y][x]) > 1:
                        entropy = len(wave[y][x])
                        if entropy < min_entropy:
                            min_entropy = entropy
                            min_cell = (y, x)

            if min_cell is None:
                break

            # Колапс клітки з мінімальною ентропією
            y, x = min_cell
            possible = list(wave[y][x])
            weights = [self.weights[p] for p in possible]
            total = sum(weights)
            chosen = random.choices(possible, weights=[w/total for w in weights])[0]
            wave[y][x] = {chosen}

            # Поширення обмежень (BFS)
            queue = deque([(y, x)])
            while queue:
                cy, cx = queue.popleft()
                for dy, dx, direction, opposite in [(-1,0,"up","down"),(1,0,"down","up"),(0,-1,"left","right"),(0,1,"right","left")]:
                    ny, nx = cy + dy, cx + dx
                    if 0 <= ny < h and 0 <= nx < w and len(wave[ny][nx]) > 1:
                        allowed = set()
                        for pat_idx in wave[cy][cx]:
                            allowed |= self.adjacency[pat_idx][direction]
                        new_options = wave[ny][nx] & allowed
                        if new_options != wave[ny][nx]:
                            wave[ny][nx] = new_options
                            queue.append((ny, nx))

        # Збираємо результат із першого тайлу кожного паттерну
        for y in range(h):
            for x in range(w):
                if wave[y][x]:
                    pat_idx = next(iter(wave[y][x]))
                    result[y][x] = self.patterns[pat_idx][0]
        return result

AI-оцінка та поліпшення рівнів

from openai import AsyncOpenAI

client = AsyncOpenAI()

async def evaluate_level_design(level_grid: np.ndarray, config: DungeonConfig) -> dict:
    """LLM аналізує ASCII-представлення рівня та дає дизайн-оцінку"""
    TILE_CHARS = {0: "#", 1: ".", 2: "+", 3: "C", 4: "S", 5: "E", 6: "^", 7: "B"}
    ascii_map = "\n".join(
        "".join(TILE_CHARS.get(int(cell), "?") for cell in row)
        for row in level_grid
    )

    response = await client.chat.completions.create(
        model="gpt-4o",
        messages=[{
            "role": "system",
            "content": """Ти — геймдизайнер, спеціаліст по level design.
            Оціни підземелля за критеріями та запропонуй поліпшення.

            Позначення: # стіна, . підлога, + двері, C сундук, S спавн, E вихід, ^ пастка, B босс

            Повернути JSON: {
                flow_score: 1-10,  // логічність маршруту
                pacing_score: 1-10,  // розподіл напруги
                exploration_score: 1-10,  // мотивація досліджувати
                issues: ["опис проблеми"],
                improvements: ["конкретні правки"],
                estimated_playtime_minutes: int
            }"""
        }, {
            "role": "user",
            "content": f"Складність: {config.difficulty}\nКарта:\n{ascii_map[:2000]}"
        }],
        response_format={"type": "json_object"}
    )
    import json
    return json.loads(response.choices[0].message.content)

Інтеграція з Unity та Unreal Engine

Unity: генерована сітка серіалізується в JSON та читається монобіхевіором. Tilemap API заповнює TileBase за типами тайлів, NavMesh запікується автоматично через NavMeshSurface.

Unreal Engine 5: PCG-граф у PCG Framework приймає параметри як атрибути, Procedural Mesh Component будує геометрію із даних генератора, World Partition управляє завантаженням великих підземель по чанкам.

Порівняння алгоритмів за типом гри

PCG-система з BSP-підземеллям та оцінкою через LLM — 3–4 тижні. Повнофункціональний генератор з WFC, підтримкою тем біомів та Unity-плагіном — 8–12 тижнів.