Как найти дорогу в лабиринт

Была ли эта статья полезной?

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

Мало ли когда вам пригодится это знание, но все же уметь выбираться из лабиринта — важная способность.

Учимся находить кратчайший путь через простой двумерный алгоритм на Python

Как именно мы находим выход из лабиринта? Как быстрее всего проехать из точки А в ближайшую пиццерию? Можем ли мы провести игрового персонажа к выходу так, чтобы он не уперся в стену?

Поиск пути – типичная задача программирования, решаемая в самых разных ситуациях. Она известна в основном из навигационных задач и разработки игр. Но, изучив ключевые алгоритмы поиска пути, вы узнаете, что они применимы к более абстрактным задачам оптимизации и построения последовательностей.

В этом руководстве рассмотрен простейший алгоритм поиска пути, основанный на алгоритме Дейкстры. Этот алгоритм также известен под названием поиск по первому наилучшему совпадению, ключевая логика у него общая со многими другими алгоритмами, например, A*, заливка методом наводнения и диаграммы Вороного.

Здесь мы рассмотрим практическое применение этого алгоритма. Вам понадобятся базовые знания программирования и языка Python.

Настройка Python

Весь код к этому посту находится в репозитории path-finding. Его нужно клонировать и переключиться в ветку tutorial_1. Также установите пакет pygame, он понадобится нам для графики.

python3 -m pip install -U pygame
git clone git@github.com:mortoray/path-finding.git
cd path-finding
git checkout path_finding_1

Теперь проверим, все ли сделали правильно:

python3 find-basic.py

Должно появиться окно с клетками, а в клетках – цифры. Теперь можете закрыть это окно. Мы вернемся к нему позже.

Лабиринт

Поиск пути – это продвижение из точки А в точку B. Алгоритм может описывать прогулку человека по парку, движение автомобиля по городу, либо курс персонажа, который преследует вас в игре. Давайте сведем все эти окружения к абстракции, которую назовем «лабиринт».

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

На схеме стартовая клетка обозначена желтым цветом, в ней стоит “0”. Все допустимые шаги обозначены как “1”. Мы должны перейти в зеленую клетку, это наша цель.

Запускаем код

В коде предоставлена функция, создающая за нас простейший лабиринт. Нужно разобраться, как использовать алгоритм поиска пути для генерации гораздо более интересных лабиринтов, но пока давайте просто вызовем функцию create_wall_maze.

import mortoray_path_finding as mpf

maze = mpf.create_wall_maze( 20, 12 )

Мы создали лабиринт размером 20x12. Поле maze.board – это решетка из объектов Cell. Нам нужен способ отобразить наш лабиринт.

finder = mpf.Finder()
finder.set_board(maze.board)
finder.run()

Исходный файл: tutorial_1_1.py

Finder – это утилита, отображающая за нас лабиринт. Серые клетки свободны, то есть, путь может пройти через них. Коричневые клетки – это стены, через них путь пройти не может. В каждой из клеток также записан ноль, это значение Cell.count для данной позиции. Оно пригодится нам при поиске пути.

Измерение расстояния

Поиск пути во многом основан на исходном алгоритме Дейкстры. Существует множество его вариаций, например, алгоритм Флойда-Уоршелла, он же B*. Они действуют по схожему принципу: в них используются списки узлов и подсчитывается расстояние. Для разных ситуаций можно сочетать различные приемы.

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

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

1. Получаем из списка открытых узлов тот узел, от которого нас отделяет наименьшее расстояние  

2. Вычисляем расстояние до каждого из соседних узлов

3. Если расстояние до соседнего узла меньше, чем вычисленное – то добавляем этот узел в список открытых

Термины

Для начала рассмотрим некоторые термины, поскольку они могут быть вам неизвестны.

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

Узлы, которые можно соединить, проложив между ними путь, являются соседними. Путь между узлами-соседями характеризуется расстоянием, для которого есть более общий термин «стоимость». В теории графов путь называют «ребром».

«Список открытых узлов» – это в буквальном смысле список узлов. «Открытые» узлы – это узлы, которые алгоритм все равно должен проверить. Например, если вы ищете елочные игрушки, разложенные в ящиках у вас в подвале, то вы просматриваете каждый из ящиков и отмечаете его в списке. Если внутри большого ящика обнаружатся более мелкие, то их также можно добавить в список.

Алгоритм

Алгоритм, реализованный в этой функции, называется fill_shortest_path. Держите его перед глазами, читая это объяснение. Эта функция непосредственно не находит кратчайший путь, а измеряет расстояние от стартовой позиции до других клеток в лабиринте. Позже мы рассмотрим, как эта информация используется для генерации пути.

def fill_shortest_path(board, start, end, max_distance = math.inf):
  nboard = board.clone()
  nboard.clear_count(math.inf)

“Список открытых узлов” – это вектор позиций в решетке. В нем содержатся все местоположения, необходимые нам для поиска пути. Инициализируем список стартовой позицией лабиринта. Также мы должны установить счетчик в 0, поскольку на старте расстояние равно нулю.

nboard.at( start ).count = 0
    
open_list = [ start ]

Этого достаточно, чтобы запустить алгоритм. Перебираем узлы, пока open_list не опустеет.

  while open_list:
    	cur_pos = open_list.pop(0)
    	cur_cell = nboard.at( cur_pos )

Подождите, разве алгоритм не требует перейти к узлу, расстояние до которого является наименьшим? Этот код просто берет следующий узел в списке. Он работает, даже если взять случайный узел, даже если временная сложность в таком случае оказывается гораздо выше. В нашем коде это не важно, так как следующий узел – как раз тот, расстояние до которого является наименьшим. Почему так – будет показано позже.

Для каждого узла рассмотрим всех его соседей.

