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.