For information and navigation, check out my post that introduces this Unity series here.
TL;DR? Skip to the game.
After the first introductory section of the Udemy Course, Ben Tristem and the GameDev.tv team take us through a basic scripting algorithm. Later on in the course, this script is then reused to show how to add a User Interface (UI). As I have already done a fair bit of coding, and to make sure that I pack all the juicy learning I can into each and every post, I’ve decided to cover both of these sections simultaneously.
Now, it’s time to meet the Number Wizard!
After you pick a number between 1 and 1000, the mighty Number Wizard will attempt to find your number in as few guesses as possible. In fact, the wizard is able to eliminate half the remaining numbers with each guess. This is achieved by using a Binary Search.
But just what is a binary search? Well, I’m glad you asked.
Imagine you are in a library and you really want the latest book by an author called Angela Appleson. You would probably start at AA and work your way along until you get to the book. That might work rather well in this case, but what if the author’s name was Wilson Wheelbarrow (I’m not the best at coming up with names). Now you would have to go through almost the entire library. You could instead start at ZZ and work your way up, but there is a way to ensure you do as little searching as possible, regardless of the author’s name. This is where the binary search comes in.
A binary search begins in the middle, around M perhaps. If the book you are after is before M, then you can immediately eliminate the lower section of the library, if it is after then you do the opposite. You then repeat this process, eliminating half the remaining books each time. By doing this, you could search 1,024 books in a maximum of 11 guesses (see below).
While you might not be able to tell exactly where the middle is, you should be able to make a fairly accurate guess.
I have made a video of a Binary Search using a pack of cards. I also do a bit of my own numerical wizardry at the end. You can see it below.
Hackerrank has also made a video on Binary Searches (not just for this blog post though). It goes into more detail than my video and shows you how to code one in java. It also goes over the Big O notation that I talk about in the next section.
I’m including both videos so you can choose the one you prefer or watch them both. Go nuts!
Let’s get technical!
Finally, as you need to double the number of elements you are searching to add another step in the search, we can say that the complexity of a Binary Search is log(n). Or, O(log n) in Big O Notation. There is a graph below to demonstrate what this looks like.
In the graph, the y-axis represents the maximum number of steps needed to perform the search and the x-axis shows the number of items to be searched.
With most of the games in this series, I will be doing my best to add a little bit of panache. However, the simplicity of this first game didn’t leave much room for that. Still, I did my best and I hope you enjoy it.
You can see the Number Wizard’s awe-inspiring usage of the binary search by clicking here.
Easy: If you’d like to get a better idea of just how efficient a Binary Search is, why not work out the maximum number of steps are required to search each of the following things:
- A pile of 3 books.
- A pile of 4 books.
- A classroom of 16 children.
- A classroom of 15 children.
- A 235-page journal.
Hard: While the Number Wizard works wizardly magic with numbers, I’ve thought of an even more impressive trick! I’ve set up the start of a program (in C#) for searching through a pack of cards. Anyone who would like a challenge can try to finish it off.
If you manage to complete the card search or have any challenges of your own that you would like to suggest, then please let me know either in the comments below or via Twitter @TheLearnJourn.