# (x,y) смещения от текущей клетки
neighbours = [ [-1,0], [1,0], [0,-1], [0,1] ]
for neighbour in neighbours:
  ncell_pos = mpf.add_point(cur_pos, neighbour)
  if not nboard.is_valid_point(ncell_pos):
continue
  
  cell = nboard.at( ncell_pos )

Каждый элемент в neighbors – это Евклидово смещение от текущей клетки до соседней. Например, [-1,0] – это сосед слева. Если cur_pos равно [ 5, 7 ], то сложив его с [-1, 0] получим [4, 7], то есть, ход на клетку влево. Аналогично, [1,0] – это движение в положительном направлении по оси x, то есть, на клетку вправо. [0,-1] влияет только на y и является переходом на одну позицию вверх, тогда как [0,1] – на одну вниз.

Пользуясь численными абстракциями направлений, можно в рамках данного алгоритма точно так же обработать любые другие переходы. Можно учесть и другие направления, например, [1,1], это ход по диагонали вверх и далее вправо. Но при этом мы должны держать в уме и края решетки, за что и отвечает is_valid_point. Например, если мы дойдем до правого края решетки,  то смещение [1,0], соответствующее одному переходу вправо, выведет нас за пределы графа, поэтому мы такой ход пропустим.

Также будем пропускать все непустые клетки, поскольку это стены лабиринта, и пройти через них мы не можем.

if cell.type != mpf.CellType.Empty:
  continue

Переходим к вычислению расстояния.

dist = cur_cell.count + 1

Поскольку мы все время движемся по прямой, клетка за клеткой, здесь можно вспомнить о «Манхэттенском расстоянии», то есть, расстояниями между двумя точками, которое можно покрывать лишь в направлении x или y, причем, ни в один ход нельзя перейти сразу по двум осям. Название обусловлено тем, как пересекаются улицы на Манхэттене, образующие именно такую сетку. Манхэттенское расстояние применимо к Евклидовой геометрии, например, к такой сетке, с которой мы здесь работаем.

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

if cell.count > dist:
  cell.count = dist
  cell.path_from = cur_cell
  open_list.append(ncell_pos)

Используем обобщенное поле cell.count для измерения расстояния, а также обновим поле path_from, указывающее, каким путем мы пришли в данную точку.

Ранее мы говорили, что первым в open_list всегда идет узел с наименьшим значением count. Уже понятно, почему, ведь каждый соседний узел удален от нас ровно на 1. Стартовый узел считается как 0, поэтому добавляем в список открытых несколько узлов, значения которых равны 1. Теперь, поскольку все узлы мы обрабатываем по порядку, добавляем в список несколько двоек, пока не будут охвачены все единицы. В итоге у нас в списке останутся двойки. Продолжим охватывать двойки, также добавляя в список некоторые тройки.

Этот простой эффект гарантирует качественное решение. Но, расширяя вычисление расстояния и добавляя в него эвристику, мы не сможем полагаться только на это. В более сложном случае алгоритм особо не изменился бы, но мы использовали бы для open_list не вектор, а очередь с приоритетами.

Визуализируем

Давайте уделим немного времени визуализации. Вызовем fill_shortest_path из кода, входящего в дистрибутив.

import mortoray_path_finding as mpf
    
maze = mpf.maze.create_wall_maze( 20, 12 )
filled = mpf.tutorial_1.fill_shortest_path(maze.board, maze.start, maze.end)

finder = mpf.draw.Finder()
finder.set_board(filled)
finder.run()

Исходник: tutorial_1_2.py

Откроется такое окно, как показано ниже. Стартовая клетка обозначена желтым, в ней стоит 0. Числа увеличиваются по мере отдаления от этой точки, с инкрементом в единицу. Все клетки в решетке обозначены в соответствии с манхэттенским расстоянием от стартовой точки до них. Находим клетку, обозначенную зеленым, и вычисляем, каково расстояние от стартовой точки до нее.

Получение пути

Кратчайшего пути у нас пока нет, но есть пара способов, которыми его можно получить.

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

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

Альтернативный способ – отслеживать путь, заполняя расстояния. Это именно тот код, который мы пока игнорировали.

if cell.count > dist:
  cell.count = dist
  cell.path_from = cur_cell
  open_list.append(ncell_pos)

Всякий раз, добавляя узел в список открытых узлов, мы также устанавливаем cell.path_from. Здесь хранятся записи о кратчайшем входящем пути, что упрощает отслеживание обратного курса от места назначения.

def backtrack_to_start(board, end):
  """ Возвращает путь до конечной точки, при этом предполагается, что поле заполнялось при помощи алгоритма fill_shortest_path """
  cell = board.at( end )
  path = []
  while cell != None:
    	path.append(cell)
    	cell = cell.path_from
   	 
  return path

В главном коде можно добавить вызов этой функции, чтобы в окне выводился путь от начальной до конечной точки.

import mortoray_path_finding as mpf
    
maze = mpf.maze.create_wall_maze( 20, 12 )
filled = mpf.tutorial_1.fill_shortest_path(maze.board, maze.start, maze.end)
path = mpf.tutorial_1.backtrack_to_start(filled, maze.end)

finder = mpf.draw.Finder()
finder.set_board(filled)
finder.set_path(path)
finder.run()

Исходник: tutorial_1_3.py

Здесь есть любопытный момент: функция fill_shortest_path вычисляет расстояние «от старта» для каждой клетки, а не только для конечной. Тот же самый код для отслеживания обратного пути до любого узла. Оказывается, такие исчерпывающие знания могут во многих отношениях пригодиться при поиске пути. Но, если наша приоритетная цель – оптимизация, то мы адаптируем алгоритм так, чтобы он прекращал поиск, как только найдет выход из лабиринта. Также есть алгоритм A*, использующий эвристику, которая позволяет обходиться без сканирования всей карты.

Заключение

