"Confused Digger" 算法 运行 太慢了，有什么办法可以加快速度吗？
"Confused Digger" algorithm running too slow, any way to speed it up?
我有一个基于回溯迷宫算法的算法，删除了一些部分，从而产生了这个美妙的地牢。不幸的是，它运行 非常慢 这使得它几乎不可能填充一个适当大小的地图。我真的不想扔掉它，但我想不出有什么办法可以加快它的速度。我正在使用 Python，所以我知道这是我的问题的一部分，但我还没有完全准备好扔掉我的 roguelike 的整个现有代码库，它现在运行得足够快。这是目前的代码：
start = (random.randint(0, self.width), random.randint(0, self.height))
self.dungeon['up_stairs'] = start
visited = [start]
while len(visited) < 300:
current = visited[-1]
apos = random.choice([(1, 0), (0, 1), (0, -1), (-1, 0)])
new = utils.tuple_add(current, apos)
if not new in visited and self.on_map(new):
self.place_cell(new, is_wall=False)
visited.append(new)
else:
visited.pop()
[编辑]
- 为了回答评论中的一些问题，place_cell 根据位置参数 is_wall 在提供的位置元组中创建一堵墙或一个空单元格。因此，例如，在上面的代码中，
self.place_cell(new, is_wall=False) 调用将地图上新位置的单元格更改为空单元格。
- Visited 真的应该叫别的名字，我只是...那样懒。我可能稍后会修复它。
< 300条件是因为299个单元格是它在合理的时间范围内最多可以绘制的。 （超过299格，突然开始挂了。）
我建议进行以下改进：
不要仅仅因为一步失败就弹出访问过的单元格。这可能会导致饥饿：弹出并再次尝试，弹出......等等。您应该选择您过去访问过的另一个单元格，然后从那里继续。如果失败，再选一个...
使用 set 来跟踪访问过的单元格：这将允许更快的查找
使用另一个 "frontier" set 来跟踪哪些已访问的单元格仍然有未访问的邻居
当一个小区被访问时，随机检查所有邻居是否未被访问。第一个将是您的下一次访问。但是，如果所有这些都被访问过（或在网格之外），则从边界集中选择一个随机单元格。
这是建议的代码：
start = (random.randint(0, self.width-1), random.randint(0, self.height-1))
self.dungeon['up_stairs'] = start
current = start
frontier = set()
visited = set([start])
while len(visited) < 400:
frontier.add(current)
self.place_cell(current, is_wall=False)
found = False
while not found:
choices = [(1, 0), (0, 1), (0, -1), (-1, 0)]
random.shuffle(choices)
for apos in choices:
new = utils.tuple_add(current, apos)
if not new in visited and self.on_map(new):
found = True
break
if not found:
# we can remove this cell from frontier as it is
# completely surrounded by visited cells
frontier.discard(current)
# pick a random other one to start from
current = random.sample(frontier, 1)[0]
current = new
visited.add(current)
我有一个基于回溯迷宫算法的算法，删除了一些部分，从而产生了这个美妙的地牢。不幸的是，它运行 非常慢 这使得它几乎不可能填充一个适当大小的地图。我真的不想扔掉它，但我想不出有什么办法可以加快它的速度。我正在使用 Python，所以我知道这是我的问题的一部分，但我还没有完全准备好扔掉我的 roguelike 的整个现有代码库，它现在运行得足够快。这是目前的代码：
start = (random.randint(0, self.width), random.randint(0, self.height))
self.dungeon['up_stairs'] = start
visited = [start]
while len(visited) < 300:
current = visited[-1]
apos = random.choice([(1, 0), (0, 1), (0, -1), (-1, 0)])
new = utils.tuple_add(current, apos)
if not new in visited and self.on_map(new):
self.place_cell(new, is_wall=False)
visited.append(new)
else:
visited.pop()
[编辑]
- 为了回答评论中的一些问题，place_cell 根据位置参数 is_wall 在提供的位置元组中创建一堵墙或一个空单元格。因此，例如，在上面的代码中，
self.place_cell(new, is_wall=False)调用将地图上新位置的单元格更改为空单元格。 - Visited 真的应该叫别的名字，我只是...那样懒。我可能稍后会修复它。
< 300条件是因为299个单元格是它在合理的时间范围内最多可以绘制的。 （超过299格，突然开始挂了。）
我建议进行以下改进：
不要仅仅因为一步失败就弹出访问过的单元格。这可能会导致饥饿：弹出并再次尝试，弹出......等等。您应该选择您过去访问过的另一个单元格，然后从那里继续。如果失败，再选一个...
使用
set来跟踪访问过的单元格：这将允许更快的查找使用另一个 "frontier"
set来跟踪哪些已访问的单元格仍然有未访问的邻居当一个小区被访问时，随机检查所有邻居是否未被访问。第一个将是您的下一次访问。但是，如果所有这些都被访问过（或在网格之外），则从边界集中选择一个随机单元格。
这是建议的代码：
start = (random.randint(0, self.width-1), random.randint(0, self.height-1))
self.dungeon['up_stairs'] = start
current = start
frontier = set()
visited = set([start])
while len(visited) < 400:
frontier.add(current)
self.place_cell(current, is_wall=False)
found = False
while not found:
choices = [(1, 0), (0, 1), (0, -1), (-1, 0)]
random.shuffle(choices)
for apos in choices:
new = utils.tuple_add(current, apos)
if not new in visited and self.on_map(new):
found = True
break
if not found:
# we can remove this cell from frontier as it is
# completely surrounded by visited cells
frontier.discard(current)
# pick a random other one to start from
current = random.sample(frontier, 1)[0]
current = new
visited.add(current)