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.