В этом руководстве было рассмотрено, как найти выход из простого двумерного лабиринта. Ключевой алгоритм ведет список открытых узлов, измеряя расстояние от узла до соседних ему узлов и обновляя информацию о кратчайших маршрутах. В данной логике наиболее важен гибкий поиск маршрута. Алгоритм применим к решению многих задач, например, эвристического поиска пути, заполнения методом заливки и работы с диаграммами Вороного.

Прежде чем узнать, как найти выход из лабиринта, интересный вопрос!

А вы много знаете о лабиринтах? ПРАВДА или ВЫМЫСЕЛ, что в Китае некоторые входы в здания строят в виде нескольких изгибов наподобие лабиринта?

Узнать ответ и проверить себя вы сможете в конце статьи.

Лабиринт представляет собой сеть запутанных коридоров и ходов. Задача попавшего в него человека- найти выход. В большинстве своём он находится там же, где и вход.

Подробнее об истории возникновения и видах лабиринтов мы поговорим в следующих статьях. А пока давайте поймём, как выбраться из почти любого лабиринта, используя хитрые методы и теорию вероятности.

Смотрим на стены

И первое, что нам нужно сделать, это определить вид лабиринта. А именно, является он односвязным или многосвязным.

• Односвязный лабиринт имеет одну сплошную извилистую стену или перегородку. То есть если бы мы решили повторить его очертания на бумаге, нам не пришлось бы отрывать карандаш от листа.
• У многосвязного лабиринта всё сложнее. Есть отдельно стоящие перегородки различной формы, как если бы фигурки из тетриса кто-нибудь рассыпал на пол.

Конечно, если лабиринт находится в двухмерном пространстве, то есть нарисован на земле, полу или бумаге, проще понять к какому виду он относится.

Однако с высокими стенами, которые могут быть намного выше человеческого роста, вряд ли получится сделать это сразу.

Выход из односвязного лабиринта

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

В поиске выхода нам поможет правило одной руки. Выбираем любую руку и кладём её на стену лабиринта. По мере продвижения вперёд на протяжении всего пути, выбранная рука не должна отрываться от стены.

Так, скользя рукой по стене, если изначально правильно был определён тип лабиринта, вы рано или поздно найдёте выход.

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

Выход из многосвязного лабиринта

Для прохождения многосвязных лабиринтов существует специальный алгоритм.

Разработал его математик по фамилии Тремо. А позже, другой математик по фамилии Люк, доработал его идеи и описал их в своей книге. Отсюда описанный далее способ прохождения носит название «алгоритм Люка-Тремо».

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

Секрет кроется в том, чтобы не ходить в одни и те же коридоры более двух раз. Что это значит:

• Двигаясь по коридору от перекрёстка до перекрёстка, помечайте начало и конец прохода выбранным способом (например, рисуем на земле крестики).
• Дойдя до перекрёстка (развилки), всегда поворачивайте туда, где ещё нет крестиков. Если метки стоят на всех возможных поворотах, то сворачивайте в любую сторону.

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

• По мере прохождения лабиринта, вам придётся проходить многие коридоры дважды, это тоже часть алгоритма. Самое главное, на перекрёстке всегда сворачивать туда, где ноль или только один крест, а не два.

Алгоритм работает таким образом, что коридоры с двойными метками точно не приводят к выходу.

Так, отдавая предпочтение проходам, где вы ещё не были, можно выйти из многосвязного лабиринта.

Как итог

Конечно, интересно попробовать найти выход из лабиринта самостоятельно, не прибегая к хитростям.

Но, также, не менее интересно и попробовать выше названые способы в действии и проверить, действительно ли возможно при помощи алгоритмов выбраться из лабиринта.

А теперь вернёмся с вами к нашему вопросу: ПРАВДА или ВЫМЫСЕЛ, что в Китае некоторые входы в здания строят в виде нескольких изгибов наподобие лабиринта?

ПРАВДА

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

А какой способ найти выход выбрали бы вы, оказавшись в лабиринте?

Прохождение Сталкер Лабиринт

Просмотрите вступительный видеоролик, чтобы узнать предысторию игры.

Кордон (Глава 1. Сидорович)

Как обычно, вас ждёт множество интересных сюжетных и побочных заданий (последние мы также будем описывать, и в скобках указывать на то, что они опциональны), разбросанных по нескольким игровым локациям. Соответственно и наш гайд будет разделён на эти самые локации, внутри которых будут подзаголовки с заданиями.

Посылка

Убейте нескольких наёмников, которые атаковали ваш лагерь. Обыщите их тела. На трупе Сиплого будет синяя флешка. Заберите предмет, откройте инвентарь, щёлкните по флешке и выберите вариант «Изучить». Прочитайте текст. Закройте ПДА, чтобы получить новую цель и заставку с началом «Главы 1. Сидорович».

Выполните задание «Экскурсовод» (по желанию), после чего пройдите под мостом и идите налево, на северо-восток к ещё одной аномалии у тепловоза. Ищите в траве большой сейф. Взаимодействуйте с ним и введите код из ПДА: 354689. Заберите из сейфа рукописные карты подземелий Зоны и электронное устройство, с плоским кабелем и специфичным разъёмом. Идите на базу сталкеров и поговорите с Фургоном. Передайте ему электронное устройство. Передайте Фургону две бутылки водки (наверняка можно купить у торговца на базе, но у меня водка и без того была в инвентаре). Можете побеседовать с Шиловым, но его задание будет связано с грабежом курьеров Сидоровича. Я решил не ссориться с Сидоровичем, поэтому отказался от выполнения квеста. Если вы всё-таки захотите выполнить эту миссию, читайте ниже описание задания «Конкуренты».

Как только пройдёт полчаса внутриигрового времени, вы сможете вернуться к Фургону. Поговорите с ним повторно, вы получите декодер замков. Задание завершено.

