Сокобан что это такое
Сокобан что это такое
Правила
Сокобан (в переводе с японского — «кладовщик«) — это классическая головоломка, созданная в Японии, по сложности сопоставимая с кубиком Рубика, шашками и даже шахматами. Автором оригинальной игры является Хироюки Имабаяши, создавший Сокобан в 1980-м году. В 1982 году игра была издана японской компанией Thinking Rabbit («Думающий Кролик»).
Правила Сокобана очень просты. На складе, представленном в игре в виде плана, находится кладовщик и ящики. Задача состоит в перемещении ящиков по лабиринту (складу) с целью поставить их на заданные конечные места. При этом ящики можно толкать, но нельзя тянуть. Кроме того, нельзя перемещать более одного ящика зараз. Кладовщик может свободно перемещаться по складу, но не может проходить через ящики и стены.
Отсюда можно сделать несколько простых выводов по стратегии игры.
Кроме того, может возникнуть ситуация, когда ящиками будет заблокирована определенная область лабиринта. И любая попытка разблокировать эту область, подвинув ящик, приведет к одной из описанных выше ситуаций.
Управление
Вы можете двигать ящики человечком нажатием стрелок на клавиатуре или перетягивая ящики мышью (ящик будет двигаться только в том случае, если вы вправе подвинуть его на нужную клетку)
Показать полное описание Скрыть полное описание
Верхняя панель кнопок
Ход назад, Ход вперёд (также клавиши «стрелка влево» и «стрелка вправо» на клавиатуре) позволяют вам двигаться по вашему решению вперёд и назад, вплоть до самого начала.
Сокобан что это такое
Правила
Сокобан (в переводе с японского — «кладовщик«) — это классическая головоломка, созданная в Японии, по сложности сопоставимая с кубиком Рубика, шашками и даже шахматами. Автором оригинальной игры является Хироюки Имабаяши, создавший Сокобан в 1980-м году. В 1982 году игра была издана японской компанией Thinking Rabbit («Думающий Кролик»).
Правила Сокобана очень просты. На складе, представленном в игре в виде плана, находится кладовщик и ящики. Задача состоит в перемещении ящиков по лабиринту (складу) с целью поставить их на заданные конечные места. При этом ящики можно толкать, но нельзя тянуть. Кроме того, нельзя перемещать более одного ящика зараз. Кладовщик может свободно перемещаться по складу, но не может проходить через ящики и стены.
Отсюда можно сделать несколько простых выводов по стратегии игры.
Кроме того, может возникнуть ситуация, когда ящиками будет заблокирована определенная область лабиринта. И любая попытка разблокировать эту область, подвинув ящик, приведет к одной из описанных выше ситуаций.
Управление
Вы можете двигать ящики человечком нажатием стрелок на клавиатуре или перетягивая ящики мышью (ящик будет двигаться только в том случае, если вы вправе подвинуть его на нужную клетку)
Показать полное описание Скрыть полное описание
Верхняя панель кнопок
Ход назад, Ход вперёд (также клавиши «стрелка влево» и «стрелка вправо» на клавиатуре) позволяют вам двигаться по вашему решению вперёд и назад, вплоть до самого начала.
Sokoban
Sokoban (Soko-Ban, яп. 倉庫番 сокобан — «кладовщик») — логическая игра-головоломка, в которой игрок передвигает ящики по лабиринту, показанному в виде плана, с целью поставить все ящики на заданные конечные позиции. Только один ящик может быть передвинут за раз, причём герой игры — «кладовщик» — может только толкать ящики, но не тянуть их. Поскольку игру достаточно сложно воссоздать физически, обычно она реализуется в виде компьютерной игры.
Игра Sokoban была создана в 1980 году Хироюки Имабаяси, и издана в 1982 году японской компанией Thinking Rabbit. Кроме того, компания выпустила три сиквела: Boxxle, Sokoban Perfect и Sokoban Revenge.
Игра была реализована для множества компьютерных платформ, включая практически все домашние и персональные компьютеры. Также существуют версии игры для карманных компьютеров, игровых приставок, цифровых фотоаппаратов и мобильных телефонов.
В бывшем СССР игра также была известна, как KURTAN и «Мудрый крот». Эти (и другие) игры для старых компьютеров работают на современных под управлением Dosbox.
Сокобаны делятся на четыре категории. В первой, для прохождения, любой ящик может быть на любом специальном поле для ящика. Во второй на специальном поле могут быть только ящики, соответствующие этому полю по цвету. В третьей и в четвёртой от толчка по ящику ящик едет или скользит до другого ящика или стены. А в четвёртой на специальном поле могут быть только ящики, соответствующие этому полю по цвету.
Клоны
См. также
Ссылки
Полезное
Смотреть что такое «Sokoban» в других словарях:
Sokoban — Concepteur Hiroyuki Imabayashi Date de sortie 1982 Genre puzzle Mode de jeu Un joueur Sokoban est un jeu vidéo de puzzle inventé au Japon. Ce nom que l on écrit 倉庫番 en japonais, ou sôkoban transcrit … Wikipédia en Français
Sokoban — KSokoban, una implementación de Sokoban para GNU/ Linux Desarrolladora(s) ASCII Corporation, Thinking Rabbit Distribuidora(s) … Wikipedia Español
Sokoban — A Sokoban puzzle. Sokoban 「倉庫番」 (warehouse keeper?) is a type of transport puzzle, in which the player pushes boxes or crates around in a warehouse, trying to get them to storage locations. The puzzle is usually implemented as a … Wikipedia
Sokoban — Bildschirmfoto von YASC, einer GPL Implementierung von Sokoban Sokoban (倉庫番 Sōkoban, japanisch „Lagerhausverwalter“) ist ein Computerspiel, das von Hiroyuki Imabayashi entwickelt und 1982 erstmals für verschiedene Computersysteme veröffentlicht… … Deutsch Wikipedia
Sokoban — noun A computer puzzle game, devised in 1980 and frequently reimplemented, in which the player must push boxes to designated locations under a set of movement constraints. These so called deadlock states are largely responsible for the failure of … Wiktionary
Sokoban World — Sokoban Sokoban Concepteur Hiroyuki Imabayashi Date de sortie 1982 Genre puzzle Mode de jeu Un joueur Sokoban est un jeu vidéo de puzzle inventé au Japon. Ce nom que l on écrit 倉庫番 en japonais, ou sôkoban transcrit ave … Wikipédia en Français
Power Sokoban — Infobox VG title = Power Sokoban developer = Atelier Double publisher = Nintendo designer = released = vgrelease|JP=January 1, 1999 genre = Puzzle modes = Single player platforms = Super Famicom, Nintendo Power flash RAM cartridge media =… … Wikipedia
Boxworld — Sokoban Sokoban Concepteur Hiroyuki Imabayashi Date de sortie 1982 Genre puzzle Mode de jeu Un joueur Sokoban est un jeu vidéo de puzzle inventé au Japon. Ce nom que l on écrit 倉庫番 en japonais, ou sôkoban transcrit ave … Wikipédia en Français
Rocks’n’Diamonds — Разработчик Artsoft Entertainment Издатель Artsoft Entertainment Создатели Геймдизайнер Holger Schemel … Википедия
Rocks\’n\’Diamonds — Разработчик Artsoft Entertainment Издатель Artsoft Entertainment Дизайнер Holger Schemel Дата выпуска 1995 … Википедия
Сокобан
Смотреть что такое «Сокобан» в других словарях:
Sokoban — Уровень 4 игры для PC (Spectrum Holobyte, 1984) Sokoban (Soko Ban, яп. 倉庫番 сокобан «кладовщик») логическая игра головоломка, в которой … Википедия
Soko-Ban — Уровень 4 игры для PC (Spectrum Holobyte, 1984) Sokoban (Soko Ban, яп. 倉庫番 сокобан «кладовщик») логическая игра головоломка, в которой игрок передвигает ящики по лабиринту, показанному в виде плана, с целью поставить все ящики на заданные… … Википедия
NetHack — Nethack … Википедия
Sed — (от англ. Stream EDitor) потоковый текстовый редактор (а также язык программирования), применяющий различные предопределённые текстовые преобразования к последовательному потоку текстовых данных. Первоначально был написан как UNIX утилита… … Википедия
Kdegames — kdegames пакет программ, разработанных в рамках проекта KDE. Содержит разного рода игры, в том числе пакеты kdegames arcade (аркадные игры), kdegames board (игры на доске), kdegames tactic (тактические игры) and kdegames card (карточные… … Википедия
Пазл (жанр компьютерных игр) — Игра Тетрис одна из самых известных головоломок жанра. Головоломка (англ. Puzzle) название жанра компьютерных игр, целью которых является решение логических задач, требующих от игрока задействования логики, стратегии и интуиции или в иных… … Википедия
CHDK — CHDK … Википедия
Казуальная игра — Казуальная игра компьютерная игра, предназначенная для широкого круга пользователей. Сам термин «казуальная» происходит от лат. casualis, что означает «случайный». Таким образом, казуальная игра это игра, в которую играют от… … Википедия
Реиграбельность — (англ. replayability, replay value) свойство компьютерной игры быть интересной при повторном прохождении. Содержание 1 По жанрам 1.1 Реиграбельность близка к нулю … Википедия
Паззл (жанр компьютерных игр) — Игра Тетрис одна из самых известных головоломок жанра. Головоломка (англ. Puzzle) название жанра компьютерных игр, целью которых является решение логических задач, требующих от игрока задействования логики, стратегии и интуиции или в иных… … Википедия
AI на минималках: пишем свой Сокобан и учим компьютер его решать
В этой статье я расскажу как написать свою реализацию известной игрушки Сокобан, а также алгоритм для её решения с нуля. Заодно применю на практике некоторые шаблоны проектирования и принципы SOLID.
Предыстория
Я пользуюсь кнопочным телефоном. Из развлечений на нём только радио и единственная игра Сокобан из 15 уровней. Из них я решил только 10 и застрял на одиннадцатом. Как-то раз я целый день ехал в поезде и решал этот злосчастный 11 уровень, но не преуспел. Тогда я решил прибегнуть к помощи компьютера, благо опыт программирования имею достаточный для такой задачи. Поставил цель: самостоятельно написать реализацию с решением этой игрушки. По результатам появилась эта статья.
Тот самый 11 уровень (решение в конце статьи):
Сама игрушка представляет собой прямоугольное 2D-поле, на котором раскиданы ящики, стены и метки. Ящики можно толкать, но не тянуть, в этом вся сложность. Ваша цель: переместить все ящики на клетки с метками. Пример игры:
Пишем реализацию
Давайте не будем усложнять себе задачу и создавать отдельный GUI со спрайтами и редактором уровней. Вместо этого остановимся на консольном варианте а-ля Rogue-like, где уровни будут отрисовываться построчно и загружаться из текстового файла. Сначала нужно придумать какие символы будут обозначать элементы на уровне. Я сделал такой выбор:
Теперь самый ответственный момент — выбор архитектуры приложения. Если ошибиться, то можно сильно повредить всей дальнейшей разработке. В нашем случае идеально подходит шаблон MVC — Модель, Представление, Контроллер. Модель хранит внутреннее игровое состояние и поле, даёт доступ к данным, не знает ничего о контроллере и представлении. Представление только печатает состояние модели в консоль. Контроллер считывает символы с клавиатуры и изменяет модель. Типичная ошибка новичков — добавлять бизнес-логику в контроллер вместо модели. В результате получаются переполненные чужим кодом контроллеры, нарушающие первую букву SOLID. Согласно ей, каждый класс должен брать на себя только одну ответственность. Представление — печатать уровни в консоль, модель — хранить состояние игрушки и логику работы с ним, контроллер — обрабатывать действия пользователя. То есть контроллер не должен знать как именно двигать ящики и игрока по полю, это ответственность модели. Контроллеру всего лишь нужно вызвать соответствующий метод. Ещё хорошо бы скрыть реализации всех трёх сущностей за интерфейсами. Это даёт следующее:
Вторая частая ошибка новичков в ООП — компоненты сами управляют своими зависимостями, например создают экземпляры конкретных реализаций интерфейсов в конструкторах:
Здесь первая зависимость model была установлена как надо, через ссылку в параметре конструктора, а вторая view создана напрямую. Это плохо хотя бы потому, что теперь ConsoleController должен знать не только о View, но и ConsoleView, что повышает зацепление. Изменения ConsoleView могут повлечь за собой изменения в ConsoleController, чего можно избежать, написав вот так:
Теперь класс ConsoleController стало проще тестировать. Суть буквы D в SOLID в том, что класс не должен контролировать как именно удовлетворяются его зависимости. Эта ответственность теперь ложится на клиентов класса. Есть множество механизмов разрешения зависимостей, самый популярный из которых — контейнер зависимостей. Это отдельный модуль, обычно реализованный каким-нибудь фреймворком типа Spring или библиотекой, который сам может прокинуть все необходимые экземпляры в конструкторы или сеттеры. От вас нужно только их объявить.
Нужно придумать что из себя вообще представляет модель игрушки. Посмотрим ещё раз на скриншот, что мы видим?
Было бы логично научить модель саму себя решать, то есть поместить алгоритм поиска решения внутри модели. Однако, если мы захотим иметь несколько таких алгоритмов и сравнивать их между собой, то будет лучше вынести их в отдельный модуль, скрытый за интерфейсом. В этом суть шаблона «Стратегия» — выносить несколько реализаций одной функции в отдельные классы и прятать их под общим интерфейсом, потому что клиенту в большинстве случаев всё равно как именно вычисляется ваша функция, он хочет просто получить результат. У меня получилось вот такая архитектура:
Заметьте, здесь модель представлена не одним классом, а целым пакетом Model. Главный класс Sokoban не скрыт за интерфейсом, потому что представляет единственную реализацию модели игрушки. Метод move() двигает игрока в одну из четырёх сторон. Сам Sokoban можно изменить только вызвав этот метод. Методы getCrates() и getMarks() возвращают неизменяемое представление множеств. Забегая вперёд, скажу что я сразу заложил два алгоритма решения Сокобана: обход графа конфигураций в ширину и поиск оптимального пути от начальной конфигурации до выигрышной с помощью A* (A star algorithm).
Уровни будут загружаться из текстового файла со строками символов клеток, например:
Чтение и парсинг файла лучше тоже вынести в отдельный класс-создатель модели. Здесь идеально подходит шаблон «Абстрактная фабрика». Вкратце: внутри класса CharSokobanFactory пишем код чтения и парсинга файла, создаём игрока, поле, множество меток и ящиков. Важно, чтобы конструктор класса Sokoban оставался чистым, то есть содержал только присвоения зависимостей, это упрощает тестирование:
Вместо стрелок я решил выбрать vi-like раскладку:
Игра считается завершённой, если множества ящиков и меток равны:
Получается такая схема:
С такой архитектурой код контроллера становится очень простым:
Красота, как обычно, в мелочах. Как я уже говорил в начале статьи, контроллер не должен содержать никакой бизнес-логики, только читать команды от пользователя, перенаправлять их модели и отрисовывать представление. Такая реализация как раз не содержит ничего лишнего.
Реализация представления тоже проста до невозможности:
Строка 15 обрабатывает клетку с ящиком на метке. Буква G (Good) специально предназначена, чтобы обозначать ящик, задвинутый на метку. Однако такая клетка никак не моделируется, поэтому существует только в представлении.
Остаётся только научить модель передвигать игрока. Нужно учесть следующие моменты:
Проверить эти условия несложно, в этом поможет флаг «walkable» в перечислении Tile:
Тогда проверка на то, можно ли сходить на данную ячейку сократится до нескольких строк:
Итак, модель умеет передвигать игрока, контроллер обрабатывать команды пользователя, а представление рисовать уровни в консоль. Самое время собрать всех вместе и запустить:
Для теста возьмём вот этот уровень:
В результате получаем именно то, что хотим:
Как и ожидалось, в стены ходить нельзя, ящики передвигаются как надо, игра заканчивается как только третий ящик оказывается на метке. Вот так просто можно написать простую игрушку Сокобан. Однако, самое сложное ещё впереди — нужно научить компьютер её решать.
Пишем свой искусственный интеллект
Что мы делаем когда передвигаем ящики в Сокобане? Мы меняем конфигурацию уровня. Конфигурация здесь это расположение игрока и ящиков на уровне. У каждой конфигурации есть несколько дочерних, в которые можно перейти, передвинув ящик на соседнюю клетку:
Понятно, что когда игрок просто двигается по уровню не трогая ящики, то конфигурация не изменится. Мы не перейдём в другую вершину графа. Можно было бы предположить, что позиция игрока вообще не имеет значения, и в конфигурацию входит только множество точек ящиков, но это не так. Позиция игрока не важна только пока он передвигается по одной компоненте связности внутри уровня. Кроме графа конфигураций, есть ещё граф инцидентных
клеток для конкретной конфигурации, например:
Игрок может перемещаться только по правой компоненте не трогая ящики, конфигурация от этого не изменится. Однако, если поместить игрока на клетку (1:1), он попадёт в левую и решить такой уровень будет невозможно.
Игра в Сокобан представляет собой прогулку по графу конфигураций в поиске выигрышной вершины. Решение — это путь в таком графе от начальной конфигурации до выигрышной.
Рёбра в графе помечены шагами игрока от его исходной позиции до передвижения ящика. Вес ребра это количество таких шагов. Нам интересно не просто определить имеет ли решение конкретный уровень, но ещё и найти это самое решение. В зависимости от уровня такой граф может иметь любую структуру, поэтому нам нужен алгоритм поиска пути, работающий для любых графов. Если забыть что рёбра взвешенные, то отлично подойдёт алгоритм поиска в ширину — Breadth-First Search (BFS).
Поиск решения с помощью BFS
В отличие от своего «кузена» — поиска в глубину (Depth-First Search) — в невзвешанном графе BFS строит кратчайшие пути от исходной вершины до всех достижимых, постепенно выращивая дерево родителей. Кстати, эти два алгоритма отличаются только порядком извлечения вершин из списка. BFS извлекает вершины в порядке очереди (FIFO), а DFS в порядке стека (LIFO), то есть это по сути один и тот же алгоритм. Псевдокод BFS:
Нам нужно уметь порождать все соседние конфигурации из данной. Каждая соседняя конфигурация порождается движением ящика в одну из четырёх сторон. Причём по бокам
клетки должны быть пустыми. Например, если двигать ящик вправо, то надо чтобы игрок мог добраться до клетки слева от ящика и чтобы справа была свободная клетка. Аналогично с вертикальным движением. Также при проверке можно отсекать заведомо проигрышные конфигурации, когда ящик прислоняется к стене без дальнейшей возможности движения:
Комбинируя все замечания, получаем вот такой код:
Обратите внимание, что «порождённая» таким методом копия не меняет множество меток. Кстати, класс Point я специально сделал неизменяемым (immutable). Нет смысла создавать отдельную структуру данных «Граф», заполнять его вершинами и рёбрами, а потом уже запускать BFS, это только пустая трата циклов процессора. Свойства v.p и v.marked можно симулировать ассоциативным словарём и множеством.
Теперь у нас в арсенале есть всё необходимое для реализации самого алгоритма:
Такой алгоритм находит решение, но далеко не факт что оно будет оптимальным, потому что BFS не учитывает вес ребра, то есть рассматривает граф конфигураций как невзвешенный. Чтобы найти наименьший путь во взвешенном графе можно взять, например, алгоритм Дейкстры, однако тут есть одна загвоздка. Понятно, что даже у простого уровня граф конфигураций может быть гиганским, а оптимальный путь чуть ли не единственным. Алгоритм,
который будет рассматривать вообще «весь» граф, будет работать слишком долго. Причём в графе будет много тупиковых ветвей, куда заходить вообще не надо. Было бы здорово указать на это машине.
На помощь приходит алгоритм А* (A star), который по сути является Дейкстрой с одним отличием. А* вводит т.н. эвристическую функцию h оценки расстояния от текущей вершины до решения. Значение h складывается с текущей оценкой пути. Идея следующая — если алгоритм заходит на одну из таких тупиковых ветвей, то большое значение h превысит текущее оптимальное и алгоритм просто дальше не пойдёт. Нужно только придумать достаточно
«хорошую» эвристику. Я взял сумму расстояний ящиков до ближайших к ним меток. Класс AStarSolver реализует описанную логику. Код преводить не буду чтобы не загружать статью, всё есть по адресу.
Выводы
Мы создали свою реализацию игрушки Сокобан, применили на практике шаблоны проектирования «Абстрактная Фабрика», «Фабричный Метод», «Стратегия», рассмотрели принципы S, O и D из SOLID и реализовали алгоритмы BFS и A*.
Done. Moves are: R D R 4D 2L 2U L U D R 2D 2R 2U L R 2U L D L D 2L U 3R U 2R D L D 2L U 2L D R U 2R D R U 3L D R U 2R 3D 2L U D 2R 3U L 2U 2L 2D 3R 3D 2L 2U R 3U 2L 2D L D 2R L 3U 2R 2D 2R U L D 2L 3D 2R 2U 2D 2L 2U R 3L U R 2U 2R 2D L D L U 2R U 2R D 3L 3D 2R 2U 2D 2L 2U R 2U 2R D L D 2L U R L D 2L U R D 2R 3U 2L D
Буду рад любым комментириям как по коду, так и по самой статье. Увидимся!