FAQ Search
Memberlist Usergroups
Profile
  Forum Statistics Register
 Log in to check your private messages
Log in to check your private messages
Moonpod Homepage Starscape Information Mr. Robot Information Free Game Downloads Starscape Highscore Table
must... see...screenies!!!
Goto page Previous  1, 2, 3  Next
Post new topic   Reply to topic    Discussion Pod Forum Index -> Independent Game Development View previous topic :: View next topic  
 Author
Message
icarus
Troll
Troll


Joined: 01 Mar 2004

Location: Olympia Washington



PostPosted: Sat Jul 12, 2008 4:04 am    Post subject: Reply with quote

Also. Is making a word game an attempt to appease Konedima?
Back to top
View user's profile Visit poster's website
Konedima
Grammar Police
Grammar Police


Joined: 25 Oct 2003
Posts: 1068
Location: Sydney, Land of Censorship



PostPosted: Sat Jul 12, 2008 5:00 am    Post subject: Reply with quote

icarus wrote:
Also. Is making a word game an attempt to appease Konedima?
I doubt it'll be my sort of word game... pulling random forum posts from the net and earning points for finding errors.

What would also work is playing against someone else, see who can find all the errors first.

Wow, if only I knew how to make games worth playing...
Back to top
View user's profile Visit poster's website
Weeble
Starscape Jedi
Starscape Jedi


Joined: 25 Apr 2003
Posts: 1143
Location: Glasgow, Scotland



PostPosted: Sat Jul 12, 2008 9:20 am    Post subject: Reply with quote

