Hy, I am trying to implement an Connect Four Game in javascript / jQuery. First off this is no homework or any other duty. I'm just trying to push my abilities.

My "playground" is a simple html table which has 7 rows and 6 columns.
But now I have reached my ken. I'm stuck with the main functionality of checking whether there are 4 same td's around. I am adding a class to determine which color it should represent in the game. First I thought I could handle this with .nextAll() and .prevAll() but this does not work for me because there is no detection between.
Because I was searching for siblings, when adding a new Item and just looked up the length of siblings which were found and if they matched 4 in the end I supposed this was right, but no its not :D Is there maybe any kind of directNext() which provides all next with a css selector until something different comes up ?

I will put all of my code into this jsfiddle: /

Maybe somebody has ever tried the same or someone comes up with a good idea I'm not asking anybody to do or finish my code. I just want to get hints for implementing such an algorithm or examples how it could be solved !

Thanks in anyway !

Hy, I am trying to implement an Connect Four Game in javascript / jQuery. First off this is no homework or any other duty. I'm just trying to push my abilities.

My "playground" is a simple html table which has 7 rows and 6 columns.
But now I have reached my ken. I'm stuck with the main functionality of checking whether there are 4 same td's around. I am adding a class to determine which color it should represent in the game. First I thought I could handle this with .nextAll() and .prevAll() but this does not work for me because there is no detection between.
Because I was searching for siblings, when adding a new Item and just looked up the length of siblings which were found and if they matched 4 in the end I supposed this was right, but no its not :D Is there maybe any kind of directNext() which provides all next with a css selector until something different comes up ?

I will put all of my code into this jsfiddle: http://jsfiddle.net/LcUVf/5/

Maybe somebody has ever tried the same or someone comes up with a good idea I'm not asking anybody to do or finish my code. I just want to get hints for implementing such an algorithm or examples how it could be solved !

Thanks in anyway !

• javascript
• jquery
• html

• 6 I would maintain a 2 dimensional array and use the HTML table just for displaying the current state. The checks should be easier and faster without having to access the DOM multiple times. – Sirko Commented Feb 17, 2012 at 15:45
• Yeah that was my first intension too, have you done anything simmilar ? BTW: post this as answer, as far nothing more helpful comes up so that I could accept your answer! – mas-designs Commented Feb 17, 2012 at 15:46

3 Answers 3

DOM traversal is not particularly efficient so, when you can avoid it, I'd recommend doing so. It'd make sense for you to build this as a 2D array to store and update the state of the game. The table would only be a visual representation of the array.

I know that, normally, you would build the array with rows as the first dimension and columns as the second dimension but, for the purposes of being able to add pieces to each column's "stack," I would make the first dimension the columns and the second dimension the rows.

To do the check, take a look at this fiddle I made:

http://jsfiddle.net/Koviko/4dTyw/

There are 4 directions to check: North-South, East-West, Northeast-Southwest, and Southeast-Northwest. This can be represented as objects with the delta defined for X and Y:

directions = [
  { x: 0, y: 1  }, // North-South
  { x: 1, y: 0  }, // East-West
  { x: 1, y: 1  }, // Northeast-Southwest
  { x: 1, y: -1 }  // Southeast-Northwest
];

Then, loop through that object and loop through your "table" starting at the farthest bounds that this piece can possibly contribute to a win. So, since you need 4 pieces in a row, the currently placed piece can contribute in a win for up to 3 pieces in any direction.

minX = Math.min(Math.max(placedX - (3 * directions[i].x), 0), pieces.length    - 1);
minY = Math.min(Math.max(placedY - (3 * directions[i].y), 0), pieces[0].length - 1);
maxX = Math.max(Math.min(placedX + (3 * directions[i].x),     pieces.length    - 1), 0);
maxY = Math.max(Math.min(placedY + (3 * directions[i].y),     pieces[0].length - 1), 0);

To avoid any issues with less-than and greater-than (which I ran into), calculate the number of steps before looping through your pieces instead of using the calculated bounds as your conditions.

steps = Math.max(Math.abs(maxX - minX), Math.abs(maxY - minY));

Finally, loop through the items keeping a count of consecutive pieces that match the piece that was placed last.

function isVictory(pieces, placedX, placedY) {
  var i, j, x, y, maxX, maxY, steps, count = 0,
    directions = [
      { x: 0, y: 1  }, // North-South
      { x: 1, y: 0  }, // East-West
      { x: 1, y: 1  }, // Northeast-Southwest
      { x: 1, y: -1 }  // Southeast-Northwest
    ];

  // Check all directions
  outerloop:
  for (i = 0; i < directions.length; i++, count = 0) {
    // Set up bounds to go 3 pieces forward and backward
    x =     Math.min(Math.max(placedX - (3 * directions[i].x), 0), pieces.length    - 1);
    y =     Math.min(Math.max(placedY - (3 * directions[i].y), 0), pieces[0].length - 1);
    maxX =  Math.max(Math.min(placedX + (3 * directions[i].x),     pieces.length    - 1), 0);
    maxY =  Math.max(Math.min(placedY + (3 * directions[i].y),     pieces[0].length - 1), 0);
    steps = Math.max(Math.abs(maxX - x), Math.abs(maxY - y));

    for (j = 0; j < steps; j++, x += directions[i].x, y += directions[i].y) {
      if (pieces[x][y] == pieces[placedX][placedY]) {
        // Increase count
        if (++count >= 4) {
          break outerloop;
        }
      } else {
        // Reset count
        count = 0;
      }
    }
  }

  return count >= 4;
}

