|
How to write a word game/Dungeon Scroll Post-mortem
by Seth A. Robinson
What's the attraction with word games?
Like chess, word games tax the brain in a special way. Being able to find and compose words from jumbled letters is an acquired skill that can be improved. It's neat that after getting good at one of them, the pattern recognition and vocabulary prowess carries over to pretty much any other word game.
And best of all, they are just really fun to play. I've put many hours into Scrabble, Bookworm and TextTwist.
From a developer's point of view there are a few additional perks:
- Low content requirements
- Quick development turn around
- Deep gameplay is possible without much work
In this article I'll talk about some problems and solutions to word games and give you some handy class based source for dealing with word lists, finding anagrams using a combinatorial function, and doing fast "is this a valid word" checks. (C++ for the windows platform, tested with MSVC++6)
The Development Of Dungeon Scroll
I have been wanting to do my own word game for a while, just for fun.
Originally I was going to do one for a Ludum Dare 48 hour contest, but the themes didn't really work out. (the theme you have to follow is decided right before the contest starts)
My idea was take the basic idea of creating words with a limited set of letters but making it original by crossing it with an RPG theme that gave the gameplay a much more intense experience.
I didn't have a good 2D engine. I've been working a lot on my 3D engine, but my design didn't call for any effects I would need 3D hardware for, so might as well use DirectDraw7 and have it run on weak computers too.
Enter the excellent DirectX wrapper CDX. I'd looked at Allegro and SDL but I liked its OO layout; seemed a better fit for me. I used it while making Bathroom Teacher for a 48 hour contest so I knew it would do the job ok. (July 2006 Note: I've sinced switched to Clanlib, it's a neat OO multiplatform game library)
Good stuff about CDX
- Adds some stuff missing from DDraw such as alpha blitting, rotation, bitmapped font support and animation classes
- Comes with a lot of examples, easily understandable thanks to the OO design
- Can be used as a .DLL or statically compiled lib
- Open source under the GNU artistic license
Bad stuff about CDX
- A bit bulky, may have a lot of stuff you don't need (sprite class, scrolling background classes, sound, input, midi)
- I found a few bugs. I fixed an alpha blit problem in 16 bit, fixed classes to be smart enough to avoid memory leaks if ->LoadImage is called twice, that kind of thing. I sent some fixes and additions the library maintainer, Bil Simser. If anyone else wants them let me know. (4-23-2005 update, the changes I made can be downloaded here)
- Hasn't been updated in a while
Random tip: I used the great free util Bitmap Font Builder to make the fonts for Dungeon Scroll. I then imported them into Photoshop and snazzied them up using layer styles. I added some code to CDX to analyze the font at loadtime and do variable width spacing, everything worked great.
Mechanics First
I created a basic no-frills playable version of the game in a couple of days. I used Photoshop and stolen art from the web to create a temporary GUI. It's important not to fall in love with anything at this stage so it will be easier for you to replace something. Don't do the final artwork 'till the end if possible. (With larger games this isn't really as applicable..)
At the end of the project Akiko re-did the interface graphics in a couple of days. Screenshots: With temp art, with final art.
The only unknown about this project was how to deal with the words. I needed to make an easy to use class; I named it CWordList.
My requirements for CWordList were:
- Super quick "is this word in the list" lookup
- Load and save word lists, regular text and also a presorted special format (for speed)
- Must be able to get a list of words (without duplicates) that can be created with an arbitrary group of letters
First, I looked around and unsuccessfully tried to find some source I could stea, er use. I did find a few places talking about techniques and where to find word lists though.
Word lists - Learn about lists of words you can use and what licenses they are under.
Storing and loading the words in CWordList
You can use this class without knowing a thing about it, but, if you're interested in adding things or writing your own this info may be useful.
The class stores all the words as a vector of strings. I make use of the STL - it saves a lot of time.
Each item in the vector stores the word itself, "cat", and also a version of the word with the letters sorted alphabetically. "act". (so, dad becomes add, saucy becomes acsuy)
The vectors themselves are sorted by the second word. (Sorted by act, not cat)
Why go through all this hassle? It's so our "generate anagrams" function will be quicker. (The"Oracle tile" in dungeon scroll causes the best possible word to magically form, it does it with this function)
It lets us take a combinatorial approach rather than straight permutations. A 6 letter word has 6! (6 factorial) permutations, or 720 ways of rearranging the letters. Do you really want to wait around while you check each one to see if it's a valid word?
Probably not. With our alphabetically sorting of each letter we can get the same information WITHOUT needing to check every possible ORDER of the same letters. Guess how many combinations (unordered sets) of 6 letter words you can make with 6 letters? Exactly 1.
1 instead of 720 checks sounds a lot better, eh? But hold on, we also want to know how many 5 letter words we can make with those 6 letters. There are six possible sets to check in that case. How many 3 letter sets can we make with those 6? 20. Still not bad, and much better than doing all permutations for each one.
The resulting combination will actually be sorted alphabetically just before comparing them to our word list, if there are any matches, those words can be made with the set.
It does start to get hairy when the amount of letters get higher, especially if you call the function with a large 'ignore these words' list. This page let's you experiment to see how many combinations there are. Enter 15 and 3, and you'll see how many (order unimportant) combinations of three letters you can make with 15 letters. (455)
A good link to more info on this...
To check if a word exists in the dictionary, we basically do the same thing. Convert it to our "search format" (cat becomes act) and then check it against the dict. It would be too slow to scan it against every word, so to speed it up I use a technique where I check the center of the dictionary (total words/2) it, and use a "high or lower" approach to find the correct place in the dictionary to check. (Kind of like those "guess what number I'm thinking of" games) The max checks it takes in my game dungeon scroll for any given word is 15 or so.
The source code to the CWordList class with an example project can be found at the end of this article.
Choosing starting letters intelligently
To fill up a game board or give your players starting tiles you're going to have to choose some letters. What if he gets all Z's? What if he gets a combination that is bad for making words?
One solution is to use a weighted random that let's you dynamically change the weight as you go. This is really simple to do and useful in a lot of situations where you need to get a random number.
Have you ever done this kind of slop:
int i = random(10);
if (i <= 4)
{
//40% chance of firing, awesome!
EnemyFires();
} else if (i <= 8)
{
EnemyRuns();
} else
{
//very rarely, enemy will do this
EnemyForgivesYouAndMakesUp();
}
and everything worked great; the enemy did the first two actions 80% of the time (40% each) and the last one only 20%. And then you decided to add a new option that happens as much as EnemyRuns and EnemyFires and keep the same ratio. It's a fricken' pain! You have to change everything to re-balance it, and since you're in a hurry you won't pay much attention or test it and in an ever so subtle way your game has changed forever.
You can avoid this problem by using CWeightRand class, (or write your own) it's very simple, here is how we would replace the above with it.
CWeightRand rand; rand.AddChoice(0, 4); //the second number is the 'weighting' It's compared to the other choices' weights. //If you had only two choices, and they were weighted 1 and 10, the 10 one would // get chosen 90% of the time. rand.AddChoice(1, 4); rand.AddChoice(2, 2); int i_choice = rand.GetRandom();
If you add another choice, like this:
rand.AddChoice(3, 4);
All choices will automatically be scaled so choices with 4 weighting are chosen an equal amount of the time, and the 2 is still chosen 1/2 as many times as any of the 4's. You could also use 2's and 1's and instead of 4's and 2's, as it's just the ratio that's important.
To get random letters in the same frequency as they occur in everyday english we can do this:
CWeightRand rand; rand.AddChoice(0, 85108); //A rand.AddChoice(1, 20506); //B rand.AddChoice(2, 45641); //C rand.AddChoice(3, 42668); //D rand.AddChoice(4, 135371); //E rand.AddChoice(5, 24558); //F rand.AddChoice(6, 19928); //G rand.AddChoice(7, 39717); //H rand.AddChoice(8, 85248); //I rand.AddChoice(9, 1695); //J rand.AddChoice(10, 7349); //K rand.AddChoice(11, 46744); //L rand.AddChoice(12, 35381); //M rand.AddChoice(13, 82427); //N rand.AddChoice(14, 89790); //O rand.AddChoice(15, 26481); //P rand.AddChoice(16, 2746); //Q rand.AddChoice(17, 77557); //R rand.AddChoice(18, 86114); //S rand.AddChoice(19, 104724); //T rand.AddChoice(20, 39670); //U rand.AddChoice(21, 13939); //V rand.AddChoice(22, 15028); //W rand.AddChoice(23, 3971); //X rand.AddChoice(24, 20622); //Y rand.AddChoice(25, 1039); //Z //we've properly weighted the letters. Z will occur the least, E the most and so on. //now we'll do this for each letter we need: int i_choice = rand.GetRandom(); rand.AddChoice(i_choice, rand.GetOdds(i_choice)/3); char c_chosen_letter = 65+i_choice; //add the offset, so it's the correct //letter on the ascii table
And there you have it, you are now very likely to get a nice letter set.
Take a look at "rand.AddChoice(i_choice, rand.GetOdds(i_choice)/3);"
This line is actually overwriting the odds of the choice that was chosen with new odds.
When this happens CWeightRand will recompute the ratios between all choices the next time.GetRandom is called. This is the dynamically changing part mentioned early. It let's us reduce or increase the chances of getting a certain letter.
In addition to this, in Dungeon Scroll I forced the vowel count per tileset to be within a certain range to insure good word making opportunities.
In Summary
Dungeon Scroll was a really fun game to work on and I think a fun game to play. Originally it was going to be freeware, but in the end I decided it was good enough to charge for and added some extras.
The game was completed and being sold online in about a month, working at a very leisurely pace.
Trivia: The Dungeon Scroll bonus screensaver registered users get was made in a couple hours. The hardest part was getting the Wise install system to install/uninstall the screensaver correctly.
If you have any questions, comments or fix bugs in my source please send them to me.
-Seth
Supporting files:
CWordListWithExample.zip - the CWordList class with a super simple console based example showing how to use it to check a word and then generate all possible words. Includes a meg sized disctionary which is why the zip is big.
CWeightRand.zip - A tiny class that let's you easily setup weighted random choices that can be dynamically altered on the fly.
WordPrep.zip - A little utility I created for Dungeon Scroll to sort word lists and create optimized versions. (uses CWordList for all the real work)
Dungeon Scroll - the shareware game I created using these classes.