A Drunkard's Walk with hiding spots

I’ve been playing around lately with procedural map generation and different ways to generate contiguous areas on a hexagonal grid. To keep things a simple as possible I started with a Random Walk (also known as “Drunkard’s Walk”) but found it a bit lacking. Part of my map generation needs to include dead-ends (or hiding spots) that will be difficult to discover when traversing distance from one hex to another hex.

A simple “Drunkard’s Walk” is to start at one cell and pick a random neighbor that hasn’t been visited yet. If there are no neighbors that haven’t already been visited, take all remaining visited cells that have unvisited neighbors and pick one at random. This can be repeated until a percentage of cells have been picked and will result in a contiguous area that can be used for a map.

Here is how it looks, taking a random contiguous path for 70% of the cells on the grid:

Note that in the above hex map, every cell has at least 2 entry points. What I would like to change is an increased likelyhood of “hiding spots” or cells with only one entry point so that when traversed, players in these dead-end cells are less likely to be discovered.

Here is the same walk, filling 70% of the cells but with more dead-ends:

This is very similar to the other logic, except with a set probability, if the current cell has 5 neighbors that haven’t been visited, it is added to a list of dead-ends. Then, instead of picking one of those neighbors to visit next, we pick a random hex in the list of visited cells. If there are no cells that meet that criteria, then we start at a random cell in the dead-end list.

As the map density is increased, there are fewer dead-ends as they will be re-purposed to fill the map, resulting in mostly “horseshoe” hexes. Below you can play with the cell density and the probability of marking a dead-end. For my own map, a density of 60% and a dead-end probability of 40% is about right.

If you read this far, I’m hoping to write a few posts on writing a multi-player 2D game and hopefully this is the first post of many (we will see). The game is called Star Dewar which is an anagram for an old BBS game I liked as a kid.