I released a fully working version of the game on Github.

It implements an optimised variation on the algorythm Sirko mentioned.

To avoid any unnecessary redunancy, the algorythm directly checks the DOM rather than a JS table. As that algorythm requires a minimum amount of checks, the performance overhead for accessing the DOM is neglectable.

The current player and a flag for keeping track of whether the game has ended are basicly the only statuses stored in the JS itself.

I even used the DOM to store strings. It has no external dependencies and is supported by all versions of IE from IE6 upwards as well as modern browsers.

Code is optimised for filesize and performance. The latest version also includes animation, even though the total JS code of the game is still only 1.216 bytes after minification.

The Code :

Here's the full, un-minified JS code :

(function (doc, win, onclick, gid, classname, content, showMessage) {
    var
        a, b, c, colorLabel, cid, players, current, finished, newgameLabel, wonLabel, laststart = 1,
        cellAt = function (i, j) {
            return doc[gid](cid + i + j);
        },
        isCurrentColor = function (i, j) {
            return cellAt(i, j)[classname] === players[current];
        },
        start = function () {
            current = laststart = (laststart + 1) % 2;
            finished = 0;
            colorLabel[content] = colorLabel[classname] = players[current = (current + 1) % 2];
            for (a = 1; a < 7; a++)
                for (b = 1; b < 8; b++)
                    cellAt(a, b)[classname] = '';
        },
        makeMove = function (i, j, s) {
            s > 0 && (cellAt(s, j)[classname] = '');
            cellAt(s + 1, j)[classname] = players[current];
            s === i - 1 ? function (i, j) {
                return function (i, j) {
                    for (a = j - 1; 0 < a && isCurrentColor(i, a); a--) {
                    }
                    for (b = j + 1; 8 > b && isCurrentColor(i, b); b++) {
                    }
                    return 4 < b - a;
                }(i, j) || function (i, j) {
                    for (c = i + 1; 7 > c && isCurrentColor(c, j); c++) {
                    }
                    return 3 < c - i;
                }(i, j) || function (i, j) {
                    for (a = i - 1, b = j - 1; 0 < a && !(1 > b) && isCurrentColor(a, b); a--)
                        b--;
                    for (c = i + 1, b = j + 1; 7 > c && !(7 < b) && isCurrentColor(c, b); c++)
                        b++;
                    return 4 < c - a
                }(i, j) || function (i, j) {
                    for (a = i - 1, b = j + 1; 0 < a && !(7 < b) && isCurrentColor(a, b); a--)
                        b++;
                    for (c = i + 1, b = j - 1; 7 > c && !(1 > b) && isCurrentColor(c, b); c++)
                        b--;
                    return 4 < c - a;
                }(i, j);
            }(i, j)
                    ? finished = 1 && win[showMessage](doc[gid](wonLabel)[content].replace("%s", players[current].toLowerCase())) && start()
                    : colorLabel[content] = colorLabel[classname] = players[current = (current + 1) % 2]
                    : setTimeout(function () {
                        makeMove(i, j, s + 1)
                    }, 20);

        };

    return function (n, w, c, h, p1, p2) {
        cid = c;
        newgameLabel = n;
        wonLabel = w;
        colorLabel = doc[gid](c);
        players = [doc[gid](p1)[content], doc[gid](p2)[content]];
        for (a = 1; a < 7; a++)
            for (b = 1; b < 8; b++)
                cellAt(a, b)[onclick] = function (b, a) {
                    return function () {
                        if (!finished)
                            for (a = 6; a > 0; a--)
                                if (!cellAt(a, b)[classname]) {
                                    makeMove(a, b, 0);
                                    break;
                                }
                    };
                }(b);
        ;
        doc[gid](h)[onclick] = function () {
            win[showMessage](doc[gid](newgameLabel)[content]) && start()
        };
        start();
    };
})(document, window, "onclick", "getElementById", "className", "innerHTML", "confirm")("newgame", "won", "color", "restart", "p1", "p2");

A screenshot :

In general a 2dimensional array would be better suited for checking for a line of 4. You could then do something like the following:

function check( lastPiece, playground, player ) {
   // check length in each direction
   var l = 1, 
       i = 1;

   // top to bottom
   while( (playground[ lastPiece.x ][ lastPiece.y - i ] === player) && ((lastPiece.y - i) >= 0) ) { l += 1; i += 1; };
   i = 1;
   while( (playground[ lastPiece.x ][ lastPiece.y + i ] === player) && ((lastPiece.y + i) <= MAX_Y) ) { l += 1; i += 1; };
   if ( l >= 4 ) { return true; }

   // left to right
   l = 1;
   while( (playground[ lastPiece.x - i][ lastPiece.y ] === player) && ((lastPiece.x - i) >= 0) ) { l += 1; i += 1; };
   i = 1;
   while( (playground[ lastPiece.x + i][ lastPiece.y ] === player) && ((lastPiece.x + i) <= MAX_X) ) { l += 1; i += 1; };
   if ( l >= 4 ) { return true; }

   // same for top left to bottom right and bottom left to top right
   // . . .

   // if we got no hit until here, there is no row of 4
   return false;
}

EDIT: added checks for borders of the playground