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
    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?2012-06-17
  • 0
    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.2012-06-17
  • 0
    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.2012-06-18
  • 0
    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.2012-06-18
  • 0
    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 say2012-06-19
  • 0
    No, a while loop will end the first time the condition is not fulfilled. Therefore, considering your diagram, if we start with A 0 0 z 0 0 B, then after the first iteration you have A 1 0 z 0 0 B, then A 1 1 z 0 0 B and here the loop ends as the loop condition fails.2012-06-19
  • 0
    Sorry for not understanding, really. I have looked at this problem for too long to be clear about it. So I have a loop that goes through the list of all the possible moves a rook can make, two lists that have the possible X and Y coordinates, for example: `listX = {1,2,3,4...} listY = {0,0,0,0...}` Now I go through those lists and check `if: chessBoard[listX[i]][listY[i]] == no obstacle` if there is no obstacle I add the new node to an array. `if: chessBoard[listX[i]][listY[i]] == obstacle` Then I end the loop as you say. What next? I really appreciate you helping me.2012-06-19
  • 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