July 27 2017

Hex Game – Procedural Board Generation

Michael Lynch Game Development, Software Development 0

Procedural Board Generation

There are two main changes I made to convert this from a totally random board. First, the procedure decides ahead of time how many bombs and how many dangers are placed on the board. The second improvement is to make sure there are no islands, that is making sure every goal is reachable no matter where you started on the board. To do this, I decided to make sure each game was solvable.

I made one additional change to solve the issue of ‘first click game over’. The solution was to generate a blank board to start, and then on the first click, add bombs and goals, ensuring that the first click was not a bomb. This also led me to make my procedural board generator take into account the first move to solve the issue of unwinnable games. Now every game can be made winnable. I am on the fence about both of these changes, maybe the game is more fun somehow to have a random first move, and to know your first decision matters. Of course, if you are not reading this you may never know that the reality is the game board is always winnable and your first move is never a bomb.

Board Generation – Discovering a method

The first thing I needed to do to generate boards is to discover the rules of each board space type. I found the following:

Empty spaces cost the user points to traverse. So I can label all the empty spaces on the board with the number of points deducted for each move.
Dangers cost the user more points, so any space that I end up labeling a danger, I should update the cost of that space to the cost of the danger.
Goals give the user more points so they should be updated to have a negative value equal to a number of points that they give.

Validating a board

As a thought exercise, I thought about how I might validate a board. I could create a random board, and then find a path that reaches each goal and then total the spots that were exposed during the trip, if that value is positive, then the board is valid, if it is negative then it is not valid. What I learned from this was:

A valid way to check any path is, to sum up, all the hexes that it traverses.
If a valid path to all goals exists, and the total cost of that path is greater than 0, then the board is winnable.

The next step is to think about how I could generate a board that was valid every time.

Board Generation – Description

At the start, I will add all hexes that are adjacent to the first move to an array, called ‘frontier’. There are three scenarios for this, shown in the image below. You can begin with 3, 4 or 6 moves with a round board. Of course, other situations might arise as more board options are added.

Each turn I will select an element from the frontier, and randomly decide what to do with it. The three choices being ‘move to it’, ‘move to it, and place a goal on it’, and ‘place a danger on it’. If I move to a hex (goal, or just a move), then the hexes around that hex will be added to the frontier. If I select to add a bomb to that space, it is simply removed from the frontier.

Every time I make a move or mark a space a bomb it is removed from the frontier. There is a check each time to make sure the frontier never goes below one hex. So if there is only one element in the frontier, that element is expanded and there is no chance of it being a danger.

In addition at each step, whatever is placed (goal/bomb/empty space) the total remaining points will be updated.

Further Improvements

Difficulty Levels

Using some observations that I made while playing the game, I could introduce levels of difficulty while generating the board. Players quickly realize that if a bomb is two spaces away, and a danger is 3 or more, then every space surrounding the space that I am on, is also safe. To increase the difficulty, it makes sense to place bombs next to goals, so that very few spaces would be known to be safe, and in order to determine the safe vs danger spaces, you would have to move at least one additional time. Adding too much of this would make the game frustrating, but it could be used as a lever during board creation. bombs close to goals.

A second mechanism that could be used to make the game more difficult is to space out the goals. Since each movement between goals gets you closer to losing, making the goals farther away from one another means the player will be crossing long deserts to get to the oasis.

Another important discovery was that in order to give the user information, the distance must be greater than 1. A distance of 1 means any touching square. So if it is a bomb, for example, that is at distance one and you want to avoid it, you simply do not have enough information to do so. So to make the game easier, their first move should not have a bomb within 1 hex.

Finally, another idea to ratchet up difficulty would be to simply decrease the number of goals, or increase the number of dangers on the map. As the ratio of danger to goal increases so does the difficulty.