# Webworkers HTML5 for game AI?

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

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

• I really like your proposal and would like to give it a go. but when I say HTML5, I think it makes it quite reasonable to assume that I am not looking to support all browsers... Its just an experiment to build something unique and useful from all the new tech... :) But you are right in saying its about the efficient algorithm... I concur...! :) – Shouvik Nov 22 '10 at 5:19

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.

• Its pretty bad.. But with webworkers, I get SO errors... – Shouvik Nov 19 '10 at 12:56
• If you get stack overflows then just switch from your recursive solution to an iterative based one. – Ivo Wetzel Nov 19 '10 at 14:37
• @Ivo In that case the search becomes to long! I have the most optimized way to search for the validity possible with that function! – Shouvik Nov 21 '10 at 12:26