带障碍网格节点步数计算方法及A*算法h值适用性咨询

嘿，这个需求我太熟了，来给你好好唠唠～

1. 递归实现的可行性：不推荐！ #

递归理论上能实现，但真的不适合这个场景。你想啊，递归本质是深度优先的遍历，在网格里很容易重复访问同一个节点（比如从A到B，再从B递归回A），不仅效率低到爆炸，网格稍微大一点就会触发栈溢出。而且障碍物的处理也会变得很麻烦，一不小心就会陷入死循环或者漏算可达节点。所以递归可以用来理解思路，但实际开发绝对是绕开的选择。

2. 最优实现：广度优先搜索（BFS） #

这才是解决这类问题的标准答案！因为网格是无权图（每走一步代价都是1），BFS天生就能找出从起点到所有可达节点的最短路径，而且一次性就能算出所有节点的步数，完美匹配你的需求。具体步骤大概是这样：

• 先搞一个和网格一样大的步数矩阵，初始值全设为-1（代表不可达），把起点的步数设为0。
• 准备一个队列，把起点坐标先放进去。
• 开始循环处理队列：每次取出队首的节点，检查它上下左右四个邻居。如果邻居在网格范围内、不是障碍物、而且还没被计算过（步数是-1），就把邻居的步数设为当前节点步数+1，然后把邻居放进队列。
• 等队列空了，步数矩阵就填完了，每个可达节点的数值就是到起点的最短步数。

如果你的网格特别大，或者需要频繁计算不同起点的步数，还可以优化：比如静态网格的话，提前预计算所有节点的步数矩阵，之后直接查表就行；如果是动态网格（障碍物会变），那每次用BFS重新算也很快，毕竟BFS的时间复杂度是O(M*N)，M和N是网格的行列数，一般都能接受。

3. 能不能当A*的h cost？分情况！ #

首先得明确A*的h cost要求：必须是可采纳的，也就是h(n)不能大于节点n到终点的实际最短路径长度。

• 如果你的步数是「从固定起点到所有节点的距离」，那肯定不能直接当任意终点的h cost，因为这和终点没关系啊。
• 但如果是「从终点到所有节点的最短步数」（也就是把终点当起点跑一遍BFS得到的结果），那这个h cost简直完美！因为它完全等于实际最短路径长度，满足可采纳性，甚至是最优的启发函数——此时A*会直接走最短路径，效率拉满。

当然，要是你不想每次针对终点都跑一遍BFS，也可以用曼哈顿距离、切比雪夫距离这类估计值当h cost，但这些都是近似值，而你说的精确步数是更优的选择，代价就是需要额外的计算或者预存储。

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