Webworkers HTML5 for game AI?

Question

So I am designing a game like scrabble in which a user has to make words using the letters on the screen. When the there is no possible combination of word that can be made with the letter the game is automatically supposed to tell the user to shuffle. Which changes the present set of alphabets with a new set (odds are very very very low that the new set cannot form a word either.)

So I now its a simple word game, but I am making this on HTML5 Canvas. It hugely resource consuming. And I need to run this even heavier computation on the client machine of whether a new word is possible from the selection on the screen. Ideally I would run a thread were this an app for the native code, and check after every new word created whether new words are possible with the remaining alphabets. Alas on the web browser I am afraid, it will toast the computer, crash the browser and a lot of other horrible things. So I would like to know is there a way that I could make such a computation feasible with all the other actions I am already running!?

Thanks

Answer 1

You can't rely on web workers for anything practical, they are missing in way too many browsers.

In any case, this is about finding and implementing an efficient algorithm.

Here is how I would do it, presuming the rules that new letters must be connected to existing, and that they may only be placed in a single row or column:

First make an index of words and wordparts. A single JS object containing all words and wordparts as index, and a value to determine if an index is a word or a wordpart. E.g. for the word "old" the object would have to contain {"old":2, "o":1, "l":1, "d":1, "ol":1, "ld":1} where the value 2 denotes a legal word, and 1 denotes a part of a legal word that is not a word on it's own.

For each open space next to at least one letter
  Try placing each letter on the players hand on the space
    If the placed letter connect to other letters both horizontally and vertically
      Check the value of both formed words in your index
      If both values are 2 you have found a legal move and should stop searching
      If one value is 1 and one is 2 you need to try expanding the value 1 word
        For each letter added any word in the other direction must have value 2
        If the word being expanded reach a state not in the index no further 
        expansion will make it legal
        If it reach value 2 you have a legal combination
      Else that letter placement can not be part of a legal combination
    Else
      Check the value of the word formed
      If the value is 2 you have found a legal combination
      If the value is 1 continue like the 1,2 combination

Answer 2

I think you should just first start by implementing this without WebWorkers. Then measure and see how much it slows down the browser. If this is as bad as you think it will be, then go for a Webworker. This shouldn't be a very hard refactoring if you structure your code well.