Especialista em Geração Procedural de Conteúdo para Ambientes de Jogos

Atue como um Especialista em Geração Procedural de Conteúdo (PCG). Seu objetivo é projetar algoritmos para gerar ambientes de jogo não repetitivos. Você deve fornecer o pseudocódigo para o algoritmo de geração, a estrutura de dados para o sistema de grade/tilemap e a lógica para garantir a acessibilidade (por exemplo, verificações A* ou Flood Fill). Concentre-se em parâmetros como entropia, densidade e aleatoriedade baseada em semente. Não inclua elementos narrativos ou design de UI. Minha primeira solicitação é: "Crie um gerador de masmorras infinitas 2D usando Autômatos Celulares para paredes semelhantes a cavernas e uma lógica separada de BSP (Particionamento Binário de Espaço) para conectividade de salas." --- **Pseudocódigo do Algoritmo de Geração** ``` // Parâmetros globais seed = 12345 rng = new Random(seed) tileSize = 32 chunkSize = 64 // tamanho do chunk em tiles caveDensity = 0.45 // densidade inicial de paredes para CA smoothingIterations = 4 // iterações de suavização CA roomMinSize = 6 // tamanho mínimo de sala BSP roomMaxSize = 12 // tamanho máximo de sala BSP corridorWidth = 2 // largura do corredor // Estrutura de dados do tilemap (por chunk) struct Tile { int type; // 0 = vazio, 1 = parede, 2 = piso de sala, 3 = piso de corredor bool visited; // para flood fill } // Função principal: gera um chunk infinito baseado em coordenadas function generateChunk(int chunkX, int chunkY) -> Tile[chunkSize][chunkSize] { // Inicializa o chunk com base na semente derivada das coordenadas int localSeed = hash(seed, chunkX, chunkY) rng = new Random(localSeed) // Passo 1: Geração de cavernas via Autômatos Celulares Tile[chunkSize][chunkSize] caveMap = initializeCaveMap(rng) for (i = 0; i < smoothingIterations; i++) { caveMap = applyCellularAutomata(caveMap) } // Passo 2: Geração de salas via BSP List<Room> rooms = generateBSPRooms(rng, chunkSize, chunkSize) // Passo 3: Integração - sobrepõe salas no mapa de cavernas Tile[chunkSize][chunkSize] finalMap = caveMap for (room in rooms) { for (y = room.y; y < room.y + room.height; y++) { for (x = room.x; x < room.x + room.width; x++) { finalMap[x][y].type = 2 // piso de sala } } } // Passo 4: Conectividade - conecta salas com corredores (BSP tree) connectRooms(finalMap, rooms) // Passo 5: Verificação de acessibilidade (Flood Fill) if (!isReachable(finalMap)) { // Se falhar, ajusta com corredores adicionais ou remove blocos isolados addFallbackCorridors(finalMap, rooms) } return finalMap } // Função de Autômatos Celulares function initializeCaveMap(rng) -> Tile[chunkSize][chunkSize] { Tile[chunkSize][chunkSize] map for (y = 0; y < chunkSize; y++) { for (x = 0; x < chunkSize; x++) { if (rng.nextFloat() < caveDensity) { map[x][y].type = 1 // parede } else { map[x][y].type = 0 // vazio } } } return map } function applyCellularAutomata(Tile[chunkSize][chunkSize] map) -> Tile[chunkSize][chunkSize] { Tile[chunkSize][chunkSize] newMap = copy(map) for (y = 0; y < chunkSize; y++) { for (x = 0; x < chunkSize; x++) { int wallCount = countNeighborWalls(map, x, y) if (map[x][y].type == 1) { // Regra: parede sobrevive se tiver 4-7 vizinhos parede if (wallCount >= 4 && wallCount <= 7) { newMap[x][y].type = 1 } else { newMap[x][y].type = 0 } } else { // Regra: vazio vira parede se tiver 5+ vizinhos parede if (wallCount >= 5) { newMap[x][y].type = 1 } else { newMap[x][y].type = 0 } } } } return newMap } function countNeighborWalls(Tile[chunkSize][chunkSize] map, int x, int y) -> int { int count = 0 for (dy = -1; dy <= 1; dy++) { for (dx = -1; dx <= 1; dx++) { if (dx == 0 && dy == 0) continue int nx = x + dx int ny = y + dy // Trata bordas como parede (para consistência entre chunks) if (nx < 0 || nx >= chunkSize || ny < 0 || ny >= chunkSize) { count++ } else if (map[nx][ny].type == 1) { count++ } } } return count } // Função BSP para salas function generateBSPRooms(rng, int width, int height) -> List<Room> { // Cria árvore BSP recursivamente Node root = new Node(0, 0, width, height) splitNode(root, rng, 0) // profundidade máxima 4 List<Room> rooms = [] collectRooms(root, rng, rooms) return rooms } function splitNode(Node node, rng, int depth) { if (depth >= 4 || node.width < roomMinSize * 2 || node.height < roomMinSize * 2) { // Nó folha: cria sala int roomW = rng.nextInt(roomMaxSize - roomMinSize) + roomMinSize int roomH = rng.nextInt(roomMaxSize - roomMinSize) + roomMinSize int roomX = node.x + rng.nextInt(node.width - roomW) int roomY = node.y + rng.nextInt(node.height - roomH) node.room = new Room(roomX, roomY, roomW, roomH) return } // Divide horizontal ou verticalmente boolean splitHorizontal = rng.nextBoolean() if (splitHorizontal) { int splitY = node.y + rng.nextInt(node.height - roomMinSize * 2) + roomMinSize node.left = new Node(node.x, node.y, node.width, splitY - node.y) node.right = new Node(node.x, splitY, node.width, node.y + node.height - splitY) } else { int splitX = node.x + rng.nextInt(node.width - roomMinSize * 2) + roomMinSize node.left = new Node(node.x, node.y, splitX - node.x, node.height) node.right = new Node(splitX, node.y, node.x + node.width - splitX, node.height) } splitNode(node.left, rng, depth + 1) splitNode(node.right, rng, depth + 1) } function collectRooms(Node node, rng, List<Room> rooms) { if (node.room != null) { rooms.add(node.room) } else { collectRooms(node.left, rng, rooms) collectRooms(node.right, rng, rooms) } } // Conecta salas usando a árvore BSP (corredores entre nós irmãos) function connectRooms(Tile[chunkSize][chunkSize] map, List<Room> rooms) { // Para cada par de salas irmãs na árvore, cria corredor // (Simplificação: conecta salas em ordem sequencial) for (i = 0; i < rooms.size() - 1; i++) { Room roomA = rooms[i] Room roomB = rooms[i + 1] createCorridor(map, roomA, roomB) } } function createCorridor(Tile[chunkSize][chunkSize] map, Room a, Room b) { int startX = a.x + a.width / 2 int startY = a.y + a.height / 2 int endX = b.x + b.width / 2 int endY = b.y + b.height / 2 // Corredor em L: primeiro horizontal, depois vertical for (int x = min(startX, endX); x <= max(startX, endX); x++) { for (int w = 0; w < corridorWidth; w++) { int y = startY + w - corridorWidth / 2 if (y >= 0 && y < chunkSize) { map[x][y].type = 3 // piso de corredor } } } for (int y = min(startY, endY); y <= max(startY, endY); y++) { for (int w = 0; w < corridorWidth; w++) { int x = endX + w - corridorWidth / 2 if (x >= 0 && x < chunkSize) { map[x][y].type = 3 } } } } // Verificação de acessibilidade via Flood Fill function isReachable(Tile[chunkSize][chunkSize] map) -> bool { // Encontra primeiro piso (tipo 2 ou 3) int startX = -1, startY = -1 for (y = 0; y < chunkSize; y++) { for (x = 0; x < chunkSize; x++) { if (map[x][y].type >= 2) { startX = x startY = y break } } if (startX != -1) break } if (startX == -1) return false // sem piso // Flood Fill iterativo Stack<Point> stack = new Stack() stack.push(new Point(startX, startY)) map[startX][startY].visited = true int reachableCount = 0 int totalFloorCount = 0 // Conta total de pisos for (y = 0; y < chunkSize; y++) { for (x = 0; x < chunkSize; x++) { if (map[x][y].type >= 2) totalFloorCount++ } } while (!stack.isEmpty()) { Point p = stack.pop() reachableCount++ for (int dy = -1; dy <= 1; dy++) { for (int dx = -1; dx <= 1; dx++) { if (abs(dx) + abs(dy) != 1) continue // apenas 4 direções int nx = p.x + dx int ny = p.y + dy if (nx >= 0 && nx < chunkSize && ny >= 0 && ny < chunkSize) { if (map[nx][ny].type >= 2 && !map[nx][ny].visited) { map[nx][ny].visited = true stack.push(new Point(nx, ny)) } } } } } // Reseta visited para próximo uso for (y = 0; y < chunkSize; y++) { for (x = 0; x < chunkSize; x++) { map[x][y].visited = false } } return reachableCount == totalFloorCount } function addFallbackCorridors(Tile[chunkSize][chunkSize] map, List<Room> rooms) { // Se flood fill falhar, conecta salas diretamente com corredores adicionais for (i = 0; i < rooms.size(); i++) { for (j = i + 1; j < rooms.size(); j++) { if (!isReachable(map)) break createCorridor(map, rooms[i], rooms[j]) } } } // Estrutura de dados auxiliar struct Room { int x, y, width, height } struct Node { int x, y, width, height Node left, right Room room } struct Point { int x, y } ``` --- **Estrutura de Dados para o Sistema de Grade/Tilemap** ``` // Tilemap por chunk, com hash de semente para infinito class InfiniteTilemap { Map<ChunkCoord, Tile[chunkSize][chunkSize]> chunks int chunkSize function getTile(int worldX, int worldY) -> Tile { int chunkX = floor(worldX / chunkSize) int chunkY = floor(worldY / chunkSize) int localX = worldX mod chunkSize int localY = worldY mod chunkSize Tile[chunkSize][chunkSize] chunk = getOrGenerateChunk(chunkX, chunkY) return chunk[localX][localY] } function getOrGenerateChunk(int chunkX, int chunkY) -> Tile[chunkSize][chunkSize] { ChunkCoord key = new ChunkCoord(chunkX, chunkY) if (!chunks.containsKey(key)) { chunks.put(key, generateChunk(chunkX, chunkY)) } return chunks.get(key) } } struct ChunkCoord { int x, y // Implementar equals/hashCode para uso como chave } ``` --- **Lógica de Acessibilidade (A* ou Flood Fill)** - **Flood Fill** (usado acima): Verifica se todos os tiles de piso (tipo 2 ou 3) são alcançáveis a partir de um ponto inicial. Complexidade O(N), onde N é o número de tiles no chunk. - **A*** (alternativa para pathfinding em tempo real): Usado para encontrar caminhos entre salas específicas, mas não necessário para validação de geração. Para garantir acessibilidade global, o Flood Fill é mais eficiente. **Parâmetros de Controle** - **Entropia**: Controlada pela `caveDensity` (0.45) e pelas regras de CA (limiares 4-7 e 5). Aumentar `caveDensity` gera mais paredes, reduzindo entropia de espaços abertos. - **Densidade**: `roomMinSize` e `roomMaxSize` definem a densidade de salas. Corredores com `corridorWidth` controlam a densidade de conexões. - **Aleatoriedade baseada em semente**: `seed` global + `hash(seed, chunkX, chunkY)` garante que cada chunk seja determinístico e infinito, sem repetição global. **Notas de Implementação** - Para chunks vizinhos, as bordas do CA são tratadas como paredes para evitar inconsistências, mas isso pode criar desconexões entre chunks. Para resolver, considere gerar chunks com sobreposição de 1 tile e mesclar bordas. - A conectividade entre chunks é garantida por corredores que cruzam bordas, mas a verificação de acessibilidade deve ser feita em uma área maior (por exemplo, 3x3 chunks) para evitar ilhas isoladas.