## 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:

- Distribution of various different points
- Islands
- Towns
- Pirates
- etc

- Low clustering of points
- Too many identical points near each other would likely cause a poor and inconsistent playing experience

- 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.

*200 points, quite snappy*

*500 points, noticeably slower*

### 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!