Expert en génération procédurale de contenu pour environnements de jeu

Générez un générateur de donjon infini 2D en utilisant l’Automate Cellulaire pour les murs de type caverne et une logique BSP (Partitionnement Binaire de l’Espace) séparée pour la connectivité des pièces. ```pseudocode // ====================== // 1. STRUCTURES DE DONNÉES // ====================== // Grille infinie (chunkée) struct Chunk { int chunkX, chunkY; TileType tiles[CHUNK_SIZE][CHUNK_SIZE]; // CHUNK_SIZE = 64 bool reachable[CHUNK_SIZE][CHUNK_SIZE]; }; // TileType: WALL, FLOOR, DOOR, ROOM_FLOOR // Gestionnaire de chunks (mémoire limitée) class InfiniteGrid { unordered_map<pair<int,int>, Chunk> chunks; int seed; Chunk& getChunk(int cx, int cy) { if (!chunks.count({cx,cy})) { chunks[{cx,cy}] = generateChunk(cx, cy); } return chunks[{cx,cy}]; } TileType getTile(int x, int y) { int cx = floor(x / CHUNK_SIZE); int cy = floor(y / CHUNK_SIZE); return getChunk(cx, cy).tiles[x % CHUNK_SIZE][y % CHUNK_SIZE]; } }; // ====================== // 2. GÉNÉRATION DE CHUNK // ====================== Chunk generateChunk(int cx, int cy) { Chunk c; c.chunkX = cx; c.chunkY = cy; // Étape 1 : Automate Cellulaire (murs de caverne) // Utilise un seed dérivé du chunk + seed global int localSeed = hash(seed, cx, cy); c.tiles = cellularAutomata(localSeed); // Étape 2 : BSP pour les pièces (connectivité) // Génère des pièces dans le chunk, puis les connecte via des couloirs vector<Room> rooms = bspGenerate(localSeed, c.tiles); // Étape 3 : Vérification de la connectivité (Flood Fill) // Marque les tuiles accessibles depuis le centre du chunk floodFillReachability(c); return c; } // ====================== // 3. AUTOMATE CELLULAIRE // ====================== TileType[][] cellularAutomata(int seed) { // Initialisation aléatoire avec densité (ex: 45% de murs) TileType[][] grid = new TileType[CHUNK_SIZE][CHUNK_SIZE]; Random rng = new Random(seed); for (int x = 0; x < CHUNK_SIZE; x++) { for (int y = 0; y < CHUNK_SIZE; y++) { grid[x][y] = (rng.nextDouble() < 0.45) ? WALL : FLOOR; } } // Itérations de l'automate (4 à 5 itérations) for (int iter = 0; iter < 5; iter++) { TileType[][] newGrid = grid.clone(); for (int x = 1; x < CHUNK_SIZE-1; x++) { for (int y = 1; y < CHUNK_SIZE-1; y++) { int wallCount = countNeighbors(grid, x, y, 1); // 8 voisins if (grid[x][y] == WALL) { // Règle : un mur survit si 4+ voisins sont des murs newGrid[x][y] = (wallCount >= 4) ? WALL : FLOOR; } else { // Règle : un sol devient mur si 5+ voisins sont des murs newGrid[x][y] = (wallCount >= 5) ? WALL : FLOOR; } } } grid = newGrid; } // Post-traitement : suppression des petites îles (optionnel) // Utiliser un BFS pour trouver les composantes de sol < taille minimale return grid; } // ====================== // 4. BSP POUR LES PIÈCES // ====================== struct Room { int x, y, width, height; }; vector<Room> bspGenerate(int seed, TileType[][] baseGrid) { // Divise récursivement le chunk en régions // Chaque feuille BSP contient une pièce aléatoire BSPNode root = new BSPNode(0, 0, CHUNK_SIZE, CHUNK_SIZE); splitNode(root, seed, 0); // Profondeur max = 4 vector<Room> rooms; collectRooms(root, rooms); // Connecte les pièces adjacentes (via les nœuds frères) connectRooms(root, rooms, baseGrid); return rooms; } void splitNode(BSPNode node, int seed, int depth) { if (depth >= 4 || node.width < MIN_ROOM_SIZE*2 || node.height < MIN_ROOM_SIZE*2) { // Feuille : crée une pièce aléatoire Random rng = new Random(seed ^ node.x ^ node.y); int w = rng.nextInt(node.width - MIN_ROOM_SIZE) + MIN_ROOM_SIZE; int h = rng.nextInt(node.height - MIN_ROOM_SIZE) + MIN_ROOM_SIZE; int px = node.x + rng.nextInt(node.width - w); int py = node.y + rng.nextInt(node.height - h); node.room = {px, py, w, h}; return; } // Division verticale ou horizontale (aléatoire) bool splitVertical = (rng.nextBoolean() && node.width > node.height) || (!rng.nextBoolean() && node.height > node.width); if (splitVertical) { int splitX = node.x + MIN_ROOM_SIZE + rng.nextInt(node.width - 2*MIN_ROOM_SIZE); node.left = new BSPNode(node.x, node.y, splitX - node.x, node.height); node.right = new BSPNode(splitX, node.y, node.width - (splitX - node.x), node.height); } else { int splitY = node.y + MIN_ROOM_SIZE + rng.nextInt(node.height - 2*MIN_ROOM_SIZE); node.left = new BSPNode(node.x, node.y, node.width, splitY - node.y); node.right = new BSPNode(node.x, splitY, node.width, node.height - (splitY - node.y)); } splitNode(node.left, seed, depth+1); splitNode(node.right, seed, depth+1); } void connectRooms(BSPNode node, vector<Room>& rooms, TileType[][] grid) { if (node.left == null || node.right == null) return; // Connecte la pièce du sous-arbre gauche à celle du droit Room r1 = getRoomFromSubtree(node.left); Room r2 = getRoomFromSubtree(node.right); createCorridor(r1, r2, grid); connectRooms(node.left, rooms, grid); connectRooms(node.right, rooms, grid); } void createCorridor(Room r1, Room r2, TileType[][] grid) { // Centre des pièces int x1 = r1.x + r1.width/2; int y1 = r1.y + r1.height/2; int x2 = r2.x + r2.width/2; int y2 = r2.y + r2.height/2; // Couloir en L (horizontal puis vertical) for (int x = min(x1, x2); x <= max(x1, x2); x++) { grid[x][y1] = FLOOR; } for (int y = min(y1, y2); y <= max(y1, y2); y++) { grid[x2][y] = FLOOR; } } // ====================== // 5. CONNECTIVITÉ (FLOOD FILL) // ====================== void floodFillReachability(Chunk& c) { // Initialise toutes les tuiles comme non accessibles for (int x = 0; x < CHUNK_SIZE; x++) { for (int y = 0; y < CHUNK_SIZE; y++) { c.reachable[x][y] = false; } } // Point de départ : centre du chunk (ou une pièce BSP) int startX = CHUNK_SIZE/2; int startY = CHUNK_SIZE/2; if (c.tiles[startX][startY] == WALL) { // Trouve le sol le plus proche findNearestFloor(c, startX, startY); } // BFS (Flood Fill) sur les tuiles de sol queue<pair<int,int>> q; q.push({startX, startY}); c.reachable[startX][startY] = true; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (auto [dx, dy] : {{-1,0},{1,0},{0,-1},{0,1}}) { int nx = x + dx, ny = y + dy; if (nx >= 0 && nx < CHUNK_SIZE && ny >= 0 && ny < CHUNK_SIZE) { if (!c.reachable[nx][ny] && c.tiles[nx][ny] != WALL) { c.reachable[nx][ny] = true; q.push({nx, ny}); } } } } // Post-traitement : convertit les sols non accessibles en murs for (int x = 0; x < CHUNK_SIZE; x++) { for (int y = 0; y < CHUNK_SIZE; y++) { if (c.tiles[x][y] == FLOOR && !c.reachable[x][y]) { c.tiles[x][y] = WALL; // Élimine les îles isolées } } } } // ====================== // 6. PARAMÈTRES CLÉS // ====================== // Entropie : contrôlée par la densité initiale (0.45) et les règles de l'automate // Densité : ajustable via le seuil de voisins (4/5) // Seed : dérivé du chunk (hash(seed, cx, cy)) pour la reproductibilité // Infinite : les chunks sont générés à la demande et mis en cache // Exemple d'utilisation : // InfiniteGrid world(42); // seed global = 42 // TileType t = world.getTile(100, -50); // génère le chunk correspondant ```