Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I originally posted this question of stackoverflow but I was suggested to post it here. So: I am stuck solving a task requiring me to calculate the minimal number of steps required to go from point A to point B with different chess pieces on a n*m board that has obstacles and save the all the shortest paths.

So far I have an algorithm that for all squares calculates the amount of steps to reach them: Example for a knight starting from "A2" (the square marked with zero). Obstacles are marked with "-2" and free squares with "-1"

Before algorithm: https://dl.dropbox.com/u/65978956/before.JPG

After algorithm: https://dl.dropbox.com/u/65978956/after.JPG

The algorithm looks like this:

public int[,] BFS(int[,] chessBoard, Tuple<int, int> startXY, int obstacles, int piece) {
  int dimensionX = chessBoard.GetLength(0);
  int dimensionY = chessBoard.GetLength(1);

  // Look at all the movements a knight can make
  int[] knightMovementY = { -2, -2, -1, -1, 1, 1, 2, 2 };
  int[] knightMovementX = { -1, 1, -2, 2, -2, 2, -1, 1 };
  var allMoves = new Tuple<int[],int[]>(knightMovementX, knightMovementY);

  chessBoard[startXY.Item1, startXY.Item2 - 1] = 0;
  int cnt = dimensionX * dimensionY - obstacles - 1;
  int step = 0;

  // loop until the whole board is filled
  while (cnt > 0) {
    for (int x = 0; x < dimensionX; x++) {
      for (int y = 0; y < dimensionY; y++) {
        if (chessBoard[x, y] == step) {
          for (int k = 0; k < allMoves.Item1.Length; k++) {
            int dx = allMoves.Item1[k] + x, dy = allMoves.Item2[k] + y;
            if (dx >= 0 && dx < dimensionX && dy >= 0 && dy < dimensionY) {
              if (chessBoard[dx, dy] == -1) {
                chessBoard[dx, dy] = step + 1;
                cnt--;
              }
            }
          }
        }
      }
    }
    step++;
  }
  return chessBoard;
}   

The algorithm works also for the king, but for the queen, rook and bishop I need something else, because they can move many squares at a time and cannot jump over obstacles.

I am very thankful for suggestions as to what I am supposed to do to solve this problem for the queen, bishop and rook and how to save the shortest paths from the picture "after algorithm" to an array. I have been looking for days and know that A* algorithm is often used for finding paths, but I don't know how it is going to work when some chess pieces can move such large distances in one move.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

Here's a recursive process to find the number of moves from point $X$ to point $Y$ in a grid $G$ with obstacles $O$.

Search algorithms work by generation the set of squares that can be reached in $n$ moves.

Let $B_0 = \{X\}$ - the border of expansion, $I_0 = \emptyset$ - interior, $E_0 = (G / O) / B_0$ -exterior.
Let $f$ - a function such that for any $g \in G$, $f(g)$ is the set of squares that can be reached from $g$ in one move. This function is the definition of the chess piece you use.

Now, iterate:
$B_n = \bigcup \limits_{x \in B_{n-1}} f(x) \cap E_{n-1}$
$I_n = I_{n-1} \cup B_{n-1}$
$E_n = E_{n-1} / B_n$

Continue until $Y \in B_n$ or $B_n = \emptyset$. In the first case $\text{distance}(X, Y) = n$, in the second, there is no path from $X$ to $Y$.

I hope that explains the general idea. There is plenty of code examples for pathfinding problems. Note that instead of sets of squares, lists of Nodes are used, where a Node is an object containing the position of a square, a reference to the Node that generated it, for the purposes of backtracking and also a priority number if heuristics are used. Heuristic is the simple idea that if $Y$ lies to the left from $X$, the path from $X$ to $Y$ most likely goes to the left (which is not true in case of obstacles). There isn't much point to use heuristics here since $f$ is usually not trivial and the grid is small.

share|improve this answer
    
Thank you for explaining the notion of Nodes to me. I see it everywhere but have not understood it till now. Also, you mentioned that heuristics is probably not needed in this scenario. What algorithm should I be looking for then? Dijkstra? –  JoonasL Jun 17 '12 at 19:12
    
The code of the algorithm depends a lot on the representation of the map (grid, graph, etc). I'm not sure, but it seems to me that Dijkstra's algorithm is more commonly applied to various representations of a graph. A* is probably the better choice as it is often used in grid based games. Note, that if you intend to adapt someone's code for your problem, you only really need to change the expansion function $f$. The heuristics will, at worst, be useless. Although the best thing is to look into several similar algorithms, to see what changes and what remains. –  Karolis Juodelė Jun 17 '12 at 20:40
    
Thanks to your help I managed to implement A* algorithm that finds the shortest path for the king and the knight. I am having trouble implementing the algorithm for the queen, bishop and rook, because they cannot hop over obstacles and when I try to check their movement the same way as with the king and knight they my result will be incorrect, as for example movement along a horizontal can be {1,2,3,4,5,6,7,8} if there is an obstacle on number 4 then because my algorithm checks all possible moves I can still move to square 5, as there is no obstacle there. –  JoonasL Jun 18 '12 at 15:37
    
Consider the rook. You'r expansion function could go like this: let moves be a list of available squares you want to generate, let x, y be the position of the rook. While (x+1, y) is on the grid and not an obstacle, push Node(x+1, y) to moves and increment x. Naturally, you'd have loops for other directions too. –  Karolis Juodelė Jun 18 '12 at 17:57
    
But this causes the problem I was talking about, imagine the scenario A 0 0 z 0 0 0 B When I start at A and start looking at the possible moves a rook can make by incrementing (x+1) it sees that with 1 move I can go to A 1 1 x 1 1 1 B the only square that I can not move to is the "z" square and that should stop the incrementing of x and increment y instead. I hope you understand what I am trying to say –  JoonasL Jun 19 '12 at 6:24
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.