我正在尝试以有序的方式管理寻路脚本的坐标列表

Question

我想做的是剪掉寻路过程中使用的点列表的所有不必要的索引，并将使用的点按顺序排列。 在我运行的模拟器中，生物只能向左、向右、向上和向下行走，因此寻路不能使用对角线移动。 （下面的图片有助于我所说的内容。）

我的意思是： 当寻路开始时我可以访问起点。我想要一个具有清晰的到达终点的有序路径的列表。例如：如果我的列表从点 0,0 到 3,4，它看起来像

[(0,0), (1,0), (1,1), (2,1), (2,2), (2,3), (3,3), (3,4)]

如果之前一切都搞砸了，就像：

[(0,0),  (2,2), (1,0), (1,1), (2,3), (3,3), (2,1), (2,3), (3,4), (3,5), (3,6), (2,4)]

注意：在固定坐标中，所有坐标都是彼此相邻的。

我在寻路中使用了随机，所以它们都是不同的，但这里是通过重复删除器运行后的点列表的示例。

[(6, 7), (6, 6), (5, 6), (2, 6), (1, 6), (3, 4), (1, 5), (2, 5), (3, 6), (4, 6), (0, 4), (0, 5), (0, 7), (0, 6), (1, 4), (2, 3), (1, 3), (2, 4), (0, 3), (4, 4), (4, 3), (4, 2), (4, 1), (3, 1), (3, 0), (2, 0), (1, 0), (0, 0)]

这是我的控制台的图片： 1 代表寻路示例中使用的点，“-”什么也没有，目标是 0,0。绿色代表我想保留的点，红色圈出不重要、应该销毁的点。灰色代表寻路必须绕过的墙壁。起点是 7,7 或右下角。

我试图使用这个函数来告诉你一个坐标是否与另一个坐标相邻，我并不排除它的有用性。在解决方案中，类似的东西可能会被用来将正确的点拼在一起。

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)

Answer 1

您在这里寻找的是“广度优先搜索”。你从一个起点开始（我假设这里是（0,0））。对于每个点，您都会尝试所有四个方向。如果该新点位于有效点列表中并且是您之前未访问过的点，则您可以将其推入点队列中以进行下一步尝试。

这个算法的好处是，在开始查看 2 步之外的点之前，您先查看所有 1 步之外的点，等等。因此，当您访问一个点时，您知道它是最短路径到那时。

pts = [(6, 7), (6, 6), (5, 6), (2, 6), (1, 6), (3, 4), (1, 5), (2, 5), (3, 6), (4, 6), (0, 4), (0, 5), (0, 7), (0, 6), (1, 4), (2, 3), (1, 3), (2, 4), (0, 3), (4, 4), (4, 3), (4, 2), (4, 1), (3, 1), (3, 0), (2, 0), (1, 0), (0, 0)]

dirs = [(1,0),(0,1),(-1,0),(0,-1)]

# Choose a starting point.

seen = set()
start = pts.pop()
pending = [(start,[start])]
while pending:
    (x,y),path = pending.pop(0)
    seen.add( (x,y))
    if (x,y) == pts[0]:
        print( path )
        break

    for dx,dy in dirs:
        x0 = x+dx
        y0 = y+dy
        if (x0,y0) in pts and (x0,y0) not in seen:
            pending.append( ((x0,y0),path+[(x0,y0)]) )

输出：

[(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (4, 1), (4, 2), (4, 3), (4, 4), (3, 4), (2, 4), (2, 5), (2, 6), (3, 6), (4, 6), (5, 6), (6, 6), (6, 7)]