You are here: irt.org | Games | Techniques | #01 - Detecting Line
By: Keith Drakard
Quite a few games involve checking lines in some fashion - whether it is Connect Four seeing if there really is 4-in-a-row or Tetris seeing if it can remove a row and drop the rest of the bricks down a level.
I've compiled some example functions (in the order that they were written) which I've used in the JavaScript games I've created - so if your game needs some complicated line checking, then hopefully these will give you a good starting point.
In this game, I needed to check that the move the player wanted to make was a legal one - ie. no diagonal jumping over the marbles or over an empty hollow etc.
I made the task easier by relying on the way that I'd set up the board - so remember to take care right from the start in writing your game, or you may make extra work for yourself.
function check_move(from, to) {
var middle= ""; // the board number of the ball in the middle of
// "from" and "to" else "" if illegal move
from= from* 1; to= to* 1; // convert from string to number
// could also do: to= (to- 0);
var diff= from- to; var xpos= (from% 7);
// first we check to see if "diff" equals either 2, -2, 14 or -14
// because that holds true for all valid moves only (ie: it is two
// spaces away in a direct line - due to the setup of the board)
if (diff== 2) {
// now we check to see if a wraparound of "from" and "to" has occured
// on the left hand side of the board
if (!(xpos==1 || xpos==2)) { middle= "ball"+ (from- 1); }
} else if (diff== -2) {
// or alternatively, on the right hand side
if (!(xpos==6 || xpos==0)) { middle= "ball"+ (from+ 1); }
} else if (diff== 14) {
// there's a no need to check this case because of the setup
// of the board (numbers: left to right, top to bottom)
middle= "ball"+ (from- 7);
} else if (diff== -14) {
// and no need to check this case either
middle= "ball"+ (from+ 7);
} else { // illegal move, but we flag it later
}
// okay, so it's a valid move, but lets just make sure that there
// actually is a marble to be jumped over...
if (middle!= "") {
var len= document.images[middle].src.length;
var img= document.images[middle].src.substring(len-10, len);
if (img== "ball_0.gif") { middle=""; } // doh! no marble, no move
}
// we've done our checks and now we return the board number of the
// marble in the middle or the default "" if it's an illegal move
return (middle);
}
In Connect Four, almost any go may produce 4-in-a-row and that can occur in any direction (except straight up) with a possible displacement from the disc position of up to 3 more squares.
When faced with checking that much, you either come up with a really fancy function or a brute force method - so here's the brute force method; although I don't check every square on the board, this function will check up to 25 squares every go.
There's a few ways in which I could halt a line check if it's clear that there isn't going to be a line of four (ie. using while loops instead of for loops) - but it works and the difference to the end user is relatively minimal.
function check(x, y) {
// check the left and right horizontal
four= 0;
for (sq= -3; sq<= 3; sq++) { four= chk(x+ sq, y, four); }
if (four> 3) return(1);
// check down only (you can't drop a disc down a column and
// complete a line of four upwards...)
four= 0;
for (sq= -3; sq<= 0; sq++) { four= chk(x, y+ sq, four); }
if (four> 3) return(1);
// check the diagonals left-down && right-up
four= 0;
for (sq= -3; sq<= 3; sq++) { four= chk(x+ sq, y+ sq, four); }
if (four> 3) return(1);
// check the diagonals left-up && right-down
four= 0;
for (sq= -3; sq<= 3; sq++) { four= chk(x+ sq, y- sq, four); }
if (four> 3) return(1);
return(0);
}
and here's the sub-function used:
function chk(x, y, f) {
// is the square is within the limits of the board?
if (x>0 && x<8 && y>0 && y<maxheight+1) {
// and does it match the player?
if (document.images["x"+x+"y"+y].src== disc[player].src) {
return(f+1);
} else {
if (f>= 4) return(f); else return(0);
}
} else return(f);
}
This is a similiar situation to Connect Four, with the slight variation of having to manipulate lines as well as check them. I would have reused the above code except lines aren't displaced in Reversi - they only start from where you place your disc.
Before the discs in a line can be flipped (from black to white or vice-versa), I had to check that the player has chosen to play in a legal position:
function check_lines(x, y) {
// we're just concerned here whether or not a legal line exists
// - flipping the discs is done in a separate function
// up OR down:
if (check(3-player,x,y,0,-1) || check(3-player,x,y,0,1)) return(1);
// left OR right:
if (check(3-player,x,y,-1,0) || check(3-player,x,y,1,0)) return(1);
// up left OR up right
if (check(3-player,x,y,-1,-1) || check(3-player,x,y,1,-1)) return(1);
// down left OR down right
if (check(3-player,x,y,-1,1) || check(3-player,x,y,1,1)) return(1);
// no legal line in any direction...
return(0);
}
Once it was established that such a line exists, I could commit myself to placing the player's disc and checking in all directions for any of the opponent's discs (3-player) that needed to be swapped:
function go(x, y) {
// place the first disc and increase the score
var swap= 0; score[player]++;
document.images["x"+x+"y"+y].src= counter[player].src;
for (j=-1; j<2; j++) {
for (i=-1; i<2; i++) {
// set swap to equal the number of discs to change in a
// given direction (i,j) from the original position (x,y)
swap= check(3-player, x, y, i, j); score[3-player]-= swap;
while (swap) {
// flip the disc
document.images["x"+(x+(i*swap))+"y"+(y+(j*swap))].src=
counter[player].src;
// increment the score and decrease the number of discs
// left to swap
score[player]++; swap--;
}
}
}
update_scores(); // separate function
}
and here's the sub-function used by both check() and go():
function check(p, tx, ty, dx, dy) {
// (dx,dy) controls the direction to check from (tx,ty)
// the colour of the disc to check is controlled by (p)
var count= 0; tx+= dx; ty+= dy;
while ((tx>=0 && tx<8) && (ty>=0 && ty<8) &&
document.images["x"+tx+"y"+ty].src== counter[p].src) {
// then we're still on the board and counting the opposite
// colour counters
tx+= dx; ty+= dy; count++;
}
// now we've stopped counting the opposite colour counters
// but have we reached a legal end? - ie. our colour counter
// and not the edge of the board or an empty square
if ((tx<0 || tx>7) || (ty<0 || ty>7) ||
document.images["x"+tx+"y"+ty].src== counter[0].src)
return(0); // illegal
else
return(count); // legal
}
Like Solitaire, writing Hnefatafl involved checking the movement of the pieces - although in this example, there was additional constraints involving one piece and the square it originated in.
Note that with JavaScript, you don't often need to store the the board position in a separate array since you can use the document.images["name"] tag to do everything for you, as long as you've set up the names properly.
function check_move(nx, ny, piece) {
// find out which direction to check in:
var dx= 0; var dy= 0;
if (ox> nx) dx= -1; else if (ox< nx) dx= 1;
if (oy> ny) dy= -1; else if (oy< ny) dy= 1;
// check no diagonals (horizontal and vertical moves only):
if (dx!=0 && dy!=0) return(0);
// check nothing between old square and target square:
var xx= dx; var yy= dy;
var what_now= document.images["x"+(ox+xx)+"y"+(oy+yy)].src;
while (what_now== counter[0].src) {
// only the king allowed on or through the centre:
if ((ox+xx== 5) && (oy+yy== 5) && piece!= 3) return(0);
// but the king can't travel more than three squares:
if (piece== 3 && (xx<-3 || xx>3 || yy<-3 || yy> 3)) return(0);
// otherwise, see if we're at the target:
if ((dx && (ox+xx)== nx) || (dy && (oy+yy)== ny)) return(1);
// or carry on:
xx+= dx; yy+= dy;
what_now= document.images["x"+(ox+xx)+"y"+(oy+yy)].src
}
return(0);
}
Games are distributed under the WebGames License