我的A *算法有问题 . 这必须在n * 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
基本上我不知道当遇到无法跳过棋子并且可以一次移动多个方块的棋子遇到障碍物时该怎么办 . 跳过被阻挡的方块不做..
谢谢大家