2

I have a problem with my A* algorithm. That has to find shortest paths on a n*m board. My algorithm works for the king and the knight and is as follows:

public List<Node> aStar(int[,] chessBoard , Tuple<int , int> startXY , Tuple<int , int> endXY , int piece)
{
  //Tuple<int[] , int[]> moves = getAllMoves(piece , chessBoard.GetLength(0) , chessBoard.GetLength(1));

  // This getAllMoves function on the previous row
  // returns all the possible moves in two arrays like so:

  int[] knightMovementY = { -2, -2, -1, -1, 1, 1, 2, 2 };
  int[] knightMovementX = { -1, 1, -2, 2, -2, 2, -1, 1 };
  var moves = new Tuple<int[],int[]>(knightMovementX, knightMovementY);

  List<Node> open = new List<Node>();
  List<Node> closed = new List<Node>();
  List<Node> zero = new List<Node>();
  Node currentNode = new Node(startXY);
  int newX = 0;
  int newY = 0;

  // Adding the first node to the open list
  open.Add(currentNode);

  // Checking the adjacent squares and adding them 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);
      }

    }
  }
  // Removing the start node from the open list and adding it to the closed list
  closed.Add(open[0]);
  open.RemoveAt(0);

  // Repeat until the open list is empty or exit with error
  while (open.Count != 0)
  {

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

    // If the target square is added to the closed list a path has been 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 the adjacent squares that are not in a closed list, not blocked and fit on the game board.
    // Blocked squares have a value of -2 and open squares a value of -1
    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 the cost of that node is larger
          // than the cost of the current node, change the parent of the node in the
          // open list to the current node
          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;
}

I would very much like for it to work for the rook, queen and bishop as well. The problem is that at the moment when the algorithm encounters a blocked node with a value of -2, then it skips it and checks for the next available move.

If I mark the squares that the rook can move to with 0's, then

A  B  C  D  E  F G          A B C  D E F G
x -1 -1 -2 -1 -1 y  becomes x 0 0 -2 0 0 y 

Basically I don't know what to do when an obstacle is encountered with chess pieces that cannot jump over them and can move many squares at a time. Skipping the blocked square does not do..

Thank you all in advance

JoonasL
  • 524
  • 9
  • 19
  • Can't you mark all squares *after* the blocked square as blocked, too? – usr Jun 19 '12 at 13:01
  • The blocked squares are provided in an input file. Do you mean I should block all squares to the right of the actual blocked square in the algorithm? – JoonasL Jun 19 '12 at 13:11
  • Well, I'd block all squares the piece can't move to. A* works on any planar graph so all you have to do is get the graph right. – usr Jun 19 '12 at 13:16
  • But the rook can move to for example E1,if D1 is blocked. It just has to make 3 moves to get there (A1->A2->E2->E1). And even if I did block the squares it would still allow me to go from A1 to target square G1 even if there are obstacles in between, because a rook is allowed to move horizontally an unlimited number of moves. That's what I have trouble with. Changing the algorithm somehow so that it would not only forbid a chess piece from stepping ON a blocked square but also from stepping OVER a blocked square. – JoonasL Jun 19 '12 at 13:28
  • I understand what you are saying. The blocked and available squares depend on the position of the rook at a moment in time. A* is capable of handling this. Construct a graph where there are the following edges (among others): A1->A2->E2->E1. You just need to construct the graph of allowed movements correctly. – usr Jun 19 '12 at 13:42
  • So on the first move I have to block every square the rook cannot go to, then for the new position recalculate the graph and again, block all positions the rook cannot go to? – JoonasL Jun 19 '12 at 14:04
  • No the graph is static. Each square is a vertex and there is an edge between all squares your piece can move between. Moving chess pieces is entirely analogous to moving cars on streets. Intersection = square, street = edge. – usr Jun 19 '12 at 14:09
  • Damn, I would like to move this to chat, but I don't have enough points to talk there. Basically, I am so lost it is not even funny. Do you mean I have to redo the entire algorithm? At the moment I don't have any edges and the graph is the same for all the chess pieces. Right now I have a two dimensional list where some elements are blocked positions and some open positions. Do I need to construct a graph from it with edges between all the vertices I can move to and then change my algorithm so that it checks these edges instead of the moves a chess piece can make like I do right now? – JoonasL Jun 19 '12 at 14:37
  • You got that right. I don't think you are lost. What you want is just a standard A* search. See http://stackoverflow.com/questions/2138642/simplest-c-sharp-implementation-of-a-algorithm . I think the car-on-roads analogy is really good, btw. That's what A* is originally made for. – usr Jun 19 '12 at 14:41

0 Answers0