At my second meet-up of this week, I ventured north to the east 20s for Building JavaScript Games. Our task was to build a seemingly simple game called Strike 9.

### How the Game is Played

At the beginning of a turn, the “computer” rolls two die. The player has squares numbered 1 through 9 to make the sum of the computer’s roll. The trick is that when the player uses a number it is removed from the board. So for example, if computer rolls a 9, the player can choose to remove any of the following combinations: , [1,8], [2,7], [1,2,6], [2,3,4], etc. If he or she uses, say, the 1 and the 8, on the next roll neither 1 or 8 will be available.

### Huh? / Live Demo

Yeah, it’s kind of hard to explain in words. Here’s a live demo (and my GitHub repo).

### How I Approached the Basic Gameplay

The meat of this project lives in `strike9-board.js`. `onload` we initialize some arrays and variables, then call `resetGame()`, which draws our 9 HTML `canvas`’s and rolls the 2 die for the first time.

From there we wait for the player to click one of the 9 canvases. When a canvas is clicked, we make sure it hasn’t been clicked yet in this game. Then we mark it as clicked in the `board_array` and we remove that number from the `player_moves_remaining` array. We also add the number to `player_total`.

Eventually we have to figure out if the player won, lost, or can keep playing on that turn. Here’s a excerpt of that code:

``````// the player just made a sum...

// check if player has won
if (board_array.indexOf(0) == -1){
resetGame();
} else { //still playing
// re-roll dice.
computer_roll = rollTwoDie();

// with new dice roll, we can already figure out if the game is over
if (isGameOver(computer_roll, player_moves_remaining)){
alert("Computer's next roll is " + computer_roll + "...Game over :(");
resetGame();
} else { // if there exists a way to make the roll's sum...
sendMessage(randPraise() + "<br>New roll is " + computer_roll);
// reset for new roll, same game
possible_combinations = [];
player_total = 0;
}
}
``````

By far the most interesting of these outcomes to check is if the player lost– which we do with the `isGameOver()` function called above. I wanted the game to know if the player lost right away– in other words if the player had 1, 2, and 4 remaining and the computer’s new roll was 5, I wanted the game to tell the player they had lost.

This might sounds simple, but– at least the way I went about it– turned out to be pretty non-trivial.

### Coolest Challenge: When is the Game Over?

Ideally I wanted a function called `isGameOver` that returns `true` if the player can’t make the sum with the remaining numbers (like the case above), and `false` if the player can make the sum.

My approach was to generate an array of all ways to make a sum (in the above hypothetical, all the ways to add numbers to make 5). So given, say, `6`, `getAllPossAddends` should return an array of arrays: `[, [1,5], [2,4], [1,2,3]]`. Note that we don’t want `[3,3]` because there’s only one 3 on the board, and we don’t want `[5,1]` because we already have `[1,5]` and order doesn’t matter here. And `6` itself should be included because, in line with the rules of the game, if the computer rolls a 6 you can just use the 6 square.

Once we get this array of possible combinations to make a given sum, which I call `possible_combinations`, we’ll just need to compare it to what numbers the player has left (`player_moves_remaining`) to see if `isGameOver` should be `true` or `false`. Cool? Sounds easy? OMG took me a whole day.

Let’s do this.

### Part 1: Generating possible_combinations

Note: The section below has been edited and updated to reflect some significant refactoring I’ve performed.

So the first thing I wanted to do was write the function that would take in a `sum`, say `6` and spit back `[[1,5], [2,4], [1,2,3], ]`. I decided to call this function `getAllPossAddends` (“addends”, according to Wikipedia, is the technical term for what you add together to get a sum).

After a few days of tinkering, I wrote a recursive function to accomplish this task.

``````var possible_combinations = []; // I made this global

// if baggage argument is undefined, this is our first run through
// so set baggage = []
// baggage is effectively an optional argument with a default value of [] if undefined in function call
if (typeof baggage == 'undefined'){
baggage = [];
possible_combinations = [];
possible_combinations.push([sum]); // can just play the number itself
}

for (var j=1; j < sum/2; j++){
// if j is not in baggage and sum-j is not in baggage
if (baggage.indexOf(j) == -1 && baggage.indexOf(sum-j) == -1){
// add j and sum-j back to baggage to make our new array we may add as a possible_combination
var new_array = baggage.concat(j, sum-j);

// if new_array is NOT a subArray of possible_combinations yet...
if (!isSubArray(new_array,possible_combinations)){
possible_combinations.push(new_array);
}

var new_baggage = baggage.concat(j);
}
}

return possible_combinations;
}
``````

Let’s walk through it as if we called it with `getAllPossAddends(10)`, so `sum = 10` and `baggage` is `undefined`.

Right off the bat we use an `if` statement to check if `baggage` is undefined. If it is, we know that this is the “first time” we’re running through `getAllPossAddends`, and that we should set `baggage = []` and reset `possible_combinations`. This setting of `baggage` to `[]` will make a little more sense in a minute.

Now to the meat of the function. First we loop from 1 to `sum/2` (5 in our case). We then do some checks against baggage, which we’ll learn about in a minute. Note: this loop doesn’t go up to 5 because we put `i < sum/2` not `i <= sum/2`, which is what we want– remember there aren’t 2 5s so we don’t want `[5,5]` to count as a `possible_combination`.

Eventually we make a new_array and set it equal to `baggage.concat(j, sum-j)`. We don’t have any baggage yet, so for the first run through, `j==1` and `sum-j==9`. And that’s good, because [1,9] is a possible way of making 10.

That’s a start, but what about `[1,4,5]` or (gulp) `[1,2,3,4]`? This is the problem that the recursion handles:

