C# finding shortest path for rook, bishop and queen on n*m board

See more:

C#

algorithm

Hello.

I have a question regarding an algorithm. This is my code that finds the shortest paths for the king and knight from point A to point B and moves around obstacles on its path.

public List<Node> aStar(int[,] chessBoard, Tuple<int, int> startXY, Tuple<int, int> endXY, int piece) {
  // All possible kings movements for this example
  int[] kingMovementX = { -1 , -1 , -1 , 0 , 0 , 1 , 1 , 1 };
  int[] kingMovementY = { 0 , -1 , 1 , 1 , -1 , 1 , 0 , -1 };
  var moves = new Tuple<int[] , int[]>(kingMovementX , kingMovementY);

  // Add first node to open list
  List<Node> open = new List<Node>();
  List<Node> closed = new List<Node>();
  List<Node> zero = new List<Node>();
  Node currentNode = new Node(startXY);

  open.Add(currentNode);

  int newX = 0;
  int newY = 0;

  // Adding adjacent nodes to the open list
  for (int i = 0; i < moves.Item1.Length; i++) {
    newX = currentNode.Position.Item1 + moves.Item1[i];
    newY = currentNode.Position.Item2 + moves.Item2[i];
    if (newX >= 0 && newX < chessBoard.GetLength(0) && newY >= 0 && newY < chessBoard.GetLength(1)) {
      if (chessBoard[newX, newY] == -1) {
        Tuple<int, int> newPos = new Tuple<int, int>(newX, newY);
        Node adjacentNode = new Node(newPos, currentNode, 1);
        open.Add(adjacentNode);
      }
    }
  }
  // remove starting node from open list and add to closed list
  closed.Add(open[0]);
  open.RemoveAt(0);

  // repeat until the open list is empty or stop with an error
  while (open.Count != 0) {

    // selecting the node with the lowest cost from the open list and adding to closed list
    int lowest = 99;
    int lowestIndex = 0;
    for (int i = 0; i < open.Count(); i++) {
      if (open[i].Cost < lowest) {
        lowest = open[i].Cost;
        lowestIndex = i;
      }
    }

    // if target is added to closed list the path is found
    closed.Add(open[lowestIndex]);
    if (open[lowestIndex].Position.Item1 == endXY.Item1 && open[lowestIndex].Position.Item2 == endXY.Item2) {
      return closed;
    }
    open.RemoveAt(lowestIndex);

    // check all adjacent nodes that are not in a closed list and do not have obstacles
    currentNode = closed.ElementAt(closed.Count - 1);
    for (int i = 0; i < moves.Item1.Length; i++) {
      bool isInClosed = false;
      bool isInOpened = false;
      newX = currentNode.Position.Item1 + moves.Item1[i];
      newY = currentNode.Position.Item2 + moves.Item2[i];
      if (newX >= 0 && newX < chessBoard.GetLength(0) && newY >= 0 && newY < chessBoard.GetLength(1)) {
        if (chessBoard[newX, newY] == -1) {
          Tuple<int, int> newPos = new Tuple<int, int>(newX, newY);
          Node adjacentNode = new Node(newPos, currentNode, currentNode.Cost + 1);

          for (int j = 0; j < closed.Count; j++) {
            if ((closed[j].Position.Item1 == adjacentNode.Position.Item1) && (closed[j].Position.Item2 == adjacentNode.Position.Item2)) {
              isInClosed = true;
            }
          }
          // If a node is already in the open list and when the cost of the node
          // in the open list is larger than the cost of the current node add current
          // node as a parent to the node in the open list
          if (isInClosed == false) {
            for (int x = 0; x < open.Count; x++) {
              if ((open[x].Position.Item2 == adjacentNode.Position.Item1) && (open[x].Position.Item1 == adjacentNode.Position.Item2)) {
                isInOpened = true;
                if (adjacentNode.Cost + 1 < open[x].Cost) {
                  open[x].Parent = adjacentNode;
                  open[x].Cost = adjacentNode.Cost + open[x].Cost;
                }
              }
            }
            // if a node is not in the open list, add it.
            if (isInOpened == false) {
              open.Add(adjacentNode);
            }
          }
        }
      }
    }
  }
  Console.WriteLine("No path found");
  return zero;
}

To be more precise, this part of the code handles checking if a square is free (has a value of -1):

// Adding adjacent nodes to the open list
  for (int i = 0; i < moves.Item1.Length; i++) {
    newX = currentNode.Position.Item1 + moves.Item1[i];
    newY = currentNode.Position.Item2 + moves.Item2[i];
    if (newX >= 0 && newX < chessBoard.GetLength(0) && newY >= 0 && newY < chessBoard.GetLength(1)) {
      if (chessBoard[newX, newY] == -1) {
        Tuple<int, int> newPos = new Tuple<int, int>(newX, newY);
        Node adjacentNode = new Node(newPos, currentNode, 1);
        open.Add(adjacentNode);
      }
    }
  }

The problem is with the queen, rook and bishop in a scenario where for example the board looks like this

A -1 -1 -1 x -1 -1 B -1
-1.....................
.......................
etc.

When moving with the rook for example the output will be wrong, because the algorithm checks all the moves the rook can make and checks if those squares are occupied or not, so it starts checking from x,y(0,0) and raising the x value

A 1 1 1 x 1 1 B 1
.................
.................
etc.

When the algorithm sees that a square X is already occupied it just checks the next possible move for the rook (x+1) and arrives at the square next to the obstacles
In the end I get a path straight from A1 to B1 although there is an obstacle in between.

I know this may seem hard to understand because I am having difficulty explaining it, but I appreciate any help you can give me with the problem.