Алгоритм «Confused Digger» работает слишком медленно, чтобы ускорить его?

Question

У меня есть алгоритм, основанный на алгоритме лабиринта обратной трассировки с удалением некоторых частей, в результате чего это замечательное подземелье. К сожалению, он очень быстро выполняет , что делает практически невозможным заполнение карты с приличным размером. Я действительно не хочу его выкидывать, но я не могу придумать, как ускорить его. Я использую 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) изменяет ячейку в позиции new на карте на пустую ячейку.
2. Посещение должно действительно называться чем-то другим, я просто ... ленив. Я исправлю это позже.
3. Состояние < 300 связано с тем, что 299 ячеек - это самое лучшее, что можно сделать в разумные сроки. (За 299 клеток, он вдруг начинает висеть.)

Answer 1

Я хотел бы предложить следующие улучшения:

• Не поп посетил камеру только потому что вы не на один шаг. Это может привести к голоду: всплывать и снова пытаться, выскакивать ... и т. Д. Вместо этого вы должны выбрать другую ячейку, которую вы посетили в прошлом, и продолжить оттуда. Если это не удается, выбрать другую ...

• Используйте set для отслеживания посещенных клеток: это позволит быстрее

просмотру Количества

• Используйте другую «граница» 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)