Finding Four-in-a-Row for the Win

A win algorithm for Vue.js Connect Four

With the Connect Four game we created in the previous post, we're able to use Vue transitions to animate checkers dropping into place on the game board. Though we're able to add checkers, we still weren't declaring the winner when four-in-a-row had been achieved—kind of the whole point of the game. We'll tackle that in this post.

Before we dive in, here's a pen of the game with the win logic we'll be describing so you'll see where we'll end up:

See the Pen Connect Four with Vue.js, SVG: detect winner and animated checkers by Ross Kaffenberger (@rossta) on CodePen.

When a player achieves four-in-a-row, we update the visual elements on the board to indicate the win and provide a "Play again" link to reset the game state.

Imagining the algorithm

We want the game logic to evaluate the state of the board after each checker is played and before allowing the next player to drop their checker. If four-in-a-row is found, we'll want to highlight the winning segment of checkers and declare the winner in the UI. We'll also want to declare a draw if the board is full and no one has won.

The basic skeleton of the win algorithm will work as follow:

check all viable horizonal segments FOR THE WIN. Return the winner OR
check all viable vertical segments FTW. Return the winner OR
check all viable "forward slash" segments FTW. Return the winner OR
check all viable "back slash" segments FTW. Return the winner OR

We use the word viable to mean that the segment must contain four "slots" that exist on the game board. In other words, since the game board has seven columns, indexed as 0-6, each row contains only four horizonal segments: 0-3, 1-4, 2-5, 3-6.

As described, it's a bit wasteful to check every possible segment in the board. This is especially true at the outset, when few checkers are on the board, or near the end when many segments have already been checked on previous turns. Since we're checking the board on each drop and we know the position of the last checker played, we can reduce the number of computations by treating the last checker as a focal point. So we update our definition of a viable segment to mean segments of four on the board that intersect with the last checker played.

To figure out which segments over lap with the last checker played, we need a few values:

Given an object lastChecker of the form { row, col }, and the properites rowCount and colCount representing the total number of rows and columns respectively, we can determine these values as follows in JavaScript:

const min = num => Math.max(num - 3, 0);
const max = (num, max) => Math.min(num + 3, max);

const { row: focalRow, col: focalCol } = lastChecker;
const minCol = min(focalCol);
const maxCol = max(focalCol, this.colCount-1);
const minRow = min(focalRow);
const maxRow = max(focalRow, this.rowCount-1);

The min and max row and column values form the boundaries of the search space, which may be much smaller than the total number of segments on the board, especially when the last checker played is near the edges.

Checking the horizonal segment

Using these values, we can select only the segments in the horizontal, vertical, and diagonal intersections with our last played checker. Let's say the last checker ended up in row 3 and column 2. There are only three horizonal segments we need to check from this position. Here's a visual:

In the context of our GameContainer component, here's one way of iterating through those segments and searching for a winner:

// GameContainer method
checkHorizontalSegments({ focalRow, minCol, maxCol }) {
  for (let row = focalRow, col = minCol; col <= maxCol; col++) {

    // the horizonal segment contains four neighboring coordinates across
    const segment = [[row, col], [row, col+1], [row, col+2], [row, col+3]];

    // this.getChecker returns the checker object { row, col, color } for a given position
    const checkers = segment.map(([row, col]) => this.getChecker({row, col}));

    // If all colors are valid and match
    if (checkers.reduce((a, b) => a === b && a !== EMPTY)) {
      return { color: checkers[0].color, checkers };
    }
  }
},

If a win is detected, we'll record the color and checker positions of the winning segment, which we can later use as data to show the winning state on the game board. Similar functions for checking the vertical and diagonal segments are left as an exercise for the reader... or you may inspect the source of the CodePen demo.

Updating the Vue

Putting this altogether, our win algorithm in JavaScript could be as follows:

// GameContainer method
checkForWin(lastChecker) {
  if (!lastChecker) return;

  const min = num => Math.max(num - 3, 0);
  const max = (num, max) => Math.min(num + 3, max);

  const { row: focalRow, col: focalCol } = lastChecker;
  const minCol = min(focalCol);
  const maxCol = max(focalCol, this.colCount-1);
  const minRow = min(focalRow);
  const maxRow = max(focalRow, this.rowCount-1);
  const coords = { focalRow, focalCol, minRow, minCol, maxRow, maxCol };

  return this.checkHorizontalSegments(coords) ||
    this.checkVerticalSegments(coords) ||
    this.checkForwardSlashSegments(coords) ||
    this.checkBackwardSlashSegments(coords);
},

