A Flash Developer Resource Site

Results 1 to 4 of 4

Thread: [Help] Word game algorithm?

  1. #1
    Junior Member
    Join Date
    Oct 2003
    Posts
    6

    [Help] Word game algorithm?

    Im looking to build a word game similar to boggle. Basically I have random letters appear in a 4x4 grid. I need to know how many words can be spelled using that specific layout of letters. So my question has 2 parts:

    1) Where can I get a dictionary of words to check against for use in a game like this? Ive heard of some people creating their own, but Im not looking to compile a list of a handful of words, Im looking to compare against every word in the english language. Like a scrabble dictionary or something similar.

    2) Once I have the dictionary, how do I go about writing an algorithm that will first create a grid of random letters, and then analyze that grid and scan it for all the possible words that are in the dictionary?

    Hopefully that makes sense. Im just making this game for giggles and if anything it would be good practice and give me a good learning experience. Especially if someone can shed some light on algorithms.

    Any advice would be really appreciated! Thanks!

  2. #2
    Junior Member
    Join Date
    Oct 2003
    Posts
    6
    Anyone at all have any advice or suggestions for how to go about approaching this?

  3. #3
    Pumpkin Carving 2008 ImprisonedPride's Avatar
    Join Date
    Apr 2006
    Location
    Grand Rapids MI
    Posts
    2,379
    1) http://www.mieliestronk.com/wordlist.html <- will get you started, 58000 words. You'll need to convert it to an array or parse the list from a text file yourself.

    2) You're looking at the process backwards. What you should do is denote a difficulty based on a length of a word. From there, sub-categorize the difficulties and select a random yet acceptable word and place it on the board. Next, grab a random letter from that word and decide where in the new word that letter will be placed. Scan the parsed dictionary for words matching both your preferred difficulty and/or space requirement. If it does not, choose a new letter. When no more space remains, fill the remaining empty spaces with random consonants (rather than vowels to avoid unintended words). That should be enough to get you started on a working prototype.
    The 'Boose':
    ASUS Sabertooth P67 TUF
    Intel Core i7-2600K Quad-Core Sandy Bridge 3.4GHz Overclocked to 4.2GHz
    8GB G.Skill Ripjaws 1600 DDR3
    ASUS ENGTX550 TI DC/DI/1GD5 GeForce GTX 550 Ti (Fermi) 1GB 1GDDR5 (Overclocked to 1.1GHz)
    New addition: OCZ Vertex 240GB SATA III SSD
    WEI Score: 7.6

  4. #4
    Junior Senior
    Join Date
    Nov 2000
    Location
    sydney
    Posts
    565
    I did something similar a while ago, forget now where I got my wordlists from, there are many of them, and I think in the end I had to splice a few together to get it just right.

    Your second question is a bit more difficult. For 16 random letters there is an absolutely huge number of permutations to check (20922789888000 combinations just for 16 letter words) so basically... don't do it, it will take minutes or maybe hours to calculate.

    If all you wanted to do however was check a handful of words (eg 10 x 4 letter words going across, down and diagonal) then your best bet as far as speed vs memory goes is to do a binary search. I found I could check several hundred strings per frame without hitching 30fps, it could maybe do more, I didn't need that many checks.

    It takes a long time to compile the wordlist, you might want to keep it in a separate swf. I actually have one of these as a swf which you are welcome to use, shoot me a PM if you want it, it just has a wordlist and the binary search, though it is old and in AS2. From the main program it has only two functions: isWord(string) which returns a boolean and randomWord() which returns any one word from the dictionary.
    Signature

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  




Click Here to Expand Forum to Full Width

HTML5 Development Center