Databases
StackOverflow2013
Postsdbo
POA-star algorithm for chess piece pathfinding
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POA-star algorithm for chess piece pathfinding
    primarykey
    data
    text
    <p>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:</p> <pre><code>public List&lt;Node&gt; aStar(int[,] chessBoard , Tuple&lt;int , int&gt; startXY , Tuple&lt;int , int&gt; endXY , int piece) { //Tuple&lt;int[] , int[]&gt; 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&lt;int[],int[]&gt;(knightMovementX, knightMovementY); List&lt;Node&gt; open = new List&lt;Node&gt;(); List&lt;Node&gt; closed = new List&lt;Node&gt;(); List&lt;Node&gt; zero = new List&lt;Node&gt;(); 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 &lt; moves.Item1.Length ; i++) { newX = currentNode.Position.Item1 + moves.Item1[i]; newY = currentNode.Position.Item2 + moves.Item2[i]; if (newX &gt;= 0 &amp;&amp; newX &lt; chessBoard.GetLength(0) &amp;&amp; newY &gt;= 0 &amp;&amp; newY &lt; chessBoard.GetLength(1)) { if (chessBoard[newX , newY] == -1) { Tuple&lt;int , int&gt; newPos = new Tuple&lt;int , int&gt;(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 &lt; open.Count() ; i++) { if (open[i].Cost &lt; 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 &amp;&amp; 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 &lt; 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 &gt;= 0 &amp;&amp; newX &lt; chessBoard.GetLength(0) &amp;&amp; newY &gt;= 0 &amp;&amp; newY &lt; chessBoard.GetLength(1)) { if (chessBoard[newX , newY] == -1) { Tuple&lt;int , int&gt; newPos = new Tuple&lt;int , int&gt;(newX , newY); Node adjacentNode = new Node(newPos , currentNode , currentNode.Cost + 1); for (int j = 0 ; j &lt; closed.Count ; j++) { if ((closed[j].Position.Item1 == adjacentNode.Position.Item1) &amp;&amp; (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 &lt; open.Count ; x++) { if ((open[x].Position.Item2 == adjacentNode.Position.Item1) &amp;&amp; (open[x].Position.Item1 == adjacentNode.Position.Item2)) { isInOpened = true; if (adjacentNode.Cost + 1 &lt; 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; } </code></pre> <p>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.</p> <p>If I mark the squares that the rook can move to with 0's, then</p> <pre><code>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 </code></pre> <p>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..</p> <p>Thank you all in advance</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USJoonasL
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. COCan't you mark all squares *after* the blocked square as blocked, too?
      singulars
      1. POA-star algorithm for chess piece pathfinding
      1. USusr
    2. COThe 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?
      singulars
      1. POA-star algorithm for chess piece pathfinding
      1. USJoonasL
    3. COWell, 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.
      singulars
      1. POA-star algorithm for chess piece pathfinding
      1. USusr
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload