Experte für prozedurale Inhaltsgenerierung für Spielumgebungen

Erstelle einen 2D-unendlichen Dungeon-Generator unter Verwendung von Cellular Automata für höhlenartige Wände und einer separaten BSP-Logik (Binary Space Partitioning) für Raumverbindungen. ```pseudocode // Hauptalgorithmus FUNCTION generateInfiniteDungeon(seed, chunkSize, density, entropy) SET randomGenerator = new Random(seed) SET chunkMap = new HashMap<Vector2, Chunk>() WHILE true Vector2 chunkPos = getNextChunkPosition() // z.B. spiral order IF NOT chunkMap.contains(chunkPos) Chunk newChunk = generateChunk(chunkPos, chunkSize, density, entropy, randomGenerator) chunkMap.put(chunkPos, newChunk) connectChunks(newChunk, chunkMap, randomGenerator) END IF END WHILE END FUNCTION // Chunk-Generierung FUNCTION generateChunk(chunkPos, chunkSize, density, entropy, randomGenerator) // Phase 1: Cellular Automata für Wände Grid grid = new Grid(chunkSize, chunkSize) grid.initializeRandom(density, randomGenerator) // Zufällige Belegung mit Dichte FOR iteration = 1 TO 4 // Anzahl der CA-Schritte Grid newGrid = grid.copy() FOR each cell in grid INT wallCount = countNeighbors(cell, grid, radius=1) IF cell.isWall IF wallCount < 4 THEN newGrid.setCell(cell, FLOOR) ELSE newGrid.setCell(cell, WALL) ELSE IF wallCount > 5 THEN newGrid.setCell(cell, WALL) ELSE newGrid.setCell(cell, FLOOR) END IF END FOR grid = newGrid END FOR // Phase 2: BSP für Räume und Verbindungen BSPNode root = new BSPNode(0, 0, chunkSize, chunkSize) root.split(randomGenerator, minRoomSize=6, maxDepth=5) List<Room> rooms = [] root.generateRooms(randomGenerator, rooms) // Jeder Blattknoten erzeugt einen Raum FOR each room in rooms carveRoom(grid, room) // Rechteckige Räume in die CA-Karte schneiden END FOR // Phase 3: Verbindungen zwischen Räumen (innerhalb des Chunks) List<Vector2> roomCenters = rooms.map(room -> room.center) FOR i = 0 TO roomCenters.size - 2 connectRooms(grid, roomCenters[i], roomCenters[i+1], randomGenerator) END FOR // Phase 4: Entropie-basierte Variation IF entropy > 0.5 addRandomDecorations(grid, randomGenerator, entropy) // z.B. zusätzliche Löcher oder Felsen END IF RETURN new Chunk(chunkPos, grid, rooms) END FUNCTION // Verbindung zwischen Chunks FUNCTION connectChunks(newChunk, chunkMap, randomGenerator) FOR each neighborPos in getNeighborPositions(newChunk.position) IF chunkMap.contains(neighborPos) Chunk neighbor = chunkMap.get(neighborPos) // Finde nächste Räume zwischen Chunks Room nearestRoomNew = findNearestRoomToEdge(newChunk, neighborPos) Room nearestRoomNeighbor = findNearestRoomToEdge(neighbor, newChunk.position) // Tunnel durch die Grenze graben carveTunnelBetweenChunks(newChunk, neighbor, nearestRoomNew, nearestRoomNeighbor, randomGenerator) END IF END FOR END FUNCTION // Datenstruktur für Grid/Tilemap CLASS Grid INT width, height ARRAY OF INT cells // 0 = FLOOR, 1 = WALL, 2 = ROOM_FLOOR, 3 = CORRIDOR METHOD initializeRandom(density, randomGenerator) FOR each cell in cells IF randomGenerator.nextFloat() < density THEN cells[cell] = WALL ELSE cells[cell] = FLOOR END FOR END METHOD METHOD countNeighbors(cell, radius) INT count = 0 FOR dx = -radius TO radius FOR dy = -radius TO radius IF dx == 0 AND dy == 0 THEN CONTINUE Vector2 neighbor = cell + (dx, dy) IF isInBounds(neighbor) AND cells[neighbor] == WALL THEN count++ END FOR END FOR RETURN count END METHOD METHOD isInBounds(pos) RETURN pos.x >= 0 AND pos.x < width AND pos.y >= 0 AND pos.y < height END METHOD END CLASS // BSP-Knoten CLASS BSPNode Rect bounds BSPNode left, right Room room METHOD split(randomGenerator, minSize, depth) IF depth <= 0 OR bounds.width < minSize*2 OR bounds.height < minSize*2 THEN RETURN BOOL splitHorizontal = randomGenerator.nextBoolean() IF splitHorizontal AND bounds.height >= minSize*2 INT splitY = randomGenerator.nextInt(minSize, bounds.height - minSize) left = new BSPNode(bounds.x, bounds.y, bounds.width, splitY) right = new BSPNode(bounds.x, bounds.y + splitY, bounds.width, bounds.height - splitY) ELSE IF NOT splitHorizontal AND bounds.width >= minSize*2 INT splitX = randomGenerator.nextInt(minSize, bounds.width - minSize) left = new BSPNode(bounds.x, bounds.y, splitX, bounds.height) right = new BSPNode(bounds.x + splitX, bounds.y, bounds.width - splitX, bounds.height) ELSE RETURN END IF left.split(randomGenerator, minSize, depth - 1) right.split(randomGenerator, minSize, depth - 1) END METHOD METHOD generateRooms(randomGenerator, roomList) IF left == NULL AND right == NULL INT roomWidth = randomGenerator.nextInt(4, bounds.width - 2) INT roomHeight = randomGenerator.nextInt(4, bounds.height - 2) INT roomX = bounds.x + randomGenerator.nextInt(1, bounds.width - roomWidth - 1) INT roomY = bounds.y + randomGenerator.nextInt(1, bounds.height - roomHeight - 1) room = new Room(roomX, roomY, roomWidth, roomHeight) roomList.add(room) ELSE left.generateRooms(randomGenerator, roomList) right.generateRooms(randomGenerator, roomList) END IF END METHOD END CLASS // Erreichbarkeitsprüfung (Flood Fill) FUNCTION isReachable(grid, startPos, endPos) Queue<Vector2> queue = new Queue() Set<Vector2> visited = new Set() queue.enqueue(startPos) visited.add(startPos) WHILE NOT queue.isEmpty() Vector2 current = queue.dequeue() IF current == endPos THEN RETURN TRUE FOR each neighbor in getFloorNeighbors(current, grid) IF NOT visited.contains(neighbor) visited.add(neighbor) queue.enqueue(neighbor) END IF END FOR END WHILE RETURN FALSE END FUNCTION // A* für Pfadfindung (optional, für Tunnel) FUNCTION findPath(grid, startPos, endPos) // Standard A* mit Manhattan-Distanz als Heuristik // Gibt Liste von Positionen zurück END FUNCTION // Hilfsfunktionen FUNCTION carveRoom(grid, room) FOR x = room.x TO room.x + room.width FOR y = room.y TO room.y + room.height grid.setCell(x, y, ROOM_FLOOR) END FOR END FOR END FUNCTION FUNCTION connectRooms(grid, centerA, centerB, randomGenerator) // L-förmiger Korridor Vector2 current = centerA WHILE current.x != centerB.x current.x += sign(centerB.x - current.x) grid.setCell(current, CORRIDOR) END WHILE WHILE current.y != centerB.y current.y += sign(centerB.y - current.y) grid.setCell(current, CORRIDOR) END WHILE END FUNCTION FUNCTION carveTunnelBetweenChunks(chunkA, chunkB, roomA, roomB, randomGenerator) // Tunnel durch die Grenze mit variabler Breite (1-3 Zellen) INT tunnelWidth = randomGenerator.nextInt(1, 3) Vector2 start = roomA.center Vector2 end = roomB.center // Pfad mit A* oder direktem L-Korridor über die Grenze List<Vector2> path = findPath(chunkA.grid, start, end) FOR each pos in path FOR dx = -tunnelWidth TO tunnelWidth FOR dy = -tunnelWidth TO tunnelWidth IF abs(dx) + abs(dy) <= tunnelWidth chunkA.grid.setCell(pos + (dx, dy), CORRIDOR) END IF END FOR END FOR END FOR END FUNCTION ``` **Datenstruktur für Grid/Tilemap:** - `Grid` Klasse mit 2D-Array von Integer-Werten (0 = Boden, 1 = Wand, 2 = Raum, 3 = Korridor) - `Chunk` Klasse enthält Position, Grid, und Liste von Räumen - `HashMap<Vector2, Chunk>` für unendliche Welt (nur geladene Chunks im Speicher) **Parameter:** - `density`: Initiale Wanddichte für Cellular Automata (0.4 - 0.6 typisch) - `entropy`: Steuert zusätzliche Variation (0.0 - 1.0), höhere Werte erzeugen mehr Löcher und unregelmäßige Formen - `seed`: Deterministische Zufallsbasis für reproduzierbare Welten **Erreichbarkeitslogik:** - Nach der Generierung jedes Chunks wird `isReachable` mit Flood Fill auf alle Raumzentren angewendet - Falls nicht erreichbar, werden zusätzliche Korridore mit `connectRooms` oder A* gegraben - Zwischen Chunks wird die Verbindung durch `carveTunnelBetweenChunks` sichergestellt, wobei die Grenzen überlappen **Hinweise zur Nicht-Wiederholung:** - Jeder Chunk verwendet einen Hash aus globalem Seed und Chunk-Position als lokalen Seed - Die BSP-Struktur wird pro Chunk neu aufgebaut, aber mit unterschiedlichen Zufallswerten - Entropie-Parameter kann adaptiv erhöht werden, wenn benachbarte Chunks zu ähnlich sind (optional)