I am intrigued by the word-game idea. I think I would quite enjoy a word-game with depth. (I liked Tommy and the Magical Words, but after a while got a bit bored with the story mode because there wasn't really much to do at the top level - you just completed the levels in order and built up a small stock of utility items as you went.) Is this a hidden words game or a word construction game, or something else? Does it depend on a dictionary? If so, what are you using? Something like a Scrabble dictionary?
Back to top
View user's profile Visit poster's website MSN Messenger
Poo Bear
Pod Team
Pod Team


Joined: 14 Oct 2002
Posts: 4121
Location: Sheffield, UK



PostPosted: Sat Jul 12, 2008 9:33 am    Post subject: Reply with quote

Word construction from the 250k word free scrabble dictionary. Getting that to load and search quickly was quite a fun challenge.

There's a separate index for pirate words, but I had to create than one manually so it isn't very big, need to work on that a bit more.
Back to top
View user's profile Visit poster's website
icarus
Troll
Troll


Joined: 01 Mar 2004

Location: Olympia Washington



PostPosted: Sat Jul 12, 2008 3:51 pm    Post subject: Reply with quote

Poo Bear wrote:
Word construction from the 250k word free scrabble dictionary. Getting that to load and search quickly was quite a fun challenge.

There's a separate index for pirate words, but I had to create than one manually so it isn't very big, need to work on that a bit more.


Include an option to add your own dictionaries.
Back to top
View user's profile Visit poster's website
Slyh



Joined: 25 Nov 2004
Posts: 480
Location: Karlsruhe, Germany



PostPosted: Sat Jul 12, 2008 8:01 pm    Post subject: Reply with quote

Poo Bear wrote:
Getting that to load and search quickly was quite a fun challenge.

Loading approx. 3MB does not sound too hard. Smile
But how/when/why do you have to search the list?

Poo Bear wrote:
There's a separate index for pirate words, but I had to create than one manually so it isn't very big, need to work on that a bit more.

Sweet. Please include pirate names from Monkey Island. Thanks. Smile
Is a German version planned? Twisted Evil
Back to top
View user's profile
Weeble
Starscape Jedi
Starscape Jedi


Joined: 25 Apr 2003
Posts: 1143
Location: Glasgow, Scotland



PostPosted: Sat Jul 12, 2008 9:56 pm    Post subject: Reply with quote

Poo Bear wrote:
Word construction from the 250k word free scrabble dictionary. Getting that to load and search quickly was quite a fun challenge.

Tries?
Back to top
View user's profile Visit poster's website MSN Messenger
SethP



Joined: 24 Apr 2006
Posts: 302
Location: Connecticut, USA



PostPosted: Sun Jul 13, 2008 6:21 pm    Post subject: Reply with quote

Weeble wrote:
Poo Bear wrote:
Word construction from the 250k word free scrabble dictionary. Getting that to load and search quickly was quite a fun challenge.

Tries?


Wow, that is a pretty neat little data structure. Man, now I'm itchin' to write a word game myself, just so I can use a trie Razz
Back to top
View user's profile MSN Messenger
Poo Bear
Pod Team
Pod Team


Joined: 14 Oct 2002
Posts: 4121
Location: Sheffield, UK



PostPosted: Sun Jul 13, 2008 7:47 pm    Post subject: Reply with quote

Never heard of Tries, they sound cool.

Loading
The problem I had was loading the data, parsing it, storing it in an appropriate format - that all took too long. Doing anything non-trivial 250k times puts too big a dent in your loading bar. So it was a case of writing a utility to pre-load the raw text, convert it into a searchable format and then save it out as a binary file. When the game runs it just loads that data straight into memory, it doesn't do anything to it, just dumps it all into ram and leaves it naturally in the proper structure for searching.

The dictionary used to take 15secs to load, now it takes 3 and there is only one big memory allocation.

Searching
When you enter a word the game searches the dictionary to check it's spelt correctly. When the AI takes a turn he has between 9 and 17 random letters and needs to search the dictionary to create an ordered list of valid words. Then he picks one proportional to how dumb he is meant to be and you see him key it in.

Searching couldn't be allowed to take more than 15mSecs. Any more than that and there was a noticeable glitch. I didn't want to search in another thread as that would introduce too many bugs, multi threading is tricky. Instead I packaged the search process and all related data into an object. The AI has one, the player has one. They each put in requests to look up words and then the search object gets a 10mSec window each frame to go about its business. Within 250mS to 500mS the answer is waiting, depending on cpu power. It feels instant to the player and there is no chance of any slow down even on a rubbish computer.


As for foreign language support, that would depend on how popular the game is and the availability of an appropriate large word list.
Back to top
View user's profile Visit poster's website
Johnh



Joined: 06 Sep 2003
Posts: 160



PostPosted: Mon Jul 14, 2008 4:13 am    Post subject: Reply with quote

Poo Bear wrote:
Never heard of Tries, they sound cool.

Loading
The problem I had was loading the data, parsing it, storing it in an appropriate format - that all took too long. Doing anything non-trivial 250k times puts too big a dent in your loading bar. So it was a case of writing a utility to pre-load the raw text, convert it into a searchable format and then save it out as a binary file. When the game runs it just loads that data straight into memory, it doesn't do anything to it, just dumps it all into ram and leaves it naturally in the proper structure for searching.

The dictionary used to take 15secs to load, now it takes 3 and there is only one big memory allocation.

Searching
When you enter a word the game searches the dictionary to check it's spelt correctly. When the AI takes a turn he has between 9 and 17 random letters and needs to search the dictionary to create an ordered list of valid words. Then he picks one proportional to how dumb he is meant to be and you see him key it in.

Searching couldn't be allowed to take more than 15mSecs. Any more than that and there was a noticeable glitch. I didn't want to search in another thread as that would introduce too many bugs, multi threading is tricky. Instead I packaged the search process and all related data into an object. The AI has one, the player has one. They each put in requests to look up words and then the search object gets a 10mSec window each frame to go about its business. Within 250mS to 500mS the answer is waiting, depending on cpu power. It feels instant to the player and there is no chance of any slow down even on a rubbish computer.


As for foreign language support, that would depend on how popular the game is and the availability of an appropriate large word list.


This is why I love you guys. Getting a peek into the code is always intriguing to me.
Back to top
View user's profile
Slyh



Joined: 25 Nov 2004
Posts: 480
Location: Karlsruhe, Germany



PostPosted: Mon Jul 14, 2008 6:24 pm    Post subject: Reply with quote

Poo Bear wrote:

Loading
[...]
The dictionary used to take 15secs to load, now it takes 3 and there is only one big memory allocation.

Searching
When you enter a word the game searches the dictionary to check it's spelt correctly. When the AI takes a turn he has between 9 and 17 random letters and needs to search the dictionary to create an ordered list of valid words. [..]

Searching couldn't be allowed to take more than 15mSecs.


I know I might sound like a smart *** here... but I just tried to solve this problem in Java:
It takes about 290 ms to read the scrabble dictionary (267751 words) from a plain, newline-separated text file and about 65 ms to find all words with a certain set of letters -- in the worst case. I'm running on an Ahtlon64 5200+, which is probably quite high-end. But keep in mind that the code most likely is completely "interpreted" and not compiled to native code in this short period of runtime.

Maybe there is some bug in my code which makes it run that fast. But debugging did not show anything noticeable.

I'll post the code in another message, in case someone wants to take a look at it.

Poo Bear wrote:
As for foreign language support, that would depend on how popular the game is and the availability of an appropriate large word list.

I knew you'd say that. ;-)
I'm quite impressed by this Scrabble dictionary. (I didn't even know there was something like the National Scrabble Association.) There is probably a list of (all?) words available for other languages. But I doubt that they are cleaned from dirty words. And doing this probably would take a looot of time...
Back to top
View user's profile
Slyh



Joined: 25 Nov 2004
Posts: 480
Location: Karlsruhe, Germany



PostPosted: Mon Jul 14, 2008 6:26 pm    Post subject: Reply with quote