Экскурсовод (побочное задание)

Прежде чем отправиться по сюжету игры в аномальные зоны, для начала откройте карту и найдите поблизости лагерь сталкеров. Следуйте туда. Можете пообщаться с разными персонажами. Войдите внутрь здания, где есть торговец и техник. У техника Фургона будет это задание (спросите за работёнку). Согласитесь. Награда — 5000 рублей, но только в том случае, если хотя бы один человек доберётся до нужного места живым. Можете воспользоваться услугами техника по назначению.

Отправляйтесь по маркеру и поговорите с Алексом Трупаком. Сопровождайте сталкеров до первой аномальной зоны, по пути убивая мутантов. Сталкеры присядут на корточки и начнут что-то изучать. Если у вас есть детектор, в этой аномальной зоне можете отыскать «Медузу». Также есть сейф, но код из ПДА не подходит. Защищайте сталкеров, поскольку их атакуют псевдособаки.

На пути к следующей аномалии сталкеры остановятся у туннеля. Вас атакуют снорки. Защитит сталкеров от снорков около аномальной зоны под мостом. Около вагона можете найти артефакт «Кристалл». Сопроводите парней обратно. Наверняка придётся убить бандитов на ближайшей базе. Идите к Фургону за наградой.

• Награда: 5000 рублей.

Как открыть сейф на базе сталкеров?

В разговоре с Фургоном вы также услышите за сталкера Сапёра, которому принадлежит местный сейф. Он куда-то ушёл и пропал, а перед этим мастерил щуп для поиска мин. Внизу Кордона есть локация «Минное поле». Если попадёте на минное поле (к слову, сделать это можно во время задания «Сборы в дорогу», и тогда военные не будут по вам стрелять), сможете отыскать рюкзак с флешкой. Прочитайте информацию с флешки, чтобы получить код от сейфа — 835976. Сейф можно использовать как тайник. Кроме того, внутри него лежат пистолет USP и патроны.

Конкуренты (побочное задание)

Это задание можно взять на базе сталкеров у торговца Шилова после того, как принесёте электронное устройство технику Фургону (по сюжету игры), и он попросит подождать полчасика. Вам нужно сразу же пойти в указанное место и убить трёх врагов. С трупа одного из них заберите хабар Сидоровича и верните Шилову.

• Награда: 6000 рублей.

Примечание. Позже точно такое же задание можно будет взять у Сидоровича. Если вы отказали Шилову, Сидорович скажет, что кто-то убил его курьера. Видимо, Шилов нанял другого человека. И Сидорович попросит убить курьеров Шилова и доставить его Хабар. В общем, всё то же самое.

Давняя мечта

Это сюжетное задание начнётся сразу по завершении миссии «Посылка». Двигайтесь в деревню новичков и поговорите с Волком. Он даст ключ от двери в первом здании деревни. Откройте её и спуститесь в подземелье.

Откройте дверь, применив декодер на замке, и убейте всех наёмников. Поговорите с раненным Прохвостом. Вы узнаете много полезных данных. Обыщите трупы, выберитесь наружу и пообщайтесь с Волком внутри подземелья и снаружи.

Не переживайте за отмену этого задания во время прыжка в аномальный пузырь. Это запланировано по сюжету, и после возвращения из будущего вы сможете продолжить эту миссию.

Петля времени

Как только запрыгните в аномальный пузырь, окажетесь во временной петле. Задания «Сборы в дорогу» и «Давняя мечта» будут отменены. Вам предлагают осмотреть АТП. Следуйте туда, пока не запустится кат-сцена. Фанат попадёт в окружение наёмников. Пообщайтесь с Петей Перевозчиком. Следуйте в деревню новичков, спуститесь в подвал и поговорите с Богданом Пузырём. Выйдите наружу и поговорите с… Меченым. Уничтожьте огромную группу наёмников и вновь пообщайтесь с Меченым. Затем отправляйтесь к Сидоровичу в его бункер. Можете поторговать.

Выйдите наружу и отправляйтесь на базу сталкеров. Пообщайтесь со Шпалой. В указанном месте будет блокпост военных. И если играете на высокой сложности, они убьют вас в два счёта. Поэтому, держа палец на «аптечках», обогните бетонную трубу и проберитесь внутрь неё, не забывая исцеляться. Войдите в пузырь времени, чтобы вернуться в своё настоящее. Задание завершится. Вновь станут доступны квесты «Давняя мечта» и «Сборы в дорогу».

Сборы в дорогу

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

Не переживайте за отмену этого задания во время прыжка в аномальный пузырь. Это запланировано по сюжету, и после возвращения из будущего вы сможете продолжить эту миссию.

Пообщайтесь с Сидоровичем после задания «Петля времени». Двигайтесь на АТП. Перед входом вы будете остановлены Валетом, который просит не размахивать пушкой на базе и с уважением общаться с Йогой (видимо, главарём бандитов). Поговорите с Боровом и скажите, что вам нужны артефакты «Снежинка» и «Пузырь».

Здесь вы можете заплатить 40 000 рублей, и тогда не придётся искать автомат Борова. Но смысла в этом нет, тем более задание не такое уж сложное. А выполнив задание, вы заплатите за артефакты всего лишь 5000 рублей.

Теперь посетите техника Ворона и передайте ему водку «Казаки». Затем пообщайтесь с торговцем Вавилоном. Наконец, следуйте к Валету и узнайте за Жмотяру. И вновь пообщайтесь с Боровом. Выйдите за пределы базы и поговорите с Вованом.

Где найти Жмотяру?

Часовые дали вам противоречивую информацию. Так где же искать Жмотяру? Вас интересует аномальная зона поблизости от АТП, в левом нижнем углу от железной дороги. Жмотяра, одетый в плащ, сидит на железной бочке. Поговорите с ним.

