Word game dictionary

13 posts

Flag Post

C# etc. programmer just starting out with AS3.

Need advice on best practice for dealing with dictionary/word list in a word game.

  • does Kongregate have a recommended dictionary?
  • what’s the most efficient way of checking words to see if they’re in a word list?
 
Flag Post
what’s the most efficient way of checking words to see if they’re in a word list?

trace(dictionary["word"]);

 
Flag Post

I guess I mean including the word list in the game at all. Are people really downloading an entire dictionary file?

 
Flag Post

I guess so.

 
Flag Post

Some dictionaries have APIs. Of course, you have to pay if you use them in a commercial application.

 
Flag Post

Check this out

 
Flag Post

I had earlier worked on a word game. The game had 5 minigames and all of them required dictionary/word-list.
What I did was to first make an array of the whole word list. I had to make a program which can read from a text file and create an array for me outputting it in trace. Next I omitted words which were 15 letters or more (based on your game requirement you can delete more words by removing words with lesser number of letters). The original word-list occupied 801 KB (over 70k words). After removing words with more than 15 letters and letters ending in ‘s’ (this was hell of a task, I made a program which will search for words which were similar to one before it with an additional ‘s’ in the end and remove those) the size reduced to 502 KB (a little over 50k words). To make the search faster I stored the positions of starting two letters for example ‘aa’ starts from 0th position and ‘ab’ starts from 112 position and ‘ac’ starts from 187 and so on till zz, so if you encounter a word say ‘abbot’ you have to check against array position 112 to 186. I also compared two strings in different way (I dont recall what I implemented at that time), I guess you can search online for it. The outcome was very good and searching/comparing was instant.

 
Flag Post

Going off of what simplegoogly said:

Instead of searching through all the words of a certain 2 letter combo, you can use this function to drastically reduce the amount of array scanning:

function checkWord(array:Vector.<String>, value:String, left:int, right:int):int {
    if(left > right) return -1;
    var middle:int = (left + right) / 2;
    if(array[middle] == value) return middle;
    else if(array[middle] > value) return checkWord(array, value, left, middle - 1);
    else return checkWord(array, value, middle + 1, right);
}

Use it like so:


if(checkWord(wordDictionary, “word you want to check”, 0, wordDictionary.length)) {
// is a word
} else {
// is not a word
}

Basically it checks if the word is between two arbitrary positions in your dictionary array, if so, it cuts it in half and continues checking in this manner until 1 word is left. If that 1 word is the same as “the word you want to check” then it is in fact a word.

With a standard word list, the function loops around 15-20 times. It would be about 2-3 times faster if you employed simplygoogly’s strategy of benchmarking the locations of each second letter (aa, ab, ac, etc). Meaning you could check if any combination of letters makes up a word at 7-8 loops max.

 
Flag Post

And it would be hundreds (if not thousands) of times faster if you simply did if(dictionary["word"]), as I’ve already suggested.

 
Flag Post

Arrgh, am confused.

I am loading the dictionary file with a URLLoader. On complete, it calls a function which uses words = event.target.data.split(“\r\n”);

words is an array; after the split it has the correct number of items.
If I use a for loop to scan through, it finds the word I am looking for. If I do words[word], it comes back as undefined. Any ideas, Senekis?

 
Flag Post

Array#split maps the split string to numerical indices of an Array. Senekis’ idea is to map the boolean value true to every word that exists and then they can simply be accessed through the syntax he showed. This data structure is called an associative array and, in my opinion, would be better suited for this situation. I don’t know how your external data is formatted so I can’t tell you the best way to put it in an associative array.

If you want to stick with Array, you can use the indexOf method but I’m not sure how well it will scale when used with a very large Array. It will certainly be slower than an associative array access.

 
Flag Post

Thanks, that’ll sort me out, I think!

 
Flag Post

Yep, all good. Thanks for the clue of “associative array”.