我的 A* 算法有问题。那必须在* m板上找到最短路径。我的算法适用于国王和骑士，如下：
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;
}
我非常希望它也适用于车、王后和主教。问题在于，当算法遇到值为 -2 的阻塞节点时，它会跳过它并检查下一个可用的移动。
如果我用 0 标记车可以移动到的方格，那么
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
基本上我不知道当遇到无法跳过它们并且一次可以移动许多方格的棋子遇到障碍时该怎么办。跳过被阻挡的方块是不行的。
谢谢大家