Спустя несколько секунд кто-то попытается вас убить, и вам предложат наказать обидчика. Разберитесь с отмеченным сталкером и обыщите его труп, чтобы получить ключ, флешку и прочую добычу. Прочитайте содержимое флешки. Судя по всему, Вован нанял Качка, чтобы тот вас убил. Вернитесь на АТП и найдите на его территории место с могильными крестами. Справа от них, на здании висит большой электрощиток. Откройте его ключом, найденным на трупе Качка, и заберите автомат Борова. Передайте оружие квестодателю.

Кто стащил автомат Борова?

Интересный вопрос, поскольку на флешке, которую вы нашли на трупе Качка, есть всего одна буква инициала — «В». И имена всех опрошенных вами бандитов начинаются на букву «В». Жмотяра сообщил, что Вована на посту не было, а сам Вован сказал, что видел Жмотяру. Так что всё указывает именно на него. На самом деле обвинить вы можете всех, и ответ Борова будет одинаковым. Так что узнать наверняка не выйдет.

Если найдёте оружие Борова, то сможете купить артефакты за 5000 рублей.

Лучшее решение по этому квесту: выполните задание Борова, даже если у вас есть 40 000 рублей. Когда найдёте автомат Борова, соберите 40 000 рублей и вернитесь к нему. Вы сможете купить артефакты за 40 000 рублей и оставить автомат Борова!

Вернитесь к Сидоровичу с артефактами и поговорите на все темы. Он даст дипломат и направит вас к Халецкому. Герой попросит у майора броник, пулемет и шлем с ночным видением. 100 000 рублей у вас наверняка нет. Он предложит всё это за 20 000 рублей, но в обмен вы должны вернуть долг Йоги с АТП.

Пообщайтесь с Сидоровичем, чтобы получить новую информацию. Отправляйтесь на АТП к Йоге. И вновь поговорите с Сидоровичем. Он даст дипломат с иконой. Придётся убить Жмотяру и забрать его оружие. Поговорить с ним не выйдет, так что убейте и заберите оружие. Идите к Йоге, чтобы получить от него 60 000 рублей. Доберитесь до точки перехода и убейте кровососа. Вернитесь к Йоге. У вас будет 30 секунд, чтобы покинуть базу. Но прежде откройте инвентарь и осмотрите флешку с кодом — 835977. Введите код на сейфе в углу и достаньте всё содержимое. Затем быстро покиньте АТП.

Если вернётесь туда, придётся сражаться с бандитами. Даже если выбрались своевременно. Идите к Халецкому, отдайте кейс и 20 000 рублей. Вы получите пулемёт АКС-74У, патроны, кожаный плащ и противогаз (вместо броника и шлема ночного видения).

Можно провернуть «танцы с бубном» и сдвинуть майора с пути, выбросив на пол пару комплектов брони и толкая их постепенно на персонажа. Так вы получите доступ к его кабинету, где есть бронекостюм «Булат» и флешка, лежащая на диване слева. На флешке есть код «78295», но открыть сейф в этой комнате даже со знанием кода не получится. Сделать это можно будет после, по сюжету, так что торопиться не стоит.

Итак, вернитесь к Сидоровичу, чтобы обсудить следующий план. Он скажет, что нужно избавиться от людей Халецкого. Сначала придётся ликвидировать разведчиков. Доберитесь до указанного места (подтвердите быстрое перемещение) и поговорите с Привратником. Он предложит оружие с оптикой за 54 000 рублей. Идите к отцу Валерьяну. В обмен на Светляк он просит помочь его бойцам зачистить АТП. В любом случае с бандитами вы уже поссорились.

Код от сейфа Шпалы (Валерьяна)?

В помещении с Валерьяном стоит сейф. Осмотрите его и вновь поговорите с Валерьяном. Он скажет, что сейф принадлежал сталкеру Шпале. Отправляйтесь на железнодорожный мост. Поднимитесь на холм и идите вдоль рельс к вагонам с наклонённым листом металла. Двигайтесь слева от вагона к опрокинотому контейнеру и под вагоном ищите рюкзак с тайником. Заберите оттуда флешку с кодом от сейфа — 835975. Откройте сейф в комнате Валерьяна, чтобы найти детектор «Велес».

Зачистите АТП, предварительно встретившись со сталкерами, затем вернитесь к Валерьяну. Вы получите Светляк. Идите к Привратнику, передайте артефакт, чтобы получить оружие «Рысь» и патроны к нему.

Ничего не остаётся делать: идём на блокпост военных и зачищаем его. Сделав это, загляните в комнату с сейфом. Откройте его кодом 78295. Заберите содержимое (патроны и тактический шлем). Возьмите лежащий на шкафу справа бронекостюм «Булат». Задание «Сборы в дорогу» завершено. Начнётся новый квест «Лабиринт».

Лабиринт

Обыщите всех солдат (учтите, что после завершения предыдущей миссии появится вертолёт) и идите к Сидоровичу. Поговорите с ним. Идите к Волку за ключом. Спуститесь в подземелье и введите код на двери слева — 354689 (совпадает с кодом от сейфа).

Глава 2. Обитатели подземелья

Идите вперед и через дыру в стене справа. На развилке идите влево. Каждый раз выбирайте левый путь. Вскоре вы столкнетесь с ещё одной группой тушканов. Они придут из тупика, поэтому вы сверните вправо. Убейте полтергейста и осмотрите дверь, ведущую в тоннели под Агропромом. Поднимитесь по лестнице, идите в конец коридора и взломайте замок класса Б. убейте полтергейста, пройдите через дверь в стене слева. Взломайте замок класса Б у двери слева, в лаборатории с большим энергетическим шаром и странной установкой. Внутри комнаты есть сейф, но код от него пока что неизвестен.

