Originally published in the TGC Newsletter March 2014
There are many grid-based word games on the market at present, with other popular titles such as Words With Friends,Word Feud, Wordz Up and many more. Sean Mann of Napland Games gives us an insight on the makings of such an application.
Word lists
All word games need a qualified word list. There are many free lists out there and the best public domain list is ENABLE (Enhanced North American Benchmark LExicon) available from the Google Project site.This list contains some 170,000 words and is widely accepted as one of the best. It did need some minor modifications to be ready for use in a game. For example, we removed all single letter words since you have to play at least 2 letters and we removed all words longer than 15 letters since the board is 15×15 tiles. We also removed any words which have a purely vulgar meaning as we felt that they were inappropriate for a game designed for all ages. We also added all of the commonly accepted 2-letter words from other games.
The list also had to go through some modification so that it could be accessed in an optimal way. A word list of 170,000 words can be a bit cumbersome to search. If the list was stored on the device it would be very slow. We stored the list in our MySQL database on our server which is very fast for searches, but still the list was split into multiple small tables so that search time would never take long (indeed it takes 0.0019 seconds to search our largest list). The way we split up the lists is straight-forward. There is a list for every letter and word length combination (i.e. all words beginning with A and 2 letters long, A and 3 letters, A and 4 letters, etc.). To accomplish this I created a simple program that parsed the big word list and simply saved it into smaller text files. It created quite a few text files (about 26 * 14) but they were easy to mass import to a MySQL database.
Protecting the data One thing to look out for when importing is that text files have characters for new lines and these can get stored in your database, which potentially can cause searching issues. Another major advantage of having the list stored on a server is we can add and remove words on demand. We’ve already had a number of users request additional words and have added some of them to our dictionary immediately. Leveraging an online database to control elements in your game is very useful. We can also send out news messages to our players from our online database and lock out obsolete versions of the game if we ever need to.
Since our word lists are stored in our protected database online, we didn’t have to worry about users potentially modifying the files. If you plan to store your files within the app you should consider your own method of encryption and validation to ensure that users haven’t modified the files. One of my favorite methods is simply storing a key in an array for your program and using that key along with XOR to encrypt/decrypt the bytes in a data file.
This method made the basics of verifying a word to our dictionary very quick and simple. The more difficult part was verifying the words on the board since you have to take into consideration the various possible crosswords. The idea behind the algorithm for doing this is quite simple, but implementation was a bit tricky. Simply determine the upper-most, left-most letter that has been placed on the board and look left, right, up, and down for other unplayed letters or played letters.
I hope this gives a brief insight into Word Games and inspires you to think about making your own in the near future.
