C# - A* 算法给出错误的结果
C# - A* algorithm gives wrong results
我正在尝试在 C# 中制作 4 向 A-star 寻路算法，但无法使其正常工作。在 Main 方法中，我有一个示例 5x5 int 数组映射来设置可以访问哪些字段，哪些不能（0 - 清除字段，1 - 障碍物）。例如，我将 START 点设置为 (1, 3)，将 TARGET 点设置为 (4, 4)，因此我希望路径避开墙壁并继续等等，但事实并非如此。我什至让我的算法显示每个 parent 及其后继者（邻居）。在我的例子中，它显示 (2,4) 作为节点之一，尽管它在 Fields (Map) 中被标记为障碍物，这是怎么发生的？在 GetSuccessors 方法中有明确的声明只包括标记为 0 的那些，但它仍然包括 (2, 4) 点。我不确定 GetSuccessors 或 FindPath（主要算法）是否有问题。
示例地图：
int[,] fields = new int[5, 5] //MAP, 1 - OBSTACLE
{
{ 0, 0, 0, 0, 0 },
{ 0, 1, 1, 1, 0 },
{ 0, 1, 1, 1, 0 },
{ 0, 0, 1, 0, 0 },
{ 0, 0, 1, 0, 0 }
};
示例点：
Node start = new Node(1, 3); //START LOCATION ON MAP
Node target = new Node(4, 4); //TARGET LOCATION ON MAP
生成的路径（从 TARGET 到 START）：
4, 4
3, 4
2, 4
1, 3
完整代码（FindPath 和 GetSuccessors 是主要代码，但我仍然可以用其他方法做错事）：
using System;
using System.Collections.Generic;
using System.Linq;
namespace FoxLib
{
public class Node
{
public Node(int x, int y)
{
this.x = x;
this.y = y;
}
public int x, y; //POSITION ON MAP
public Node parent; //NEEDED TO RETRIEVE PATH LATER
public int G, H, F;
//G - COST FROM START NODE TO THIS NODE
//H - COST FROM THIS NODE TO TARGET (HEURISTIC)
//F - G + H; NODE COST
}
public class Pathfinding
{
public static void FindPath(int startX, int startY, int targetX, int targetY, int[,] fields) //MAIN ALGORITHM
{
bool pathFound=false; //IS PATH AVAILABLE?
Node start = new Node(startX, startY); //STARTING NODE
Node target = new Node(targetX, targetY); //TARGET NODE
start.parent = start;
start.G = 0;
start.H = Math.Abs(target.x - start.x) + Math.Abs(target.y - start.y);
start.F = start.G + start.H;
Node current = new Node(0, 0);
List<Node> openList = new List<Node>(); //NODES WAITING TO BE CHECKED
List<Node> closedList = new List<Node>(); //ALREADY CHECKED NODES
openList.Add(start);
while(openList.Count>0) //DO AS LONG AS THERE ARE STILL NODES TO DISCOVER
{
current = MinFNode(openList); //FIND NODE WITH LOWEST F COST (LOWER=BETTER PATH)
openList.Remove(current); //REMOVE CURRENT NODE FROM QUEUE
if ((current.x==target.x)&&(current.y==target.y)) //TARGET FOUND
{
Console.WriteLine("PATH FOUND");
pathFound = true;
//DISPLAY PATH (FROM TARGET TO START) BY CHECKING PARENTS
Console.WriteLine("[FULL PATH]");
do
{
Console.WriteLine(current.x + ", " + current.y);
current = current.parent;
} while ((current.x != start.x) && (current.y != start.y));
Console.WriteLine(start.x + ", " + start.y);
break;
}
List<Node> successors = GetSuccessors(current.x, current.y, fields); //GET SUCCESSORS
foreach (Node node in successors)
{
node.parent = current; //SET CURRENT NODE AS PARENT TO RETRIEVE PATH LATER
node.G = current.G + 10; //10 - DISTANCE FROM CURRENT TO ITS SUCCESSOR, current.G DISTANCE FROM CURRENT TO START
node.H = Math.Abs(target.x - node.x) + Math.Abs(target.y - node.y); //HEURISTIC DISTANCE TO TARGET
node.F = node.G + node.H; //NODE FINAL COST
Console.WriteLine(current.x + ", " + current.y + " PARENT | SUCCESSOR: " + node.x + ", " + node.y); //TEST DISPLAY TO CHECK SUCCESSORS CURRENT NODE PRODUCED
if (closedList.FirstOrDefault(l => l.x == node.x && l.y == node.y) != null) //IF SUCCESSOR ALREADY EXISTS ON CLOSED LIST
{
Node temp = closedList.FirstOrDefault(l => l.x == node.x && l.y == node.y);
if (node.F < temp.F) //IF NEW PATH TO THIS NODE IS BETTER? (LOWER F = SHORTER PATH)
{
closedList.Remove(temp); //REMOVE OLD NODE
temp.parent = node.parent;
temp.F = node.F;
closedList.Add(temp); //ADD UPDATED NODE
}
}
else
if(openList.FirstOrDefault(l => l.x == node.x && l.y == node.y) != null) //IF SUCCESSOR ALREADY EXISTS ON OPEN LIST
{
Node temp = openList.FirstOrDefault(l => l.x == node.x && l.y == node.y);
if (node.F < temp.F) //IF NEW PATH TO THIS NODE IS BETTER? (LOWER F = SHORTER PATH)
{
openList.Remove(temp); //REMOVE OLD NODE
temp.parent = node.parent;
temp.F = node.F;
openList.Add(temp); //ADD UPDATED NODE
}
}
else
{
openList.Add(node); //ADD SUCCESSOR TO OPEN LIST
}
}
closedList.Add(current); //MARK CURRENT NODE AS CHECKED (NO NEED TO CHECK IT UNTIL BETTER PATH TO THIS NODE IS FOUND)
}
if(!pathFound)
{
Console.WriteLine("PATH NOT FOUND");
}
}
//FIND NODE WITH LOWEST F COST
public static Node MinFNode(List<Node> nodes)
{
Node result = nodes[0];
foreach(Node node in nodes)
{
if (node.F < result.F)
result = node;
}
return result;
}
//GET SUCCESSORS OF CURRENT NODE (ONLY THE ONES WITH "0" VALUE)
public static List<Node> GetSuccessors(int x, int y, int[,] fields)
{
List<Node> Successors = new List<Node>();
if ((x - 1 >= 0) && (fields[x - 1, y]==0))
Successors.Add(new Node(x - 1, y)); //LEFT
if ((x + 1 < fields.GetLength(0)) && (fields[x + 1, y]==0))
Successors.Add(new Node(x + 1, y)); //RIGHT
if ((y - 1 >= 0) && (fields[x, y - 1]==0))
Successors.Add(new Node(x, y - 1)); //UP
if ((y + 1 < fields.GetLength(1)) && (fields[x, y + 1]==0))
Successors.Add(new Node(x, y + 1)); //DOWN
return Successors; //RETURN LIST OF AVAILABLE SUCCESSORS
}
static void Main()
{
int[,] fields = new int[5, 5] //MAP, 1 - OBSTACLE
{
{ 0, 0, 0, 0, 0 },
{ 0, 1, 1, 1, 0 },
{ 0, 1, 1, 1, 0 },
{ 0, 0, 1, 0, 0 },
{ 0, 0, 1, 0, 0 }
};
Node start = new Node(1, 3); //START LOCATION ON MAP
Node target = new Node(4, 4); //TARGET LOCATION ON MAP
FindPath(start.x,start.y,target.x,target.y,fields); //MAIN ALGORITHM
Console.WriteLine("END");
Console.ReadLine();
}
}
}
正如 Ivan 所指出的，您的工作是基于一个错误的假设。在二维数组中，第一个索引是行号，而不是列。这意味着 fields[2,4] 是第二行，第四列......这是 0.
简单修复...将所有 fields 引用的索引切换为 fields[y, x]，您应该更近一步。
Eric 的评论是完全正确的。您应该可以通过一些调试来解决这个问题。单步执行代码并查看实际发生的情况，您将对问题有更深入的了解。由于 VS2015 Community Edition 是免费的，所以没有太多理由不这样做，如果您不是在 Windows 上开发，还有其他 C# IDE 可以让您单步执行代码并检查程序运行时的状态. MonoDevelop 是 Linux 和 Mac 的首选。
我正在尝试在 C# 中制作 4 向 A-star 寻路算法，但无法使其正常工作。在 Main 方法中，我有一个示例 5x5 int 数组映射来设置可以访问哪些字段，哪些不能（0 - 清除字段，1 - 障碍物）。例如，我将 START 点设置为 (1, 3)，将 TARGET 点设置为 (4, 4)，因此我希望路径避开墙壁并继续等等，但事实并非如此。我什至让我的算法显示每个 parent 及其后继者（邻居）。在我的例子中，它显示 (2,4) 作为节点之一，尽管它在 Fields (Map) 中被标记为障碍物，这是怎么发生的？在 GetSuccessors 方法中有明确的声明只包括标记为 0 的那些，但它仍然包括 (2, 4) 点。我不确定 GetSuccessors 或 FindPath（主要算法）是否有问题。
示例地图：
int[,] fields = new int[5, 5] //MAP, 1 - OBSTACLE
{
{ 0, 0, 0, 0, 0 },
{ 0, 1, 1, 1, 0 },
{ 0, 1, 1, 1, 0 },
{ 0, 0, 1, 0, 0 },
{ 0, 0, 1, 0, 0 }
};
示例点：
Node start = new Node(1, 3); //START LOCATION ON MAP
Node target = new Node(4, 4); //TARGET LOCATION ON MAP
生成的路径（从 TARGET 到 START）：
4, 4
3, 4
2, 4
1, 3
完整代码（FindPath 和 GetSuccessors 是主要代码，但我仍然可以用其他方法做错事）：
using System;
using System.Collections.Generic;
using System.Linq;
namespace FoxLib
{
public class Node
{
public Node(int x, int y)
{
this.x = x;
this.y = y;
}
public int x, y; //POSITION ON MAP
public Node parent; //NEEDED TO RETRIEVE PATH LATER
public int G, H, F;
//G - COST FROM START NODE TO THIS NODE
//H - COST FROM THIS NODE TO TARGET (HEURISTIC)
//F - G + H; NODE COST
}
public class Pathfinding
{
public static void FindPath(int startX, int startY, int targetX, int targetY, int[,] fields) //MAIN ALGORITHM
{
bool pathFound=false; //IS PATH AVAILABLE?
Node start = new Node(startX, startY); //STARTING NODE
Node target = new Node(targetX, targetY); //TARGET NODE
start.parent = start;
start.G = 0;
start.H = Math.Abs(target.x - start.x) + Math.Abs(target.y - start.y);
start.F = start.G + start.H;
Node current = new Node(0, 0);
List<Node> openList = new List<Node>(); //NODES WAITING TO BE CHECKED
List<Node> closedList = new List<Node>(); //ALREADY CHECKED NODES
openList.Add(start);
while(openList.Count>0) //DO AS LONG AS THERE ARE STILL NODES TO DISCOVER
{
current = MinFNode(openList); //FIND NODE WITH LOWEST F COST (LOWER=BETTER PATH)
openList.Remove(current); //REMOVE CURRENT NODE FROM QUEUE
if ((current.x==target.x)&&(current.y==target.y)) //TARGET FOUND
{
Console.WriteLine("PATH FOUND");
pathFound = true;
//DISPLAY PATH (FROM TARGET TO START) BY CHECKING PARENTS
Console.WriteLine("[FULL PATH]");
do
{
Console.WriteLine(current.x + ", " + current.y);
current = current.parent;
} while ((current.x != start.x) && (current.y != start.y));
Console.WriteLine(start.x + ", " + start.y);
break;
}
List<Node> successors = GetSuccessors(current.x, current.y, fields); //GET SUCCESSORS
foreach (Node node in successors)
{
node.parent = current; //SET CURRENT NODE AS PARENT TO RETRIEVE PATH LATER
node.G = current.G + 10; //10 - DISTANCE FROM CURRENT TO ITS SUCCESSOR, current.G DISTANCE FROM CURRENT TO START
node.H = Math.Abs(target.x - node.x) + Math.Abs(target.y - node.y); //HEURISTIC DISTANCE TO TARGET
node.F = node.G + node.H; //NODE FINAL COST
Console.WriteLine(current.x + ", " + current.y + " PARENT | SUCCESSOR: " + node.x + ", " + node.y); //TEST DISPLAY TO CHECK SUCCESSORS CURRENT NODE PRODUCED
if (closedList.FirstOrDefault(l => l.x == node.x && l.y == node.y) != null) //IF SUCCESSOR ALREADY EXISTS ON CLOSED LIST
{
Node temp = closedList.FirstOrDefault(l => l.x == node.x && l.y == node.y);
if (node.F < temp.F) //IF NEW PATH TO THIS NODE IS BETTER? (LOWER F = SHORTER PATH)
{
closedList.Remove(temp); //REMOVE OLD NODE
temp.parent = node.parent;
temp.F = node.F;
closedList.Add(temp); //ADD UPDATED NODE
}
}
else
if(openList.FirstOrDefault(l => l.x == node.x && l.y == node.y) != null) //IF SUCCESSOR ALREADY EXISTS ON OPEN LIST
{
Node temp = openList.FirstOrDefault(l => l.x == node.x && l.y == node.y);
if (node.F < temp.F) //IF NEW PATH TO THIS NODE IS BETTER? (LOWER F = SHORTER PATH)
{
openList.Remove(temp); //REMOVE OLD NODE
temp.parent = node.parent;
temp.F = node.F;
openList.Add(temp); //ADD UPDATED NODE
}
}
else
{
openList.Add(node); //ADD SUCCESSOR TO OPEN LIST
}
}
closedList.Add(current); //MARK CURRENT NODE AS CHECKED (NO NEED TO CHECK IT UNTIL BETTER PATH TO THIS NODE IS FOUND)
}
if(!pathFound)
{
Console.WriteLine("PATH NOT FOUND");
}
}
//FIND NODE WITH LOWEST F COST
public static Node MinFNode(List<Node> nodes)
{
Node result = nodes[0];
foreach(Node node in nodes)
{
if (node.F < result.F)
result = node;
}
return result;
}
//GET SUCCESSORS OF CURRENT NODE (ONLY THE ONES WITH "0" VALUE)
public static List<Node> GetSuccessors(int x, int y, int[,] fields)
{
List<Node> Successors = new List<Node>();
if ((x - 1 >= 0) && (fields[x - 1, y]==0))
Successors.Add(new Node(x - 1, y)); //LEFT
if ((x + 1 < fields.GetLength(0)) && (fields[x + 1, y]==0))
Successors.Add(new Node(x + 1, y)); //RIGHT
if ((y - 1 >= 0) && (fields[x, y - 1]==0))
Successors.Add(new Node(x, y - 1)); //UP
if ((y + 1 < fields.GetLength(1)) && (fields[x, y + 1]==0))
Successors.Add(new Node(x, y + 1)); //DOWN
return Successors; //RETURN LIST OF AVAILABLE SUCCESSORS
}
static void Main()
{
int[,] fields = new int[5, 5] //MAP, 1 - OBSTACLE
{
{ 0, 0, 0, 0, 0 },
{ 0, 1, 1, 1, 0 },
{ 0, 1, 1, 1, 0 },
{ 0, 0, 1, 0, 0 },
{ 0, 0, 1, 0, 0 }
};
Node start = new Node(1, 3); //START LOCATION ON MAP
Node target = new Node(4, 4); //TARGET LOCATION ON MAP
FindPath(start.x,start.y,target.x,target.y,fields); //MAIN ALGORITHM
Console.WriteLine("END");
Console.ReadLine();
}
}
}
正如 Ivan 所指出的，您的工作是基于一个错误的假设。在二维数组中，第一个索引是行号，而不是列。这意味着 fields[2,4] 是第二行，第四列......这是 0.
简单修复...将所有 fields 引用的索引切换为 fields[y, x]，您应该更近一步。
Eric 的评论是完全正确的。您应该可以通过一些调试来解决这个问题。单步执行代码并查看实际发生的情况，您将对问题有更深入的了解。由于 VS2015 Community Edition 是免费的，所以没有太多理由不这样做，如果您不是在 Windows 上开发，还有其他 C# IDE 可以让您单步执行代码并检查程序运行时的状态. MonoDevelop 是 Linux 和 Mac 的首选。