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

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

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

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



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

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

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

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

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

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

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


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

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

    Фрагмент кода
    dirset = {
        vecs: {
            0: [1, 0], 45: [1, 1], 90: [0, 1], 135: [-1, 1],
            180: [-1, 0], 225: [-1, -1], 270: [0, -1], 315: [1, -1]
        },
        get: function(v) {
            return v in this.vecs? this.vecs[v] : [0, 0];
        },
        find: function(x, y) {
            x = x == 0? 0 : (x > 0? 1 : -1);
            y = y == 0? 0 : (y > 0? 1 : -1);
            for (var v in this.vecs) {
                var vec = this.vecs[v];
                if (vec[0] == x && vec[1] == y) return parseInt(v);
            }
            return false;
        }
    };
    

    Метод 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).

    Скриншот 1

    Скриншот 2

    Скриншот 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).

    Рис. 1

    Рис. 2

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

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

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

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

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


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

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

    Код игры
    // requestAnimationFrame/cancelAnimationFrame polyfill:
    (function() {
        var tLast = 0;
        var vendors = ['webkit', 'moz'];
        for(var i = 0; i < vendors.length && !window.requestAnimationFrame; ++i) {
            var v = vendors[i];
            window.requestAnimationFrame = window[v+'RequestAnimationFrame'];
            window.cancelAnimationFrame = window[v+'CancelAnimationFrame'] ||
                window[v+'CancelRequestAnimationFrame'];
        }
        if (!window.requestAnimationFrame)
            window.requestAnimationFrame = function(callback, element) {
                var tNow = Date.now();
                var dt = Math.max(0, 17 - tNow + tLast);
                var id = setTimeout(function() { callback(tNow + dt); }, dt);
                tLast = tNow + dt;
                return id;
            };
        if (!window.cancelAnimationFrame)
            window.cancelAnimationFrame = function(id) {
                clearTimeout(id);
            };
    }());
    
    (function() {
    
        window.picxonix = function(v1, v2) {
            if (typeof v1 != 'string') {
                return init(v1, v2);
            }
            switch (v1) {
                case 'level': // начать новый уровень
                    loadLevel(v2);
                    break;
                case 'end': // закончить уровень
                    endLevel(v2);
                    break;
                case 'play': // пауза/возобновление игры
                    setPlayMode(v2);
                    break;
                case 'cursorDir': // угол движения курсора
                    typeof v2 == 'string'? setDir(v2) : setDirToward(v2);
                    break;
                case 'cursorSpeed': // скорость движения курсора
                    setCursorSpeed(v2);
                    break;
                case 'enemySpeed': // скорость движения точек
                    setEnemySpeed(v2);
                    break;
                case 'enemySpawn': // увеличить число сухопутных точек
                    spawn();
                    break;
                case 'state': // текущее состояние уровня
                    return buildLevelState();
                default:
            }
            return 0;
        }
    
        var cfgMain = {
            width: 600,
            height: 400,
            sizeCell: 10,
            colorFill: '#000000',
            colorBorder: '#00aaaa',
            colorBall: '#ffffff',
            colorBallIn: '#000000',
            colorWarder: '#000000',
            colorWarderIn: '#f80000',
            colorCursor: '#aa00aa',
            colorCursorIn: '#00aaaa',
            colorTrail: '#a800a8',
            timeoutCollision: 1000,
            callback: null,
            callbackOnFrame: false
        };
        var cfgLevel = {
            nBalls: 1,
            nWarders: 1,
            speedCursor: 5,
            speedEnemy: 5
        };
        // cell attributes:
        var CA_CLEAR = 1 << 0;
        var CA_TRAIL = 1 << 1;
        // размеры:
        var sizeCell;
        var width, height;
        // ресурсы:
        var elContainer;
        var ctxPic;
        var ctxMain;
        var imgPic;
        var imgBall;
        var imgWarder;
        var imgCursor;
        // объекты игры:
        var dirset;
        var cellset;
        var cursor;
        var aBalls = [], aWarders = [];
        var nBalls = 0, nWarders = 0;
        // текущее состояние уровня:
        var idFrame = 0;
        var tLevel = 0;
        var tLastFrame = 0;
        var tLocked = 0;
        var bCollision = false;
        var bConquer = false;
        var dirhash = {
            'left': 180, 'right': 0, 'up': 270, 'down': 90, 'stop': false
        };
    
        function init(el, opts) {
            if (elContainer || !el || !el.appendChild) return false;
            elContainer = el;
            // установка общих настроек игры:
            merge(cfgMain, opts);
            if (!cfgMain.sizeCell) return false;
            sizeCell = cfgMain.sizeCell;
            if (typeof cfgMain.callback != 'function') cfgMain.callback = null;
            // установка настроек уровня:
            if (opts.speedCursor ^ opts.speedEnemy) {
                opts.speedCursor = opts.speedEnemy = Math.max(opts.speedCursor || 0, opts.speedEnemy || 0);
            }
            merge(cfgLevel, opts);
            setLevelData(cfgMain.width, cfgMain.height);
            var oWrap = document.createElement('div');
            oWrap.style.position = 'relative';
            // создаем канвас фона (картинки):
            (function() {
                var canvas = document.createElement('canvas');
                ctxPic = canvas.getContext('2d');
                canvas.width = width;
                canvas.height = height;
                canvas.style.position = 'absolute';
                canvas.style.left = canvas.style.top = (2*sizeCell) + 'px';
                ctxPic.fillStyle = cfgMain.colorTrail;
                ctxPic.fillRect(0, 0, width, height);
                oWrap.appendChild(canvas);
            }());
            // создаем канвас игрового поля:
            (function() {
                var canvas = document.createElement('canvas');
                ctxMain = canvas.getContext('2d');
                canvas.width = width+ 4*sizeCell;
                canvas.height = height+ 4*sizeCell;
                canvas.style.position = 'absolute';
                canvas.style.left = canvas.style.top = 0;
                fillCanvas();
                ctxMain.fillStyle = cfgMain.colorFill;
                ctxMain.fillRect(2*sizeCell, 2*sizeCell, width, height);
                oWrap.appendChild(canvas);
            }());
            elContainer.appendChild(oWrap);
            // создаем временный канвас:
            var canvas = document.createElement('canvas');
            var ctxTmp = canvas.getContext('2d');
            canvas.width = sizeCell;
            canvas.height = sizeCell;
            // создаем изображение морской точки:
            var r = sizeCell / 2, q = sizeCell / 4;
            ctxTmp.clearRect(0, 0, sizeCell, sizeCell);
            ctxTmp.beginPath();
            ctxTmp.arc(r, r, r, 0, Math.PI * 2, false);
            ctxTmp.fillStyle = cfgMain.colorBall;
            ctxTmp.fill();
            if (cfgMain.colorBallIn) {
                ctxTmp.beginPath();
                ctxTmp.arc(r, r, q, 0, Math.PI * 2, false);
                ctxTmp.fillStyle = cfgMain.colorBallIn;
                ctxTmp.fill();
            }
            imgBall = new Image();
            imgBall.src = ctxTmp.canvas.toDataURL();
            function prepareSquare(colorOut, colorIn) {
                ctxTmp.clearRect(0, 0, sizeCell, sizeCell);
                ctxTmp.fillStyle = colorOut;
                ctxTmp.fillRect(0, 0, sizeCell, sizeCell);
                if (colorIn) {
                    ctxTmp.fillStyle = colorIn;
                    ctxTmp.fillRect(q, q, sizeCell - r, sizeCell - r);
                }
            }
            // создаем изображение сухопутной точки:
            prepareSquare(cfgMain.colorWarder, cfgMain.colorWarderIn);
            imgWarder = new Image();
            imgWarder.src = ctxTmp.canvas.toDataURL();
            // создаем изображение курсора:
            prepareSquare(cfgMain.colorCursor, cfgMain.colorCursorIn);
            imgCursor = new Image();
            imgCursor.src = ctxTmp.canvas.toDataURL();
            return {width: width+ 4*sizeCell, height: height+ 4*sizeCell};
        }
    
        function loadLevel(data) {
            if (tLevel || tLastFrame || !data || !data.image) return;
            if (!data.image) return;
            var img = new Image();
            img.onload = function() {
                applyLevel(img, data);
            };
            img.src = data.image;
        }
    
        function applyLevel(img, data) {
            imgPic = img;
            merge(cfgLevel, data, true);
            setLevelData(img.width, img.height);
            ctxMain.canvas.width = width+ 4*sizeCell;
            ctxMain.canvas.height = height+ 4*sizeCell;
            fillCanvas();
            cellset.reset();
            ctxPic.canvas.width = width;
            ctxPic.canvas.height = height;
            ctxPic.drawImage(imgPic, 0, 0, width, height, 0, 0, width, height);
            var pos = cellset.placeCursor();
            cursor.reset(pos[0], pos[1]);
            aBalls = []; aWarders = [];
            var i, aPos;
            aPos = cellset.placeBalls(nBalls);
            for (i = 0; i < nBalls; i++)
                aBalls.push(new Enemy(aPos[i][0], aPos[i][1], false));
            aPos = cellset.placeWarders(nWarders);
            for (i = 0; i < nWarders; i++)
                aWarders.push(new Enemy(aPos[i][0], aPos[i][1], true, 45));
            tLevel = Date.now();
            tLastFrame = 0;
            startLoop();
        }
    
        function endLevel(bClear) {
            if (tLastFrame) return;
            tLevel = 0;
            if (!bClear) return;
            fillCanvas();
            ctxMain.clearRect(2*sizeCell, 2*sizeCell, width, height);
        }
    
        function setLevelData(w, h) {
            if (w) width = w - w % (2*sizeCell);
            if (h) height = h - h % (2*sizeCell);
            if (cfgLevel.nBalls) nBalls = cfgLevel.nBalls;
            if (cfgLevel.nWarders) nWarders = cfgLevel.nWarders;
        }
    
        function setPlayMode(bOn) {
            if (bOn ^ !tLastFrame) return;
            tLastFrame? endLoop() : startLoop();
        }
    
        function setDir(key) {
            if (!tLastFrame) return;
            if (key in dirhash) cursor.setDir(dirhash[key]);
        }
    
        function setDirToward(pos) {
            if (!tLastFrame || !pos || pos.length < 2) return;
            var xc = Math.floor(pos[0] / sizeCell) - 2,
                yc = Math.floor(pos[1] / sizeCell) - 2;
            var b = cellset.isPosValid(xc, yc);
            if (!b) return;
            var posCr = cursor.pos(), dirCr = cursor.getDir(), dir = false;
            if (dirCr === false) {
                var dx = xc - posCr[0], dy = yc - posCr[1],
                    dc = Math.abs(dx) - Math.abs(dy);
                if (dc == 0) return;
                dir = dirset.find(dx, dy);
                if (dir % 90 != 0) {
                    var dir1 = dir-45, dir2 = dir+45;
                    dir = dir1 % 180 == 0 ^ dc < 0? dir1 : dir2;
                }
            }
            else {
                var delta = dirCr % 180? xc - posCr[0] : yc - posCr[1];
                if (!delta) return;
                dir = (delta > 0? 0 : 180) + (dirCr % 180? 0 : 90);
            }
            cursor.setDir(dir);
        }
    
        function setCursorSpeed(v) {
            if (v > 0) cfgLevel.speedCursor = v;
        }
    
        function setEnemySpeed(v) {
            if (v > 0) cfgLevel.speedEnemy = v;
        }
    
        function startLoop() {
            if (!tLevel) return;
            idFrame = requestAnimationFrame(loop);
        }
    
        function endLoop() {
            if (idFrame) cancelAnimationFrame(idFrame);
            tLastFrame = idFrame = 0;
        }
    
        // Главный цикл анимации
        function loop(now) {
            var dt = tLastFrame? (now - tLastFrame) / 1000 : 0;
            bCollision = bConquer = false;
            if (!tLastFrame || update(dt)) {
                render();
                tLastFrame = now;
            }
            if (bCollision) {
                lock();
                cfgMain.callback && cfgMain.callback(1);
                return;
            }
            if (bConquer) {
                bConquer = false;
                tLastFrame = 0;
                cellset.conquer();
                if (cfgMain.callback && cfgMain.callback(2))
                    return;
            }
            else
                cfgMain.callback && cfgMain.callbackOnFrame && cfgMain.callback(0);
            startLoop();
        }
    
        function update(dt) {
            var distCursor = Math.round(dt * cfgLevel.speedCursor),
                distEnemy = Math.round(dt * cfgLevel.speedEnemy);
            if (!(distCursor >= 1 || distEnemy >= 1)) return false;
            cursor.update(distCursor);
            var i;
            for (i = 0; i < nBalls; i++) aBalls[i].update(distEnemy);
            for (i = 0; i < nWarders; i++) aWarders[i].update(distEnemy);
            return true;
        }
    
        function render() {
            cellset.render();
            cursor.render();
            var i;
            for (i = 0; i < nBalls; i++) aBalls[i].render();
            for (i = 0; i < nWarders; i++) aWarders[i].render();
        }
    
        function lock() {
            tLastFrame = 0;
            bCollision = false;
            var posCr = cursor.pos();
            cellset.add2Trail(posCr[0], posCr[1], false);
            setTimeout(unlock, cfgMain.timeoutCollision);
        }
    
        function unlock() {
            if (!tLevel) return;
            cellset.clearTrail();
            var pos = cellset.placeCursor();
            cursor.reset(pos[0], pos[1], true);
            var aPos = cellset.placeWarders(nWarders);
            for (var i = 0; i < nWarders; i++)
                aWarders[i].reset(aPos[i][0], aPos[i][1]);
            startLoop();
        }
    
        function spawn() {
            if (!tLevel) return;
            var pos = cellset.placeSpawned();
            if (!pos) return;
            aWarders.push(new Enemy(pos[0], pos[1], true));
            nWarders++;
        }
    
        function buildLevelState() {
            return {
                play: Boolean(tLastFrame),
                posCursor: cursor.pos(),
                warders: nWarders,
                speedCursor: cfgLevel.speedCursor,
                speedEnemy: cfgLevel.speedEnemy,
                cleared: cellset.getPercentage()
            };
        }
    
        function fillCanvas() {
            ctxMain.fillStyle = cfgMain.colorBorder;
            ctxMain.fillRect(0, 0, width+ 4*sizeCell, height+ 4*sizeCell);
        }
    
        function drawCellImg(img, x, y) {
            ctxMain.drawImage(img,
                0, 0, sizeCell, sizeCell,
                (x+2)*sizeCell, (y+2)*sizeCell, sizeCell, sizeCell
            );
        }
    
        function clearCellArea(x, y, w, h) {
            ctxMain.clearRect(
                (x+2)*sizeCell, (y+2)*sizeCell, (w || 1)* sizeCell, (h || 1)* sizeCell
            );
        }
    
        function fillCellArea(color, x, y, w, h) {
            ctxMain.fillStyle = color;
            ctxMain.fillRect(
                (x+2)*sizeCell, (y+2)*sizeCell, (w || 1)* sizeCell, (h || 1)* sizeCell
            );
        }
    
        // Множество доступных направлений:
        dirset = {
            vecs: {
                0: [1, 0], 45: [1, 1], 90: [0, 1], 135: [-1, 1], 180: [-1, 0], 225: [-1, -1], 270: [0, -1], 315: [1, -1]
            },
            get: function(v) {
                return v in this.vecs? this.vecs[v] : [0, 0];
            },
            find: function(x, y) {
                x = x == 0? 0 : (x > 0? 1 : -1);
                y = y == 0? 0 : (y > 0? 1 : -1);
                for (var v in this.vecs) {
                    var vec = this.vecs[v];
                    if (vec[0] == x && vec[1] == y) return parseInt(v);
                }
                return false;
            }
        };
    
        // Матрица ячеек игрового поля:
        cellset = {
            nW: 0,
            nH: 0,
            nWx: 0,
            nCleared: 0,
            dirTrail: 0,
            iPreTrail: 0,
            aCells: [],
            aTrail: [],
            aTrailNodes: [],
            aTrailRects: [],
            reset: function() {
                var nW = this.nW = Math.floor(width / sizeCell);
                var nH = this.nH = Math.floor(height / sizeCell);
                var n = (this.nWx = nW+4)* (nH+4);
                this.nCleared = 0;
                this.aCells = [];
                var aAll = [];
                for (var i = 0; i < n; i++) {
                    var pos = this.pos(i), x = pos[0], y = pos[1];
                    this.aCells.push(x >= 0 && x < nW && y >= 0 && y < nH? 0 : CA_CLEAR);
                    aAll.push(i);
                }
                fillCellArea(cfgMain.colorFill, 0, 0, nW, nH);
            },
            render: function() {
                if (this.aTrailRects.length) {
                    for (var i = this.aTrailRects.length-1; i >= 0; i--) {
                        fillCellArea.apply(null, [cfgMain.colorFill].concat(this.aTrailRects[i]));
                    }
                    this.aTrailRects = [];
                }
            },
            isPosIn: function(x, y) {
                return x >= 0 && x < this.nW && y >= 0 && y < this.nH;
            },
            isPosValid: function(x, y) {
                return x >= -2 && x < this.nW+2 && y >= -2 && y < this.nH+2;
            },
            find: function(x, y) {
                return this.isPosValid(x, y) ? (this.nWx)*(y+2) + x+2 : -1;
            },
            pos: function(i) {
                return [i % this.nWx - 2, Math.floor(i / this.nWx)-2];
            },
            posMap: function(arr) {
                var _this = this;
                return arr.map(function(v) { return _this.pos(v) });
            },
            value: function(x, y) {
                var i = this.find(x,y);
                return i >= 0? this.aCells[i] : 0;
            },
            set: function(x, y, v) {
                var i = this.find(x,y);
                if (i >= 0) this.aCells[i] = v;
                return i;
            },
            setOn: function(x, y, v) {
                var i = this.find(x,y);
                if (i >= 0) this.aCells[i] |= v;
                return i;
            },
            setOff: function(x, y, v) {
                var i = this.find(x,y);
                if (i >= 0) this.aCells[i] &= ~v;
                return i;
            },
            placeCursor: function() {
                return [Math.floor(this.nW/2), -2];
            },
            placeBalls: function(n) {
                var a = [], ret = [];
                for (var i = 0; i < n; i++) {
                    var k;
                    do k = Math.floor(Math.random() * this.nW * this.nH);
                    while (a.indexOf(k) >= 0);
                    a.push(k);
                    var x = k % this.nW, y = Math.floor(k / this.nW);
                    ret.push([x, y]);
                }
                return ret;
            },
            placeWarders: function(n) {
                var z;
                var aPos = [
                    [Math.floor(this.nW/2), this.nH+1],
                    [-1, this.nH+1], [this.nW, this.nH+1], [-1, -2], [this.nW, -2],
                    [-1, z = Math.floor(this.nH/2)], [this.nW, z],
                    [z = Math.floor(this.nW/4), this.nH+1], [3*z, this.nH+1]
                ];
                var i0 = (n+ 1)% 2;
                return aPos.slice(i0, Math.min(n+ i0, 9));
            },
            placeSpawned: function() {
                if (nWarders >= 9) return false;
                function dist(pos1, pos2) {
                    return Math.pow(pos1[0]- pos2[0], 2) + Math.pow(pos1[1]- pos2[1], 2);
                }
                function find(pos0) {
                    var n = nWarders;
                    for (var l = 0; l < x0; l++) {
                        for (var dx = -1; dx <= 1; dx+= 2) {
                            var p = [pos0[0]+ l* dx, pos0[1]];
                            for (var i = 0; i < n && dist(aWarders[i].pos(), p) >= 4; i++) ;
                            if (i >= n) return p;
                        }
                    }
                    return pos0;
                }
                var x0 = Math.floor(this.nW/2);
                var aPos = [[x0, this.nH+1], [x0, -2]];
                var posCr = cursor.pos();
                var posSt = dist(aPos[0], posCr) > dist(aPos[1], posCr)? aPos[0] : aPos[1];
                var ret = find(posSt);
                return ret;
            },
            applyRelDirs: function(x, y, dir, aDeltas) {
                var ret = [];
                for (var n = aDeltas.length, i = 0; i < n; i++) {
                    var d = (dir + aDeltas[i] + 360) % 360;
                    var vec = dirset.get(d), xt, yt;
                    ret.push([xt = x + vec[0], yt = y + vec[1], d, this.value(xt, yt)]);
                }
                return ret;
            },
            add2Trail: function(x, y, dir) {
                var i = this.setOn(x, y, CA_TRAIL);
                if (i < 0) return;
                var n = this.aTrail.length;
                if (!n || dir !== this.dirTrail) {
                    var iNode = n? this.aTrail[n-1] : i;
                    if (!n || iNode != this.aTrailNodes[this.aTrailNodes.length-1])
                        this.aTrailNodes.push(iNode);
                    if (!n) {
                        var aPos = this.applyRelDirs(x, y, dir, [180]);
                        this.iPreTrail = this.find(aPos[0][0], aPos[0][1]);
                    }
                }
                this.aTrail.push(i);
                this.dirTrail = dir;
            },
            lastTrailLine: function() {
                var pos0 = this.pos(this.aTrailNodes[this.aTrailNodes.length-1]),
                    pos = this.pos(this.aTrail[this.aTrail.length-1]);
                return [
                    Math.min(pos[0], pos0[0]), Math.min(pos[1], pos0[1]),
                    Math.abs(pos[0] - pos0[0])+1, Math.abs(pos[1] - pos0[1])+1
                ];
            },
            clearTrail: function() {
                this.aTrailRects = this._buildTrailRects();
                for (var n = this.aTrail.length, i = 0; i < n; i++) {
                    this.aCells[this.aTrail[i]] &= ~CA_TRAIL;
                }
                this.aTrail = []; this.aTrailNodes = [];
            },
            getPreTrail: function() {
                return this.iPreTrail;
            },
            conquer: function() {
                var nTrail = this.aTrail.length;
                if (!nTrail) return;
                if (nTrail > 1)
                    this.aTrailNodes.push(this.aTrail[nTrail-1]);
                var aConqRects = this._conquer() || this._buildTrailRects();
                this.aTrail = []; this.aTrailNodes = [];
                if (!aConqRects || !aConqRects.length) return;
                for (var n = aConqRects.length, i = 0; i < n; i++) {
                    var rect = aConqRects[i];
                    var x0 = rect[0], y0 = rect[1], w = rect[2], h = rect[3];
                    for (var x = 0; x < w; x++) {
                        for (var y = 0; y < h; y++) {
                            if (this.value(x + x0, y + y0, CA_CLEAR) & CA_CLEAR) continue;
                            this.set(x + x0, y + y0, CA_CLEAR);
                            this.nCleared++;
                        }
                    }
                }
                for (i = 0; i < n; i++) {
                    clearCellArea.apply(null, aConqRects[i]);
                }
                aConqRects = [];
            },
            getPercentage: function() {
                return this.nCleared / (this.nW * this.nH) * 100;
            },
            _conquer: function() {
                var nTrail = this.aTrail.length, nNodes = this.aTrailNodes.length;
                var dz = Math.abs(this.aTrailNodes[0] - this.aTrailNodes[nNodes-1]);
                var aOutlineset = [], bClosedTrail = false;
                if (bClosedTrail = nNodes >= 4 && dz == 1 || dz == this.nWx) {
                    aOutlineset.push([this.aTrailNodes, 1]);
                }
                var bAddTrail = false;
                var posPre = this.pos(this.iPreTrail), posCr = cursor.pos();
                var aDeltas = [-90, 90];
                for (var d = 0; d < 2; d++) {
                    var dd = aDeltas[d];
                    var k = 0;
                    var sum = 0, bSum = false, bEndAtNode = false;
                    for (var l = 0; l < nTrail && sum < nTrail; l++) {
                        var iStart = this.aTrail[l];
                        var pos = this.pos(iStart);
                        var pos0 = l? this.pos(this.aTrail[l - 1]) : posPre;
                        var x = pos[0], y = pos[1];
                        var dir = (dirset.find(x - pos0[0], y - pos0[1]) + dd + 360) % 360;
                        var aDirs = bEndAtNode? [] : [dir];
                        if (this.aTrailNodes.indexOf(iStart) >= 0) {
                            var pos2 = l < nTrail - 1? this.pos(this.aTrail[l + 1]) : posCr;
                            dir = (dirset.find(pos2[0] - x, pos2[1] - y) + dd + 360) % 360;
                            if (dir != aDirs[0]) aDirs.push(dir);
                        }
                        if (this.aTrail[l] == this.aTrailNodes[k+1]) ++k;
                        var ret = 0;
                        for (var nDs = aDirs.length, j = 0; j < nDs && !ret; j++) {
                            dir = aDirs[j];
                            var vec = dirset.get(dir);
                            var xt = x + vec[0], yt = y + vec[1];
                            var v = this.value(xt, yt);
                            if (v & CA_CLEAR || v & CA_TRAIL) continue;
                            ret = this._outline(xt, yt, dir);
                            if (!ret || ret.length < 3) return false;
                        }
                        bEndAtNode = false;
                        if (!ret) continue;
                        var len = ret[0], aNodes = ret[1], bClosed = ret[2], iEnd = aNodes[aNodes.length-1];
                        if (bClosed) {
                            aOutlineset.push([aNodes, len]);
                            bSum = true;
                            continue;
                        }
                        var aXtra = [iStart];
                        for (var i = l+1; i < nTrail && this.aTrail[i] != iEnd; i++) {
                            if (this.aTrail[i] == this.aTrailNodes[k+1])
                                aXtra.push(this.aTrailNodes[++k]);
                        }
                        if (i >= nTrail) continue;
                        aOutlineset.push([aNodes.concat(aXtra.reverse()), len + i - l]);
                        sum += i - l + 1;
                        l = (bEndAtNode = this.aTrail[i] == this.aTrailNodes[k+1])? i-1 : i;
                    }
                    if (!sum && !bSum && !bClosedTrail) return false;
                    if (sum < nTrail && !bClosedTrail) bAddTrail = true;
                }
                if (!aOutlineset.length)
                    return false;
                aOutlineset.sort(function (el1, el2) { return el1[1] - el2[1]; });
                var aRects = [], n = aOutlineset.length, b = false;
                for (i = 0; i < n; i++) {
                    if (i == n- 1 && !b) break;
                    ret = this._buildConquerRects(aOutlineset[i][0]);
                    if (ret)
                        aRects = aRects.concat(ret);
                    else
                        b = true;
                }
                if (!aRects.length)
                    return false;
                return bAddTrail? aRects.concat(this._buildTrailRects()) : aRects;
            },
            _outline: function(x0, y0, dir) {
                var aNodes = [], aUniqNodes = [], aUsedDirs = [], aBackDirs = [];
                var x = x0, y = y0,
                    lim = 6 * (this.nW + this.nH), n = 0, bClosed = false;
                function isClear(arr) {
                    return arr[3] & CA_CLEAR;
                }
                do {
                    bClosed = n && x == x0 && y == y0;
                    var iCurr = this.find(x,y), iUniq = aUniqNodes.indexOf(iCurr);
                    var aCurrUsed = iUniq >= 0? aUsedDirs[iUniq] : [];
                    var aCurrBack = iUniq >= 0? aBackDirs[iUniq] : [];
                    var aPosOpts = this.applyRelDirs(x,y, dir, [-90, 90, 0]);
                    var aTestDirs = [180+45, -45, 45, 180-45, -45, 45];
                    var aPassIdx = [], aPassWeight = [];
                    for (var i = 0; i < 3; i++) {
                        var d = aPosOpts[i][2];
                        if (aCurrUsed.indexOf(d) >= 0) continue;
                        if (isClear(aPosOpts[i])) continue;
                        var aTestOpts = this.applyRelDirs(x,y, dir, aTestDirs.slice(i*2,i*2+2));
                        var b1 = isClear(aTestOpts[0]), b2 = isClear(aTestOpts[1]);
                        var b = b1 || b2 || (i == 2? isClear(aPosOpts[0]) || isClear(aPosOpts[1]) : isClear(aPosOpts[2]));
                        if (!b) continue;
                        aPassIdx.push(i);
                        aPassWeight.push(
                            (b1 && b2? 0 : b1 || b2? 1 : 2) + (aCurrBack.indexOf(d) >= 0? 3 : 0)
                        );
                    }
                    var nPass = aPassIdx.length;
                    var min = false, idx = false;
                    for (i = 0; i < nPass; i++) {
                        if (!i || aPassWeight[i] < min) {
                            min = aPassWeight[i]; idx = aPassIdx[i];
                        }
                    }
                    var pos = nPass? aPosOpts[idx] : this.applyRelDirs(x,y, dir, [180])[0];
                    var dir0 = dir;
                    x = pos[0]; y = pos[1]; dir = pos[2];
                    if (pos[2] == dir0) continue;
                    nPass? aNodes.push(iCurr) : aNodes.push(iCurr, iCurr);
                    dir0 = (dir0 + 180) % 360;
                    if (iUniq < 0) {
                        aUniqNodes.push(iCurr);
                        aUsedDirs.push([dir]);
                        aBackDirs.push([dir0]);
                    }
                    else {
                        aUsedDirs[iUniq].push(dir);
                        aBackDirs[iUniq].push(dir0);
                    }
                }
                while (n++ < lim && !(this.value(x, y) & CA_TRAIL));
                if (!(n < lim)) return false;
                if (bClosed) {
                    aNodes.push(iCurr);
                    if (aNodes[0] != (iCurr = this.find(x0,y0))) aNodes.unshift(iCurr);
                    var nNodes = aNodes.length;
                    if (nNodes % 2 && aNodes[0] == aNodes[nNodes-1]) aNodes.pop();
                }
                else
                    aNodes.push(this.find(x,y));
                return [n+1, aNodes, bClosed];
            },
            _buildTrailRects: function() {
                if (this.aTrailNodes.length == 1)
                    this.aTrailNodes.push(this.aTrailNodes[0]);
                var aRects = [];
                for (var n = this.aTrailNodes.length, i = 0; i < n-1; i++) {
                    var pos1 = this.pos(this.aTrailNodes[i]), pos2 = this.pos(this.aTrailNodes[i+1]);
                    var x0 = Math.min(pos1[0], pos2[0]), y0 = Math.min(pos1[1], pos2[1]);
                    var w = Math.max(pos1[0], pos2[0]) - x0 + 1, h = Math.max(pos1[1], pos2[1]) - y0 + 1;
                    var rect = [x0, y0, w, h];
                    aRects.push(rect);
                }
                return aRects;
            },
            _buildConquerRects: function(aOutline) {
                if (aOutline.length < 4) return false;
                var aNodes = this.posMap(aOutline);
                var n = aNodes.length;
                if (n > 4 && n % 2 != 0) {
                    var b1 = aNodes[0][0] == aNodes[n-1][0], b2;
                    if (b1 ^ aNodes[0][1] == aNodes[n-1][1]) {
                        b2 = aNodes[n-2][0] == aNodes[n-1][0];
                        if (!(b2 ^ b1) && b2 ^ aNodes[n-2][1] == aNodes[n-1][1])
                            aNodes.pop();
                        b2 = aNodes[0][0] == aNodes[1][0];
                        if (!(b2 ^ b1) && b2 ^ aNodes[0][1] == aNodes[1][1])
                            aNodes.shift();
                    }
                    b1 = aNodes[0][0] == aNodes[1][0]; b2 = aNodes[1][0] == aNodes[2][0];
                    if (!(b1 ^ b2) && b1 ^ aNodes[0][1] == aNodes[1][1] && b2 ^ aNodes[1][1] == aNodes[2][1])
                        aNodes.shift();
                }
                if (aNodes.length % 2 != 0) return false;
                var aRects = [];
                for (var l = 0; l < 10 && aNodes.length > 4; l++) {
                    n = aNodes.length;
                    var dim1 = 0, dim2 = 0, iBase = 0, iCo = 0;
                    var posB1, posB2, posT1, posT2;
                    for (var i = 0; i < n; i++) {
                        posB1 = aNodes[i]; posB2 = aNodes[(i+1)%n];
                        posT1 = aNodes[(i-1+n)%n]; posT2 = aNodes[(i+2)%n];
                        var dir = dirset.find(posT1[0]-posB1[0], posT1[1]-posB1[1]);
                        if (dir != dirset.find(posT2[0]-posB2[0], posT2[1]-posB2[1])) continue;
                        var dirTest = Math.floor((dirset.find(posB2[0]-posB1[0], posB2[1]-posB1[1])+ dir) / 2);
                        var vec = dirset.get(dirTest - dirTest% 45);
                        if (this.value([posB1[0]+ vec[0], posB1[1]+ vec[1]]) & CA_CLEAR) continue;
                        var b = false, t, w, k;
                        if ((t = Math.abs(posB1[0]-posB2[0])) > dim1) {
                            b = true; k = 0; w = t;
                        }
                        if ((t = Math.abs(posB1[1]-posB2[1])) > dim1) {
                            b = true; k = 1; w = t;
                        }
                        if (!b) continue;
                        var k2 = (k+1)%2;
                        vec = dirset.get(dir);
                        var sgn = vec[k2];
                        var co2 = posB1[k2];
                        var left = Math.min(posB1[k], posB2[k]), right = Math.max(posB1[k], posB2[k]);
                        var min = Math.min(sgn* (posT1[k2]- co2), sgn* (posT2[k2]- co2));
                        for (var j = i% 2; j < n; j+= 2) {
                            if (j == i) continue;
                            var pos = aNodes[j], pos2 = aNodes[(j+1)%n], h;
                            if (pos[k2] == pos2[k2] && (h = sgn*(pos[k2]- co2)) >= 0 && h < min &&
                                pos[k] > left && pos[k] < right && pos2[k] > left && pos2[k] < right)
                                break;
                        }
                        if (j < n) continue;
                        dim1 = w; dim2 = sgn*min;
                        iBase = i; iCo = k;
                    }
                    var iB2 = (iBase+1)%n, iT1 = (iBase-1+n)%n, iT2 = (iBase+2)%n;
                    posB1 = aNodes[iBase];
                    posB2 = aNodes[iB2];
                    posT1 = aNodes[iT1];
                    posT2 = aNodes[iT2];
                    var aDim = [0, 0], pos0 = [];
                    var iCo2 = (iCo+1)%2;
                    aDim[iCo] = dim1;
                    aDim[iCo2] = dim2;
                    pos0[iCo] = Math.min(posB1[iCo], posB2[iCo]);
                    pos0[iCo2] = Math.min(posB1[iCo2], posB2[iCo2]) + (aDim[iCo2] < 0? aDim[iCo2]: 0);
                    var rect = [pos0[0], pos0[1], Math.abs(aDim[0])+1, Math.abs(aDim[1])+1];
                    var bC = Math.abs(posT1[iCo2] - posB1[iCo2]) == Math.abs(dim2);
                    if (this._containBall(rect)) return false;
                    aRects.push(rect);
                    if (bC) {
                        posB2[iCo2] += dim2;
                        aNodes.splice(iBase,1);
                        aNodes.splice(iT1 < iBase? iT1 : iT1-1, 1);
                    }
                    else {
                        posB1[iCo2] += dim2;
                        aNodes.splice(iT2,1);
                        aNodes.splice(iB2 < iT2? iB2 : iB2-1, 1);
                    }
                }
                var aX = aNodes.map(function(v) {return v[0]});
                var aY = aNodes.map(function(v) {return v[1]});
                var x0 = Math.min.apply(null, aX);
                var y0 = Math.min.apply(null, aY);
                rect = [x0, y0, Math.max.apply(null, aX)-x0+1, Math.max.apply(null, aY)-y0+1];
                if (this._containBall(rect)) return false;
                aRects.push(rect);
                return aRects;
            },
            // проверяем, содержит ли прямоуг. область морскую точку:
            _containBall: function(rect) {
                var x1 = rect[0], x2 = x1+ rect[2] - 1;
                var y1 = rect[1], y2 = y1+ rect[3] - 1;
                for (var i = 0; i < nBalls; i++) {
                    var o = aBalls[i], x = o.x, y = o.y;
                    if (x >= x1 && x <= x2 && y >= y1 && y <= y2) return true;
                }
                return false;
            }
        };
    
        // Курсор:
        cursor = {
            x: 0, // текущая x координата
            y: 0, // текущая y координата
            x0: 0, // предыдущая x координата
            y0: 0, // предыдущая y координата
            dir: false, // текущий угол движения (в градусах)
            state: false, // текущий режим курсора (true - режим следа)
            state0: false, // предыдущий режим курсора
            // сброс позиции курсора:
            reset: function(x, y, bUnlock) {
                var bPre = bUnlock && cellset.value(this.x, this.y) & CA_CLEAR;
                this.x0 = bPre? this.x : x;
                this.y0 = bPre? this.y : y;
                this.x = x;
                this.y = y;
                this.dir = this.state = this.state0 = false;
            },
            // обновление позиции - перемещение на заданное расстояние:
            update: function(dist) {
                if (this.dir === false) return;
                var x = this.x, y = this.y;
                var vec = dirset.get(this.dir), vecX = vec[0], vecY = vec[1];
                var bEnd =  false;
                for (var n = 0; n < dist; n++) {
                    if (cellset.find(x + vecX, y + vecY) < 0) {
                        this.dir = false; break;
                    }
                    x += vecX; y += vecY;
                    if (cellset.value(x, y) & CA_TRAIL) {
                        bCollision = true; break;
                    }
                    var b = cellset.value(x, y) & CA_CLEAR;
                    if (this.state && b) {
                        bEnd = true; break;
                    }
                    this.state = !b;
                    if (this.state) cellset.add2Trail(x, y, this.dir);
                }
                this.x = x;
                this.y = y;
                if (!bEnd) return;
                if (cellset.getPreTrail() == cellset.find(x,y))
                    bCollision = true;
                else {
                    this.dir = this.state = false;
                    bConquer = true;
                }
            },
            // рендеринг текущей позиции:
            render: function() {
                if (this.x0 == this.x && this.y0 == this.y) {
                    if (tLastFrame) return;
                }
                else {
                    if (this.state0) {
                        var rect = cellset.lastTrailLine();
                        fillCellArea.apply(null, [cfgMain.colorTrail].concat(rect));
                    }
                    else {
                        if (cellset.isPosIn(this.x0, this.y0))
                            clearCellArea(this.x0, this.y0);
                        else
                            fillCellArea(cfgMain.colorBorder, this.x0, this.y0);
                    }
                    this.x0 = this.x; this.y0 = this.y;
                }
                this.state0 = this.state;
                drawCellImg(imgCursor, this.x, this.y);
            },
            // получить текущую позицию:
            pos: function() {
                return [this.x, this.y];
            },
            // получить текущий угол движения:
            getDir: function() {
                return this.dir;
            },
            // изменить угол движения:
            setDir: function(dir) {
                if (dir === this.dir) return;
                if (this.state && this.dir !== false && Math.abs(dir - this.dir) == 180)
                    return;
                this.dir = dir;
            }
        };
    
        // Конструктор класса точки (морской и сухопутной):
        function Enemy(x, y, type, dir) {
            this.x = x;
            this.y = y;
            this.x0 = x;
            this.y0 = y;
            var aDirs = [45, 135, 225, 315];
            this.dir = dir === undefined? aDirs[Math.floor(Math.random()*4)] : dir; // текущий угол движения
            this.type = Boolean(type); // (boolean) тип точки (false - морская, true - сухопутная)
        }
        // Методы класса точки:
        Enemy.prototype = {
            // сброс позиции:
            reset: function(x, y) {
                this.x = x;
                this.y = y;
            },
            // обновление позиции - перемещение на заданное расстояние:
            update: function(dist) {
                var ret = this._calcPath(this.x, this.y, dist, this.dir);
                this.x = ret.x;
                this.y = ret.y;
                this.dir = ret.dir;
            },
            // рендеринг текущей позиции:
            render: function() {
                if (this.x0 == this.x && this.y0 == this.y) {
                    if (tLastFrame) return;
                }
                else {
                    if (this.type && cellset.isPosIn(this.x0, this.y0))
                        clearCellArea(this.x0, this.y0);
                    else
                        fillCellArea(this.type? cfgMain.colorBorder : cfgMain.colorFill, this.x0, this.y0);
                    this.x0 = this.x; this.y0 = this.y;
                }
                drawCellImg(this.type? imgWarder : imgBall, this.x, this.y);
            },
            // получить текущую позицию:
            pos: function() {
                return [this.x, this.y];
            },
            // вычислить путь движения (перемещения):
            _calcPath: function(x, y, dist, dir) {
                var vec = dirset.get(dir), vecX = vec[0], vecY = vec[1];
                var posCr = cursor.pos();
                var xC = posCr[0], yC = posCr[1],
                    vC = cellset.value(xC, yC), bC = !this.type ^ vC & CA_CLEAR;
                if (bC && Math.abs(x - xC) <= 1 && Math.abs(y - yC) <= 1 ||
                    !this.type && this._isCollision(x, y, dir)) {
                    bCollision = true;
                }
                for (var n = 0; n < dist && !bCollision; n++) {
                    var xt = x + vecX, yt = y + vecY;
                    var dirB = this._calcBounce(x, y, dir, xt, yt);
                    if (dirB !== false)
                        return this._calcPath(x, y, dist - n, dirB);
                    if (bC && Math.abs(xt - xC) <= 1 && Math.abs(yt - yC) <= 1 ||
                        !this.type && this._isCollision(xt, yt, dir))
                        bCollision = true;
                    if (!this.type && !cellset.isPosIn(xt, yt))
                        break;
                    x = xt; y = yt;
                }
                return {x: x, y: y, dir: dir};
            },
            // вычислить отскок точки от границы поля (если есть):
            _calcBounce: function(x, y, dir, xt, yt) {
                var ret = cellset.applyRelDirs(x,y, dir, [-45, 45]);
                var b1 = this.type ^ ret[0][3] & CA_CLEAR,
                    b2 = this.type ^ ret[1][3] & CA_CLEAR;
                return b1 ^ b2?
                    (b1? dir + 90 : dir + 270) % 360 :
                    this.type ^ cellset.value(xt, yt) & CA_CLEAR || b1 && b2?
                        (dir+180) % 360 : false;
            },
            // проверить столкновение точки с курсором:
            _isCollision: function(x, y, dir) {
                if (cellset.value(x, y) & CA_TRAIL) return true;
                var aDirs = [-45, 45, -90, 90];
                for (var i = 0; i < 4; i++) {
                    var d = (dir + aDirs[i] + 360) % 360, vec = dirset.get(d);
                    if (cellset.value(x + vec[0], y + vec[1]) & CA_TRAIL) return true;
                }
                return false;
            }
        };
        
    
        function merge(dest, src, bFilter) {
            if (!src) return dest;
            for(var key in dest) {
                if (!dest.hasOwnProperty(key) || !src.hasOwnProperty(key)) continue;
                var v = src[key];
                if ((!bFilter || v) && (typeof v != 'number' || v >= 0))
                    dest[key] = v;
            }
            return dest;
        }
    
    })();
    

    За сим закругляюсь. Спасибо за внимание.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 21

      +14
      В 9 классе я при помощи пристального взгляда, Турбо Паскаля и небольшого перебора сломал формат данных SeXoniX, подро… эм, подробно исследовал все изображения и поменял на смишные картинки, которые были под рукой. Играть при маме стало более комфортно.
        +2
        Я не помню на каком дремучем компе в середине 80-х я впервые увидел Xonix. А он УЖЕ чей-то клон…
          0
          То возможно был Агат, сам впервые играл в Xonix именно на нем, а точнее на Агат-9
            +2
            Причём Агат — это ведь тоже клон!
          +2
          Алгоритм определения завоеванных областей, конечно, интересный, но неоправданно сложный. На карте с уже отмеченным следом можно сделать простую заливку от каждой «морской» точки, а потом все незалитые точки перенести на карту как захваченные.
            +1
            Тут вам не 80е! Тут нельзя просто пару раз по всем точкам пройтись и всё!

            А вот зачем ввели «угол в градусах» — этого я уж совсем понять не могу. Разве с заданием движения в виде пары чисел (Δx, Δy) не удобнее работать? Кстати в JavaScript Δx и Δy — валидные называния переменных, так что можно писать что-нибудь типа
            direction = { Δx: 1, Δy: 0}
            — просто и понятно.
              0
              Наверное это дело вкуса. Мне лично удобнее работать с градусами. К тому же так легче рассчитывать отскок точек от границ.
                +1
                Это какую же операцию делать легче, я извиняюсь? Рассчёт отскока с парой чисел выглядит так:
                if allowed(X + Δx, Y + Δy) return [Δx, Δy] // Движение вперёд
                if allowed(X - Δx, Y + Δy) return [-Δx, Δy] // отражение по X
                if allowed(X + Δx, Y - Δy) return [Δx, -Δy] // отражение по Y
                return [-Δx, -Δy] // возврат
                В буквальном смысле четыре строчки. Ну ещё пяток чтобы реально точку передвинуть. Как это делать непосредственно с градусами — я вообще себе представить не могу! Собственно тот алгоритм, что у вас реализован так и работает — с той только разницей, что у вас там есть ещё дополнительная сущность предназначенная «для запутывания противника».
              –1
              Наверное вы этого не знаете, но в HTML5 Canvas заливка работает не так, как во многих (десктопных) графических библиотеках. Здесь не получится просто указать точку «где-то внутри» замкнутой области и цвет заливки. Здесь нужно явно задавать контур заливаемой области (см. описание Canvas.fill). Что возвращает нас к задаче определения контуров.
              Но даже если бы в Canvas заливка работала «привычным» способом, это все равно не решило бы всех проблем. Главная (но не единственная) проблема — в том, что заливать нужно не все замкнутые области, а только те, внутри которых нет «морских» точек. Что в итоге опять же возвращает к задаче определения контуров).
                +1
                HTML5 я не знаю практически вообще, как, собственно, и JS. Но я же говорю про алгоритм. Если нельзя воспользоваться готовой заливкой, можно сделать свою, на таком маленьком поле даже просто рекурсивный алгоритм в несколько строчек кода будет работать нормально. А чтоб не искать области внутри которых находятся «морские» точки, нужно заливать именно начиная с этих точек. В результате незалитые области и будут захваченной территорией.

                Ваш алгоритм, хоть он и на порядок сложнее, по идее должен быть быстрее заливки в большинстве случаев.
                  0
                  Всё же это будет немного сложнее — захваченная территория должна всегда быть меньше незахваченной, это если след делит море на две части.
                  Как быть в случае нескольких замкнутых областей, как на скриншоте-2, если незахваченные области справа от следа будут в сумме больше левой области, но каждая по отдельности будет меньше — пока не понятно.
                    0
                    Неверно. В ксониксе захваченная территория всегда та, на которую, после очередного прокладывания следа, не могут попасть «морские» точки-враги. Не важно какая часть больше, а какая меньше. Сам след при этом всегда превращается в захваченную территорию.

                    А про скриншот-2 перефразирую еще раз: заливкой мы ищем не захваченную территорию, а наоброт, территорию которая осталась за врагами, т.е. заливаем области начиная с «морских» точек-врагов, со всех по очереди. Потом смотрим что осталось незалито — это и есть захваченная территория.
                      0
                      В ксониксе захваченная территория всегда та, на которую, после очередного прокладывания следа, не могут попасть «морские» точки-враги. Не важно какая часть больше, а какая меньше.
                      В таком случае всё как-то слишком уж упрощается. Главное — стек не переполнить при рекурсивной заливке :)
                        0
                        Лучше не стек, а очередь. Меньше вероятность переполнения. Обычно там живёт «расширяющийся граница», но изначально туда кладут одну точку. Тут же нужно туда сразу положить сразу все морские точки, а дальше — как обычно.
                    0
                    Эти области (с «морскими» точками) и не нужно заливать, они и так уже залиты нужным цветом (черным). Или вы предлагаете заливать их другим цветом? Как это поможет залить (стереть) области без морских точек?
                    Само собой, рекурсивный алгоритм реализуется гораздо проще. Но лично я предпочитаю не использовать рекурсию там, где можно обойтись без нее.
                      0
                      Нужно залить их другим цветом на «теневой» графической странице, а то, что там осталось чёрным нужно на основной странице — перекрасить. Делов-то. Так оно делалось в 80е, когда никаких хитрых библиотек ни у кого не было, а зато пара графических страниц — была (обычно она использовалась чтобы можно было вывести новое изображение, а потом «в один фрейм» сменить новое на старое).
                    0
                    Наверное, Вы не в курсе, но заливка растра – это хорошо изученная проблема, которая имеет несколько классических вариантов решений.
                      –1
                      Я в курсе про заливку растра. Только вот речь в этой ветке шла о том, чтобы использовать заливку так сказать «из коробки». Если же реализовывать ее самому, то я не вижу никаких преимуществ по сравнению с описанным мной методом. Этот метод, во-первых — не рекурсивный. Во вторых, он не обходит все ячейки внутри области: алгоритм нахождения контуров проверяет только ячейки контура плюс соседние с ними; а алгоритм разбиения на прямоугольники имеет дело с вершинами многоугольника, число которых на порядок меньше даже числа ячеек контура, не говоря уже о всех ячейках области. Ну и в-третьих, этот метод сводит к минимуму число графических операций. Здесь не считывается цвет каждой проверяемой ячейки, и закрашиваются здесь не ячейки, а прямоугольники, из которых состоит область. Сколько прямоугольников, столько и графических операций (вызовов метода clearRect).
                        +1
                        Вы как-то совсем неверно воспринимаете мои слова, или я на столько косноязычен? Про заливку из коробки я ничего не говорил. И при чем тут вообще цвет? При чем тут графические операции? Почему увидев слово «заливка» вы подумали не про алгоритм, а про фукнцию заливки в «десктопных» графических библиотеках?

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

                        Как я уже писал, ваш алгоритм действительно должен быть быстрее в большинстве случаев чем заливка. Однако это ускорение едва ли будет заметно если сделать нормальную заливку, и при этом код все равно получится на порядок проще.
                        Кстати, если сделать заливку сканированием линий, как в статье википедии упомянутую pehat'ом, и оптимизировать ее с учетом того, что не бывает захваченных областей окруженных незахваченной территорией, то вообще то по быстродействию заливка будет по крайней мере такая же, как ваш алгоритм, потому что она тоже будет обходить только границы областей и заливать сразу линиями.
                          –1
                          Я и в самом деле вас неверно понял. Мне почему-то показалось, что вы имели в виду стандартную функцию заливки.
                          Теперь я понял вашу мысль: не париться по поводу эффективности, а использовать готовый алгоритм. Возможно, я действительно перемудрил и стоило так и сделать.
                          И все же я считаю проблемой общих алгоритмов заливки то, что они не учитывают особенности данной конкретной задачи — информацию о следе курсора. Поэтому им приходится так или иначе проверять все возможные элементы (все ячейки сетки). К тому же для данной задачи это придется делать два раза: первый раз, чтобы, как вы писали, найти незахваченные территории (отметить их); а второй — чтобы найти оставшиеся, т.е. захваченные. За один заход, мне кажется, вы это сделать не сможете.

                          Насчет сканирования линий. Этот метод, конечно, не рекурсивный, но он тоже проверяет все элементы. К тому же он не подходит для определения захваченных/незахваченных областей.
                  0
                  Откровенно говоря, после того как игрок вернулся из моря на сушу и контур образовался, вся задача сводится к поиску единственной точки, относительно которой нужно выполнить рекурсивную заливку. Идея определения контуров мне понравилась: оригинальная. А вот разбивка на прямоугольники это, имхо, уже явный перебор. :)

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

                  Only users with full accounts can post comments. Log in, please.