3

我有一个基于回溯迷宫算法的算法，其中一些部分被移除，从而产生了这个美妙的地牢。不幸的是，它的运行速度非常慢，这使得几乎不可能填满一张合适大小的地图。我真的不想扔掉它，但我想不出任何方法来加速它。我正在使用 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()

[编辑]

  1. 为了回答评论中的一些问题，place_cell 根据位置参数 is_wall 在提供的位置元组处创建墙或空单元。例如，在上面的代码中，self.place_cell(new, is_wall=False)调用将地图上新位置的单元格更改为空单元格。
  2. 访问真的应该被称为别的东西，我只是......这样懒惰。我以后可能会修复它。
  3. < 300条件是因为 299 个单元格是它在合理的时间范围内最多可以绘制的。（超过 299 个单元，它突然开始挂起。）
4

1 回答 1

2

我建议进行以下改进：

  • 不要仅仅因为你一步失败就弹出一个访问过的单元格。这可能会导致饥饿：弹出并再次尝试，弹出......等等。您应该选择您过去访问过的另一个单元格，然后从那里继续。如果失败，请选择另一个...

  • 使用 aset来跟踪访问的单元格：这将允许更快的查找

  • 使用另一个“边界”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)
于 2017-02-11T00:36:14.483 回答