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
Word game experiments
Post new topic   Reply to topic    Discussion Pod Forum Index -> Independent Game Development View previous topic :: View next topic  
 Author
Message
Weeble
Starscape Jedi
Starscape Jedi


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



PostPosted: Sat Jan 30, 2010 3:31 am    Post subject: Word game experiments Reply with quote

Pirate Princess got me thinking about word-games, and I thought I'd hack up a quick prototype to experiment with some ideas. I figured someone here might be interested in this, so I'll post my code:

http://sites.google.com/site/clockworksaint/wordgame

Requirements: Python 2.6, Pygame, "sowpods.txt" (A Scrabble dictionary. You should put this in the same directory as the .py files.)

EDIT - I think you need Pygame 1.9: I tried it on Pygame 1.8 and it seems some of the API is slightly different.

To start it, open a command-prompt in the same directory and type "python textdrop.py". I've been developing on Linux, but it should work on Windows too. It takes a good few seconds to start up and process the dictionary into a trie data-structure.

So far it's really not a game, so I'd only download it if you're interested in the code or in the discussing the ideas - it's not going to be much fun at the moment. It draws a grid of letters on the screen, and you have to look for words in a manner similar to Boggle - letters must be adjacent (orthogonally or diagonally) but need not be in a straight line. You cannot use a letter more than once in a word. Control is by the keyboard - once you've spotted a word, type it in and it will be highlighted. (If there's more than one way to make the same word, I'm afraid you're stuck with what it picks. I've got an idea to let you tab through the choices, but I've not done it yet.) If the word is in the dictionary, it will appear blue, if not, red. Hit enter to remove those letters. (It doesn't actually stop you from using words that are not in the dictionary.) Letters fall in from the top. (There's no animation, though.) Press space and it will print to the console a list of all the words that it can currently make, which I think will be useful for implementing an AI. (Caveat: in practice, this is fast. In theory, I think it could take a very long time if there are a particularly pathological set of letters on the board.) I am wondering if this could work in a Puzzle Quest style - the player and the computer take turns working on the same board, and making good moves will damage your opponent.

The word search operates by a depth-first search of all possible paths through the grid, pruned heavily by the dictionary trie. I am thinking about adding wildcard tiles, but I'm a bit worried this will cause a massive explosion in the number of words that can be made, and may make it impractical to enumerate *all* of them.

I'm wondering how to stop the (hypothetical) AI from playing all the weird words that nobody has ever heard of. I wonder if I could take a bunch of public domain books and build up a list of words that appear in them, then discard all the words (like proper nouns) that are not in the Scrabble dictionary. That might make for a fairer dictionary for the computer to pick moves from.


Last edited by Weeble on Wed Feb 03, 2010 1:16 pm; edited 1 time in total
Back to top
View user's profile Visit poster's website MSN Messenger
Weeble
Starscape Jedi
Starscape Jedi


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



PostPosted: Tue Feb 02, 2010 2:39 am    Post subject: Reply with quote

I sank far too much time trying to improve the dictionary loading time - ~10s on my laptop was beginning to annoy me. So I profiled it, focused on improving the bits that seemed to be the bottlenecks, got a 33% speed-up under the profiler... only to discover that the performance outside of the profiler had hardly budged. All profilers incur some performance penalty, and in this case the code initially took 30s under the profiler. Tweaks to the code reduced this to 20s, but outside of the profiler the code was still taking just short of 10s. I even tried out Pyrex, which lets you write Python-like code that it translates into C, and was surprisingly easy to use. The great thing about Pyrex is not avoiding having to write C, but avoiding having to use the Python C API - it can seamlessly convert between Python types and native types for you. But that was a bit of a quagmire, because to get big speed-ups requires eliminating all the Python objects from the inner loops, and that was looking to be an awful lot of work for unsure gains. Then I tried something I should have tried right at the start - I turned off Python's garbage collector while building the trie. Bam, 65% faster. It looks like while I was building a huge data structure (and creating no garbage) the garbage collector was spending a lot of time scanning over the whole thing multiple times. *sigh* Well, after all that time wasted, I can live with a 3.5s loading time.

Now, maybe I should get back to writing some features. I think I'll try to get the AI going so that at least it plays like a game.

