Jump to content
  • Advertisement
Sign in to follow this  
Deemo24

Wordsearch Game: Efficient word insert algorithm

This topic is 4335 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ok heres the background. I have got a wordsearch grid represented as a multi dimensional array in the format Grid[Row][Column]. I have a list of words that i'd like to insert into the grid, in a mixed up fashion (i.e. some horizontal, some vertical and some diagonal). The current method i am using involved the following;(language isn't really important for this)
for each 'word' in 'wordlist' do
{
while(OK)
{
pick a random orientation //(hoz,vert, diagF(\) diagB(/)) pick a starting position for the insert base upon orientation and word lenght
grab whats already in that grid space
compare the two
  if each letter in the
    for each 'letter' in word do
    {
      if (grabbedword.letter != empty space)
      {
        if (grabbedword.letter != word.letter)
        {
	    then OK = false;
        }
      } 
    }
  }
}


If the above code executes ok then the position is logged and the word is entered into the position. The problem is that with some combination of words and random positions the gird will get stuck, because it keeps finding a position that the words won’t fit in. Currently I have implemented a timer which checks to see if it takes to long, if it does then it starts again. Basically there seems to me that there must be a more efficient way of doing this. Because as long as the number of words is not to high you can always fit the words in, even if its just putting them all horizontal or vertical. Any help on this would be good, particularly any math-like way. I hope I’ve made it clear but if not please ask what you don’t understand.

Share this post


Link to post
Share on other sites
Advertisement
The easiest solution would be to try a random orientation first; if that fails, try each possible orientation in order. This will guarantee that, if a word can be fit, it will be. Try this with random positions on the grid for, say, 4 attempts; if 4 random positionings don't get a fit, try to brute-force find a location. In order to prevent "clumping," have your brute-force search start from different corners and run in different directions each time. For instance, the first word you cram in by brute force, start in the top-left corner and move to the right then down. The second time, start in the bottom-right and move up then left. When you cycle back to the top-left corner, switch directions (go down first, then right) - and so on.

There's probably a more sophisticated way you could arrange the words to try and maximize the "interestingness" of the puzzle, but I have a feeling it'd take a bit of genetic training algorithms and some other cruft that I'm far too tired to suss out at the moment [smile]

Share this post


Link to post
Share on other sites
Cheers for the idea, i didn't think of that. Well if u have any ideas once u have got some rest then please let me kno! :D Its kinda annoying because it does seem like there is a bettter way.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!