Xonix на Javascript с картинками

Автор: admin от 31-07-2015, 18:08, посмотрело: 1002

Xonix — популярная игра времен DOS, клон видеоигры Qix.

На javascript Xonix уже был портирован несколько раз. Лучшая и наиболее приближенная к оригиналу из существующих реализаций на сегодняшний день, пожалуй, вот эта. Ее я поначалу пытался приспособить для своей реализации/модификации… Но, к сожалению, код даже после деобфускации так и не стал понятным (во всяком случае для меня). К тому же, насколько я смог понять, код там местами не совсем эффективен, либо вовсе устаревший. Так что пришлось все писать с нуля.

В результате у меня получился такой вот «свой» Xonix, с картинками и ответами.

Xonix на Javascript с картинками


Демо | Исходники

Код получился довольно объемным, поэтому здесь я буду объяснять не все, а только наиболее важные (с моей точки зрения) моменты.

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

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

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

Движение всех объектов (курсора и точек) происходит строго по ячейкам, так что в каждый момент времени каждый объект занимает ровно одну ячейку. Такая структура игрового поля значительно упрощает реализацию игры. Сложность представляет только определение «завоеванных» областей, образующихся при пересечении курсором «моря», но об этом позже.

Движение объектов


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

В Xonix у любого объекта есть всего 4 варианта направления движения: для курсора — вверх/вниз/вправо/влево, для точки (обоих типов) — то же самое, только по диагонали. Объединяем эти варианты в множество возможных направлений, которые будем задавать в градусах. Получаем 8 углов движения: от 0 до 315 градусов с шагом 45. Каждому значению угла ставим в соответствие пару координат вектора направления движения. В результате получаем такую структуру, которую будем использовать при расчете движения:


Метод get возвращает для данного угла (в градусах) соответствующий вектор движения. Метод find делает обратное: для данного вектора движения (не обязательно единичного) возвращает соответствующий угол в градусах, либо ближайший к нему из доступных.

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

Для расчета столкновений точек с курсором, отскока точек от границы «своей» области и некоторых других вещей нам понадобится матрица состояний всех ячеек — двумерный массив (n+4) * (m+4),
где (n+4), (m+4) — соответственно ширина и высота игрового поля в ячейках, а первый элемент матрицы соответствует ячейке в левом верхнем углу игрового поля.

Каждый элемент будет хранить состояние соответствующей ячейки, включающее в себя 2 признака: тип области, к которой она относится (море/суша), а также то, проходит ли по ней в данный момент «след» от движения курсора по «морю». Храниться это состояние будет в битовом поле из двух битов. Для этого нам нужно объявить две константы-маски для каждого признака соответственно:

var CA_CLEAR = 1  0; // ячейка очищена, т.е. относится к суше
var CA_TRAIL = 1  1; // ячейка - часть следа движения курсора по "морю"

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

i = n * (y + 2) + x + 2;
x = i % n - 2;
y = Math.floor(i / n) - 2

Для расчета отскока точки («морской» или «сухопутной») от границы «своей» области нам нужно знать состояние трех ячеек, не считая ячейки самой точки. Ниже с помощью псевдографики показано положение этих ячеек относительно текущей ячейки точки при угле движения в 45 градусов.


OOO
OX1
O23

Ячейка точки отмечена крестиком, а искомые ячейки цифрами 1, 2, 3. Нолики просто изображают соседние ячейки. Направление движения точки в данном случае получается юго-восточное, поскольку ось ординат (Y) сетки у нас направлена вниз.

Отскок от границы имеет место, если хотя бы в одной из указанных трех ячеек тип области противоположен типу точки. Т.е. если, например, точка «морская», то одна из этих ячеек должна быть «сухопутной». При этом, если данное условие выполняется только в одной из ячеек 1 или 2 (но не в обоих), то к углу движения прибавляется соответственно +90 или -90 градусов. В противном случае угол движения изменяется на противоположный (+180 градусов).

При любом другом угле движения логика отскока очевидно будет точно такой же.

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

Определение столкновения «сухопутной» точки с курсором тривиально. Просто проверяем контакт точки с курсором, сравнивая координаты ячеек точки и курсора. Определение столкновения «морской» точки с курсором чуть сложнее: нам нужно проверить не только контакт самой точки с курсором, но и касание следа движения курсора. Для этого используем второй бит состояния ячеек: проверяем его у всех соседних с точкой ячеек.

Определение «завоеванных» областей


Как уже упоминалось, самое сложное в реализации — определение «завоеванных» у «моря» областей. Это замкнутые области, образующиеся в результате пересечения курсором «моря», внутри которых нет «морских» точек. В большинстве случаев при этом образуются две замкнутые области, получаемые разделением (следом движения курсора) доступной «морской» области на две части, из которых «завоеванной» становится только одна либо ни одной (см. скриншот 1). Но в некоторых, особенно сложных, случаях может образоваться сразу множество замкнутых (см. скриншот 2) и в том числе «завоеванных» областей. Кроме того, возможна ситуация, когда след курсора сам по себе образует замкнутую область (см. скриншот 3).

Xonix на Javascript с картинками
Скриншот 1

