Pieces of 8-Bit Windows game

Map Generation

Not only is Pieces of 8-Bit to be a roguelike, where random map generation is almost mandatory, exploration takes a particularly heavy focus since, you know, pirate game.

This was therefore recognised very early to be a thing that has to feel right, so today I'm going to describe how I have taken on this daunting task so far.

Aim

There are far too many ways to generate random maps that my mind can't possibly cope, so I sought to constrain the problem up front with a basic outline of what is desirable.

An acceptable game map was specified to be one which met the following:

1. Distribution of various different points
   • Islands
   • Towns
   • Pirates
   • etc
2. Low clustering of points
   • Too many identical points near each other would likely cause a poor and inconsistent playing experience
3. Non-regular placement
   • No grids! This is the ocean, not a chessboard

This led my investigations to node-based generation techniques, and what I have settled on (for now!) is based on Voronoi diagrams.

I won't try to explain fully how to (as there are far better tutorials than I can manage a small Google away), but I will instead detail them from the perspective of what they bring to the game.

Voronoi diagrams

A Voronoi diagram arranges points by a set of random polygons. The output of a basic computation is below:

The centroids of these polygons are the points we're interested in:

We can spot the undesirable effect right away - there is a lot of clustering. This would mean a very inconsistent and unpredictable pacing during travel.

This can be altered by performing the computation multiple times:

The above has performed the algorithm 3 times in a row, and we can see everything is a lot more regularly spaced, but still with a decent amount of organic random-ness.

Placing points

So from a Voronoi diagram I have a randomly-spaced bunch of points.

The next step is to make this a map by placing the points randomly. Easy, just assign a probability to each point type and press go, right?

... CLUSTERS...

Placing points completely randomly seems overall OK, but does create clusters of the same point type, which are sometimes notably large. This makes sense, since using a simple random chance means it's just as likely to have every port be placed adjacent to another port, as it is to have a completely even spread.

This violates my simple requirements, so I had to solve this.

Mathematics to the rescue!

Fortunately, this problem is one I'm more comfortable with than most I have faced, and so I wrote a very dumb mathematical optimiser which takes a set of points and tries to push identical point types away from each other.

If you're curious, the algorithm is based on simulated annealing.

This gives a much better spread of point types, for relatively little computation. The intention is that this will ensure that the player's always has a reasonable variety of different sites to explore in a given area.

Visual Polish

The point placement was sufficient, but there's still a major problem up to this point. The player will look at the map a LOT, so it has to look nice.

I decided I wanted a pixellated ocean backdrop to fix this. I'm nothing if not dedicated to a consistent visual theme.

Conveniently, in a previous hobby development project I had investigated different random noise algorithms - algorithms which generate a smooth random numbers through multple dimensions.

Perlin noise seems to be one of the most popular/well known of these, and Unity has an implementation built in. However, being a super awesome hardcore programmer, I opted to use OpenSimplex - basically Perlin's cooler younger brother.

Running this across the dimensions of the map is how I generate the following background sprite:

And that's all! I'm satisfied enough for now, such that only player feedback could guide any further improvements.

I have map generation down to a single script I can run where I give:

• Map size
• Seeds to use for random number generation (so I can reproducibly generate maps)
• Relative chance of each point type
• Some super special boring algorithm inputs

And out pops a map.

For early development, each game will have a fixed map size. Since I've built in a decent amount of customisation, I'll be able to define different map sizes/presets, and/or to expose direct customisation to the user, including for example allowing user-input seeds so that players can share a particularly interesting map.

Generation Speed

The GIFs below shows map generation in real-time for 200 and 500 points. The code is very sub-optimal, and I COULD work to make it faster but I resist for now. Since map generation is run once per game, I don't think this is necessary at this stage, if ever.

No code is sacred

I'm more than happy to share specifics of how things are done, right down to the C# code for anyone who is so inclined.

Just comment, message or tweet at me and I'll be happy to have a chat!