Introduction

In Mad Island, the entire game takes place on a single island. And being a roguelike. there's lots of dying and starting over. So each run needs to take place on a newly generated island. That being the case, I needed a good (and preferably fast) way of creating that island each time. After some experimentation with various methods, I settled on the one I'm about to outline in this post.

The speed of this algorithm comes from its simplicity. I'm not trying to simulation the buildup of the landmasses that would create an island, or figure out how erosion would create rivers or how mountains would be developed. I just needed something that would give me an interesting looking island shape.

Limitations

Here are the limitations for my particular game I was working within:

• Has to be completely contained within the map area, fully surrounded by water.
• Has to work on a square, relatively low-res grid. For the final game I used a 70x50 tile map.
• Has to have a volcano in the center of the island (because of course).

Overview

Given all that, here's an overview of the process I came up with:

• Start in the center of the map and run a random walk algorithm until some number of tiles have been visited.
• Guard against infinite loops and getting too close to the edge of the map.
• Do this some number of times (I used three) and combine the results of each iteration together to create a more filled out mass.
• Find the general center of the island using a process called inside buffering.
• Create the volcano at the that center tile using a simplified combination of random walk and buffering.

Here's are some examples of generated islands using those steps:

I want to emphasize that third point about running the random walk algorithm more than once. I found that doing it only one time could result in an island that was too small or too odd looking. I wanted to hedge my bets and have a better guarantee of generating one that would fill out the entire area and have more of a rounded island shape every time. So the solution there was to simply run it more than once and combine the results of each pass. Here's an example of the output after each iteration, and you can see how the island continues to grow and take shape each time.

Code

About the actual code, I debated about whether or not to add it here because it would take quite a bit of time and effort to extract and simplify what I use for the game itself to create a fully working version independent of my use of it. But I'll go ahead and paste in the two main algorithms as-is in the off chance that they'll be useful to someone.

Here's the random walk function. This is C#, so you'll see some Linq in there. And the helper functions I use are extremely simple and should be common enough that it's not worth including them. And like I said, I run this three times to get the full island.

void SetIslandTiles()
{
    // Put a limit on the algorithm as a general safety net.
    const int maxIterations = 1000;
    // Make sure we can break out of any infinite loops by limiting
    // the number of times we can visit the same tile.
    const int numRepeatsMax = 4;
    var curTile = Tiles[Width / 2][Height / 2];
    var curIterations = 0;
    var numRepeats = 0;
    var numVisited = 0;
    while (numVisited < _desiredWalkableCount && curIterations < maxIterations)
    {
        curIterations++;
        if (numRepeats > numRepeatsMax)
        {
            // It's possible to get in an loop where we keep walking over the same
            // tiles, so check to see if that's happened and then find a new random             // tile from the outer visited tiles and make that the current one.
            curTile = Tiles
                .Where(t => !t.IsVisited)
                .Where(c => !IsEdgeTile(c))
                .Where(c => c.SafeNeighborTiles.Any(sc => sc.IsWalkable))
                .RandomElement(Nez.Random.random);
        }
        if (IsEdgeTile(curTile, 2))
        {
            // Bail if we hit the edge of the map area, and increment the repeat count             // so that a new current tile can be picked if needed.
            numRepeats++;
            continue;
        }
        if (curTile.IsVisited)
        {
            // Make a note of the fact that we hit a tile we've already been to.
            numRepeats++;
        }
        else
        {
            // We found a new valid tile, so keep track of it and update our
            // bookkeeping numbers.
            curTile.IsWalkable = true;
            curTile.IsVisited = true;
            numRepeats = 0;
            numVisited++;
        }
        // Pick a new random tile from the ones surrounding the current tile
        // and keep going.
        curTile = curTile.SafeNeighborTiles.RandomElement(Globals.Random);
    }
    // Reset the visited property of all tiles since we use that elsewhere.
    ResetVisitedTiles();
}

And here's the code to find the center of the island. The process involves finding all the border tiles of the largest walkable tile group. These are the tiles that aren't completely surrounded by other walkable tiles. Once you've found those, store them, find the next set of innermost border tiles, store those, and then keep repeating until you run out of tiles. You're basically working your way inward from the edge of the island until there's nowhere else to go.

public MapTile GetCenterTile()
{
    // Reset the visited property because we'll be using that later.
    for (var i = 0; i < Tiles.Count; i++)
    {
        Tiles[i].IsVisited = false;
    }
    // First get all of the tiles around the edge of the region,
    // meaning the border between walkable and blocking.
    var curEdgeTiles = Tiles
        .Where(t => t.IsWalkable && t.SafeNeighborTiles.Any(nt => nt.IsBlocking))
        .Distinct()
        .ToList();
    var lastEdgeTiles = new List<MapTile>();
    // Now get the next set of border tiles in from the current set of border tiles,
    // and keep doing that, replacing the current set each time, until we've processed
    // all of the walkable tiles and found the set that are the furthest in.
    while (curEdgeTiles.Any())
    {
        for (int i = 0; i < curEdgeTiles.Count; i++)
        {
            curEdgeTiles[i].IsVisited = true;
        }
        lastEdgeTiles = curEdgeTiles;
        curEdgeTiles = curEdgeTiles
            .SelectMany(t => t.SafeNeighborTiles.Where(nt => nt.IsWalkable && !nt.IsVisited))
            .Distinct()
            .ToList();
    }
    // Pick a random tile from the last set of border tiles we found and use that as the center.
    return lastEdgeTiles.RandomElement(Globals.Random);
}

Closing Thoughts

That's all. I hope it's useful. I found it to be a simple and cheap solution to creating interesting island-like shapes. My implementation could be further optimized for larger maps, and there are a number of knobs you could build in to fine-tune the output for your specific needs.

To close, here's an example of what a final island would look like in the game. I didn't mention it before, but the shoreline is created using an algorithm that includes bits of the two functions above. It's just the result of the first pass at getting the border tiles for the inner buffering process, along with a bit of recursive random walking to break up the inner edge. And that lava tile is the same one returned from the GetCenterTile() function.

Enjoy!