Xonix на Javascript с картинками
Скриншот 2

Xonix на Javascript с картинками
Скриншот 3

Итак, нам нужно найти все такие замкнутые области, после чего определить тип каждой из них («завоеванная»/«незавоеванная»).

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

Но есть и другой способ (который я в итоге и выбрал): использовать контуры замкнутых областей, образующихся при пересечении курсором «моря». Под контуром имеется в виду замкнутая ломаная толщиной в одну ячейку. Если известен контур замкнутой области, то остается только найти ее содержимое, т.е. все ячейки внутри нее. Но как найти эти контуры?

Контуры замкнутых областей


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

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

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

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

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

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

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

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

Содержимое и тип замкнутой области


Теперь, когда контуры замкнутых областей найдены, необходимо по каждому контуру определить содержимое соответствующей области (все содержащиеся в ней ячейки) и ее тип («завоевана» или нет). Поскольку в Xonix курсор может двигаться только вертикально/горизонтально, то каждая замкнутая область может быть разбита на несколько прямоугольников разных размеров. Таким образом задача определения содержимого замкнутой области сводится к нахождению составляющих ее прямоугольников. Кстати, этим самым мы «убиваем» сразу двух «зайцев»: облегчаем подсчет точек внутри замкнутых областей, а также закрашивание (вернее стирание) «завоеванных» областей.

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

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

На первой итерации находим сторону (отрезок) многоугольника с наибольшей длиной, являющуюся частью выступающего прямоугольника. Если таких отрезков несколько, выбираем любой из них. Найденный отрезок будет одной из сторон искомого прямоугольника. Теперь нам нужно найти остальные его стороны. Для этого берем отрезки, исходящие из обоих концов найденной стороны перпендикулярно к ней, и выбираем самый короткий из них. Это будет вторая сторона прямоугольника. Чтобы найти третью сторону, нужно найти (ортогональную) проекцию второго конца данного отрезка на второй из перпендикулярных к первой стороне отрезков. Соединяем найденную точку с соответствующим концом первой стороны и получаем третью сторону. Отсюда получаем весь искомый выступающий прямоугольник. Теперь нам нужно отсечь его от исходного многоугольника. Для этого нужно удалить из многоугольника первый и второй найденные отрезки и соответствующие им вершины, после чего добавить найденную точку-проекцию, соединив ее с вершиной, которая раньше соединялась со вторым найденным отрезком. В результате получаем многоугольник, имеющий на две вершины меньше, чем исходный.

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

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

Рассмотрим процесс разбиения на прямоугольники на конкретном примере.
Пусть мы имеем многоугольник ABCDEFGHIJKL (см. рис. 1), представляющий собой контур области. Применим пошагово описанный алгоритм разбиения.

1. Находим сторону многоугольника ABCDEFGHIJKL с наибольшей длиной. Это отрезок CD с длиной 4. Но он нам не подходит, т.к. не является частью выступающего прямоугольника. Поэтому игнорируем его и ищем дальше. Находим 3 отрезка с длиной 3: AL, FG, GH. GH нам не подходит по той же причине, что и CD. Так что остаются отрезки AL, FG. Выбираем любой из них. Пусть это будет AL. Перпендикулярные к нему отрезки — AB и KL, из них самый короткий — AB. Находим проекцию точки B на отрезок KL — это точка M (см. рис. 2). Таким образом получаем отсекаемый прямоугольник — ABML. После его отсечения остается многоугольник CDEFGHIJKM.

2. Находим сторону многоугольника CDEFGHIJKM с наибольшей длиной. Это отрезок FG с длиной 3… Отсекаемый прямоугольник — FGNE (см. рис. 2). После его отсечения остается многоугольник CDNHIJKM.

3. Находим сторону многоугольника CDNHIJKM с наибольшей длиной. Это уже знакомый нам отрезок CD с длиной 4… Отсекаемый прямоугольник — CDNO. После его отсечения остается многоугольник OHIJKM.

4. Находим сторону многоугольника OHIJKM с наибольшей длиной. Таких сторон две. Это отрезки OH и HI с длиной 2. Выбираем первый из них — OH… Отсекаемый прямоугольник — OHPM. После его отсечения остается прямоугольник KPIJ. Теперь отсекать уже нечего. Так что на этом алгоритм завершается.

В результате мы получаем 5 прямоугольников, составляющих содержимое замкнутой области: ABML, FGNE, CDNO, OHPM и KPIJ (см. рис. 2).

Xonix на Javascript с картинками
Рис. 1

Xonix на Javascript с картинками
Рис. 2

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

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

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

Все найденные «завоеванные» области подлежат стиранию, которое реализуется еще тривиальнее: просто стираем (методом clearRect) все прямоугольники, составляющие данную область.

Анимация, управление игрой и прочее


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

Для тех, кому это интересно, ниже приведен весь код игры. Впрочем, ценность его сомнительна, т.к. комментариев там — кот наплакал. Но основную логику я, надеюсь, объяснил.

Категория: Программирование » Game Development

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

Добавление комментария

Имя:*
E-Mail:
Комментарий:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера
Введите два слова, показанных на изображении: *