ТФВР. Лабиринт

ТФВР. Лабиринт

Давайте подумаем о задаче лабиринта в игре The Farmer Was Replaced.

Прежде всего, формализуем задачу. У нас есть
𝑛×𝑛-лабиринт, где n = get_world_size(). Наша текущая позиция — (get_pos_x(), get_pos_y()). Дрон двигается командами move(East|North|West|South). Клад можно обнаружить по условию get_entity_type() == Entities.Treasure. Информацию о проходимости соседних клеток получаем через can_move(East|North|West|South).

Честно говоря, я понятия не имею, почему так популярен подход «правая рука» или «левая рука». Я начал с DFS (поиск в глубину) и хочу объяснить этот подход в посте.

Кажется, довольно популярно начинать с этих «ручных» подходов. Но они терпят неудачу, когда вы пытаетесь заработать больше денег на охоте за сокровищами. По правилам, приз удваивается, если вместо сбора вы используете на сокровище странное вещество. В этом случае вы повторно используете лабиринт, и сокровище перескакивает в какое-то другое место. Вы можете сделать это 30 раз (и должны, если хотите иметь эффективную ферму). Также, когда сокровище прыгает, некоторые стены лабиринта исчезают. Это исчезновение имеет два последствия. Во-первых, «ручные» подходы больше не работают. С другой стороны, лабиринт упрощается, и, если вы используете соответствующий алгоритм, ваш дрон находит сокровище все быстрее и быстрее.

В этой теме я хочу показать простейший возможный код DFS, который не опирается на «строгую древовидную структуру» лабиринта.

Давайте перейдем к коду. DIRECTIONS — массив направлений для move(). visited — множество уже посещенных клеток. OPPOSITE — словарь противоположных направлений.

def go_best(d1, d2, l1, l2):
  d, l = d1, l1
  if l2 < l1:
    d, l = d2, l2
  for _ in range(l):
    move(d)


def nav(x2, y2):
  n = get_world_size()
  x1, y1 = get_pos_x(), get_pos_y()
  go_best(East, West, (x2 - x1)%n, (x1 - x2)%n)
  go_best(North, South, (y2 - y1)%n, (y1 - y2)%n)

def apply_proper_substance():
  substance = get_world_size() * 2**(num_unlocked(Unlocks.Mazes) - 1)
  use_item(Items.Weird_Substance, substance)


set_world_size(8)
nav(3, 3)
plant(Entities.Bush)
apply_proper_substance()

DIRECTIONS=[East, North, South, West]
OPPOSITE={East:West, West:East, North:South, South:North}

def dfs(visited):
    if (get_pos_x(), get_pos_y()) in visited:
        return

    visited.add((get_pos_x(), get_pos_y()))
    if get_entity_type() == Entities.Treasure:
        harvest()

    for dir_to_move in DIRECTIONS:
        if can_move(dir_to_move):
            move(dir_to_move)

            dfs(visited)

            move(OPPOSITE[dir_to_move])

visited = set()
dfs(visited)

while True:
  pass

Код максимально прост и поэтому содержит несколько очевидных проблем:

проблема: в этом алгоритме дрон все время «трясется» вперед-назад
причина: он проверяет свою текущую позицию в посещенной, поэтому ему действительно нужно перейти в ячейку, чтобы проверить ее
как исправить: написать функцию «проекции», которая вычисляет позицию дрона после шага и проверяет ее в visited

проблема: этот код немедленно собирает сокровище
причина: я хотел, чтобы этот код был максимально простым
как исправить: добавить логику, чтобы прервать рекурсию, когда дрон находится над сокровищем, и создать внешний цикл для обновления лабиринта