1
$\begingroup$

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 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(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.

1 Answers 1

1

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.

  • 0
    Consider a rook on square (4,5). To know if it can reach (2, 5), you must first know if it can reach (3, 5). By iterating through all squares in any order you don't have a good way to check these relations. Therefore you have to check squares in proper order. Say the rook is on (x, y). Then first check (x-$1$, y), then, if it is free, add a node there and check (x-$2$, y), (x-$3$, y), etc. until one of them fails. Then do the same for other directions.2012-06-19