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.

I was planning on making a word based game something like Scramble or Boggle. I searched on the internet and found that one of the best way to store the Word List is by using a trie.

My question: Is there a way I can pre-make and populate a trie data structure and send it to the user rather than sending him the whole word list and then creating the trie data structure at run-time?

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

You could create and serialize the trie offline, then push/pull the resulting string to/from the client for unserialization.

There is probably no need to roll your own code for (un)serialization. I don't have a lot of experience with modern Flash and ActionScript, but this seems to be a way to do it: http://en.wikipedia.org/wiki/Action_Message_Format

share|improve this answer
    
+1 for answer that uses native tools instead of my sucky generic answer! –  knight666 Jun 19 '12 at 9:20
    
hey thanks a lot, "You could create and serialize the trie offline" - any help how i can do this ? noob in programming when networks start to get involved! –  Happybirthday Jun 19 '12 at 10:56
    
This StackOverflow answer has some information how to serialize an object to AMF in Ruby (using something called "Rocket AMF"), and how to retrieve and deserialize it in ActionScript. The Wikipedia page for AMF mentions a lot more AMF implementations for other languages you could alternatively use to do serialization. –  Eric Jun 19 '12 at 11:40
    
For efficiency, you should not do this serialization on demand like in the SO answer. Make the AMF of the data available as a static resource for the ActionScript, and only update it when your word list changes. This is what I meant by offline creation/serialization. –  Eric Jun 19 '12 at 11:42
add comment

The best way to store a dictionary like the one you have in mind is with a red-black tree.

It has an unfortunate downside though, it is incredibly complex to comprehend and implement. Luckily somebody has already done the leg-work for you: link

As to how you want to send this dictionary to the players, well that depends.

  • Does it have to be quick to transfer?
  • Does it have to be secure?
  • Do the users get to make changes?
  • What happens when a word isn't in the dictionary?

My suggestion would be: make a textfile for your dictionary and send it to each player when the game starts. Later on you can make it faster by compressing it to a binary format and more secure by encrypting it with a certificate.

EDIT:

Here's an example of a binary file:

0x54 0x52 0x45 0x45 0x02
0x00 0x48 0x65 0x6C 0x6C 
0x6F 0x00 0x01 0x41 0x70 
0x70 0x6C 0x65 0x00

That looks like garbage, doesn't it? Now, let's look at it in a hex editor:

TREE.
.Hell
o..Ap
ple.

Still doesn't look like much, so let's break it down.

First, we have the header:

TREE - 0x54 0x52 0x45 0x45 0x02

A header is not required, but very much advised! It tells you about what type of file this is, what kind of data is in it and how much data it contains.

The 0x02 at the end there tells us this tree will contain 2 items.

Next, we get an index:

0x00 - index for dictionary item

This tells us item 0 is coming up.

Hello - 0x48 0x65 0x6C 0x6C 0x6F 0x00

This is our first dictionary item: "Hello". The 0x00 at the end tells us we've reached the end of this string.

Now we get another index:

 0x01

Item 1 is coming up!

 Apple - 0x41 0x70 0x70 0x6C 0x00

And now have our second item: "Apple". Now we can build a tree:

 Tree
 [0] = "Hello"
 [1] = "Apple"

Hope that helps!

share|improve this answer
    
thanks a lot :) A noob question : Is it possible to create this Red-Black tree data structure and fill it up with the English words and then convert it into a biinary format so that I can just send this binary file and use it on the client side without re-compiling the whole thing ? –  Happybirthday Jun 19 '12 at 8:47
    
That's not a noob question at all. :) It shows me that you know where you want to go with this. Yes, it's very possible to compress the red-black tree to a binary format and then decompress it in the client, but I can't give you a specific implementation. Basically, your program will have to read the bytes of the file and use those instructions to fill the tree structure. –  knight666 Jun 19 '12 at 8:49
    
umm .. didnt understand .. any kind of link or source code or example you could point me to ... would be very grateful. –  Happybirthday Jun 19 '12 at 8:56
    
I've updated my answer to include an example of a binary file. ;) –  knight666 Jun 19 '12 at 9:08
    
Note that a trie is an equally valid way to store a dictionary. –  Eric Jun 19 '12 at 9:30
add comment

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.