Выйдите из диспетчерской и спуститесь вниз по лестнице, к основанию установки. Сбоку есть дверь, через которую нужно пройти. Сверните влево и ещё раз влево. Справа будет дверь в столовую. Обыщите её. Помимо продуктов вы обнаружите флешку в ноутбуке с кодом 105018. Вернитесь к лестнице, по которой сюда поднялись. Рядом есть ещё одна лестница, ведущая наверх. Но она приведёт вас на верхний уровень комнаты с установкой, и там ничего нет. Поэтому идите по кругу этого закольцованного коридора и найдите ещё одну лестницу со ступенями, ведущими наверх.

Взломайте ещё один замок класса Б, встаньте у терминала в центре комнаты телепортации. введите код 105108, чтобы выбраться из ловушки, и пройдите через другую дверь. После загрузки вы окажетесь на новой локации.

Комната телепортации

Спуститесь ниже и взломайте замок класса Б. Сделайте то же самое с замком у двери в правом дальнем углу следующего помещения. Поднимитесь по ступеням слева и потяните за рычаг на пульте управления. В той же комнате, в противоположном углу есть ещё один рычаг, расположенный прямо на стене. Поднимите его, чтобы включить вспомогательный генератор. Вернитесь в зал с телепортом и найдите ещё один рычаг на стене. Когда активируете все три рычага, войдите в телепорт.

Город Призрак

Идите вперед и сверните в левую сторону. Слева будет запертая дверь с кодовым замком. Осмотрите замок. С вами начнёт беседу профессор Кузнецов.

Пузырь

В беседе с Кузнецовым начнётся новое задание. Вас просят уничтожить зомбированных. Профессор также назовёт код от крышки люка — 159753. Вернитесь немного назад и сверните вправо. Этот коридор ведёт к люку и кодовому замку. Введите код и выберитесь на поверхность. Ходите по городу и убивайте зомбированных, пока задание не обновится. Как только это произойдёт, вернитесь в подземелье к профессору.

Профессор попросит найти артефакт «Компас». Идите обратно на поверхность и ищите небольшой огороженный бетонными плитами участок. Вы можете перебраться через забор по брёвнам, но именно под ними лежит «Компас». Используйте детектор, чтобы подобрать артефакт. За самим ограждением находится экскаватор. Пообщайтесь с Марией, расположенной неподалёку от профессора. Затем пообщайтесь с Кузнецовым.

Теперь нужно отыскать шлем. Покиньте убежище профессора и бегите по коридору вправо. В самом конце будет дверь, которую теперь можно открыть кодом 174538. Пройдите в конец коридора и воспользуйтесь дырой в стене справа. Убейте тушканов. На развилке идите в дальний поворот справа. Он ведёт в тупик с трупом военного, пулемётом и нужным шлемом. Вернитесь к Марии. Вы получите артефакт «Энергия». Поговорите с Кузнецовым.

Выберитесь в Город Призрак и идите влево, мимо крана к зданию автовокзала. Поднимитесь наверх, ещё выше и в одной из комнат обнаружите телепорт, который переместит вас на крышу. Бегите в другой конец крыши, где будет второй телепорт. Войдите в него, чтобы попасть на другую крышу. Осмотрите её и войдите в третий телепорт (появится прямо на крыше). Бегите вперёд, где появится четвёртый телепорт. Вы вернётесь на предыдущую крышу, но здесь появится ящик. Это нужный вам груз. Вернитесь назад при помощи телепорта. Вас перебросит в квартиру рядом с аномалией. Спуститесь по веткам вниз и вернитесь к Кузнецову.

Откройте сейф неподалёку, введя код 777, полученный от профессора. Заберите медикаменты, вернитесь на поверхность и идите влево к крану. Залезьте на вершину крана и установите артефакт. Войдите в здание автовокзала, найдите лестничную площадку и поднимитесь на крышу. Введите код у спутниковой антенны — 58236. Антенна повернётся к другой. Идите к зданию со второй антенной и найдите снаружи пожарную лестницу. Поднимитесь на крышу и введите код 58336. Поднимитесь на крышу третьего здания, используя аналогичную лестницу, и введите код 58436. Вернитесь на вершину крана и войдите в телепорт.

Вы вернётесь в комнату телепортации. войдите в соседнее помещение и подойдите к решётке, чтобы поговорить с профессором Кузнецовым. Задание выполнено!

Нужно выбраться из лаборатории. Идите обратным путём вверх из комнаты телепортации. продолжайте возвращаться, пока не спуститесь по лестнице в комнату с дверью, ведущей в подземелье под Агропромом. Под лестницей есть дыра в стене. Двигайтесь через неё. Сверните влево, вправо. Далее будет несколько тупиков, а вам нужно найти путь, который выведет к дыре в стене и большому залу с бочками и полтергейстом. Здесь расположена дверь в подземелья под Тёмной Долиной.

Есть три тоннеля. Один из них ведёт к трупу и рюкзаку с флешкой техника Михайлова. Прочитайте информацию с флешки. Запомните код «952367». Здесь же лежит ещё один пулемёт. Возьмите его, если у вас такого ещё нет или он уже сломался. Идите обратно в комнату с установкой и другим помещениям. В спальне с несколькими кроватями стоит сейф. Введите код 952367 и заберите всё содержимое, в том числе ещё одну флешку и прицел. Вы получите ещё один код «78296». Войдите в диспетчерскую в комнате с установкой и введите код на сейфе. Изучите новую флешку. Вы получите код 78398 от двери подземелий под Тёмной Долиной. Вернитесь в зал с этой дверью (писалось выше) и откройте её.

Глава 3. Клык

