Let me introduce you to Timber, a word finding game I wrote in my days off. I mainly wrote this project because I wanted to do a coding challenge utilizing the DSA I’m currently studying.
AttentionThis post is not a tutorial. This post illustrates which DSA hide behind this game, in order to give you the means to build your own. With your rules, twists, tricks.... and of course learn in the process.
Click on the image to go to the game. (Source Code)
Timber is a word finding game
As simple as that.
The rules of this game are pretty simple:
Click the letters to compose a word to submit.
Once you’ve submitted a word, Timber will delete all the letters selected.
The length of each word that is successfully found in the dictionary will be added to the score
(On easy mode the score is decreased if the word is not found).
Score at least the points requested by the game difficulty (top-left corner)
…those are the rules.
To spice things up, Timber adds a layer of difficulty.
Timber allows the clicked letters to not necessarily be adjacent to each other. In that case, it will calculate a path to connect the letters.
Once submitted, though, not only it will remove the clicked letters, but also every letter that belongs to the path.
Under the hood
Alright, those were the rules. Here’s how they’re implemented.
- On load, Timber, with the help of Fakerjs, generates ~1 million random words.
Faker is a popular library used to generate massive amounts of fake (but realistic) data for testing and development.
- To fasten the word lookup on submit, Timber creates a Trie data structure and inserts each word in the trie.
A trie is a tree data structure used for locating specific keys from within a set.
- Timber calculates the shortest path by implementing the A* a pathfinding algorithm.
A* aims to find a path to the given goal node having the smallest cost
- Timber detects one cell islands. (if the grid does not contains anymore islands of size bigger than one, the game ends). A good ole Depth First Search implementation…
Depth First Search starts at the root node and explores as far as possible along each branch before backtracking. - geeksforgeeks.org
💡 - if the letters of an island cannot form at least one word contained in the dictionary, remove the island.
ConclusionAs you can see it is not as simple as it may look visually, there's some work going on under the hood.
I will continue to develop this project as I will get new ideas, learn new algorithms and new data structures.
The source code of Timber can be found here. I hope I have sparked your curiosity a bit. If you want to contribute or give some feedback, you’re always welcomed… Otherwise, have fun and keep on learning!
Contribute to Timber