Python 回溯迷宫真慢

Question

检查编辑, 我在 youtube 上观看 The Coding Train 时写了一些代码......迷宫回溯生成器。 youtuber在javascript写了代码，我在python写的时候试着看懂代码。看来他不得不改变帧率，因为他的程序太快了，只是为了看到生成部分。当我经过大约 10 个方块后，它已经很慢了。这不可能是硬件问题，我有一个 i5-4690K CPU 和一个很好匹配的 GPU，它一定是代码中的问题！但是我找不到它是什么。

我重新看了剧集，以便找出问题所在，但似乎我写的一切都很好。

from tkinter import *
import math
import random
import time

# initialization canvas
root = Tk()
canvas = Canvas(root, width=400, height=400, bg="#333333")
canvas.pack()

# some global variables
w = 40;
cols = math.floor(int(canvas["width"])/w)
rows = math.floor(int(canvas["height"])/w)
grid = []
current = None

class Cell():
    line_color = "#AAAAAA"
    visited_color = "green"
    visited = False
    rectangle = None

    def __init__(self, i, j):
        self.i = i
        self.j = j
        self.wall = [True, True, True, True] # top , right, bottom, left

    def __repr__(self):
        return "({}, {})".format(self.i, self.j)

    def draw_lines(self):
        x = self.i*w
        y = self.j*w

        if self.visited :
            self.rectangle = canvas.create_rectangle(x, y, x+w, y+w, fill="purple", outline="")
            canvas.update()

        if self.wall[0]:
            canvas.create_line(x, y, x+w, y, fill=self.line_color)
        else:
            canvas.create_line(x, y, x+w, y, fill="purple")
        if self.wall[1]:
            canvas.create_line(x+w, y, x+w, y+w, fill=self.line_color)
        else:
            canvas.create_line(x+w, y, x+w, y+w, fill="purple")
        if self.wall[2]:
            canvas.create_line(x, y+w, x+w, y+w, fill=self.line_color)
        else:
            canvas.create_line(x, y+w, x+w, y+w, fill="purple")
        if self.wall[3]:
            canvas.create_line(x, y, x, y+w, fill=self.line_color)
        else:
            canvas.create_line(x, y, x, y+w, fill="purple")

    def checkNeighbors(self):
        neighbors = []
        top = None
        bottom = None
        left = None
        right = None
        if index(self.i, self.j-1) != -1:
            top = grid[index(self.i, self.j-1)]

        if index(self.i, self.j+1) != -1:
            bottom = grid[index(self.i, self.j+1)]

        if index(self.i-1, self.j) != -1:
            left = grid[index(self.i-1, self.j)]

        if index(self.i+1, self.j) != -1:
            right = grid[index(self.i+1, self.j)]

        if top is not None and top.visited is False:
            neighbors.append(top)
        if right is not None and right.visited is False:
            neighbors.append(right)
        if bottom is not None and bottom.visited is False:
            neighbors.append(bottom)
        if left is not None and left.visited is False:
            neighbors.append(left)

        if len(neighbors) > 0:
            r = random.randint(0, len(neighbors)-1)
            return neighbors[r]
        else:
            return None

def removeWalls(a, b):
    x = a.i - b.i
    y = a.j - b.j

    if x != 0:
        if x == 1:
            a.wall[3] = False
            b.wall[1] = False
        else:
            a.wall[1] = False
            b.wall[3] = False

    if y != 0:
        if y == 1:
            a.wall[0] = False
            b.wall[2] = False
        else:
            a.wall[2] = False
            b.wall[0] = False

def index(i, j):
    if j < 0 or j > rows - 1 or i < 0 or i > cols - 1:
        return -1
    return j + i * cols

def setup():
    global current
    for i in range(rows):
        for j in range(cols):
            cell = Cell(i, j)
            grid.append(cell)
    current = grid[0]

next_one = None
def draw():
    global current
    global next_one
    stack = []
    almost = False
    while True:
        current.visited = True
        for cell in grid:
            cell.draw_lines()
        next_one = current.checkNeighbors()
        if next_one:
            stack.append(current)
            removeWalls(current, next_one)
            current = next_one
        elif len(stack) > 0:
            cell = stack.pop()
            current = cell

for cell in grid:
    print(cell.visited)

setup()
draw()


root.mainloop()

我很抱歉把所有的代码都放上去，但我认为所有这些都与性能有关，没有放任何有用的评论，抱歉我正在努力成为一个更好的程序员并改变它坏习惯

大编辑： 我测试过在完成计算后只绘制迷宫，它只需要不到一秒钟的时间，所以我认为它必须与我正在创建的小部件（线）的数量有关..？我怎样才能最小化小部件，以便我可以看到按照我想要的方式创建的迷宫？

Answer 1

你画线，即使它们没有改变。相反，只绘制更改的单元格。

此外，你有无限循环。即使堆栈不再包含更多元素，您也不会停止。在这里你应该打破循环。

这里有一个改进：

def draw():
    for cell in grid:
        cell.draw_lines()
    global current
    global next_one
    stack = []
    almost = False
    while True:
        current.visited = True
        next_one = current.checkNeighbors()
        if next_one:
            stack.append(current)
            removeWalls(current, next_one)
            current.draw_lines()
            next_one.draw_lines()
            current = next_one
        elif len(stack) > 0:
            cell = stack.pop()
            current = cell
        else:
            break

Python 回溯迷宫真慢

Python backtracking maze really slow

python

maze

recursive-backtracking