Dungeon Generation Algorithms

Overview

The AI Dungeon Generator uses advanced AI algorithms to create unique, procedurally generated dungeons. This page explains the three core algorithms used in the generation process and how they work together to create compelling dungeons.

Algorithm Components

The generation process combines three primary algorithms:

1. Cellular Automata - Creates organic, natural-looking room layouts
2. Markov Chain Model - Ensures theme coherence and logical room transitions
3. Genetic Algorithm - Optimizes layouts for playability, aesthetics, and challenge

Let's explore each of these in detail.

Cellular Automata

Purpose

Cellular automata create natural-looking cave systems and room layouts that avoid the artificial feel of traditional grid-based dungeon generators.

How It Works

1. Initialization: The generator starts with a grid where each cell has a random chance to be a "room" or "wall"
2. Rule Application: For multiple iterations, each cell's state is updated based on neighboring cells
3. Smoothing: The results are smoothed to create coherent room structures

Implementation Details

The plugin uses a modified Conway's Game of Life ruleset:

private boolean[][] doSimulationStep(boolean[][] oldMap, int size) {
    boolean[][] newMap = new boolean[size][size];
    
    // Evaluate each cell in the grid
    for (int x = 0; x < size; x++) {
        for (int y = 0; y < size; y++) {
            // Count neighbors (including diagonals)
            int neighbors = countNeighbors(oldMap, x, y, size);
            
            // Apply cellular automata rules
            if (oldMap[x][y]) {
                // Currently a room
                newMap[x][y] = neighbors >= deathLimit;
            } else {
                // Currently empty
                newMap[x][y] = neighbors > birthLimit;
            }
        }
    }
    
    return newMap;
}

Parameters

The cellular automata system can be tuned with several parameters:

• initialFillPercent - Initial percentage of cells that are rooms (default: 45%)
• iterations - Number of rule application cycles (default: 4)
• birthLimit - Min neighbors needed to create a new room (default: 4)
• deathLimit - Min neighbors needed to keep a room (default: 3)

Results

This algorithm produces cave-like structures with natural-feeling room shapes and connections, avoiding the grid-like appearance of traditional room-and-corridor designs.

Markov Chain Model

Purpose

The Markov Chain model ensures that room types follow logical patterns and theme consistency, creating coherent dungeon layouts with proper progression.

How It Works

1. Transition Matrix: The model uses a probability matrix that defines likely transitions between room types
2. Room Type Assignment: After the cellular automata creates the basic layout, the Markov Chain assigns specific room types
3. Theme Coherence: Ensures that room types make sense for the dungeon's theme and create a logical progression

Implementation Details

The transition probability matrix determines which room types are likely to be adjacent:

private void initializeTransitionProbabilities() {
    // For each source room type
    for (RoomType sourceType : RoomType.values()) {
        Map<RoomType, Double> transitions = new HashMap<>();
        transitionProbabilities.put(sourceType, transitions);
        
        // For each destination room type
        for (RoomType destType : RoomType.values()) {
            // Set default probabilities
            double probability = 0.0;
            
            if (sourceType == RoomType.EMPTY) {
                // Empty cells should stay empty
                probability = (destType == RoomType.EMPTY) ? 1.0 : 0.0;
            } else if (sourceType == RoomType.ENTRANCE) {
                // Entrance should connect to normal rooms
                probability = (destType == RoomType.NORMAL) ? 0.9 : 0.1;
            } else if (sourceType == RoomType.NORMAL) {
                // Normal rooms can connect to various types
                switch (destType) {
                    case NORMAL:
                        probability = 0.7;  // Most likely another normal room
                        break;
                    case TREASURE:
                        probability = 0.1;  // Sometimes treasure
                        break;
                    case TRAP:
                        probability = 0.15; // Sometimes traps
                        break;
                    case BOSS:
                        probability = 0.05; // Rarely boss rooms
                        break;
                    default:
                        probability = 0.0;  // Never others
                }
            } else if (sourceType.isSpecial()) {
                // Special rooms mostly connect back to normal rooms
                probability = (destType == RoomType.NORMAL) ? 0.9 : 0.1;
            }
            
            transitions.put(destType, probability);
        }
    }
}

Parameters

The Markov Chain can be customized through:

• transitionProbabilities - Matrix of room type transition probabilities
• Room type distributions specific to dungeon themes

Results

The Markov Chain creates logical room progressions that feel properly designed:

• Treasure rooms are appropriately rare
• Boss rooms are placed at logical endpoints
• Trap rooms are interspersed at appropriate intervals
• Special rooms are connected to normal rooms for proper flow

Genetic Algorithm

Purpose

The genetic algorithm optimizes dungeon layouts for playability, challenge balance, and aesthetic appeal, taking the raw output from the previous algorithms and refining it.

How It Works

1. Population: Creates multiple variations of the dungeon layout
2. Fitness Evaluation: Evaluates each layout based on various criteria
3. Selection: Chooses the best layouts for "breeding"
4. Crossover & Mutation: Combines and modifies layouts to create new variations
5. Evolution: Repeats the process for multiple generations to optimize

