Bug 算法路径规划实战：从数学建模到 Python 实现

1. 从“撞墙”到“绕行”：Bug算法的直觉理解

想象一下，你被蒙上眼睛，站在一个空旷的房间里，有人告诉你：“向前走十步，就能拿到桌子上的苹果。”你开始径直向前走。走了五步，你的膝盖“砰”地一声撞到了什么东西——是一把椅子。这时候你会怎么做？你肯定不会继续硬着头皮往前撞，而是会伸出手，摸着这把椅子的边缘，小心翼翼地绕着它走，直到你感觉前方没有阻碍了，再重新判断苹果的方向，继续前进。

这个“撞到就绕”的朴素策略，就是Bug算法最核心的思想。在机器人路径规划领域，Bug算法就是这样一种简单、直接、不需要“上帝视角”地图的局部规划方法。它不关心整个房间的布局，只关心“我”现在在哪里，“目标”在哪里，以及“我”眼前有没有障碍物。这种特性让它特别适合用在未知环境探索、实时避障以及计算资源有限的场景里，比如你家里的扫地机器人，或者在一个陌生仓库里穿梭的物流小车。

我刚开始接触路径规划时，总觉得那些需要构建全局地图、计算复杂代价函数的算法（比如A*、Dijkstra）才是“正统”。但后来在实际项目中，尤其是在一些嵌入式设备上，我发现全局地图的构建和更新本身就是个巨大的开销。有时候，机器人只需要完成“从A到B”这个简单任务，环境中的障碍物可能还会移动。这时候，Bug算法的优势就体现出来了：它足够轻量，反应迅速，实现起来也简单。今天，我就想和你一起，把这个算法的数学思想“翻译”成实实在在的Python代码，看看这个“笨办法”到底有多聪明。

2. Bug算法家族：三种绕障策略的深度剖析

别看Bug算法思想简单，它其实是一个“家族”，包含了Bug0、Bug1、Bug2等几个主要成员。它们共享“直线趋近”和“边界跟随”这两个基本动作，但在“何时离开障碍物”这个关键决策上，策略截然不同，这也直接导致了路径效率和计算复杂度的差异。

2.1 Bug0：直觉派的“见缝就钻”

Bug0是最简单的版本，它的策略非常符合我们一开始的直觉：

1. 直线朝目标走。
2. 撞到障碍物？那就贴着障碍物的边绕。
3. 绕的时候，随时检查：我现在能直接朝目标走了吗？如果能，立刻离开障碍物，回到步骤1。

听起来很合理，对吧？但这里有个大坑。我写第一个Bug0版本时，就遇到了机器人“反复横跳”的问题。在一个凹形障碍物面前，机器人绕到某个点，发现和目标点之间没有障碍物了（视线可达），于是它兴冲冲地离开边界，直线前进。结果没走两步，又撞到了同一个凹形障碍物的另一侧，只好再次贴边绕行……如此循环，路径变得非常冗余。

Bug0的数学描述很简单。假设机器人在时刻 t 的位置是 (x_t, y_t)，目标点是 (g_x, g_y)。在直线趋近模式下的移动增量是：

delta_x = sign(g_x - x_t) # sign是符号函数，返回1, 0, -1 delta_y = sign(g_y - y_t) 

下一个位置就是 (x_t + delta_x, y_t + delta_y)。这个 sign 函数保证了机器人每一步都朝着目标方向移动至少一格。

它的计算复杂度是O(n)，n是路径步数。因为它几乎不做“记忆”和“比较”，只关注当下，所以速度最快，但规划的路径往往不是最短的，在复杂障碍物环境下表现不稳定。

2.2 Bug1：保守派的“彻底侦察”

Bug1吸取了Bug0的教训，采取了一种更保守的策略：

1. 直线朝目标走，撞到障碍物（记下这个“撞击点”）。
2. 开始完整地绕障碍物一整圈。在绕圈的过程中，像一个侦察兵一样，默默记下所有边界点中，距离目标点最近的那个点（我们叫它“最近点”）。
3. 绕完一整圈回到最初的“撞击点”后，它不直接离开，而是沿着边界，专门再走到刚才记下的“最近点”。
4. 从这个“最近点”离开障碍物，继续直线前进。

这个策略保证了机器人至少能找到一条绕过当前障碍物的路径，并且是从障碍物周边离目标最近的地方离开的。理论上，这能产生比Bug0更优的路径。我实测下来，在单个大型复杂障碍物面前，Bug1的路径通常确实更短、更合理。

但是，它的代价是时间。Bug1的计算复杂度是O(n²)。为什么？因为绕行一整圈需要遍历障碍物边界点（假设有m个），同时，为了找到“最近点”，在每一步都需要计算当前点到目标点的距离（一次距离计算是O(1)，但需要比较m次）。在最坏情况下，它需要遍历边界点两次（绕一圈+走到最近点）。所以，当障碍物很大、边界很长时，Bug1会显得很慢。

2.3 Bug2：聪明人的“捷径思维”

Bug2引入了一个非常巧妙的概念：参考线。这条参考线就是从起点直接画到目标点的一条虚拟直线。

1. 直线朝目标走，撞到障碍物（记下这个“撞击点”，它也是参考线与障碍物的第一个交点）。
2. 开始贴着障碍物边界绕行。
3. 绕行时，它时刻盯着两个条件：第一，我是否再次碰到了参考线？第二，这次碰到参考线的位置，是否比上次的撞击点更靠近目标？
4. 只有同时满足“碰到参考线”且“更靠近目标”，机器人才会离开障碍物，继续直线前进。否则，就继续绕。

这个策略的精妙之处在于，它利用了一条全局信息（参考线）来指导局部行为。它不需要像Bug1那样绕完整的一圈，只要找到下一个更优的“出口”就撤。这常常能让机器人找到一条非常接近理论最短的路径。

Bug2的数学核心是点到直线的距离判断。假设参考线L的方程由起点 (s_x, s_y) 和终点 (g_x, g_y) 确定。机器人当前位置是 p_current，候选的下一个边界点是 p_new。离开的条件是：distance(p_new, L) < distance(p_current, L) 且 p_new 在参考线上。这里的距离通常指垂直距离或沿着坐标轴方向的可达性判断。

它的计算复杂度介于Bug0和Bug1之间，大致为O(n log n)，因为它需要在绕行过程中持续进行距离比较和条件判断，但避免了完整的环绕。

为了更直观地对比，我把它们的特点总结成了下面这个表格：