AStar网格算法是否仅支持正方形网格？矩形网格启发式方法咨询

嘿，刚好我在UE4里用C++做过不同尺寸的网格路径规划，来给你捋清楚这个问题：

1. A*是否仅适用于正方形网格？ #

当然不是！A本质是基于图的搜索算法，只要你能把任意网格（不管是矩形、六边形，甚至是不规则的凸多边形网格）抽象成「节点+边」的结构，给每个节点定义好可到达的邻居节点，以及对应的移动代价，A就能正常工作。

在UE4中，你完全可以自定义矩形网格的尺寸——比如每个格子的宽度是200cm、高度是100cm，只要在初始化网格时，给每个节点正确计算相邻节点的世界坐标和移动代价就行，根本不用局限于正方形。

2. 矩形网格的启发式处理方法 #

核心是修改A的启发函数（h值计算）。正方形网格里常用的曼哈顿/欧几里得距离，直接套用到矩形网格会出问题——因为矩形格子的宽高不等，普通距离会高估或低估实际移动代价，破坏A的最优性。

针对四方向移动（上下左右）的启发式 #

这时候用缩放版曼哈顿距离最稳妥，能保证启发函数的「可采纳性」（不会高估实际代价，确保A*找到最短路径）。计算方式如下：
假设每个矩形格子的宽度为GridWidth（X轴方向单位长度），高度为GridHeight（Y轴方向单位长度），当前节点网格坐标为(curX, curY)，目标节点为(targetX, targetY)：

// 计算网格坐标的差值
int dx = abs(targetX - curX);
int dy = abs(targetY - curY);
// 缩放后的曼哈顿距离作为h值
float h = dx * GridWidth + dy * GridHeight;

这个h值代表沿着网格轴移动到目标的最小实际代价，完全符合A*对启发函数的要求。

针对八方向移动（含对角线）的启发式 #

如果允许斜向移动，那要考虑对角线的实际移动代价（勾股定理计算：sqrt(GridWidth² + GridHeight²)）。这时候可以用加权切比雪夫距离来计算h值，同样保证可采纳性：

int dx = abs(targetX - curX);
int dy = abs(targetY - curY);
float diagonalCost = sqrt(GridWidth * GridWidth + GridHeight * GridHeight);
// 优先走对角线，剩下的走轴向
float h = max(dx, dy) * diagonalCost + abs(dx - dy) * min(GridWidth, GridHeight);

或者更简单的方式，直接用欧几里得距离作为h值（因为欧几里得距离是两点间的最短直线距离，肯定不会高估实际移动代价）：

float worldCurX = curX * GridWidth;
float worldCurY = curY * GridHeight;
float worldTargetX = targetX * GridWidth;
float worldTargetY = targetY * GridHeight;
float h = sqrt(pow(worldTargetX - worldCurX, 2) + pow(worldTargetY - worldCurY, 2));

3. UE4中的实践小提示 #

• 自定义AStarNode结构体时，要存储网格坐标和世界坐标，方便快速计算移动代价和启发值；
• 生成网格邻居时，要注意边界判断（比如边缘节点没有左/上邻居），同时给每个邻居节点设置对应的移动代价（横轴邻居代价为GridWidth，纵轴为GridHeight，对角线为斜边值）；
• 确保启发函数的h值始终小于等于实际移动代价，这是A*能找到最优路径的关键。

内容的提问来源于stack exchange，提问作者Reid Paulhus