Правило левой руки в The Farmer Was Replaced

Правило левой руки в The Farmer Was Replaced

Когда я впервые решил лабиринт TFWR, я, не задумываясь, потянулся к DFS. Но когда я попытался объяснить игру менее опытному программисту, я понял, что DFS тихо предполагает, что вы знакомы с рекурсией, наборами, посещенными состояниями… не совсем «сначала развлечение».

Итак, я наконец сосредоточился на классическом левом обходе лабиринта, о котором постоянно упоминают руководства TFWR. И впервые в жизни я действительно закодировал его.

Четыре ситуации (рисунок 1)

Идея проста: держите левую руку на стене.

➜Стена слева, вперед открыто -> идем вперед.
☛Влево и вперед заблокировано, вправо открыто → поверните направо.
➽Все заблокировано, кроме пути назад -> разворачиваемся.
➳Самый странный случай: слева нет стены -> вы только что прошли вперед и нашли ответвление слева. Чтобы «восстановить контакт» со стеной, поворачиваем налево и заходим в этот проход.

Теперь самое приятное: все четыре случая объединяются в одну крошечную процедуру:
ᐉОдин раз поворачиваем налево, потом, пока вперед нельзя, крутимся направо.

Вот и все.

Рассмотрим инструменты для этой задачи.

d = [East, North, West, South]

Направления от нулевой точки против часовой стрелки. В production, пожалуйста, не используйте однобуквенные имена.

dc = 0
dc = (dc + 1) % 4
dc = (dc - 1) % 4

Начальное направление - East. +1 - против часовой стрелки, -1 - по часовой. Спасибо Гвидо ван Россуму: % 4 всегда дает числа от 0 до 3 включительно. В C++ это немного менее очевидно.

Все вместе сейчас

d = [East, North, West, South]

# black magic to conjure the maze
plant(Entities.Bush)
substance = get_world_size() * 2**(num_unlocked(Unlocks.Mazes) - 1)
use_item(Items.Weird_Substance, substance)

dc = 0
while get_entity_type() != Entities.Treasure:
  dc = (dc + 1) % 4
  while not can_move(d[dc]):
    dc = (dc - 1) % 4
  move(d[dc])

harvest()