Code of ScrabbleWordListSearcher as mentioned in the previous post:
(Edit: Fixed a bug. Embarassed)
(Edit2: Fixed another one. D'Oh!)

Code:
package de.slyh.spielprojekt;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public class ScrabbleWordListSearcher
{
   private static List<String> wordList = new ArrayList<String>(270000);

   public static void main(String[] args) throws IOException
   {
      long lastTime = System.nanoTime();
      load();
      System.out.println("Time to load: " + ((System.nanoTime() - lastTime) / 1000 / 1000) + "ms");

      lastTime = System.nanoTime();
      int wordsFound = find("aaabbbcccdddeeefffggghhhiiijjjkkklllmmmnnnooopppqqqrrrssstttuuuvvvwwwxxxyyyzzz");
      System.out.println("Number of words found: " + wordsFound);
      System.out.println("Time to find: " + ((System.nanoTime() - lastTime) / 1000 / 1000) + "ms");
   }

   private static int find(String validLettersAsString)
   {
      validLettersAsString = validLettersAsString.toUpperCase();

      int[] validLettersOriginal = new int[26];

      for (int i = 0; i < validLettersOriginal.length; i++) {
         validLettersOriginal[i] = 0;
      }

      for (int i = 0; i < validLettersAsString.length(); i++) {
         char validLetter = validLettersAsString.charAt(i);
         validLettersOriginal[validLetter - 'A']++;
      }

      List<String> result = new ArrayList<String>(270000);

      int[] validLettersWorking = new int[26];
      for (String word : wordList) {
         System.arraycopy(validLettersOriginal, 0, validLettersWorking, 0, 26);

         boolean valid = true;
         for (int i = 0; i < word.length(); i++) {
            int wordLetterPos = word.charAt(i) - 'A';
            if (validLettersWorking[wordLetterPos] == 0)
            {
               valid = false;
               break;
            }
            validLettersWorking[wordLetterPos]--;
         }

         if (valid) {
            result.add(word);
         }
      }

      return result.size();
   }

   private static void load() throws FileNotFoundException, IOException
   {
      File scrabbleWordList = new File("sowpods.txt");

      BufferedReader in = new BufferedReader(new FileReader(scrabbleWordList));

      String line;
      while ((line = in.readLine()) != null)
      {
         wordList.add(line);
      }
   }
}


Last edited by Slyh on Tue Jul 15, 2008 6:26 pm; edited 2 times in total
Back to top
View user's profile
Slyh



Joined: 25 Nov 2004
Posts: 480
Location: Karlsruhe, Germany



PostPosted: Mon Jul 14, 2008 6:27 pm    Post subject: Reply with quote

Johnh wrote:
This is why I love you guys. Getting a peek into the code is always intriguing to me.

I second this!!
Back to top
View user's profile
colinvella



Joined: 15 Sep 2006
Posts: 82



PostPosted: Mon Jul 14, 2008 8:35 pm    Post subject: Reply with quote

That nested loop seems a little on the heavy side, computation wise. You might try something as follows (pseudo code), based on Trie maps:

Code:

Initialise:
    Build trie map of words.


Find(set_of_letters):
    for (word_length = 2 to max_difficulty)
    {
         for each 'world_length' permutation from set_of_letters
        {
             search combination in Trie map
        }
    }


In the above I'm assuming that difficulty level 5 corresponds to the AI being able to find words of up to 5 letters long. The word searches should be relatively fast ('word_length' iterations per search) but the combos may increase substantially.

P.S. There's a hidden agenda behind my willingness to help.. I want you to get this over with and develop an honest-to-goodness hardcore game like mama used to bake Smile
Back to top
View user's profile
Slyh



Joined: 25 Nov 2004
Posts: 480
Location: Karlsruhe, Germany



PostPosted: Mon Jul 14, 2008 9:10 pm    Post subject: Reply with quote

colinvella wrote:
That nested loop seems a little on the heavy side, computation wise.

This depends... :)

colinvella wrote:
In the above I'm assuming that difficulty level 5 corresponds to the AI being able to find words of up to 5 letters long. The word searches should be relatively fast ('word_length' iterations per search) but the combos may increase substantially.

Yes. This algorithm is fine for relatively short words. For 8 letter words you'd already have to create 46,232 permutations, for 10 letters 4,037,912. I doubt that this would be fast enough, even when a Trie is used.
For short words/bad AI your algorithm is definitely faster. Using a Hash Map to store all valid words would probably be faster than using a Trie, though. Tries are more useful to save memory than for performance reasons. (At least if you have a complete word and want to find the exact word in a huge set of words.)
Back to top
View user's profile
Display posts from previous:   
Post new topic   Reply to topic    Discussion Pod Forum Index -> Independent Game Development All times are GMT
Goto page Previous  1, 2, 3  Next
Page 2 of 3

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group