I'm working on a word puzzle game for a client and I had the challenge to find if a word was created on a game board and had to access 28,000 words (taken from a word list found at http://wordlist.sourceforge.net/ which are used for spell checking, word games, etc)
Originally there were over 80,000 words but I trimmed off the long words which cannot be created on the board.
To overcome the slow speed of flash accessing a huge array, I split up the word list in 26 arrays (one for each letter). This was not enough. You could tell that the CPU was doing something since the animation stop until he checks the board. So I re-split each array into another 26 arrays. Flash doesn't have red-black trees (or is there??) so I had to improvise ;) This was the simplest and now you won't notice it is checking the board for 28,000 words :D.
Subscribe to:
Post Comments (Atom)
4 comments:
You should use a binary search instead, it should be able to search that list in a dozen or so iterations at most, which should be much faster than splitting things into 26*26 arrays..
something along these lines:
public function FindWordIdx(s:String):int
{
var low:int = 0
var high:int = mWordList.length - 1
var mid:int = 0;
while (low <= high)
{
mid = (low + high) / 2
var comp:int = s.localeCompare(mWordList[mid]);
if (comp < 0)
high = mid - 1
else if (comp > 0)
low = mid + 1
else
return mid // found
}
return -1 // not found
}
I've just started work on a word game and a radix tree immensly optimizes my search.
But my problem is the initial loading of the dictionary. It hangs up the game for about 15,20 seconds :S. Any hints to overcome this?
how are you loading the dictionary?
I agree with Jason. A binary search is the best in this situation. I think any kind of tree implementation is overkill. The words from the word list are already presorted. The value of a tree comes when the input is unsorted.
Post a Comment