``````// prep new_baggage and send new sum and baggage back to top of the function
var new_baggage = baggage.concat(j);
``````

Basically, we want to take that `9` in `[1,9]` and expand it out to `[[1,9], [1,2,7], [1, 3, 6], [1, 4, 5]]`. We want to break that 9 down while keeping the 1 untouched (Notice how the `1` is the first element of every “sub-array”). I decided to call the `1` `baggage`, because it’s like, just along for the ride. With the baggage taken care of, what we want to do to the 9 is very similar to what we set out to do the 10– namely find all the ways to sum to it. Sounds like a case for recursion!

We’re going to call `getAllPossAddends` again, but first we have to set the `new_baggage`. In our example, right after we add `[1,9]`, 9 is the `sum-j` we want to break down further, and j is `1`, the baggage we want to pass along. We have to use `baggage.concat(j)` in case we got any baggage at the beginning of the run-through of the function, which will be the case every time except the first run-through.

On the second run-through in our example, the getAllPossAddends call is: `getAllPossAddends(9, )`. Now 9 is the new `sum` and `` is the `baggage` (since `baggage` is defined, we do not execute that first `if` statement).

So the array we prepare, `new_array`, WOULD BE [1,1,8], but we have a check against duplicated numbers: `if (baggage.indexOf(j) == -1 && baggage.indexOf(sum-j) == -1)`. `j`, which is equal to `1`, is in fact present in `baggage`, so we’re not going to do anything in this `for` iteration. (Note: This is a bit wasteful, but refactoring further may make this thing a little too confusing.)

So we try again. On the next iteration of the `for` loop, `j` will be equal to 2 and `sum-j` == 7. This time we will make it through the `if` checks. `baggage` is still ``, so when we get to `baggage.concat(2, 7)` it’s going to evaluate to `[1,2,7]`. Then we’ll add it to `possible_combinations`.

We’ll then call the function again which `sum-j` equal to 7 and `baggage` == `[1,2]`. So the call will be `getAllPossAddends(7, [1,2])`, and we’ll go break down that 7. And so on! Crazy, right?

### Part 2: Building My Own Array Tools

You may have noticed my use of a function called `isSubArray`. It checks whether the array we’re trying to add to `possible_combinations` has already been added (again, we don’t want duplicates).

Of course this function is not a standard JavaScript function, but one I wrote myself. I ended up writing 3 of these “array helper” functions in total.

``````// believe it or not, array.sort sorts numbers alphabetically, so we have to define our own sort for numbers
function sortArray(array){
return array.sort(function(a, b){return a-b});
}

// this guy takes an array of arrays and sorts all of its sub-arrays using the above function
function sortAllSubArrays(array){
for(var i = 0; i < array.length; i++){
array[i] = sortArray(array[i]);
}
return array;
}

// the workhorse function in the trio. It sorts both the sub-array and the array of arrays using their respective functions.
// then sees if any of the arrays in `array` match the given `subArray`
function isSubArray (subArray, array) {
subArray = sortArray(subArray); //  need to sort both the subArray...
array = sortAllSubArrays(array); // and the sub-arrays in array in order to compare them more easily

for(var i = 0; i < array.length; i++) {
if(subArray.toString() === array[i].toString()){
return true;
}
}
return false;
}
``````

### Part 3: Putting It All Together

Cool, so now we have an array, `possible_combinations`, that’s full of all the ways our player could make a given sum (a given dice roll in our case). As I mentioned above, we also have an array of numbers that the player has left, called `player_moves_remaining`. Now all we have to do is compare them to figure out if the game is over.

Again, I broke this into 2 functions, but most of the work happens in `playerHasAMove`. `player_moves_left` is `player_moves_remaining` and `passing_moves` is our mega-awesome array of arrays, `possible_combinations`.

``````function playerHasAMove(player_moves_left, passing_moves){
for(var i = 0; i < passing_moves.length; i++) {
var matches = 0;
for(var j = 0; j < passing_moves[i].length; j++) {
if (player_moves_left.indexOf(passing_moves[i][j]) != -1){
// we foudn a match
matches = matches + 1;
}
}
if (matches == passing_moves[i].length){
return true;
}
}
return false;
}

function isGameOver(roll, player_moves_remaining){
if (playerHasAMove(player_moves_remaining, ways_to_fulfill_roll)){
return false; // game is not over
} else {
return true; // game is over
}
}
``````

`playerHasAMove` first loops over the `passing_moves` and yields the sub-arrays like `[1,9]` and `[1,3,6]`. It then loops through these sub-arrays and looks for `matches` in `player_moves_left` using the `indexOf` method. If, for a given sub-array, all of its element are contained in `player_moves_left`, we return true. If we get to the end of `passing_moves` and the player is out of luck, we return false. This easily plugs into `isGameOver`, where we return the final true/false verdict.

Again, here’s where `isGameOver` is called:

``````// player just made a sum

if (board_array.indexOf(0) == -1){  // if board_array has no 0s, i.e. is all 1s
resetGame();
} else { //still playing
// re-roll dice.
computer_roll = rollTwoDie();

// with new dice roll, we can already figure out if the game is over
if (isGameOver(computer_roll, player_moves_remaining)){
alert("Computer's next roll is " + computer_roll + "...Game over :(");
resetGame();
} else { // if there exists a way to make the roll's sum...
sendMessage(randPraise() + "<br>New roll is " + computer_roll);
// reset for new roll, same game
possible_combinations = [];
player_total = 0;
}
}
``````

Side Note: I hope to write more programs that have a `randPraise` function:
``````function randPraise(){