ForWord - Code a game competition - May 4th to June 30th

[TomToad]

@Derron, I'm not using BlitzMax, but rather AGK2 which doesn't allow you to index strings so easily. I have thought of a couple more optimizations though. One would be to load the words into a memblock, that would allow me direct access to the strings.
Also,I have ordered the letters inn each word alphabetically, so once one letter matches the next input needs to start where the last one left off. An idea would be to take advantage of this order by creating another table containing how many letter each word shares with the last, that way, when a word fails to match,I only need to start from the last matching letter that falls within the shared letters, instead of starting the checks from the first letter.

This might hopefully be enough. My other idea had a few problems. One being that the inverted index will take up about 4x as much space as the original index. Second, implementing a function to remove elements from a set would prove to be very difficult. Removing from an array would be slow, probably negating any speed advantages I would gain. Linked lists are non existent in AGK2, and without pointers, implementing my own linked list would be very difficult.

[Qube]

Are you sure that AGK doesn't have the needed commands? https://www.appgamekit.com/documentation/Reference/Core.htm

Scroll down to the Strings section and you'll see it's quite feature complete.

In a nutshell, is what you are trying to achieve with speed :

You have 7 letters and any word that can be made from the word list ( max 7 letters ) is put into a new list.

If that's correct then I'll happily whip up a speedy routine for you. No way should it be 2-3 seconds on a desktop to do that

[Derron]

No way should it be 2-3 seconds on a desktop to do that

This depends on the size of the word list :-)

But I am with you: 2-3 seconds sounds as if something is done _very_ wrong.


Maybe TomToad could describe what he wants - in headwords. Also provide the language file for the 7 words-thing. While not all languages offer the same abilities, the basic logic to tackle something might be translateable into "AGK2" then.


@ not-repeating words
Just cache what you have used for now. Limit that history to X entries (loop: "remove first entry" until history count is below limit).
If you cannot come up with a new word ("empty") you remove an entry from history - even if this means you are repeating a word more often than desired.


bye
Ron

[TomToad]

Fixed the youtube video above.

I do think that using Mid() is causing a huge slowdown.  Plus, I am only doing searches for half a frame, using the other half to update particles, move sprites, render screen, etc...

For those who might be confused, let me try and explain what I'm doing a little better.  The game presents you a ring with 7 letters, You need to find a word, 3 letters or more, that will score the highest with the given board.  Each letter has a point value.  Each position on the board has a multiplier (seen across the top), so you can score higher by having higher point letters later in the word.  The board will also contain random bonuses that will affect the final score.  After the player creates a word, the letters used will be removed from the ring and replaced with new letters, similar to how letters are replaced in Scrabble.  Now the trick comes, I don't want to replace letters with just random ones.  I want to, as much as possible, replace letters so that a 7 letter word is always possible.  This becomes more important on higher levels where you must find longer words.  So I need to check with the list of 7 letter words and pick one randomly that contains all remaining letters.  So if the player has aberstt and plays "star", then I need to find a word that contains bet, such as "tablets".

I might go back to the inverse index idea.  After finding a better algorithm for set intersection, I have greatly decreased the number of worse case checks from about 40,000,000 to about 36,000 (yes, that is about 99.1% drop in checks).  So the number of worse case from 1 letter to 4 letters is 0 to 36,000.  Whereas Worst case for the original method is 135,000 to 136,000.  Best case for old method, 9000-19500, best case for new method is 0-2,500.  As for the problem I had with AGK2 not having linked lists, I found a suitable way around it using arrays. Plus, as I will be comparing indices instead of strings, I can completely get rid of the slow Mid() command.

Right now, I'm expecting a busy weekend, so I might not get back to this until Monday.

[Derron]

Short reminder:
Do not just check if the new letters can build a 7-letter-word. Also make sure you can at least build a 3 or 4 letter word (depending on what minimum the "level" sets). Else you will play a level requiring a 3-letter-word but you only add letters allowing to create a more difficult 7-letter-word.


bye
Ron

[TomToad]

Implementing the inverse index turned out to be no easy task, but I did finally get it done.  Wow! What a difference it makes.  On my PC, the search is practically instantaneous.  On both my androids, there is a very slight pause, maybe 6 or 7 frames at most.

A couple of things I learned about AGK2 while I was writing the code.
1.  Arrays in AGK2 are very efficient when inserting and removing elements.  It makes me think that internally, they behave more like linked lists than just blocks of memory.

2. conditionals are not short circuited. So "If a() = 1 and b() = 1", both a() and b() will be called, even if a() returns false.

3.  You cannot insert into the head of an empty array.  So doing
        Array As Integer[]
        Array.Insert(100,0)
     is not valid.  You have to break it into two parts. 
         If Array.Length <> -1
             Array.Insert(100,0)
         Else
             Array.Insert(100) //inserting at the end of an empty array is ok
         EndIf

[Derron]

2. conditionals are not short circuited. So "If a() = 1 and b() = 1", both a() and b() will be called, even if a() returns false.

Really? That would be a little bummer.


bye
Ron

[Steve Elliott]

These kind of efficiency savings through working the problem, give me goosebumps lol.  The days of massive advances in processor speed have halted.  We now have to go old skool and use our brains to produce greater speed.  Well done Tom!

[TomToad]

haven't been able to work on this for the last few weeks.  Next week looks to be pretty hectic as well.   I might have a few days before the deadline to work on this.  One last push and hopefully get something I can submit.