” Everyone knows what scrabble is!”
Quick Facts
| Type of project: |
| Coursework, Solo |
| Date Produced: |
| Winter 2019 |
| programs used: |
| Visual studio 2019 C++ Github |
Key points
- The program is a game of scrabble following most of the rules of the original game with some leeway.
- Multiple principles were constructed including hashing, sort and searching algorithms and basic OOP management.
the full story
For the first project in year 2 Games Technology BSc, we created a scrabble replica game only using C++. This coursework focused more on the Algorithms that can be created and used to complete the program, such as sorting and searching.
Throughout the development of the game, we needed to make decisions based on appearance, quality of life and time-complexity. “Quality of life” focuses on improvements done for the player rather than for the program. The game took place on a colourful 15×15 board with information displaying what each colour means. Another useful feature is the hash helper. The helper scans the player’s hand of tiles and gives the player a hint on what they can play using a hash: a specific form of storing data using keys. Finally, a shuffle function shuffles the player’s hand back into the deck and receive seven new tiles.
Another improvement done is significantly reducing the time and space needed to find a specific word. There is a term in Computer Science called The big-O notation. This concept approximates how long it would take to complete a procedure with a given amount of input. The Scrabble program has more than 400,000 words to search to find a specific word. If the application used linear search (where it reads each input from beginning to end until it finds the word), then the worst-case scenario is O(n). while this case is ok for the data we have, there is an improvement.
Binary search will split the list every time it searches, discarding inputs that will not contain the word we are looking. This search has the worst-case scenario of O(log(n)). in comparison, this is going from 400,000 searches to just 18! this saves on both time taken and the number of inputs we need to hold during the time. Another step-up to this is giving the search a “first-step advantage”. This function works by detecting when the first letter changes in the list of inputs and comparing to the word we need to find. This procedure will produce a list that is around 15% of the size of the original list.