Пообщайтесь со сталкером впереди. Следуйте за Клыком и убивайте монстров. В конце концов, вы вновь поговорите с Клыком. Взломайте замок у дальней двери, пробейтесь через пару десятков наёмников и поднимитесь вверх по лестнице. Осмотрите кодовый замок и вернитесь к Клыку. Продолжайте следовать за сталкером, убивая монстров. Проберитесь дальше по тоннелю, убейте трёх кровососов и Клык воссоединится с вами. Двигайтесь к выходу. Задание «Лабиринт» будет завершено.

Осада

Квест начнётся сразу после предыдущей миссии «Лабиринт». Выберитесь наружу и пообщайтесь с Клыком.  Идите следом, убейте бандитов и вновь пообщайтесь со сталкером. Если разговор не начинается, сохранитесь и перезагрузитесь.

Глава 4. Локи

Идите на базу Свободы и поговорите с Чеховым. Можете потратить время и пообщаться с остальными персонажами.

Как открыть сейф н абазе Свободы у Чехова

Спросите у Чехова за сейф. Он скажет, что вы можете им воспользоваться и забрать всё содержимое, если сможете открыть. Снаружи есть вышка с мёртвым бандитом. В сундуке рядом лежит флешка. Изучите её. В стихотворении зашифрована кодовая комбинация. Откройте сейф кодом 145234.

Идите в указанное место и уничтожьте всех бандитов. Поговорите с Локи, следуйте за ним и убейте ещё нескольких врагов. Повторно побеседуйте с Локи, продолжайте движение и зачистите ещё одно место. Пообщайтесь с Локи в последний раз. Доберитесь до фермы и зачистите её от всех бандитов. В одном из зданий лежит сейф. Откройте его, введя код 336057. Заберите ящик с кодовым замком и вернитесь к Локи. Следуйте вместе с приятелями на вражескую базу и зачистите её. Пообщайтесь с Локи, когда тот окажется внутри. Вернитесь к Чехову и пообщайтесь с ним. Он даст флешку с кодом от двери в подземелья (84659). Также Чехов подскажет, что Ашот и Яр готовы пообщаться с вами в более дружеской атмосфере (можно взять побочные задания).

Месть Ашота (побочное задание)

Побочное задание можно взять после того, как поможем Локи и Свободе, и Чехов даст флешку с кодом от подземелья. Отправляйтесь к месту со скриншота ниже:

Поднимитесь на второй этаж здания и найдите опрокинутый сейф. Откройте его, введя код «55», и заберите мешочек с высушенной травой. Можете отдать мешочек Ганже или Ашоту. Если передадите бармену, получите от него ещё одну флешку с кодом от сейфа на втором этаже школы (741963). Если передадите мешочек Ашоту, он даст другую флешку, и в ней будет информация о сейфе на первом этаже школы и коде от него (963741).

Диггер (побочное задание)

Этот квест можно взять у Дядюшки Яра на базе Свободы после того, как поможете Локи и Чехов даст флешку с кодом от подземелья. Вам нужно установить четыре сканера в четырёх разных местах. Ниже есть скриншоты с четырьмя нужными позициями:

Задание завершится сразу после того, как вы установите каждый сканер. За сканеры вы отдали 4000, а за их установку получили 6000 рублей.

Осада (продолжение)

Двигайтесь к точке перехода и спуститесь в подземелье, введя код 84659.

Глава 5. Стена огня

Задание «Осада» завершится сразу после того, как вы попадёте в подземелья под Тёмной Долиной.

Танцы со смертью

Спуститесь ниже и убейте полтергейста. Здесь будет дверь с кодовым замком класса А. Открыть её не получится. Найдите на этом же уровне труп учёного (тот самый, из оригинала). Прослушайте запись с КПК и введите код 1423 на той самой двери. Спуститесь ниже, осмотрите другую дверь и найдите труп ещё одного учёного. В том же месте, что и в оригинале. Сделав это, изучите КПК и введите код от двери 9524.

Пройдите в лабораторию, поднимитесь наверх по ступеням и заберите флешку, в которой указан код от лифта 7516. Вернитесь в место, где нашли второго учёного, и найдите кодовый замок около лифта. Введите этот код, войдите в лифт и взаимодействуйте с панелью управления.

Глава 6. Ангел

Пообщайтесь со Шпалой в клетке. Идите следом. В помещении, где Шпала убил наёмника и отнял его оружие, на столе лежит флешка. В ней указан код от двери в тоннель — 38452. Не торопитесь уходить. Рядом стоит ноутбук. Взаимодействуйте с ним. В КПК будет занесена информация с кодом 17846. В этой же комнате, в шкафу с полками стоит небольшой сейф. Откройте его этой кодовой комбинацией и заберите клочок бумаги. На странице указан другой код 1421.

Загляните в комнату справа и возьмите обрез. В сейфах лежат ваши предметы (частично). Один из сейфов закрыт на код. Помогите Шпале убить наёмников, на трупе одного из них найдите флешку (в ней указан код от сейфа 54625, можете вернуться к торговцу и открыть его). Пообщайтесь со Шпалой. Идите к лифту и езжайте на первый ярус. Убейте трёх наёмников, в самом конце откройте дверь, введя код 38452. Но прежде обязательно обыщите ящик слева от этой двери. В нём лежит всё ваше оружие.

Вы вернётесь в знакомое помещение с сейфом и ноутбуком. Введите на ноутбуке справа пароль 1421 и загрузите информацию на флешку. В ней указан код от сейфа — 705139. Откройте сейф напротив, чтобы забрать хабар. Изучите флешку из сейфа. На ней будет ещё один код 15423.

Вернитесь внутрь и обратите внимание на четыре двери с кодовыми замками в коридоре перед лифтом. Одна из дверей открывается тем самым кодом 15423.

Глава 7. Преисподняя

Задание «Танцы со смертью» сразу же завершится.

Удивительные твари

