In case you haven't already, please check out the first part of this series: Part 1
So, where were we...
We had just finished setting up the grid for our game, which serves as the foundation for the word search. The grid acts as the backdrop for the letters that players will choose from to form a sequence.
Now we can focus on replacing all these 0's with letters.
For this we are going to need an algorithm that does the following:
- arranges all of the provided words on a grid of the same size in random order
- fills all remaining cells with random letters
Lets tackle this problem
We know the words can only be placed either horizontally, vertically, diagonally up, or diagonally down. (refer to part 1, if you are lost),
So we need a grid and we need to place a list of words on that grid in one of 4 possible orientations.
To begin, we can define a function that accepts the size of the grid and a list of words as input. We can use the size to create a 2D matrix, and then iterate over the list of words using a loop
Inside the loop, we need to randomly select a direction for the current word. To do this, we can create an array containing the four possible orientations: horizontal, vertical, diagonally up, diagonally down.
Hold on just a second
I just thought of a problem that we would likely face while solving this.
If we randomly place a word on the grid and select an orientation for it, there is a possibility that the word will be positioned outside the boundaries of the grid.
For example, if I select the word "javascript" and give it a horizontal orientation, and then try to place it starting at the rightmost edge of the matrix, there will likely be an error because we will be attempting to place a letter outside the boundaries of the matrix.
To prevent this issue, we can add a do-while loop inside our for loop. This loop will continue running until the word is placed within the boundaries of the matrix. To keep track of this, we can initialize a variable "placed" that is set to False and will be set to True if the word is successfully placed. This will allow us to break out of the loop when the word has been properly positioned.
Now, as we go through the process of placing the word, if we encounter a location that is outside the boundaries of the matrix, we can use the continue keyword to restart the while loop and select a new orientation and position for that word.
Okay, back to the algorithm
So first let’s assign a random starting position for the word with the following:
Next, we can select a random orientation from our array of orientations. We will also initialize our rise and run variables, which we will use in various operations later on.
Now we just need to determine the slope (rise and run) based on the random orientation that we got.
We can use a switch case statement and assign the appropriate rise and run values. (Notice how these values can be derived from our slope validation function in part 1).
Now we need to determine if the end of our word will be placed outside the grid. To do this, we can calculate the position of the last letter in the word. We can do this by adding the row to the product of the length of the word and the run, and doing the same with the column and rise variables.
After this calculation, we will have the row and column values for the last letter of the word. If either of these numbers is larger than the length of the matrix or less than 0, we need to try a different orientation (restart the while loop) to make sure that the word fits within the grid.
If we pass this check, it means that the beginning and end of the word are both within the boundaries of the matrix.
Now, we need to check if there are any other words in the way. We can't overlap words unless they share one letter.
We need to set up a loop to iterate over each letter of the current word to check if the current position is already taken. We will also initialize a variable called failed outside the loop. This variable will be used later in the while loop.
For each letter in the word, we can calculate the position on the matrix where this letter would be placed. We can do this by multiplying the index of the letter by the run or rise and adding it to the initial row or column, respectively.
Here's how it works: on the first iteration, the index is 0, so after multiplying it to the run or rise we end up with 0 which we add to the row and column values, which means we check the starting position.
On the next iteration, the index is 1. This time we are multiplying the run and rise by 1 which means this time we will be adding the run and rise values tot he row and column values respectively. By doing these calculations we will be checking where the current letter of the word would be placed based on the orientation we selected at the beginning of the while loop.
After that, we can check if the position in the matrix is empty or if it is occupied by the same letter as the current letter of the word.
If at any point we find that this condition is false we break out of the loop as set failed to true. So that we can restart the whole loop based on this condition:
Now, if our word passes all the previous checks we know two things that are crucial before attempting to place the word on the matrix.
- the word is within the matrix
- we can place the word without overriding a previous word
So we can finally place the word!!
We have already done half of this in our last check so it is simple from here. We just calculate the new row and column using a similar calculation and then we place the current letter at that position on the matrix. Once we have finished this we can finally set placed to True and break out of the loop!!
We have finally finished the hard part
Now all that we have left to do is replace all of the empty spaces with a random word. This very simple we just iterate over the matrix with a nested for loop and if the current index is empty. We assign it a random letter.
We have a puzzle that is now ready to be solved all we have to do now is check if the player is picking the right word.
Top comments (0)