可视化寻路算法

Question

我在 pygame 中做了一个寻路可视化工具，我差不多完成了，但是还有一件事我不喜欢它的算法部分，那就是当你按下可视化算法按钮时它以黄色显示最短路径，以浅蓝色显示算法访问过的所有节点，但它会立即向您显示，我希望它逐步为节点着色以实际达到可视化效果（就像这里https://clementmihailescu.github.io/Pathfinding-Visualizer/#), 我试图在函数中编写一些代码，看起来它会按预期工作但没有，这是代码：

# Breadth First Search Algorithm
def bfs(graph, start, goal):
    explored = []

    # Queue for traversing the
    # graph in the BFS
    queue = [[start]]

    # If the desired node is
    # reached
    if start == goal:
        return

    # Loop to traverse the graph
    # with the help of the queue

    while queue:
        path = queue.pop(0)
        node = path[-1]
        y, x = node
        # Codition to check if the
        # current node is not visited

        if node not in explored and nodes_rows[x][y].color is not BLACK:

            nodes_rows[x][y].color = LIGHT_BLUE
            neighbours = graph[node]

            # Loop to iterate over the
            # neighbours of the node
            for neighbour in neighbours:
                new_path = list(path)
                new_path.append(neighbour)
                queue.append(new_path)

                # Condition to check if the
                # neighbour node is the goal
                if neighbour == goal:
                    new_path.remove(start)
                    new_path.remove(goal)
                    return new_path

            explored.append(node)

    return None

nodes_rows[x][y].color == color_name 是负责为网格上的节点着色的代码，由字典表示（我提供它是为了让您更容易理解着色在我的程序中的一般工作方式).该实现的问题是，当我在 if 语句中添加着色部分来为所有邻居着色时，它会立即在网格上执行它，而不会显示一种逐节点显示着色过程的动画，我的问题是我可以做它因此每次迭代都为它们着色，而不是通过向这段代码中添加一些东西而不是编写新代码来一次着色，如果我确实需要编写一个新代码，说明是什么，我该怎么做？

这就是我所说的像现在一样一次性着色的意思：

https://cdn.discordapp.com/attachments/772816508015083552/832303260911272046/PowerPoint_-_1_2021-04-15_20-13-35_Trim.mp4

编辑：

try:
    while True:
        if not ticks or pygame.time.get_ticks() - ticks >= 500:
           ticks = pygame.time.get_ticks()
           nodes = next(algorithm)
           if nodes_rows[nodes[-1][1]][nodes[-1][0]].color != BLUE:
              nodes_rows[nodes[-1][1]][nodes[-1][0]].color = LIGHT_BLUE
              pygame.display.update()
except StopIteration:
    pass

尝试使用 yield 进行操作，如果我打印它，它会按预期每半秒产生一个列表，最后有一个新探索的节点，但它会在等待我尝试播放的滴答总数后立即更新所有内容缩进 display.update() 但也没有用我什至不知道此时该做什么

感谢所有为帮助做出贡献的人 <3

Answer 1

我认为问题在于您没有更新 while queue 循环中的 canvas。

该程序将执行您的 bfs 算法，然后它会更新 canvas。

老实说，我不经常使用 pygame，但我认为要强制 canvas 重新绘制，您需要在 while 循环中插入一个 pygame.display.update()。

Answer 2

根据上面的评论，这里有一个简单的生成器示例，可以帮助您理解这个想法。

def counter(x):
    for i in range(x):
        yield i
c = counter(3)

In: next(c)
Out: 0
In: next(c)
Out: 1
In: next(c)
Out: 2

发生的事情是，每次调用 next 时，函数都会继续运行直到到达下一个 yield，此时它将 return屈服值。

它还会记住它在何处停止，因此下次调用 next 时，该函数将从它停止的地方继续。

在您的应用程序中，这可用于 yield 已探索位置列表，然后用您喜欢的任何颜色绘制这些位置，调用 next(bfs) 前进并生成下一个列表探索位置，依此类推，直到您当然找到解决方案并且运行没有要产出的项目。

再举一个例子，也许与您正在尝试做的事情更密切相关：

def make_path():
    path = []
    
    i = 0
    while True:
        path.append(i)
        i += 1
        yield path
        
c = make_path()

for _ in range(6):
    print(next(c))

Out: [0]
     [0, 1]
     [0, 1, 2]
     [0, 1, 2, 3]
     [0, 1, 2, 3, 4]
     [0, 1, 2, 3, 4, 5]

Answer 3

Pygame 不是我的强项，但我认为您的项目中缺少一些东西：

1.- 您无法真正控制何时在屏幕上显示颜色。 这可以通过以下方式实现：

pygame.display.update()

文档：https://devdocs.io/pygame/ref/display#pygame.display.update

通常在处理图形时，您会添加一种颜色，然后当您看到下一个屏幕绘画更新时，您必须做的是强制绘画以便您可以安全地设置动画。

2.- 默认情况下不执行着色动画。 我不禁在您最初的问题中注意到了这一点：“它会立即在网格上完成，而不会显示一种逐个节点显示着色过程的动画”。如果你想要一个像上面链接的例子（Pathfinding visualizer）那样的动画，恐怕你必须手动完成。尝试创建一个带有白色方块的测试，并开始在插值颜色内绘制不断增长的圆圈，直到到达墙壁并绘制整个方块。这应该类似于您要完成的任务。

3.- 或许您应该在为 canvas. 设置动画时添加一些停顿硬件的刷新率比人眼快得多。要正确查看着色动画，您应该在插值颜色时尝试添加执行停止。

nodes_rows[x][y].color = Color(r, g, b)  # Start with a color and interpolate incrementing or decrementing r, g and b until your reach a final color.

pygame.display.update()  # Update your screen

pygame.time.wait(1000)  # In milliseconds, add some time wait so screen can be painted, if time is long enough perhaps screen updates meanwhile and you do not need to update the screen.

4.-（可选）平行绘画：使用线程。 如果这不适合您，请添加线程。正如我之前所说，pygame 不是我的强项，但可以考虑添加线程来为每个正方形颜色设置动画。我在这里找到了一个 post 解释。

using threading in pygame

希望对您有所帮助，祝您编码愉快！ :D

可视化寻路算法

Visualize Pathfinding Algorithm

python

algorithm

grid

pygame

path-finding