Procedural Generation of Word Game Boards feature

Bent Vector Studios has been working on a new word game, Word Portal for about 10 months now. This is our first project using the Unity engine, so unsurprisingly there was a learning curve and we’ve had a lot of re-work as a result. We’re now approaching the final stages of development and expect to ship the game very (very!) soon.

Part of this finalization process has been play-testing with a broader base of players. One of the biggest things that almost immediately jumped out of this new testing was that some levels of the game are not balanced with respect to their assigned level of difficulty. Players had a really hard time with some of the early levels and weren’t able to advance as quickly as we had expected.

Word Portal is a simple word game wherein players are given a 5×5 (25) board of letters from which they must create words. The rules for creating words are simple:

1. Must be 3-12 letters long.

2. Must use the middle letter last.

3. Once you’ve used a letter from the “inner” ring, you cannot use letters from the “outer” ring (i.e.: the progression goes from outer->inner->middle).

4. Letters do not need to be touching (unlike, for example, Wordament)

5. No proper nouns or “curse” words.

Players get more points for creating long words and for using letters like Q, X and Z in words. No time limits are set on each round (no rewards for faster play). Every player gets the same set of letters for each round and are ranked on a per-round “ladder” online. Rounds can be replayed to improve player scores.

There are many, many ways to implement a word game. We tried 3 different permutations on the 5×5 board theme:

1. The letters you use to create a word are replaced, but not the unused letters. The “stream” of letters was generated using a procedural generator. This was our original design. We eventually had to eliminate this mode because it resulted in difficult or unplayable boards even with lots of rules governing which letters would be added on refresh.
2. The entire 5×5 grid is updated after each word. This was very disruptive to the players. It takes between 30-90 seconds for the average player to analyze the available letters and start building backwards from the center letter.
3. The 5×5 board is static for the entire round and players have to keep finding different words with the same letters. This is the current method in use for Word Portal. This is less distracting for the player, avoids the pitfalls of bringing new letters in like option 1 and allows for special/custom boards.

Option 1 was in place since the beginning days of Word Portal. This option “felt” right to the designer. To accommodate this, a procedural board generator was developed. For each round, players are allowed to create between 5 and 15 words of between 3 and 12 letters. That means that at most 15*12 letters would ever be used in a round. However, since letters can be discarded by the game engine for various rules (e.g.: words cannot end in Q or J) we generated 300 letters for each round using the following process:

1. Generate a random double value between 0 and 100.
2. Use English word letter frequency percentages to pick the letter that mapped to this value.
3. Don’t let more than 3/5 letters in a row be the same. Random is never really random; you can flip a coin 5 times and get 4 heads in a row. In the same way, it is possible to get 4 letter E’s in a row.
4. Don’t allow more than 4/25 letters be the same. Levels with more than 4 duplicates are (a) hard to play and (b) look badly designed.

Some of these same rules were applied during gameplay as letters used to create words were replaced:

1. Middle letter can never be Q, J, I, U, V. On lower levels, B, X and A are also avoided since these are harder to use.
2. Q can only appear in the “outer” ring and then only if there’s a U on the board already.
3. Avoid allowing more than 4/25 letters be the same.

In addition, the procedural generation tool was coded to validate the letter boards it generated. We used a list of the most common 5000 English words and counted how many 4, 5 and 6-letter words could be generated from each board. The algorithms took into account the board structure and the required use of inner, outer and middle letters on the board. Any boards that had less than 200 words in them were rejected – not sure where 200 came from, it just seemed like a reasonable cut-off.

Despite all of this work, as I mentioned above, play-testing was problematic. Some boards played easily at the start and became too hard after 3-4 words were played. Other boards started too hard and stayed that way.

Our first attempt was to create a new algorithm for option 1. Instead of using random letters, we tried building the board from random, common words:

1. Randomly pick a word from a dictionary of 2500 common words 5-8 letter long.
2. Place that word on the board with the last letter in the middle spot and randomly up to 1/2 of the remaining letters in both the inner and outer rings.
3. Find another word ending with the same letter as the first and repeat until only 1-4 letters are left on the board.
4. Fill the remaining 1-4 spots using randome letters like the old algorithm.

This implementation guarantees that there will be at least a few “common” words on each board but didn’t provide a better experience for play-testers. Players rarely found the first word added to the board (we kept track of them!) and often failed to complete rounds. The boards were still too difficult.

At this point, we started looking at building boards by hand. This meant that we could no longer use option 1 but needed to use either option 2 or option 3. Option 2 requires approximately 10 times as many boards as option 3 but we evaluated both. Players preferred option 3 because they were able to find more words in a shorter time. Completely refreshing the board after each word (option 2) resets the player’s ability to find new words by an average of 1 minute. This is because the middle letter must be used to end each word, so players need to think of new words in reverse – or at least find common word endings (-ed, -ing, -ine, -ent, etc.) and try to build on those.

Moving to the manual board design and option 3 had several major benefits:

1. Boards can be fine-tuned for difficulty so they fit better into the flow of the game.
2. Custom/special boards can be built with themes, hidden words, etc.
3. Procedurally testing boards is much easier since none of the letters change. We can now know exactly how many and WHICH words are in each level.
4. We can add a custom level builder to the game for players to use!

The custom level builder is probably the most exciting benefit (though special boards is also pretty cool)! We decided to make the level builder available in a future release of Word Portal. Players will be able to design boards to share online with their friends or the entire Word Portal community. It will be very interesting to see how this gets used and how many great and challenging levels players can come up with.

In the end, we were able to get procedural level generation working for Word Portal by taking some advice from Jason Cahill of the Wordament team: look at what you do to manually create your best boards and reproduce that with computer code. This was much easier said than done, but going back to the drawing board, we came up with a set of rules:
1. Create a list of common word endings (ing, ed, est, ene, ese, etc.).
2. Pseudo-randomly pick one (we actually duplicate the most popular ones to weight them heavier)
3. Put the last letter of this in the center and the remaining letter(s) in random positions in the inner ring.
4. Find words in the "common" dictionary (a dictionary of the most frequently-used English words - we picked 5000 of them with 3-12 letters) and add them to the board as follows:
a. Test the word to (a) ensure it wasn't already used and (b) doesn't end up putting too many repeated letters on the board (e.g.: more than 4 letter "E")
b. Truncate to remove the suffix already on the board
c. Put roughly 1/3 of the letters in the inner ring and the remaining letters in the outer ring.
5. Repeat until 3 or less letter spots remain.
6. Fill the remaining spots with letters not in use or least frequent (1x usually).
7. If a Q is being added to the board, it MUST go in the outer ring and a U is added at the same time.
8. Rare letters like Q, X, Z, J, etc. can only appear once in the board.

There are a few other rules, but that the gist of it. In order to validate our letter boards, we test each one on completion using code that knows nothing about the words in the board that was just created. This takes significantly longer than the board creation process due to the way words are constructed in Word Portal. However, we are able to hand-pick the best boards from this procedural generation process to ensure that they have at least 200 words 3-12 letters in length, at least one word 9-12 letters long and more than ten 100+ point words.