Back to Work: Winter Term Adventures with BSP and Procedural Maps

Hello again, and welcome back to The Coded Cat! After a much-needed holiday break, I’m diving back into our capstone project for winter term. This term, we’re continuing work on Wildfire Command (formerly known as Sim Firefighter), our browser-based wildfire management simulation. One of my recent tasks has been to improve our map generation system, and I wanted to share how we tackled this using Binary Space Partitioning (BSP) and Perlin Noise.

So, grab a cozy drink and let’s talk about procedural map generation (and how cats make debugging more fun).


🎯 What is Binary Space Partitioning?

Imagine you’re slicing a cake into smaller pieces. Binary Space Partitioning (BSP) is a method where we split a large space (like our map) into smaller regions by dividing it either vertically or horizontally. We keep slicing until all pieces are small enough to meet our minimum size requirement.

For our game, we use BSP to create distinct terrain zones (like forests, lakes, and firebreaks), which we then populate with Perlin Noise to add natural-looking variations.


🛠 Step 1: Implementing BSP Partitioning

Here’s a simplified version of how BSP works in our project:

function partitionMap(width, height, minSize) {
    if (width <= minSize || height <= minSize) {
        return [createRegion(width, height)];
    }

    let splitVertical = Math.random() > 0.5;
    let splitPoint = randomPoint(minSize, splitVertical ? width : height);

    let region1, region2;
    if (splitVertical) {
        region1 = partitionMap(splitPoint, height, minSize);
        region2 = partitionMap(width - splitPoint, height, minSize);
    } else {
        region1 = partitionMap(width, splitPoint, minSize);
        region2 = partitionMap(width, height - splitPoint, minSize);
    }

    return [...region1, ...region2];
}

In plain English, we:

  1. Check if the current region is small enough. If yes, stop splitting.
  2. Randomly decide whether to split the region vertically or horizontally.
  3. Calculate where to split the region.
  4. Recursively split the resulting subregions.

The result? A beautifully partitioned map, ready for more detailed terrain generation!


🌄 Step 2: Integrating BSP with the Map Generator

After implementing BSP, we integrated it into our existing map generation system. The MapGenerator class was modified to use BSP to partition the map grid and apply Perlin Noise within each partitioned region.

If you’re unfamiliar with Perlin Noise, I covered it in a previous post. You can check out this blog post for a deep dive into how Perlin Noise works and how we use it for natural-looking terrain.

Here’s a high-level overview of how we did it:

class MapGenerator {
    constructor(width, height, minSize) {
        this.width = width;
        this.height = height;
        this.minSize = minSize;
        this.perlin = new PerlinNoise(width, height);
        this.bsp = new BSPPartition(width, height, minSize);

        this.grid = this.generateMap();
    }

    generateMap() {
        const grid = [];
        const partitions = this.bsp.partition({ x: 0, y: 0, width: this.width, height: this.height });

        partitions.forEach(partition => {
            for (let y = partition.y; y < partition.y + partition.height; y++) {
                const row = [];
                for (let x = partition.x; x < partition.x + partition.width; x++) {
                    const noiseValue = this.perlin.getNoise(x, y);
                    const terrain = this.getTerrainFromNoise(noiseValue);
                    row.push(new TerrainTile(x, y, terrain));
                }
                grid.push(row);
            }
        });

        return grid;
    }

    getTerrainFromNoise(value) {
        if (value < -0.5) return 'water';
        if (value < 0) return 'forest';
        if (value < 0.5) return 'grass';
        return 'shrub';
    }
}

By integrating BSP, we ensured that each partitioned region could have unique terrain features, making our maps more diverse and engaging.


🛠 Step 3: Debugging with Utility Functions

Debugging procedural generation can be tricky, so we added some utility functions to help visualize the results. For example:

function printMap(grid) {
    grid.forEach(row => {
        console.log(row.map(tile => tile.terrain).join(' | '));
    });
}

This prints the terrain types for each tile in the grid, making it easier to spot any anomalies.


Why BSP and Perlin Noise Work Well Together

The combination of BSP and Perlin Noise gives us structured yet natural-looking maps. BSP ensures the map is divided into logical regions, while Perlin Noise adds the randomness and variation that makes each map feel unique.

By combining these techniques, we can generate diverse maps with different terrain features, making our game more engaging and realistic.


🐾 Bonus Cat Photo!

So this isn’t a photo of one of my cats, but it is a cat I saw in a Lego store when I went to visit family over the Holidays! I thought this display was really fun so I definitely had to share it!

Leave a Reply

Your email address will not be published. Required fields are marked *