Gamasutra: The Art & Business of Making Gamesspacer
View All     RSS
July 25, 2014
arrowPress Releases
July 25, 2014
PR Newswire
View All
View All     Submit Event





If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 
Procedural Generation of Word Game Boards
by Rob Targosz on 04/24/14 11:49:00 am   Featured Blogs

The following blog post, unless otherwise noted, was written by a member of Gamasutra’s community.
The thoughts and opinions expressed are those of the writer and not Gamasutra or its parent company.

 

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 5x5 (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.

Word Portal Level 1There are many, many ways to implement a word game. We tried 3 different permutations on the 5x5 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 5x5 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 5x5 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.


Related Jobs

Blizzard Entertainment
Blizzard Entertainment — Irvine, California, United States
[07.25.14]

Test Engineer
Blizzard Entertainment
Blizzard Entertainment — Irvine, California, United States
[07.25.14]

Quality Assurance Analyst
Blizzard Entertainment
Blizzard Entertainment — Irvine, California, United States
[07.25.14]

Test Manager, Quality Assurance
Blizzard Entertainment
Blizzard Entertainment — Irvine, California, United States
[07.25.14]

Software Engineering Manager






Comments


Justin Giles
profile image
Being a word game developer, this has been a good read. I found it very similar to what I went through when building my latest game, Perplexicon. It was similar in that it was based on a grid layout, however it had non-letter elements that come into play. I attempted procedural levels, however, like you said, difficulty was problematic.

In the end I resorted to manually generating levels (about 120) and tacked on a part of the game you could unlock that was an infinite-play randomly generated board (ie: play till you lose).

I think there is a trade off that you have to consider when building these Boggle style games. You can take the procedural route to speed development with the understanding there could be impossible levels and just deal with it. This is best if there is no real progression in the game. Or, build levels manually. This works best in your case where you need high control of the content so that it fits with the rules of the game.

Kudos and thanks for the post! Can't wait to give Word Portal a try!

Rob Targosz
profile image
Thanks Justin. I took a look at Perplexicon today. Very interesting concept and you've done a nice job implementing it. Your game is very approachable even for new players with no barriers to entry.

Your monetization model with various IAP options look to follow some fairly standard models in the market today. I'd be interested in discussing this and other topics with you privately by email if you like (rtargosz at bentvector dot com). I also have other feedback on your game I'd be happy to share - as a fellow developer - if you're interested!

Thanks,
-Rob

Jason Cahill
profile image
Hi Rob,

Nice post. I am the technical director for Wordament (thanks for the mention). I had a couple of thoughts: Are you really generating your boards by hand at this point? Seems slow an tedious. I think you were on the right track with procedural generation. Are you trying to generate these boards locally or ahead of time? I assume it's ahead of time, since you have a level editor. Anyway, if you are doing ahead of time, then just employ more brute force. Your procedural generator will happily make lots of boards while you are sleeping. Just be extremely selective about the ones you choose. You can get rule based and procedural on the selection phase too.

Wordament needs 523 new unique puzzles a day, so human generation is out of the question. We do employ someone that makes our rules, linguistics, themes and puzzle play testing, but even so, we computer generate all of our boards.

The best way to curate boards that you are making procedurally is to make a bunch by hand and ask yourself at each step: what did I just do? Why did I think that choice was better? If you can answer that, then you can program it.

Good luck with your game! I'll definitely give it a whirl when it ships.

Jason -- "Black Snapper"
Technical Director, Microsoft Studios

Rob Targosz
profile image
Hi Jason,

We've played more than a few games of Wordament over the years on a variety of platforms. You guys have a very fun game on your hands! Wordament - and the frustration we have experienced in consistently losing to fast-fingered 12-year-olds - has been a major inspiration for Word Portal.

We've also enjoyed reading your blog at wordament.com and the blog.windows.com article on how the game works (http://blogs.windows.com/windows_phone/b/windowsphone/archive/201
2/03/05/q-amp-a-the-minds-behind-wordament.aspx).

While I agree that hand-generation is slow and tedious, right now our main focus must be on shipping Word Portal - this game has languished too long already! Fortunately, we don't need to create 523 new puzzles every day. Our boards are permanent as are the leaderboards and we "only" need 70 of them to prepare for shipping.

Additional game boards will be made available in the weeks following our launch so we'll focus on procedural generation in that time-frame. Our procedural generator runs offline on local servers. The plan is to provide new boards as DLC being pushed to the cloud after manual validation.

We'll be sure to reply back to this posting once we've (a) shipped Word Portal and (b) updated the procedural generator to address our current problems.

Rob Targosz
Bent Vector Studios


none
 
Comment: