Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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
share|improve this answer
    
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.