Connect 4 algorithm in javascript

user_1835642 0
Viewed 6908

What is the best way to check 4 in a row in connect 4?

I won't copy the code for the array but it is basically an array of length 42. Each array element holds the X, Y position for drawing and the color

var board_array = [{x:60, y:55, c:"Red"}, // ... and so on

and looks like this:

enter image description here

Initially I took this approach. Here are all the different possible ways someone can win the game. It's not all the possible 4 in a row positions but all the different ways someone can win vertically, horizontally and vertically - you still need to check using some sort of nested for loop

// Winning vertically
wins[0]  = new Array(0, 7,  14, 21, 28, 35);
wins[1]  = new Array(1, 8,  15, 22, 29, 36);
wins[2]  = new Array(2, 9,  16, 23, 30, 37);
wins[3]  = new Array(3, 10, 17, 24, 31, 38);
wins[4]  = new Array(4, 11, 18, 25, 32, 39);
wins[5]  = new Array(5, 12, 19, 26, 33, 40);
wins[6]  = new Array(6, 13, 20, 27, 34, 41);
// Winning horizontally
wins[7]  = new Array(0,   1,  2,  3,  4,  5,  6);
wins[8]  = new Array(7,   8,  9, 10, 11, 12, 13);
wins[9]  = new Array(14, 15, 16, 17, 18, 19, 20);
wins[10] = new Array(21, 22, 23, 24, 25, 26, 27);
wins[11] = new Array(28, 29, 30, 31, 32, 33, 34);
wins[12] = new Array(35, 36, 37, 38, 39, 40, 41);
// Winning diagonally, left to right
wins[13] = new Array(14, 22, 30, 38);
wins[14] = new Array(7, 15, 23, 31, 39);
wins[15] = new Array(0, 8, 16, 24, 32, 40);
wins[16] = new Array(1, 9, 17, 25, 33, 41);
wins[17] = new Array(2, 10, 18, 26, 34);
wins[18] = new Array(3, 11, 19, 27);
//Winning diagonally, right to left
wins[19] = new Array(20, 26, 32, 38);
wins[20] = new Array(13, 19, 25, 31, 37);
wins[21] = new Array(6,  12, 18, 24, 30, 36);
wins[22] = new Array(5,  11, 17, 23, 29, 35);
wins[23] = new Array(4,  10, 16, 22, 28);
wins[24] = new Array(3,   9, 15, 21);

If you think of the board_array as this:

//0  1  2  3  4  5  6
//7  8  9  10 11 12 13
//14 15 16 17 18 19 20
//21 22 23 24 25 26 27
//28 29 30 31 32 33 34
//35 36 37 38 39 40 41

I used a 3-layer for loop and a counter to check wins array against board_array but to no avail. I just wondered if there is a simpler way.

pseudocode algorithm javascript
3 Answers

You could use a regular expression.

Convert the game representation to a string and perform a regular expression on it to find a win.

If for instance a column is stringified as "121000", it means that player 1 has two discs in this column, and player 2 has one disc in-between those two. The whole board could be stringified by concatenating such column strings, using a separator. For instance,

"100000,212121,212000,121211,212100,000000,200000"

Given such a string, you can detect a win with this regular expression:

([12])(\1{3}|(.{5}\1){3}|(.{6}\1){3}|((.{7}\1){3}))

The first character of the match will identify the player that wins, so you don't even need to know who played the last move; it follows.

Here is an implementation of that idea. I shamelessly borrowed the wonderful CSS of @FredGandt's answer:

const game = {
    reset(onchange) {
        this.columns = Array.from({length:7}, () => Array(6).fill(0)); // 2D array
        this.moveCount = 0;
        (this.onchange = onchange)(-1); // callback that can be used for rendering
    },
    drop(column) {
        let i = this.columns[column].indexOf(0);
        if (i < 0 || this.result() >= 0) return; // cannot move here
        this.columns[column][i] = this.moveCount++ % 2 + 1;
        this.onchange(this.result());
    },
    result() { // 0=draw, 1=yellow wins, 2=red wins, -1=undecided
        return +this.columns.map(col => col.join("")).join()
                    .match(/([12])(\1{3}|(.{5}\1){3}|(.{6}\1){3}|((.{7}\1){3}))/)?.[1]
            || -(this.moveCount < 42);
    }
};

// I/O handling
const container = document.querySelector("#container");
const display = result =>
    container.innerHTML = "<table>" + game.columns[0].map((_, rowNo) =>
            "<tr>" + game.columns.map(column => 
                `<td class="${['', 'yellow', 'red'][column[5-rowNo]]}"><\/td>`
            ).join("") + "</tr>"
        ).join("") + 
        `<\/table><out class="${["nobody", "yellow", "red"][result]??""}"><\/out>`;
container.addEventListener("click", e => 
    e.target.tagName == "TD"  ? game.drop(e.target.cellIndex) 
  : e.target.tagName == "OUT" ? game.reset(display) : null
);
game.reset(display);
/* Taken from @FredGandt's answer */
table,
output {
  box-shadow: .5vh .5vh 2vh .5vh rgba(0, 0, 0, .5);
}
table {
  width: 90vh;
  border-collapse: collapse;
  border: 2vh solid royalblue;
}
td {
  width: calc(90vh / 7);
  background: royalblue;
  cursor: default;
  user-select: none;
}
td:before {
  content: "";
  display: block;
  width: calc(90vh / 7);
  height: calc(90vh / 7);
  border-radius: 50%;
  box-shadow: inset .5vh .5vh 2vh .5vh rgba(0, 0, 0, .5);
  background: white;
}
td.red:before {
  background: red;
}
td.yellow:before {
  background: yellow;
}
out {
  position: fixed;
  display: none;
  width: 90vh;
  height: 10vh;
  top: 10vh;
  left: 5vh;
  background: white;
  text-align: center;
  font: 5vh sans-serif;
  line-height: 10vh;
  cursor: pointer;
}
out:before {
  content: attr(class) " wins";
}
out.red,
out.yellow,
out.nobody {
  display: block;
}
<div id="container"></div>

user_54598390
Related