Every game programmer needs a basic set of tools to use in building his/her games. In this series we will cover everything from basic computer science algorithms and simple design patterns to more complex artificial intelligence implementations. If it can be used some how, some way in game development, then it is ripe for discussion and implementation in this series.
A Binary Search In AS3
With a binary search we can find an element in a sorted array faster (conceivably) than looping through the array comparing the value we are looking for with the value of each element in the array. I say conceivably because there are certain circumstances where the loop can be faster. Those cases would be when the value you are search for happens to be near the beginning of your search.
The version we are going to look at is a classic “needle in the haystack” style problem. We are going to create and array called the “hayStack“. It will contain a sorted list of numbers from the smallest to the largest. We will create a second integer variable called the “needle“. The needle will be a value that exists in the array. We will use a classic example of recursion to search the “hayStack” for the needle value.
The recursive function, called “arraySearch()” will accept in four parameters:
1. The needle value
2. The hayStack array
3. The first element to use in the search. In our example we will search the entire array, so this value is 0, but it can be any value as long as it is not greater than the last parameter in the search.
4. The last element to use in the search. In our example this will be the hayStack.length-1, but it can be any value as long as it is greater than the first parameter.
The arraySearch() function will first find the middle of the array and then check to make sure that the last value is greater than the first value passed in.
If the value in the hayStack at the middle index is greater than the needle value then the arraySearch() function will recursively call itself but pass in middle-1 as the new last value.
If the value in the hayStack at the middle index is less than the needle value then the arraySearch() function will recursively call itself, but pass the middle+1 as the new first value.
Finally the middle value will be passed back as the correct index of the needle value.
[cc lang=”javascript” width=”550″]
package
{
import flash.display.Sprite;
/**
* …
* @author Jeff Fulton
*/
public class BinarySearch extends Sprite
{
public function BinarySearch()
{
var needle:int = 55;
var hayStack:Array = [1, 2, 3, 4, 5, 6, 10, 21, 32, 33, 34, 41, 47, 51, 52, 53, 54, 55, 66, 69, 71, 73, 76, 90];
var location:int = arraySearch(needle, hayStack, 0, hayStack.length – 1);
trace(location);
}
private function arraySearch(needle:int, hayStack:Array, first:int, last:int):int {
var middle:int = Math.floor((last + first)/2);
if (first > last) {
trace(“first > last”);
// check for error in data passed in
return -1;
} else if (hayStack[middle] > needle) {
return arraySearch(needle, hayStack, first, middle-1);
} else if (hayStack[middle] < needle) {
return arraySearch(needle, hayStack, middle+1, last);
} else {
return middle;
}
}
}
}
[/cc]
Executing this code will result in the value "17” being traced out as 55 is the 17th (0-relative) element in the hayStack array.
Now, try to set the first value to 10 and the last value to 9.
[cc lang=”javascript” width=”550″]
var location:int = arraySearch(needle, hayStack, 10, 9);
[/cc]
The result will be a “-1” returned because the first value is greater than the last value.
Next, change the needle to the value “0” (or any other value that is not in the hayStack() array. Change the arraySearch() call back to it original format:
[cc lang=”javascript” width=”550″]
var needle:int = 0;
var hayStack:Array = [1, 2, 3, 4, 5, 6, 10, 21, 32, 33, 34, 41, 47,51, 52, 53, 54, 55, 66, 69, 71, 73, 76, 90];
var location:int = arraySearch(needle, hayStack, 0, hayStack.length – 1);
[/cc]
If the value is not found, eventually the recursion will result in first > last and a -1 will result.
The recursive function can be replaced with an iterative version:
[cc lang=”javascript” width=”550″]
private function arraySearchIteration(needle:int, hayStack:Array, first:int, last:int):int {
var middleFound:Boolean = false;
var middle:int;
while (!middleFound) {
middle = Math.floor((last + first) / 2);
if (needle == hayStack[middle] || first > last) {
middleFound = true;
}else if (needle > hayStack[middle]) {
first++;
}else {
last = middle-1;
}
}
return(middle);
}
[/cc]
That’s it for a simple binary search. This is relatively simple, yet powerful technique that can be applied to solve any number of game related problems from looking for the correct MovieClip to remove from the game screen to looking up words in a word list. One problem with this technique though is that it requires a sorted list. In the future we will examine using a hash table to solve this problem. While using a hash table is a much faster (in some cases) than a binary search, it is much more complex than the simple recursion/iteration that we have constructed here.