Взломайте замок декодером, убейте парочку бюреров и в одном из ящиков найдите винторез. Спуститесь ниже и убейте ещё кучку бюреров. Обыщите комнаты, затем спуститесь ниже по другой лестнице. Взломайте замок класса Б, двигайтесь вглубь локации. На развилке идите вправо (путь влево ведёт к закрытой решётке). В конце концов, вы попадёте в комнату с новым монстром. Убейте его из пулемёта или винтореза. В комнате на стене есть рычаг. Опустите, чтобы поднять решётку в другой стороне. Не спешите отсюда уходить. На столе лежит флешка с кодом 78542, который открывает сейф с экзоскелетом.

Идите в другую сторону по коридору. За поднятой решёткой будет помещение с 6 кровоссами и одним мощным мутантом. В случае с последним рекомендую использовать гранаты Ф-15, которые наносят этому монстру какой-то запредельный урон. Убивать его только из огнестрельного оружия — плохая затея, хотя всё зависит от выбранного вами уровня сложности.

Войдите в дальнюю комнату и откройте сейф справа (код выше), чтобы получить экзоскелет. В центре стоят открываемые капсулы. В одной из них лежит клочок бумаги. Изучите его в инвентаре, чтобы узнать код 58278. Откройте дверь напротив этой комнаты и войдите в туннель. Взломайте ещё один замок и идите вперёд, пока не начнётся загрузка, завершающая это задание.

Глава 8. Между молотом и наковальней

Все те же рожи

Убейте мутантов. Неподалёку будут валяться тела Кузнецова и Марии. С трупа последней можно забрать артефакт «Энергия». Следуйте в другую сторону, сбоку будет путь к люку. Взломайте замок декодером и выберитесь на поверхность. Следуйте за Валетом и Вованом, поговорите с ними повторно. Идите следом за ними и пообщайтесь с Вороном. Затем поговорите с Валетом. У Ворона можно улучшить экзоскелет. Идите за ним, пообщайтесь. Нужно отыскать взрывчатку. Спуститесь в подвал и убейте контроллера. Идите вперёд и сверните в предпоследнюю дверь справа. Слева будет ещё одно помещения с ящиками. Под ними лежит рюкзак с взрывчаткой. Установите взрывчатку под БТР, вернитесь к Валету и встаньте вплотную к подвалу. Активируйте пульт из инвентаря. После взрыва бегите обратно за Валетом. Помогите бандитам убить наёмников.

Вернитесь внутрь и поговорите с Вавилоном, Вороном и Вованом. Двигайтесь по маркёру и пообщайтесь с Душманом. Добейте его и заберите флешку с кодом от сейфа 741369. Откройте сейф поблизости, чтобы получить артефакт. Если помните, то в школе на первом или втором этаже можно открыть сейф кодом, полученным от Ашота или Ганжи. Один сейф открывается кодом 963741, другой — 741963. Я не проверял, но, возможно, вы можете открыть оба и получать два артефакта «Пламя».

Как попасть в лабораторию X11

Обойдите основное здание, где сидят бандиты, и найдите вход в библиотеку. Осмотрите книжные полки. Взаимодействуйте с книжкой Дарвина (при её осмотре не будет надписи с подсказкой о взаимодействии), чтобы открыть скрытый вход в подземелье. Спуститесь вниз и взломайте замок класса Б.

Глава 9. Истинный фанатизм

Задание завершено, начнётся новый квест.

Акуна Матата

Идите вперёд и убейте монолитовцев. Поднимитесь по лестнице, но будьте осторожны — здесь стоит турель. Уничтожьте её (можно из обычного огнестрела) и взломайте замок класса Б. Убейте врагов и соберите припасы. Здесь же есть морозильные камеры. В двух из них лежат трупы. Под ними, за дверцами поменьше ищите рюкзаки с двумя разными детекторами («Отклик» и «Сварог»). Спуститесь по другой лестнице в предыдущем коридоре. Вы увидите ещё две лестницы. Идите вверх, на развилке уйдите влево. Этот путь приведёт вас к двери с замком класса Б. Убейте молящихся монолитовцев.

В помещении слева на столе лежит листок бумаги. Изучите его в инвентаре, откройте КПК и прочитайте запись. В ней содержится код от двери склада — 81973. Идите обратно, спуститесь по лестнице и взломайте замок класса Б. За стеклом справа будет какое-то странное устройство, излучающее энергию. Взломайте ещё один замок класса Б. В помещении с устройством нет ничего интересного, но в диспетчерской перед ним стоит сейфа, а на столе лежит клочок бумаги. Изучите его, и в КПК появится код замка двери 54628.

Идите в самое начало, к первой развилке с двумя лестницами. На этот раз спуститесь ещё ниже, убейте врага впереди. Справа будет лестница, ведущая вниз. Не спешите спускаться. Чуть дальше по правую руку будет дверь с замком класса Б. Взломайте её, можете собрать еду, пулемёт, патроны и детекторы. Дверь в конце этого коридора ведёт в ту самую молитвенную комнату. Вернитесь в середину коридора и спуститесь вниз по лестнице. Откройте дверь справа при помощи декодера, убейте врагов и взорвите турель. Можете собрать несколько артефактов.

Идите в другую сторону, взорвите турель и откройте дверь слева. Обыщите хранилище и двигайтесь дальше по коридору. Взломайте дверь в самом конце, осмотрите помещение с лифтом и ещё одной кодовой дверью. Введите код 81973, чтобы её открыть. Уничтожьте три турели, обыщите все ящики. Соберите заряды и гаусс-пушку.

Вам нужно найти коридор, где стоят другие враги. Он находится неподалёку от молитвенной комнаты. Убейте монолитовцев, поднимитесь выше и введите код от комнаты охраны на белой двери (54628). В шкафчике лежит ещё одна гаусс-пушка. На диване есть экзоскелет. На стене у входной двери установлен рубильник. Поднимите рычаг и выйдите через открывшуюся дверь. Смотрите финальный видеоролик.