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
Post new topic   Reply to topic    Discussion Pod Forum Index -> Independent Game Development View previous topic :: View next topic  
 Author
Message
Poo Bear
Pod Team
Pod Team


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



PostPosted: Mon Jul 14, 2008 11:09 pm    Post subject: Reply with quote

Yes, that's very fast, nice one. I'm doing a whole mess of other gubbins to do with ranking words, unicode, special case phrases like 'qu' in english - but allegedly there are others in other languages so it handles it generically, pirate words, etc. So I got it going fast enough and then moved on, but this shows what can be done.
Back to top
View user's profile Visit poster's website
colinvella



Joined: 15 Sep 2006
Posts: 82



PostPosted: Tue Jul 15, 2008 12:17 pm    Post subject: Reply with quote

[quote="Slyh"]
colinvella wrote:

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.)


There might be a way of pruning out the combos by doing the trie searches simultaneously with the combo construction.

For example:
---
You choose a first letter and check if the trie map root has a child node for that letter (trivially true for the 1st letter as you can find words starting with all the letters in the alphabet, given a comprehensive dictionary)

Repeat the process by selecting the next letter from the remaining valid letters and check if the trie tree can be navigated with the current combo. If not, stop working with this combo and start with a new one.
---

I would agree with you on the performance of hash maps, were it not for the fact that the hashing function for the strings is itself typically of Order(N). So even assuming no bin conflicts (usually not an issue since good hash map implementations grow automatically to counter this), a trie map should more or less perform better. Bear also in mind that some trie implementations actually collapse degenerate sections of their branches so that given a word of M letters, you don't necessarily have to traverse M nodes. Also, you can exit early from the search as soon as it is clear that the word is not in the dictionary given the current initial sub-string. For example, with a word like "xzfoopy", the search algo will terminate as soon as it tests the letter "z" because there are no valid words starting with "xz" (again my assumption!)
Back to top
View user's profile
rincebrain



Joined: 17 May 2007
Posts: 12



PostPosted: Mon Sep 21, 2009 12:23 pm    Post subject: Reply with quote

Poo Bear wrote:
That kind of thing, but a bit different. We've got another story by our friend Enzo (who did the one in MrRobot) and a ship to upgrade (not a space ship though Smile ) and a map and missions and special powers and stats and different enemies to fight and ...

Anyway, you'll see soon.


"Soon", eh?
Back to top
View user's profile
Poo Bear
Pod Team
Pod Team


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



PostPosted: Mon Sep 21, 2009 1:16 pm    Post subject: Reply with quote

Haha - yes, we end up doing contract work on boring "normal" type projects which drags us away from this stuff. Still, I'm working on it right now as a matter of fact <gasp>.

So it should be ready soon Wink
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: Mon Sep 21, 2009 11:16 pm    Post subject: Reply with quote

Is this Blizzard's definition of soon or actual soon?
Back to top
View user's profile Visit poster's website
Poo Bear
Pod Team
Pod Team


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



PostPosted: Tue Sep 22, 2009 8:09 am    Post subject: Reply with quote

Probably Blizzard's definition Wink

I was working fulltime on boring web based gaming stuff (gambling) for another company and not getting much time to do anything. There is a big recession in the UK though currently and it's turned into more of a part time contract now so I've got some free time. Not sure how long that will last though.
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: Tue Sep 22, 2009 8:30 am    Post subject: Reply with quote

Relax, you're not the only ones who operate on Valve Time.
Back to top
View user's profile Visit poster's website
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
Page 3 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