我想做的是剪掉寻路过程中使用的点列表的所有不必要的索引,并将使用的点按顺序排列。 在我运行的模拟器中,生物只能向左、向右、向上和向下行走,因此寻路不能使用对角线移动。 (下面的图片有助于我所说的内容。)
我的意思是: 当寻路开始时我可以访问起点。我想要一个具有清晰的到达终点的有序路径的列表。例如:如果我的列表从点 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)
您在这里寻找的是“广度优先搜索”。你从一个起点开始(我假设这里是(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)]