Behind The Scenes Of Absolute Crossword
I have recently launched Absolute Crossword, which as the name suggests, a crossword puzzle game for Android and iOS available in the respective app stores. In this post I would like to share the architecture and the learnings I have gained during the development process.
The Challenge
The most challenging part of the development was creating the algorithm for populating the official, diagonally symmetrical word grid for the crossword. Meaning that, if a black square appears in the upper left hand corner, there must be one in the bottom right hand corner, and so on throughout the diagram.
The crossword game on the face of it is a very simple word game whereby a grid is presented for the player to fill with words based on the clues provided. The words can go across from left to right or down from top to bottom.
However, crossword puzzle has official grid size and layouts. The layouts is also locale specific that is U.K. grids have slightly different layouts than the U.S. grid. I have decided to proceed with 13x13 U.K. grid as the focus was on the mobile devices and 13x13 grid size looked neat and tidy compared to others.
First Thoughts
My initial approach was to try and solve both the grid generation and the word layout at the same time. That is to start with a random word at a random cell within the 13x13 grid and traverse through the letters of that word and again randomly generate another word based of those letters, simple!
Generating the words was not too bad. However, keeping the grid diagonally symmetrical as per official crossword grid rule was proving to be extremely challenging.
I have decide that the best approach would be to create a 13x13 diagonally symmetrical grid with empty cell and black cell first and then fill in the words in those empty cells as a separate activity. In order to deliver the project quickly I need to focus on the word generation code rather than generating a pretty grid programmatically, so I manually created half of the grid and written the code to generate the remaining diagonally symmetrical grid based of the half grid. I also populated the start cell index of each word. Now my grid layout was complete and repeatable.
Just by looking at the grid, I thought of two dimensional array to hold the letters and words. “Obviously” I hear you say. Well, it didn’t work out so well with the two dimensional array simply because it became very difficult to map the letters in each cell to a word. I am sure it could be done with a two dimensional array but I decided not to do it.
Out Came The Paper
Out came the good old pencil and paper,I started with sketch of a simple 5x5 grid with words , so that I can start implementing the code for populating the grid.
Starting at index cell 0 and ending at cell 3, the first word is 4 character long. I created an regular expression “….” by iterating over the cells between 0 and 3, checking which characters are already in the cell. In this case, the cells were empty so any character could be placed in those cells.
Next step was to hash into the dictionary and pickup all the words the matched the regex. Finally, randomly select a word from the found word list. The first word is done.
Next cell was starting at index 0 again and ending at index 15, this word was going down so the formula for next index was current cell index + size of grid i.e. (0+5) therefore cell 5 would have the second letter. The regex for this word is “D…”, which is a four letter word starting with “D”. As before hash into the dictionary and pickup all the words matched that regex. Randomly select a word from the found word list.
The predefined grid was iterated in a similar style until the regex were applied to all cells that have a starting index. There were occasion where the words with certain regex can not be found, in that case I manually found the words by splitting the grid and replacing the word with two shorter words whilst keeping with the diagonally symmetrical grid rule.
There are usually approximately three or so words remain unresolved and it take about an hour for me create and upload a new grid. I could have worked out the remaining algorithm, however opted to work on delivering a minimum viable product for grid generation and move on to implementing the AWS infrastructure for hosting the grid.
Hosting On AWS
Hosting the levels was extremely simple thanks to the AWS cloud infrastructure. The levels were stored in S3 as json file, with AWS API Gateway supplying the security layer. Since the levels were static json file and I don’t need to query any data directly, S3 was the simplest options.
The mobile game calls the API and retrieves the json levels in a secure, fast enough and resilient infrastructure for an acceptable level of performance.
Thats it.
Feel free to download and enjoy the Absolute Crossword game.
Any comments, suggestion or questions are always welcome.