Implementation Details

The genetic algorithm evaluates dungeons based on multiple fitness criteria:

void calculateFitness() {
    double score = 0.0;
    
    // 1. Connectivity - reward well-connected layouts
    score += evaluateConnectivity() * 0.4;
    
    // 2. Room distribution - reward good room type distribution
    score += evaluateRoomDistribution() * 0.3;
    
    // 3. Aesthetics - reward interesting shapes
    score += evaluateAesthetics() * 0.2;
    
    // 4. Challenge balance - reward good difficulty progression
    score += evaluateChallenge() * 0.1;
    
    this.fitness = score;
}

Fitness Criteria

The algorithm evaluates layouts on four main criteria:

1. Connectivity: How well rooms are connected and accessible from the entrance

   private double evaluateConnectivity() {
       // Count accessible rooms using flood fill
       boolean[][] visited = new boolean[size][size];
       int accessibleRooms = floodFill(entranceX, entranceY, visited);
       
       // Calculate percentage of accessible rooms
       int totalRooms = countTotalRooms();
       return (double) accessibleRooms / totalRooms;
   }
   

2. Room Distribution: Proper mix of room types (normal, treasure, trap, boss)

   private double evaluateRoomDistribution() {
       // Count room types
       int normalRooms = countRoomsByType(RoomType.NORMAL);
       int treasureRooms = countRoomsByType(RoomType.TREASURE);
       int trapRooms = countRoomsByType(RoomType.TRAP);
       int bossRooms = countRoomsByType(RoomType.BOSS);
       
       // Calculate ideal distributions and score
       // [calculation logic...]
       
       return distributionScore;
   }
   

3. Aesthetics: Interesting and varied room shapes and layouts

   private double evaluateAesthetics() {
       // Count different room shapes/clusters
       int shapes = countRoomShapes();
       
       // Score based on variety
       return calculateShapeScore(shapes);
   }
   

4. Challenge Balance: Proper difficulty progression with boss placement

   private double evaluateChallenge() {
       // Boss distance from entrance
       double bossDistanceScore = evaluateBossDistance();
       
       // Trap distribution
       double trapDistributionScore = evaluateTrapDistribution();
       
       return bossDistanceScore * 0.6 + trapDistributionScore * 0.4;
   }
   

Parameters

The genetic optimization can be tuned with:

• populationSize - Number of layout variations per generation (default: 10)
• generations - Number of evolution cycles (default: varies by dungeon size)
• mutationRate - Chance of random changes (default: 0.2)
• crossoverRate - Rate of breeding between layouts (default: 0.7)

Results

The genetic algorithm refines dungeons to ensure they are:

• Fully connected with no isolated rooms
• Well-balanced with proper room type distribution
• Aesthetically interesting with varied layouts
• Properly challenging with good progression

Combined Process

The complete generation process flows as follows:

1. Initial Layout: Cellular automata creates the basic room structure
2. Room Type Assignment: Markov Chain assigns room types and ensures theme coherence
3. Layout Optimization: Genetic algorithm refines the dungeon for playability and balance
4. World Generation: The optimized layout is translated into actual Minecraft blocks
5. Feature Placement: Traps, monsters, treasures, and quest markers are placed in appropriate locations

Advanced Configuration

Advanced users can fine-tune the algorithms through the config.yml file:

generation:
  algorithm:
    room-size: 
      min: 5
      max: 15
    corridor-length:
      min: 3
      max: 10
    dungeon-size:
      small: 25
      medium: 40
      large: 60
    optimization-generations: 10
    cellular-automata:
      initial-fill: 45
      iterations: 4
      birth-limit: 4
      death-limit: 3
    markov:
      enforce-boss-room: true
      min-treasure-rooms: 2
      max-trap-density: 0.15
    genetic:
      population-size: 10
      mutation-rate: 0.2
      crossover-rate: 0.7

Technical Details

Asynchronous Generation

To prevent server lag, the generation process runs asynchronously:

private void processGenerationTaskAsync(GenerationTask task) {
    Bukkit.getScheduler().runTaskAsynchronously(plugin, () -> {
        try {
            // Generate dungeon layout asynchronously
            DungeonLayout layout = dungeonGenerator.generateDungeonAsync(task.getArea());
            
            // Schedule synchronous placement in world
            Bukkit.getScheduler().runTask(plugin, () -> {
                placeDungeonInWorld(layout, task.getArea());
                // [additional processing...]
            });
        } catch (Exception e) {
            plugin.getLogger().severe("Error generating dungeon: " + e.getMessage());
            // [error handling...]
        }
    });
}

Runtime Complexity

• Cellular Automata: O(n² * i) where n is dungeon size and i is iterations
• Markov Chain: O(n²) for room type assignment
• Genetic Algorithm: O(p * g * n²) where p is population size and g is generations

Memory Usage

The algorithms are designed to be memory-efficient, with a typical dungeon requiring:

• ~250KB for grid representation
• ~1-2MB during genetic optimization
• ~500KB for the final layout