Some other ideas I'd like to experiment with:
  • Wildcard ("blank") tiles that can be any letter. In order to alleviate the problems this might cause for the AI, I think I'd limit there to only being one or two on the board at once.
  • Allies/equipment/Pokemon-style creatures with "favourite words". A bit like "pirate words", each ally would have a set of themed words, and making any one of them will activate their special ability. My main fear here is that I think it could be very hard ever to make a word on one of these lists, but maybe a wildcard or two would make this easier.
  • Combat mechanics. In my current build, the player and the computer just accumulate points. I'd like to give each a health meter and have different letters do different amounts of damage.
  • Some way to disrupt the board if it's getting exhausted and all the vowels have clumped up in one corner. In Pirate Princess, the player can always just shuffle if they get absolutely stuck, but because the player and computer are sharing a board here I don't really want it to be too easy to just wipe everything away whenever either player feels like it.
  • Do something to keep the player playing. I find that when I play at the moment I tend to spend a very long time looking for longer words. I definitely don't want to put a time limit on moves or punish the player for being slow, but at the same time I don't want players to feel they need to spend ages poring over every move, because that could easily get boring. I think that having the option of spending a turn using an ability instead of spelling a word might balance this out a bit, so long as the abilities themselves aren't too mentally taxing.
  • I like the idea of a keyboard-controlled game (and not just a keyboard pretending to be a joypad), which seems to be a bit of an oddity these days. I wonder if there are fun ways to extend that to the rest of the interface. (Also guaranteeing that my game will never appear on the iPhone/iPad. Oops.)


Anyone else got any good ideas? I fear that it's a bit lacking in innovation now that I've gotten this far, but I still quite like the core elements, and I think there's good scope for interesting abilities when player and computer have to work in the same board.
Back to top
View user's profile Visit poster's website MSN Messenger
Blizgerg



Joined: 09 Jan 2005
Posts: 155
Location: The Planet Stinky Socks



PostPosted: Tue Feb 02, 2010 2:47 pm    Post subject: Reply with quote

That is pretty interesting.

I want to comment about keyboard control. Keep in mind that with all the standard windows controls you can do everything you can do with the mouse with the keyboard. This was intentional and it bugs me when I cannot navigate an application entirely with the keyboard. I have a hard time figuring out why so many peopled don't seem to know this. OFC, I'm one to talk as many of the games I play don't use a mouse or joypad/stick at all and only the keyboard. I also think anyone who expects to use a computer a lot should force themselves to learn to touch type...

Ok, I'll stop babbling now. I think I'm heading off topic. Very Happy
Back to top
View user's profile
Weeble
Starscape Jedi
Starscape Jedi


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



PostPosted: Tue Feb 02, 2010 6:53 pm    Post subject: Reply with quote

I think many apps aren't fully navigable with the keyboard simply because so few people use the keyboard for navigation. Unless it's a feature that the developers use themselves all the time or that enough users use enough to complain loudly when it breaks, it will end up either forgotten or just pushed down the priority list for the million other features clamouring to get in.

I think my favourite Windows keyboard control is "Alt+Space, Move", largely for its ability to recover windows that have somehow strayed off the screen.

Coming back to the game, I quite like being able to type in "ING" to quickly find out if those letters appear together somewhere in the grid. It feels like the computer is acting as a helpful tool without actually playing the game for me.

What I was getting at with keyboard navigation was that if the main game focuses around seeing letters and typing them in, I wonder if that "theme" can be incorporated into other parts like the overworld map. Maybe town names would appear and you could type them in to go there. Would that be fun or just annoying? Maybe it could be a little bit like The Typing of the Dead.
Back to top
View user's profile Visit poster's website MSN Messenger
Weeble
Starscape Jedi
Starscape Jedi


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



PostPosted: Wed Feb 03, 2010 12:23 am    Post subject: Reply with quote

I've uploaded a newer version of the code. You now take turns, though you play as both players. You get an extra turn for making a word of five or more characters, but every consecutive extra turn increases the number of letters you need to keep getting extra turns. There's a very rudimentary "EXTRA TURN" sign when you get an extra turn. It logs a bunch of stuff including what words you made. There are scores for each player, but I plan to replace those with health or something similar.
Back to top
View user's profile Visit poster's website MSN Messenger
Weeble
Starscape Jedi
Starscape Jedi


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



PostPosted: Wed Feb 03, 2010 12:44 am    Post subject: Reply with quote

Poo Bear wrote:
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.