Recall from the previous post, once a checker is dropped, we emit two custom events, one to create the checker component, 'drop' and a second, 'land', to indicate the falling checker animation has completed. We're bubbling these events up to the GameContainer where we can then check for the win. For the checker drop, we lock the game from additional moves while this processing is carried out and we obtain a reference to the last checker and pass to our checkForWin method:

// GameContainer method
drop({ col, row }) {
  if (this.isLocked) return;

  this.isLocked = true;

  const checker = { row, col, color };
  this.checkForWin(checker);

  // update the board
  // switch turns
},

When the animation completes, the land callback is triggered on the GameContainer. Here, we check for the win. If the winner was set by the checkForWin method, we'll display the win or unlock the game so the next player can play their turn.

// GameContainer method
land() {
  if (this.winner) {
    this.displayWin(winner);
  } else {
    this.isLocked = false;
  }
},

Display win simply sets the game status and sets a flag on each of checkers in the winner segment.

// GameContainer method
displayWin(winner) {
  this.status = 'OVER';
  this.winner.checkers.forEach((checker) => {
    this.setChecker(checker, {isWinner: true});
  });
},

Our components can react to this new state by updating various elements of the UI. One approach we've taken is to adjust the opacity of the non-winning checkers to accentuate the winners:

// BoardChecker computed
opacity() {
  return (this.status === OVER && !this.isWinner) ? 0.25 : 1.0;
},

Checking for a draw

There's one case we haven't yet accounted for—what if no one wins?

It's possible for a game to reach a state where all the cells are filled with checkers, but neither player has acheived four-in-a-row. To account for this case, we'll want to check a draw before checking for the win on each turn. A draw occurs when the number of checkers played equals the number of cells:

// GameContainer method
checkForDraw() {
  this.isDraw = Object.keys(this.checkers).length === this.rowCount * this.colCount;
},

We'll update the land method to short-circuit on a draw:

// GameContainer method
land() {
  if (this.isDraw) return this.displayDraw();

  if (this.winner) {
    this.displayWin(winner);
  } else {
    this.isLocked = false;
  }
},

Highlighting the simplicity of our Vue-based reactive system, displaying the draw means simply setting the game state to 'OVER';

displayDraw() {
  this.status = OVER;
},

Resetting the game

We can use the game status to display a message to the players and provide a "Play again" link:

<p v-if="status === 'OVER'">
  {{ gameOverMessage }}
  <a href="#" @click="reset">Play again</a>
</p>

The gameOverMessage is simply a computed property that switches on the winner state:

// GameContainer computed
gameOverMessage() {
  if (this.winner) {
    return `${titleize(this.winner.color)} wins!`;
  } else {
    return `It's a draw!`;
  }
},

For the "Play again" link, we just add a function to reset the game state:

// GameContainer method
reset() {
  this.winner = undefined;
  this.isLocked = false;
  this.status = PLAY;
  this.checkers = {};
},

Summing up

We've come a long way—we developed a basic algorithm to search the game board for a winner while ensuring we only traverse relevant segments. We also leveraged the simplicity of reactive Vue properties to trigger UI updates. We now have a decent version of Connect Four playable in the browser by individual(s) using the same browser. We've also lumped a ton of logic into the game container and have no mechanism to play opponents ver the network. There's some exciting work to do ahead: we'll work on introducing additional layers to our frontend design by building on Vue libraries like vue-router for client-side routing and vuex for state managment. This will set us up to make the game playable over the network by connecting our game to an Elixir/Phoenix backend.

Discuss it on Twitter · Part of the Connect Four series. Published on Jan 28, 2018

More posts

Deploying Vue with CircleCI 2.0

Our series on building Connect Four with Vue.js continues by setting up automated deployment to Amazon S3 with CircleCI and the command line tool s3deploy

Animating Connect Four with Vue.js

Continuing our series on building Connect Four with Vue and Phoenix, we'll use Vue transitions and a third party library to animate the SVG checkers falling and bouncing into place when added to the game board.

Background Photo by Peter Clarkson on Unsplash