寻路脚本坐标列表优化：剔除冗余点并生成有序相邻路径

在仅支持上下左右四向移动（无斜向）的模拟器寻路场景里，我们拿到的寻路坐标列表不仅顺序混乱，还包含大量冗余点。需要实现的目标是：从已知起点出发，剔除无关坐标，生成两两相邻的有序路径列表，最终形成从起点到终点的完整路径。

举个直观的例子：

• 原混乱列表：[(0,0), (2,2), (1,0), ...]
• 优化后路径：[(0,0), (1,0), (1,1), ...]

可用资源 #

• 去重后的坐标集合
• 用于判断两个坐标是否相邻的Python函数：

def PointIsNextToPoint(point1, point2):
    x1 = point1[0]
    y1 = point1[1]
    x2 = point2[0]
    y2 = point2[1]
    return (abs(x1 - x2) == 1 and y1 == y2) or (abs(y1 - y2) == 1 and x1 == x2)

• 可视化参考：绿色点为需保留的有效路径点，红色点是冗余点，灰色代表障碍物；示例中起点为(7,7)，终点为(0,0)

解决方案 #

我们可以用**广度优先搜索(BFS)**来构建符合要求的有序路径，BFS能保证路径中每个点都与下一个点相邻，且不会引入冗余点。具体实现代码如下：

def optimize_path(start_point, end_point, all_points):
    point_set = set(all_points)
    # 校验起点终点有效性
    if start_point not in point_set or end_point not in point_set:
        return []
    
    # BFS队列：元素为(当前坐标, 已构建路径)
    queue = [(start_point, [start_point])]
    visited = {start_point}
    
    while queue:
        current, path = queue.pop(0)
        if current == end_point:
            return path
        
        # 尝试四个方向的移动
        for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
            next_point = (current[0] + dx, current[1] + dy)
            if next_point in point_set and next_point not in visited:
                visited.add(next_point)
                queue.append((next_point, path + [next_point]))
    
    # 无法找到有效路径时返回空列表
    return []

代码说明 #

1. 先将输入的坐标列表转为集合，提升查找效率
2. 校验起点和终点是否存在于有效坐标集合中，避免无效输入导致的错误
3. 通过BFS逐层探索相邻点，每一步只添加符合条件的相邻点到路径中，确保路径的有序性和相邻性
4. 一旦到达终点，立即返回当前路径，这就是剔除冗余后的最优有序路径

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