I just found this quote in the Must... see... screenies!!! thread. I found it funny that I hit exactly the same problem and yet completely forgot about this. I almost went with that solution when looking at the Pyrex stuff, but it's a bit non-trivial in Python to read or mmap in a binary file and then treat it as a data structure. (Unless, of course, you're happy to work with it as an array of bytes.) I may do that in the future to try to get the loading time down further.
Back to top
View user's profile Visit poster's website MSN Messenger
Slyh



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



PostPosted: Thu Feb 04, 2010 10:34 pm    Post subject: Reply with quote

But remember that you'll make yourself platform-dependent AND compiler-dependent if you read a (say) struct in and just dump it into memory (and vice versa).
Only in native languages, though, of course. :)
Back to top
View user's profile
Weeble
Starscape Jedi
Starscape Jedi


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



PostPosted: Thu Feb 04, 2010 10:57 pm    Post subject: Reply with quote

Yeah, worth bearing in mind. However you could simply generate and dump the data-structure on install or first run, and I think that would be portable to most platforms.

I haven't uploaded a new version, but I tried out having an extremely naive AI that looks at all the possible words and picks one at random. It definitely needs work. The vast majority of the words it finds to play I've never heard of, like "ich" and "hinau". I think I'll try building up a reduced dictionary of words that people actually use and see if I can make it play a little more like a human.
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 Feb 13, 2010 7:03 pm    Post subject: Reply with quote

Good stuff.

What if there is a little side on view battle field above the word grid. Word score equals number of letters plus rarity of letters like PP. As you submit words you generate "energy", which can be used to build a unit. Weak units are cheap, powerful ones expensive. You can launch a unit by pressing F1->F12. The unit appears above the grid and moves towards the opponent. If it gets all the way to the other side then then the game is over. Exception - airborne units fly out to the opponent and then fly back before disappearing, you can't win with it. If it gets in weapons range of an enemy unit then it stops and starts firing. Exception - jets and bombers don't stop.

c=cost, m=move rate

Soldier - 1c, 1m, weak against most, damages soldiers, trucks
RPG Soldier - 2c, 1m, weak but can do minor damage to armour
Jeep - 3c, 3m, kills soldiers, fairly weak
AA Jeep - 3c, 3m, kills soldiers and airborne
Tank - 4c, 2m, kills soldiers and trucks
Heavy Tank - 5c, 2m, kills soldiers, trucks and tanks
Artillery Truck - 5c, 2m, kills at a medium distance so they can't fire back
Rocket Truck - 6c, 2m, kills at a long distance
Missile Truck - 6c, 2m, kills airborne
Helicopter - 5c, 4m, kills soldiers, trucks and jeeps
Bomber - 7c, 2m, drops a line of bombs killing multiple units
Jet - 6c, 5m, kills anything, but just one

Strategy - deploy a slow moving missile truck and a soldier to keep the opponent busy, have a helicopter ready in case of airborne visitors. Bank up resources as fast as you can, tank rush the opponent. Try and hold back cash for a jet and back up the tanks with a missile launcher.

Strategy - bank up some cash and then when the time is right just send out soldiers until you are out of cash. Unless the opponent can afford a bomber you'll probably overwhelm him.

Strategy - send out one soldier. Time it just right and periodically send out bombers so their flight paths overlap just right to keep cover the soldier and annihilating whatever is just in front of him.

If balanced right you should get a nice tug-of-war going.

Need AI to stop units overlapping each other too much.

Help with unit costs, show each possible unit down the left of the screen and show how many of each one you can currently afford.
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: Sun Feb 14, 2010 1:31 am    Post subject: Reply with quote

Ooh, it's like Battlescape with words. Bogglescape!

I have been really busy this week, so I haven't done much, but I did upload a version where the computer makes words. In order to stop it from playing so many weird words it uses a different dictionary from the player. To make the dictionary I took a few out of copyright books from Project Gutenberg, extracted all the lower-case words with no punctuation and filtered them against the SOWPODS word list in case of misspellings or made-up words. (As an aside, is the SOWPODS word list copyrighted? Can it be? And if I scanned a copyrighted text to make my word-list, would that be infringing?)

If you're giving it a go, be aware that there's no animation for when the computer makes a move, so it's not obvious what it did. At the moment I'm working around this by having it log everything to the console. Same place as before: http://sites.google.com/site/clockworksaint/wordgame
Back to top
View user's profile Visit poster's website MSN Messenger
Display posts from previous:   
Post new topic   Reply to topic    Discussion Pod Forum Index -> Independent Game Development All times are GMT
Page 1 of 1

 
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