How to determine if a path is free of obstacles in chess?

Question

I have a 2D array containing all the Piece objects, each an instance of Rook, Bishop, King etc...

How can I find out if the path from srcX,srcY to dstX,dstY is obstructed by another piece?

The only things I can think of would involve massive amounts of tedious code =/

Answer 1

Your comment about "massive amounts of tedious code" is a huge exaggeration. No path on a chessboard is more than eight squares, and all of them can be followed by a simple algorithm - incrementing or decrementing the row and/or column counter. (Except for the knight, which can only move to eight squares and can't be blocked.) I doubt that the code for any piece takes longer than twenty lines.

For example here is the code for a bishop:

// check move legality not taking into account blocking
  boolean canMoveBishopTo(int srcx,int srcY,int destX,int destY) {
      if (srcX<0 || srcX>7 ||srcY<0 || srcY>7 || destX<0 || destX>7 ||destY<0 || destY>7) {
        throw new IllegalArgumentException();
      }
      if ((srcX==destX || srcY==destY) {
        return false;
      }

      if (Math.abs(destX-srcX) == Math.abs(srcY-destY) {
        return true;
      }
      return false;
    }

boolean isBishopMoveBlocked(int srcX,int srcY,int destX,int destY) {
  // assume we have already done the tests above
  int dirX = destX > srcX ? 1 : -1;
  int dirY = destY > srcY ? 1 : -1;
  for (int i=1; i < Math.abs(destX - srcX) - 1; ++i) {
    if (pieceOnSquare(srcX + i*dirX, srcY + i*dirY) {
      return false;
    }
  }
  return true;
}
  

Answer 2

This problem yields nicely to an array solution (which is probably why it was assigned as an array exercise). It seems that what you're missing is that each of the multiple directions can be done using the sign of the step, so in the code you don't need to treat each direction explicitly. In pseudocode:

steps_bishop = [[1,1], [1,-1], [-1, 1], [-1,-1]] # an array of each possible step direction (which are also arrays)
steps_rook = [[1,0], [-1,0], [0, 1], [0,-1]]

# everything else is agnostic to step direction:
current_position = get_current_position()
steps = steps_bishop  # step like a bishop, for example

for step_direction in steps:
    while still_on_board(current_position) and no_collision(current_position):
        current_position += step_direction

Answer 3

We have a start and a destination point and know, that we only have to look at horizontal, vertical or diagonal lines.

First, calculate a direction vector. This is a 2D point with values like

Point north = new Point(0,1);
Point northEast = new Point(1,1);
Point east = new Point(1,1);
// ...
Point northWest = new Point(-1,1);

This is pretty easy:

Point start = getStart();
Point dest = getDest();
Point direction = new Point(Math.signum(dest.x-start.x), 
                            Math.signum(dest.y-start.y));

(Example: start = (2,2), destination = (7,7) -> (signum(7-2), signum(7-2)) = (1,1))

Now just increment boardpositions by the direction point until you reach destination and check for each 2D point, if the place contains a piece.

Here's a quick draft (take it as pseudo code if it doesn't compile ;) )

Point start = getStart();
Point dest = getDest();
if (start.equals(dest)) return false; // nothing in between by definition

Point direction = new Point(Math.signum(dest.x-start.x), 
                            Math.signum(dest.y-start.y));
Point current = new Point(start.x+direction.x, start.y+direction.y);
while(!current.equals(dest)) {
  if (isOccupied(board[current.x][current.y])) // test to be implemented
     return true; // something in between
  current.x = current.x + direction.x;
  current.y = current.y + direction.y;      
}
return false; // nothing in between

Answer 4

Let the 2D array represent the board, empty spaces, pieces and all.

There are 8 directions you need to check.

1. Up and to the right.
2. Up.
3. Up and to the left.
4. Left.
5. Down and to the left.
6. Down.
7. Down and to the right.
8. Right.

Now you just need to know how to increment/decrement your indices and test the positions for emptiness.

Hopefully I have not given too much away.

Answer 5

Since chess pieces all move in straight lines without jumping (except for the Knight), it should be sufficient to write a function to check if the (straight) line from src to dst passes through a piece, and use that for every piece except the knight (which will always be able to get to the destination).

Of course, for all pieces, the destination square should be empty.

And to get to the destination should actually be a legal move - that shouldn't be too hard to check either, if necessary.

The main function would just get the direction used (via dst-src interpreted as a ratio-like thing and reduced to simplest terms) and loopily check whether a piece is in the way.

Answer 6

Two conditions need to be met:

1. dst can not be occupied by a piece of the same color
2. All other (non knight) moves are either diagonal, horizontal or vertical. So just check that adjacent row, column or diagonal entries of your array have no existing pieces between src and dst

Answer 7

It all depends on which kind of board representation you choose. The one you have choses is simple to start with but you run into issues of performance very quickly. So yes, you will need to write some tedious amounts of code. It could help you to generate this code instead of writing it out by hand. On the other hand, you might be interested in other representations. For example, bitboards are the state of the art and will (correctly implemented) give tremendous speed-ups. Note that the amount of code might still be massive, and certainly a lot more complex. Here's an introduction by Robert Hyatt (author of Crafty) that you might find interesting: boardrep.

Good luck!

Answer 8

I'd take a look at A*, it's one of the most popular pathing algo: http://en.wikipedia.org/wiki/A*_search_algorithm

It might be more code than you would want to type, but it's really usefull knowledge you might be able to use elsewhere

Answer 9

Instead of calculating it every time you want to know, it might be easier to keep track of all the possibilities for each piece at all times.

Answer 10

Did you consider to represent your chess board as a graph? You can then simply traverse the graph from point A to point B and see if there are any 'nodes' in your way.