Игра Сокобан. Создание консольной программы.

ВВЕДЕНИЕ 3
ПОСТАНОВКА ЗАДАЧИ 6
ХОД РАБОТЫ 7
Редактор уровней 7
LevelFile.cs 8
Изменение размера игрового поля, корректность составленного уровня 21
Создание игры Сокобан 37
LabirintForm.cs 38
Game.cs 41
Создание консольной программы для проверки решения игрока 56
BoxSolver.cs 67
Автоходы 73
Режим на двоих в редакторе 76
Игра по сети 82
Phone.cs 83
ЗАКЛЮЧЕНИЕ 97
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 98
ПРИЛОЖЕНИЕ 99

Купить

Sokoban (Soko-Ban, яп. Ж®Ш Сокобан — «кладовщик») — логическая игра-головоломка, в которой игрок передвигает ящики по игровому полю, показанному в виде плана, с целью поставить все ящики на заданные конечные позиции. Только один ящик может быть передвинут за ход, причём герой игры — «кладовщик» — может только толкать ящики, но не тянуть их. Поскольку игру достаточно сложно воссоздать физически, обычно она реализуется в виде компьютерной игры.
Задача решения этой головоломки относится к так называемым NP- трудным задачам, как часть более общего класса задач планирования движения.
Изобретена игра была в 1980-м году, и вскоре ее портировали сначала на Nintendo, а потом и на все известные платформы.Позже под руководством изобретателя этой игры было выпущено несколько официальных сиквелов, главными из которых считаются Sokoban Perfect (1989) и Sokoban Revenge (1991). Они содержат по 360 уровней. Официальная страница игры Сокобан находится по адресу http://www.sokoban.jp . К сожалению, она имеет только японскую версию
Игра быстро стала классической. Сокобан повторил судьбу тетриса, разве что в более скромных масштабах. Есть реализации игры для карманных компьютеров, игровых приставок, мобильных телефонов и, конечно же, для PC. Возникновение клонов стало возможным, потому что автору игры и его компании принадлежат права непосредственно на программу как на конечный продукт, а не на идею. Кроме того, автору принадлежат права на планы уровней первой реализации (в версии 1984 года их было пятьдесят). Поэтому всяческие ремейки, использующие уровни того самого первого Сокобана, являются, строго говоря, незаконными. Мы в своей работе будем использовать только собственные уровни.
Стоит упомянуть и об экзотических вариантах, существующих в Интернете. Например, о гексагональном Сокобане где игровое поле составлено не из квадратов, а из шестиугольников. Такую же форму имеют и ящики, и кладовщик. Есть ряд версий, где изменена конечная цель игры. Например, в игре CyberBox нужно не расставлять ящики по своим местам, а привести фигурку кладовщикана определенный квадрат, являющийся выходом из лабиринта. Изначально этот выход основательно загроможден ящиками, и добраться до него можно, только растолкав их в разные стороны. Есть ряд игр, где задача усложняется тем, что каждый ящик требуется поместить на свое, строго определенное место.
В бывшем СССР игра была известна благодаря клонам KURTAN и «Мудрый крот». KURTAN содержал дополнительные игровые элементы — деньги за решение уровня в одном из ящиков, которые можно было использовать для решения других, двери и ключи для их открытия, необходимость выйти из уровня по коридору, тонус игрового персонажа и другие.Известна также и адаптация "Склад №18" для Dendy, выпущенная Александром Чудовым, программистом из Ульяновска, в 1997 году.
Трудность прохождения Сокобана заключается не только в уровне ветвления дерева вариантов ходов (многие исследователи сравнивают эту игру по сложности с шахматами), но и в огромной глубине поиска по этому дереву. Для того чтобы найти верное решение, требуется перебрать очень много вариантов. Необходимое количество "правильных" ходов, ведущих к выигрышу, на некоторых уровнях может достигать тысячи. Однако опытные игроки, вооруженные эвристикой, могут быстро отсеять в мозгу заведомо тупиковые варианты, тем самым существенно сузив область поиска.Сокобан представляет интерес и для исследователей искусственного интеллекта: хорошо бы построить такого робота, который выполнял бы задачу «кладовщика» и, перемещая ящики по игровому полю, ставил их на определенные места. При этом нужно, чтобы он выполнял свою задачу в оптимально короткие сроки за минимальное количество шагов.Некоторые (заметьте, только некоторые) уровни игры могут быть решены "автоматически" с помощью определенных итерационных поисковых алгоритмов, таких, как поиск кратчайшего пути в ширину, который используется в данной работе. Многие уровни всё же не проходятся без помощи человека.
За годы своего существования Сокобан превратился из простой логической игрушки в культовый объект. С каждым годом появляются все новые и новые версии этой игры. По нему пишут диссертации и научные статьи. Он оброс различными вспомогательными программами и файловыми форматами. Ну и кроме всего прочего, Сокобан - это неплохой способ убить время и потренировать мозги.
Купить