This week we took a look at a technique for generating random dungeons. Although never mentioned on the day, this technique is often called “marching squares”. It looks at the four corners of a space at a time, some of which are open and some of which are closed, and picks a shape that blocks off the closed corners.
There are sixteen possible combinations of corners on and off. All of these can be covered with these five shapes (or a rotation of them) to represent the closed off areas:
Generating the Dungeon
We generated a 2D array (a list of lists) to store our dungeon layout. At each point we used a 2D Perlin noise value (using the noise() function) to calculate a value. The point was deemed to be either open or closed based on whether this value was higher or lower than a threshold value we specified. Varying this threshold value can make the dungeon more open, or more closed in.
Drawing the Dungeon
To draw these shapes we first defined each of them as a list of x, y points defining the shape.
We then used beginShape(), vertex(), and endShape() functions to draw them at the correct size, location and orientation by scale(), transform() and rotate().
Once we were able to draw the shapes, we just needed to loop over our grid, inspecting each set of four adjacent corners in turn and drawing the appropriate shape.
Here’s a screenshot of one random dungeon. Dots (green for open, red for closed) are drawn to show the grid and the lines between the individual shapes are also shown for clarity:
and here is is without these overlays:
The files for this week can be found on our GitHub repository.