AStar算法学习与简单优化
·
A*算法介绍
A*算法是一种高效的启发式搜索算法，广泛应用于路径查找、游戏AI和机器人导航等领域。它结合了广度优先搜索的全面性和贪心算法的效率，通过启发式函数引导搜索方向，从而在大型图中快速找到最优路径。
1. 算法原理
A*算法的核心是使用一个评估函数 f(n) 来为每个节点分配优先级。该函数定义为：
- f(n) = g(n) + h(n) 其中：
- g(n) 表示从起点到节点 n 的实际成本（例如距离或时间）。
- h(n) 表示从节点 n 到目标点的估计成本（启发式函数）。
常见的启发式函数包括欧几里得距离或曼哈顿距离。
算法维护两个列表：
- 开放列表（Open List）：存储待探索的节点，优先处理 f(n) 最小的节点。
- 关闭列表（Closed List）：存储已探索的节点，避免重复处理。
2. 算法步骤
A*算法的执行流程如下：
- 初始化：将起点加入开放列表，设置 g(start) = 0，f(start) = h(start)。
- 循环处理：
- 从开放列表中选择 f(n) 最小的节点 n。
- 如果 n 是目标点，则重构路径并结束。
- 否则，将 n 移到关闭列表。
- 遍历 n 的所有邻居节点：
- 如果邻居在关闭列表中，跳过。
- 计算临时 g 值：g_temp = g(n) + cost(n, neighbor)。（一般图相邻的节点cost都为1，只有权值不同的图cost才会不同）
- 如果 g_temp< g(neighbor)（或邻居不在开放列表中），更新邻居的 g 值和 f 值，并将邻居加入开放列表。
- 路径重构：从目标点回溯到起点，使用父节点指针生成路径。
C#代码
实现的AStar类包含两个工具类（实现优先队列的类FQuene和队列中的节点类FQueneItem）和一个寻路函数。优先队列是用链表构成的，f也就是代码里的cost小的放链首，cost相同则h小的放链首，估计成本使用曼哈顿距离。传入的Action使用来涂色的，不涉及算法。Mode表示不同的评估函数，在后面的简单优化会说。
public class AStar : MonoBehaviour
{
public enum Mode
{
None = 0,
DistMode,
ChaMode,
}
public Mode mode = Mode.None; // Default mode is None
public class FQuene
{
public List<FQueneItem> fQueneItems;
public int top;
public FQuene()
{
fQueneItems = new List<FQueneItem>();
top = -1; // Initialize top to -1 to indicate an empty queue
}
public void CreateItem(int x, int y, Direction dir, int pcost, int fcost, int mode)
{
int ListId = fQueneItems.Count; // Get the current count as the new ListId
FQueneItem item = new FQueneItem(x, y, dir, pcost, fcost, ListId, mode);
if (top < 0)
{
top = item.ListId;
item.SetNextId(-1); // Set NextId to -1 for the first item
}
else
{
if (item.cost < fQueneItems[top].cost || (item.cost == fQueneItems[top].cost && item.hcost < fQueneItems[top].hcost))
{
item.SetNextId(top);
top = item.ListId;
}
else
{
int currentId = top;
while (fQueneItems[currentId].NextId != -1 && item.cost >= fQueneItems[fQueneItems[currentId].NextId].cost)
{
if (item.cost == fQueneItems[fQueneItems[currentId].NextId].cost &&
item.hcost < fQueneItems[fQueneItems[currentId].NextId].hcost)
break; // If costs are equal, prefer the one with lower hcost
currentId = fQueneItems[currentId].NextId;
}
item.SetNextId(fQueneItems[currentId].NextId);
fQueneItems[currentId].SetNextId(item.ListId);
}
}
fQueneItems.Add(item);
}
public FQueneItem Pop()
{
if (top < 0) return null; // Return null if the queue is empty
FQueneItem item = fQueneItems[top];
top = item.NextId; // Move top to the next item
return item;
}
}
public class FQueneItem
{
public int x;
public int y;
public Direction dir;
public int gcost, hcost;
public int ListId;
public int NextId;
public int mode;
public FQueneItem(int x, int y, Direction dir, int gcost, int hcost, int ListId, int mode)
{
this.x = x;
this.y = y;
this.dir = dir;
this.gcost = gcost;
this.hcost = hcost;
this.ListId = ListId;
this.mode = mode;
}
public void SetNextId(int nextId)
{
this.NextId = nextId;
}
public int cost
{
get
{
switch(this.mode)
{
case (int)Mode.DistMode:
return hcost; // Use both costs for distance mode
case (int)Mode.ChaMode:
return hcost - gcost; // Use heuristic cost minus actual cost for challenge mode
default:
return gcost + hcost; // Default to using both costs
}
//return gcost + hcost;
//return hcost;
//return hcost - gcost;
}
}
}
public enum Direction
{
None = -1, // No direction
Up = 0,
Down = 1,
Left = 2,
Right = 3
}
public IEnumerator FindPath(int startX, int startY, int endX, int endY, int[,] map, Action<int, int, Color> action)
{
FQuene openList = new FQuene();
HashSet<(int, int)> closedList = new HashSet<(int, int)>();
openList.CreateItem(startX, startY, Direction.None, 0, 0,(int)mode);
List<Vector2> dir = new List<Vector2>
{
new Vector2(0, 1), // Up
new Vector2(0, -1), // Down
new Vector2(-1, 0), // Left
new Vector2(1, 0) // Right
};
while (true)
{
FQueneItem currentItem = openList.Pop();
if (currentItem == null)
break; // No more items to process
if (currentItem.x == endX && currentItem.y == endY)
{
Debug.Log("Path found");
break; // Path found
}
if (currentItem.x != startX || currentItem.y != startY)
{
action?.Invoke(currentItem.x, currentItem.y, Color.grey);
}
Debug.LogFormat("Processing: ({0}, {1}, {2}, {3}, {4})", currentItem.x, currentItem.y,currentItem.cost, currentItem.hcost, currentItem.gcost);
closedList.Add((currentItem.x, currentItem.y));
// Check neighbors (up, down, left, right)
for (int dirId = 0; dirId <= 3; dirId++)
{
int dx = (int)dir[dirId].x;
int dy = (int)dir[dirId].y;
int neighborX = currentItem.x + dx;
int neighborY = currentItem.y + dy;
if (neighborX < 0 || neighborY < 0 || neighborX >= map.GetLength(1) || neighborY >= map.GetLength(0))
continue; // Out of bounds
if (map[neighborY, neighborX] == 1 || closedList.Contains((neighborX, neighborY)))
continue; // Wall or already processed
int gCost = currentItem.gcost + 1; // Assuming cost is 1 for each step
int hCost = Mathf.Abs(endX - neighborX) + Mathf.Abs(endY - neighborY); // Manhattan distance
openList.CreateItem(neighborX, neighborY, (Direction)dirId, gCost, hCost, (int)mode);
if (neighborX != endX || neighborY != endY)
{
action?.Invoke(neighborX, neighborY, Color.cyan);
}
yield return new WaitForSeconds(0.2f); // Yield to allow Unity to process other events
}
}
yield return null; // No path found
}
}
简单优化
在实际体验了A星算法后，感觉对于有障碍物的地图，原有的评估函数 : f = g + h,效率不是很高，尤其是对于长条的障碍，算法撞墙后甚至会返回，因为在网格图中在以开始和终点为对角的矩形中的节点 f 值都是相同的。（下图中灰色为探索过的节点，天蓝色是开放列表中的节点）
这种情况好像A星撞墙后就失去了方向感，于是我想着加强方向感，直接不用g，f就等于h，就找离终点近的，也就是mode里的DistMode，寻路结果如下
再之后我想用差来评估会不会更好指向性更强些，即f = h - g，结果如下图
可以看见在这种地图中，差或者距离作为评估函数，比和要高效一些，可以再试试其他地图，如下
地图
和评估
距离评估
差评估
不难发现在这种较为复杂的地图中差评估也能比和评估和距离评估好一些。
当然我这里只是举例子，实际情况应该也有和评估较为高效的地图。这里我只是想说评估函数的好坏也能直接影响算法的效率，要根据地图特性选择不同评估函数。
最后要是想再进一步优化可以考虑使用B星算法。
加入社区！打开量化的大门，首批课程上线啦！
更多推荐
6
0- 0
已为社区贡献1条内容
所有评论(0)