{"id":80,"date":"2025-01-14T23:47:41","date_gmt":"2025-01-14T23:47:41","guid":{"rendered":"https:\/\/blogs.oregonstate.edu\/codedcat\/?p=80"},"modified":"2025-01-14T23:47:41","modified_gmt":"2025-01-14T23:47:41","slug":"back-to-work-winter-term-adventures-with-bsp-and-procedural-maps","status":"publish","type":"post","link":"https:\/\/blogs.oregonstate.edu\/codedcat\/2025\/01\/14\/back-to-work-winter-term-adventures-with-bsp-and-procedural-maps\/","title":{"rendered":"Back to Work: Winter Term Adventures with BSP and Procedural Maps"},"content":{"rendered":"\n

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<\/strong> (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.<\/p>\n\n\n\n

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

\n\n\n\n

\ud83c\udfaf What is Binary Space Partitioning?<\/strong><\/h2>\n\n\n\n

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.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

\n\n\n\n

\ud83d\udee0 Step 1: Implementing BSP Partitioning<\/strong><\/h2>\n\n\n\n

Here\u2019s a simplified version of how BSP works in our project:<\/p>\n\n\n

\nfunction partitionMap(width, height, minSize) {\n    if (width &lt;= minSize || height &lt;= minSize) {\n        return [createRegion(width, height)];\n    }\n\n    let splitVertical = Math.random() &gt; 0.5;\n    let splitPoint = randomPoint(minSize, splitVertical ? width : height);\n\n    let region1, region2;\n    if (splitVertical) {\n        region1 = partitionMap(splitPoint, height, minSize);\n        region2 = partitionMap(width - splitPoint, height, minSize);\n    } else {\n        region1 = partitionMap(width, splitPoint, minSize);\n        region2 = partitionMap(width, height - splitPoint, minSize);\n    }\n\n    return [...region1, ...region2];\n}\n\n<\/pre><\/div>\n\n\n
In plain English, we:<\/p>\n\n\n\n
    \n
  1. Check if the current region is small enough. If yes, stop splitting.<\/li>\n\n\n\n
  2. Randomly decide whether to split the region vertically or horizontally.<\/li>\n\n\n\n
  3. Calculate where to split the region.<\/li>\n\n\n\n
  4. Recursively split the resulting subregions.<\/li>\n<\/ol>\n\n\n\n
    The result? A beautifully partitioned map, ready for more detailed terrain generation!<\/p>\n\n\n\n
    \n\n\n\n
    \ud83c\udf04 Step 2: Integrating BSP with the Map Generator<\/strong><\/h2>\n\n\n\n
    After implementing BSP, we integrated it into our existing map generation system. The MapGenerator<\/code> class was modified to use BSP to partition the map grid and apply Perlin Noise within each partitioned region.<\/p>\n\n\n\n
    If you’re unfamiliar with Perlin Noise, I covered it in a previous post. You can check out this blog post<\/a> for a deep dive into how Perlin Noise works and how we use it for natural-looking terrain.<\/p>\n\n\n\n
    Here\u2019s a high-level overview of how we did it:<\/p>\n\n\n
    \nclass MapGenerator {\n    constructor(width, height, minSize) {\n        this.width = width;\n        this.height = height;\n        this.minSize = minSize;\n        this.perlin = new PerlinNoise(width, height);\n        this.bsp = new BSPPartition(width, height, minSize);\n\n        this.grid = this.generateMap();\n    }\n\n    generateMap() {\n        const grid = [];\n        const partitions = this.bsp.partition({ x: 0, y: 0, width: this.width, height: this.height });\n\n        partitions.forEach(partition =&gt; {\n            for (let y = partition.y; y &lt; partition.y + partition.height; y++) {\n                const row = [];\n                for (let x = partition.x; x &lt; partition.x + partition.width; x++) {\n                    const noiseValue = this.perlin.getNoise(x, y);\n                    const terrain = this.getTerrainFromNoise(noiseValue);\n                    row.push(new TerrainTile(x, y, terrain));\n                }\n                grid.push(row);\n            }\n        });\n\n        return grid;\n    }\n\n    getTerrainFromNoise(value) {\n        if (value &lt; -0.5) return 'water';\n        if (value &lt; 0) return 'forest';\n        if (value &lt; 0.5) return 'grass';\n        return 'shrub';\n    }\n}\n\n<\/pre><\/div>\n\n\n
    By integrating BSP, we ensured that each partitioned region could have unique terrain features, making our maps more diverse and engaging.<\/p>\n\n\n\n
    \n\n\n\n
    \ud83d\udee0 Step 3: Debugging with Utility Functions<\/strong><\/h2>\n\n\n\n
    Debugging procedural generation can be tricky, so we added some utility functions to help visualize the results. For example:<\/p>\n\n\n
    \nfunction printMap(grid) {\n    grid.forEach(row =&gt; {\n        console.log(row.map(tile =&gt; tile.terrain).join(' | '));\n    });\n}\n\n<\/pre><\/div>\n\n\n
    This prints the terrain types for each tile in the grid, making it easier to spot any anomalies.<\/p>\n\n\n\n
    \n\n\n\n
    \u2705 Why BSP and Perlin Noise Work Well Together<\/strong><\/h2>\n\n\n\n
    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.<\/p>\n\n\n\n
    By combining these techniques, we can generate diverse maps with different terrain features, making our game more engaging and realistic.<\/p>\n\n\n\n
    \n\n\n\n
    \ud83d\udc3e Bonus Cat Photo!<\/strong><\/h3>\n\n\n
    \n
    \"\"<\/figure>\n<\/div>\n\n\n
    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!<\/p>\n","protected":false},"excerpt":{"rendered":"
    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, … Continue reading “Back to Work: Winter Term Adventures with BSP and Procedural Maps”<\/span><\/a><\/p>\n","protected":false},"author":14468,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-80","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/blogs.oregonstate.edu\/codedcat\/wp-json\/wp\/v2\/posts\/80","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.oregonstate.edu\/codedcat\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.oregonstate.edu\/codedcat\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/codedcat\/wp-json\/wp\/v2\/users\/14468"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/codedcat\/wp-json\/wp\/v2\/comments?post=80"}],"version-history":[{"count":1,"href":"https:\/\/blogs.oregonstate.edu\/codedcat\/wp-json\/wp\/v2\/posts\/80\/revisions"}],"predecessor-version":[{"id":82,"href":"https:\/\/blogs.oregonstate.edu\/codedcat\/wp-json\/wp\/v2\/posts\/80\/revisions\/82"}],"wp:attachment":[{"href":"https:\/\/blogs.oregonstate.edu\/codedcat\/wp-json\/wp\/v2\/media?parent=80"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/codedcat\/wp-json\/wp\/v2\/categories?post=80"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/codedcat\/wp-json\/wp\/v2\/tags?post=80"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}