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: [9], [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){
alert("Oh hey, You won!");
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: `[[6], [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], [6]]`

. 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
function getAllPossAddends(sum, baggage){
// 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);
}
// prep new_baggage and send new sum and baggage back to top of the function
var new_baggage = baggage.concat(j);
getAllPossAddends(sum-j, new_baggage);
}
}
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);
getAllPossAddends(sum-j, new_baggage);
```

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, [1])`

. Now 9 is the new `sum`

and `[1]`

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 `[1]`

, 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){
var ways_to_fulfill_roll = getAllPossAddends(roll);
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
alert("Oh hey, You won!");
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;
}
}
```

Think that’s about it!

*Side Note*: I hope to write more programs that have a `randPraise`

function:

```
function randPraise(){
var praise = ["Awesome!", "Good job!", "Knew you could do it!", "Sweet!", "You got this!", "Again! Again!", "Keep it up!", "Keep going!", "Easy, right?"];
var rand = Math.floor(Math.random() * (praise.length));
return praise[rand];
}
```