Предисловие

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

Ссылка на проект со всем кодом будет в самом конце

Выбор графической библиотеки

Если с языком всё ясно и выбрать нельзя, то графики на него достаточно много. И здесь всё очень просто:

"Copilot, какие графические библиотеки есть для Haxe и в чем их отличие?"

Выбор почти сразу пал на OpenFL. Просто по причине того что он проще в освоении и ближе по API к OpenGL, который мне немного известен.

Часть 1. Input

Для передвижения камеры по сцене и ее масштабирования я написал класс CameraInput

// Скорость передвижения камеры (пиксель за кадр)
private var cameraSpeed:Float = Constants.TILE_WIDTH * 10;
// Степень масштабирования камеры
private var cameraZoomSpeed:Float = 0.05;
// Ограничение масштабирования (просто scale) 
private var minScale:Float = 0.5;
private var maxScale:Float = 3;

// Время предыдущего кадра
// По сути нужен он только для получении времени прошедшего между кадрами
// для передвижения по сцене независимо от FPS
private var lastTime:Float;

// Особенность Haxe - "корень программы"
// Нужен для подписки на события и получения ширины/высота окна
private var stage:Stage;
// Главный контейнер, который будет двигаться для получения эффекта "Камеры"
private var container:DisplayObjectContainer;

Теперь простая обработка нажатий клавиш: подписываемся на нужные события и устанавливаем состояние нажатия клавиши в true/false:

private var keysDown:IntMap<Bool> = new IntMap<Bool>();

stage.addEventListener(KeyboardEvent.KEY_DOWN, onKeyDown);
stage.addEventListener(KeyboardEvent.KEY_UP, onKeyUp);
stage.addEventListener(Event.ENTER_FRAME, onEnterFrame);

// Клавиша нажата
private function onKeyDown(e:KeyboardEvent):Void
{
    keysDown.set(e.keyCode, true);
}

// Клавишу отпустили
private function onKeyUp(e:KeyboardEvent):Void
{
    keysDown.set(e.keyCode, false);
}

// Вызывается каждый кадр
private function onEnterFrame(e:Event):Void  {
    // Получаем время, прошедшее между кадрами
    var now = haxe.Timer.stamp();
    var deltaTime = now - lastTime;
    lastTime = now;

    var moved = false;
    var moveStep = cameraSpeed * deltaTime;

    // Если клавиша нажата, то сдвигаем всю сцену на заданную скорость
    // с компенсацией лагов за счет deltaTime
    if (keysDown.exists(Keyboard.A) && keysDown.get(Keyboard.A)) {
        container.x += moveStep;
        moved = true;
    } else if (...) {
        ...
    }

    // Если камера была сдвинута, то надо сообщить всем желающим об этом
    // В данном случае это необходимо для перерисовки сцены
    if (moved) {
        dispatchEvent(new OnCameraMovedEvent());
    }
}

Достаточно просто? Теперь масштабирование!

stage.addEventListener(MouseEvent.MOUSE_WHEEL, onMouseWheel);

private function onMouseWheel(e:MouseEvent):Void {
    var delta:Float = e.delta;
    // В 2025 году браузеры все еще плохо работают с разным вводом, поэтому
    // такой небольшой костыль, который приводит delta к разумным значениям
    // в Chrome (тестировалось только на Firefox/Chrome/Standalone)
    if (Math.abs(delta) > 10) delta = delta / 100;

    // Вычисляем scale
    var zoomChange:Float = delta * cameraZoomSpeed;
    var newScale:Float = container.scaleX + zoomChange;

    // ... и ограничиваем его
    if (newScale < minScale) newScale = minScale;
    else if (newScale > maxScale) newScale = maxScale;

    // Далее надо отцентрировать камеру, чтобы масштабирование
    // происходило в угол карты
    // Получаем центр экрана
    var stageCenterX = stage.stageWidth / 2;
    var stageCenterY = stage.stageHeight / 2;

    // Используем нативный метод и получим локальные координаты
    // до масштабирования
    var localBefore = container.globalToLocal(new openfl.geom.Point(stageCenterX, stageCenterY));

    // Применяем scale
    container.scaleX = newScale;
    container.scaleY = newScale;

    // Теперь получим уже получим координаты "после"
    var localAfter = container.globalToLocal(new openfl.geom.Point(stageCenterX, stageCenterY));

    // И сдвинем наш контейнер на разницу "до" и "после" - этого достаточно
    container.x += (localAfter.x - localBefore.x) * newScale;
    container.y += (localAfter.y - localBefore.y) * newScale;

    // Как и раньше сообщим о то что камера сдвинулась для перерисовки сцены
    dispatchEvent(new OnCameraMovedEvent());
}

Осталась последняя и самая интересная часть - клик! Здесь я бы хотел отслеживать по какому тайлу произошло нажатие для дальнейшей бизнес логики:

stage.addEventListener(MouseEvent.CLICK, onMouseClick);

private function onMouseClick(e:MouseEvent):Void {
    var tileWidth = Constants.TILE_WIDTH;
    var tileHeight = Constants.TILE_HEIGHT;

    var screenX = e.stageX;
    var screenY = e.stageY;

    var local = container.globalToLocal(new Point(screenX, screenY));
    var sx = local.x;
    var sy = local.y;

    // Выше ничего интересного - просто находим локальные координаты сцены
    // и с помощью стандартного подхода к изометрии получаем координаты тайла
    var x = Math.round((sy / (tileHeight / 2) + sx / (tileWidth / 2)) / 2);
    var y = Math.round((sy / (tileHeight / 2) - sx / (tileWidth / 2)) / 2);

    // И соответственно событие, куда ж без него
    dispatchEvent(new OnClickEvent(x, y));
}

(tileX - tileY) * (tileWidth / 2); // x
(tileX + tileY) * (tileHeight / 2); // y

Часть 2. Сцена

Это, наверное, самая важная часть игры - отрисовать пол!

Задача: Отрисовать пол в изометрии, который будет ограничен размерами mapWidth/mapHeight. Казалось бы что проще? Вот только есть нюанс - размер сетки 500x500! При попытке отрисовать единой фигурой приложение просто вылетает, а если рисовать потайлово, то это потребовало бы какого-то куллинга (показывать только то что на экране). В реальном проекте второй подход наверное был бы предпочтительным, т.к. навряд ли пол будет одной сплошной текстурой. Тут я бы рекомендовал обратить внимание на quad-tree.

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

// Задаем задний фон
stage.align = StageAlign.TOP_LEFT;
stage.scaleMode = StageScaleMode.NO_SCALE;
stage.color = 0x0000FF;

// Вызывается каждый раз, когда меняется камера или изменяется размер окна
public function redraw():Void {
    var scaleX = container.scaleX;
    var scaleY = container.scaleY;

    var w = stage.stageWidth;
    var h = stage.stageHeight;

    // Создаем пол один раз или при изменении размеров экрана
    if (floor == null || w != lastStageWidth || h != lastStageHeight) {
        lastStageWidth = w;
        lastStageHeight = h;

        // Удаляем старый объект
        if (floor != null && floor.parent != null) {
            floor.parent.removeChild(floor);
        }

        // Создаем новый
        floor = new Shape();

        // Получаем позиции тайлов из экранных координат
        // без ограничения по размеру карты и без учета положения камеры
        // Это нужно для вычисления размера пола
        var lt = screenToTileUnclampedFromZero(0, 0);
        var rt = screenToTileUnclampedFromZero(w, 0);
        var rb = screenToTileUnclampedFromZero(w, h);
        var lb = screenToTileUnclampedFromZero(0, h);

        var i0 = lt.x;
        var j0 = rt.y;
        // +1 это небольшой запас
        var i1 = rb.x + 1;
        var j1 = lb.y + 1;

        // Получаем координаты вершин "ромба" - изометрического пола
        // Всё тоже по тому же принципу x-y и x+y
        var p0 = { x: (i0 - j0) * (tileWidth / 2), y: (i0 + j0) * (tileHeight / 2)}; // top
        var p1 = { x: (i1 - j0) * (tileWidth / 2), y: (i1 + j0) * (tileHeight / 2)}; // right
        var p2 = { x: (i1 - j1) * (tileWidth / 2), y: (i1 + j1) * (tileHeight / 2)}; // down
        var p3 = { x: (i0 - j1) * (tileWidth / 2), y: (i0 + j1) * (tileHeight / 2)}; // left

        // Отрисовка
        floor.graphics.clear();
        floor.graphics.beginFill(0x00FF00);
        floor.graphics.moveTo(p0.x, p0.y);
        floor.graphics.lineTo(p1.x, p1.y);
        floor.graphics.lineTo(p2.x, p2.y);
        floor.graphics.lineTo(p3.x, p3.y);
        floor.graphics.endFill();

        // Добавляем в самый корневой элемент самым первым элементом
        // для порядка отрисовки
        stage.addChildAt(floor, 0);
    }

    // Получаем по стандартным правилам текущую видимую область в тайлах
    // Т.е. с учетом сцены, положения камеры и масштабирования, clamp-ом
    var viewport = getViewport();

    // Тот же самый viewport, но неограниченный по (0; 0) и (mapWidth; mapHeight)
    var lt = screenToTileUnclamped(0, 0);
    var rt = screenToTileUnclamped(w, 0);
    var rb = screenToTileUnclamped(w, h);
    var lb = screenToTileUnclamped(0, h);

    // Вычисляем кол-во отображаемых тайлов на экране
    var dx = (rb.x - lt.x) / 2;
    var dy = (lb.y - rt.y) / 2;
    
    // Ограничиваем по X
    var cx:Float;
    if (viewport.maxX >= gridWidth) {
        cx = viewport.maxX - dx - 1;
    } else {
        cx = viewport.minX + dx;
    }
    
    // Ограничиваем по Y
    var cy:Float;
    if (viewport.maxY >= gridHeight) {
        cy = viewport.maxY - dy - 1;
    } else {
        cy = viewport.minY + dy;
    }
    
    // Задаем итоговую позицию (смещаем):
    // Камера - половина экрана + центр тайла в экранных координатах * масштаб
    // В зависимости от проекта здесь могут добавляться разные цифры как 
    // -tileHeight / 2 - в этом нет ничего такого
    floor.x = container.x - w / 2 + MapUtils.getTileScreenX(cx, cy, tileWidth) * scaleX;
    floor.y = container.y - h / 2 + (MapUtils.getTileScreenY(cx, cy, tileHeight) - tileHeight / 2) * scaleY;

    // Вызываем событие перерисовки сцены (это необязательно)
    // Я использую событие чтобы скрыть лишние объекты вне экрана
    dispatchEvent(new OnSceneRedrawEvent(
        viewport.minX,
        viewport.maxX,
        viewport.minY,
        viewport.maxY));
}

// screenToTile и getViewport приведу в кратком виде:
function screenToTile(screenX:Float, screenY:Float) {
  var local = scene.globalToLocal(new openfl.geom.Point(screenX, screenY));
  var sx = local.x;
  var sy = local.y;
  var x = Math.floor((sy / (tileHeight / 2) + sx / (tileWidth / 2)) / 2)
  // (optional) Clamp
  x = Std.int(Math.max(0, Math.min(mapWidth - 1, i)));
  ...
}

function getViewport() {
  var lt = screenToTile(0, 0, scaleX, scaleY);
  ...
  return { minX: Std.int(Math.max(0, lt.x)), ... }
}

Часть 3. Создание объектов

В игре будет присутствовать два вида объектов и все одной высоты tileLength:

• Стены - объекты, у которых есть положение и размер в тайлах 1x1, 12x24 и т.д.

• Курицы - объекты, которые всегда занимают один тайл и в отличие от стен располагаются по центру. Курицы могут "забираться" на стены и не блокируют обзор.

Игра предполагает сетку размером 500х500 и огромное кол-во объектов на ней. В связи с этим просто так создать объект нельзя - отрисовка каждого будет съедать весь FPS. Поэтому было решено использовать Tilemap и батчить текстуры, но обо всем по порядку.

OpenFL уже обладает Tilemap, но для того чтобы его использовать необходимо объединить все ассеты в один атлас - сделать из множества картинок одну большую. В этом случае они также будут отрисовываться за один вызов отрисовки. Определение вызова отрисовки и батчинг немного выходят за рамки статьи, но вкратце - это за n раз нарисовать как можно больше, чтобы не напрягать компьютер.

Объединить в атлас можно "руками" хоть в Paint. Но не хотелось бы так мучаться. Поэтому я написал код, который делает это на старте:

Все размещаемые объекты на сцене имеют формат 1x1.png и т.д. и 0x0 для куриц, где первая цифра - это размер в тайлах по X, а вторая - по Y (width и height).

function buildAtlasFromAssets(maxAtlasWidth:Int = 2048):Void {
    // Находим все ассеты по маске
    var files = Assets.list();
    var pngs = files.filter(f -> ~/^assets\/(\d+)x(\d+)\.png$/.match(f));

    // Загружаем все ассеты
    var images = [];
    for (file in pngs) {
        var bmp = Assets.getBitmapData(file);
        images.push({bmp: bmp, w: bmp.width, h: bmp.height, name: file});
    }

    // Сортируем по высоте (необязательно)
    images.sort((a, b) -> b.h - a.h);

    // Размещаем построчно спрайты в атласе
    // Совет: Лучше не первышать размеры 2048x2048
    // А если такая потребность появится, то сделать несколько атласов
    var positions = [];
    var x = 0;
    var y = 0;
    var rowHeight = 0;
    var atlasWidth = 0;
    var atlasHeight = 0;

    for (img in images) {
        if (x + img.w > maxAtlasWidth) {
            // Следующая строка
            x = 0;
            y += rowHeight;
            rowHeight = 0;
        }
        positions.push({x: x, y: y, img: img});
        if (x + img.w > atlasWidth) atlasWidth = x + img.w;
        if (y + img.h > atlasHeight) atlasHeight = y + img.h;
        if (img.h > rowHeight) rowHeight = img.h;
        x += img.w;
    }

    // Создаем атлас и Tileset (OpenFL)
    var atlas = new BitmapData(atlasWidth, atlasHeight, true, 0x00000000);
    var tileset = new Tileset(atlas);

    // Копируем картинки в вычисленные позиции и 
    // запоминаем название спрайты -> его index
    for (pos in positions) {
        atlas.copyPixels(pos.img.bmp, pos.img.bmp.rect, new openfl.geom.Point(pos.x, pos.y));
        var rect = new openfl.geom.Rectangle(pos.x, pos.y, pos.img.w, pos.img.h);
        var re = ~/(\d+)x(\d+)/;
        if (re.match(pos.img.name)) {
            var key = re.matched(0);
            var idx = tileset.addRect(rect);
            tileIndexMap.set(key, idx);
        }
    }

    // Далее запоминаем все сделанное и создаем Tilemap
    // нужного размера
    this.tileset = tileset;

    var mw = Math.ceil((mapWidth + mapHeight) * (tileWidth / 2));
    var mh = Math.ceil((mapWidth + mapHeight) * (tileHeight / 2));

    this.tilemap = new Tilemap(mw, mh, tileset);
    // Небольшой сдвиг чтобы карта была по центру
    this.tilemap.x = (mw + tileWidth) / -2;
    // И немного ниже, чтобы тайлы не обрезались
    // все таки Tilemap - это квадрат и разместив объект в позиции (0; 0)
    // он вылезет за пределы этого квадрата. Поэтому отнимаем макс. высоту тайла
    this.tilemap.y = -tileHeight / 2 - tileLength;

    this.parent.addChild(tilemap);
}

Далее создадим объекты. Создание Стен и Куриц не сильно отличаются:

public function createObject(tileX:Int, tileY:Int, width:Int, height:Int):GameObject {
    // Ищем тайл в ранее созданном Tileset (атласе)
    var key = width + "x" + height;
    var tileIdx = tileIndexMap.get(key);
    if (tileIdx == null) {
        trace("Tile not registered for " + key);
        return null;
    }

    // Получаем размеры спрайта
    var rect = tileset.getRect(tileIdx);

    // width/height - размер в тайлах
    // Получаем позицию объекта в экранных координатах
    // isoToScreen - это все те же  (tileX - tileY) * (tileWidth / 2)
    var baseI = tileX + width - 1;
    var baseJ = tileY + height - 1;
    var basePos = isoToScreen(baseI, baseJ, tileWidth, tileHeight);

    // Вычисляем сдвиг, чтобы объект располагался по тайлам и по центру
    // Позиция объекта - это его минимальная (tileX; tileY)
    // также чуть поднимаем по высоте +tileLength/2
    var offsetX = basePos.x - rect.width / 2 + tileWidth / 2;
    var offsetY = basePos.y - rect.height / 2 + tileHeight / 2 + tileLength / 2;

    // Из-за того что ранее сдвинули карту, то и объект сдвинем соответственно
    var mapWidth = Math.ceil((mapWidth + mapHeight) * (tileWidth / 2));
    offsetX += mapWidth / 2;

    // Финальные расчеты сдвига
    var ox = ((width - height) / 2) * (tileWidth / 2);
    var oy = ((width + height) / 2 - 1) * (tileHeight / 2);
    offsetX -= ox;
    offsetY -= oy;

    // Создаем, добавляем тайл и возвращаем модель нашего объекта
    var tile = new Tile(tileIdx, offsetX, offsetY);
    tilemap.addTile(tile);

    return new GameObject(tile, tileX, tileY, width, height);
}

Курицы создаются аналогичным образом, но с особенностями размера и позиционирования:

    public function createPointObject(tileX:Int, tileY:Int, isUp:Bool):GameObject {
        var key = "0x0";
        var tileIdx = tileIndexMap.get(key);
        if (tileIdx == null) {
            trace("Tile not registered for " + key);
            return null;
        }

        var rect = tileset.getRect(tileIdx);
        var baseI = tileX;
        var baseJ = tileY;
        var basePos = isoToScreen(baseI, baseJ, tileWidth, tileHeight);
        var offsetX = basePos.x - rect.width / 2 + tileWidth / 2;
        var offsetY = basePos.y;

        var mapWidth = Math.ceil((mapWidth + mapHeight) * (tileWidth / 2));
        offsetX += mapWidth / 2;

        // Главное отличие! При создании курицы она может быть на стене
        // Т.е. ее положение это высота тайла (хорошо что высота одинакова для всего)
        if (isUp)
            offsetY -= tileLength;

        var tile = new Tile(tileIdx, offsetX, offsetY);
        tilemap.addTile(tile);

        return new GameObject(tile, tileX, tileY, 1, 1);
    }

Часть 4. Изометрическая сортировка

Одна из самых неприятных частей. Я не буду вдаваться в подробности сортировки тайлов в изометрии - про это уже много есть статей (правда на английском).

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

1. Найти AABB всех объектов;

2. Отфильтровать Стены от Куриц;

3. Выполнить топологическую сортировку;

4. Создать объекты (GameObject);

Топологическая сортировка в двух словах на простом - это когда мы перебираем абсолютно все объекты и сравниваем друг с другом. В обычной сортировки не каждый объект сравнивается с другим.

Реализация метода для рассчета AAB:

public function worldSpace(tileX:Int, tileY:Int, width:Int, height:Int) {
    // Задаем курицам размер 1x1, чтобы общий алгоритм работал и для них
    if (width == 0) width = 1;
    if (height == 0) height = 1;

    return {
        xMin: tileX * tileWidth,
        yMin: tileY * tileHeight,
        zMin: 0,
        xMax: tileX * tileWidth + width * tileWidth,
        yMax: tileY * tileHeight + height * tileHeight,
        zMax: tileLength
    };
}

Для того, чтобы хранить данные о сортировке я выделил их в отдельный класс:

class SortData {
    // Координаты в тайлах
    public var x:Int;
    public var y:Int;
    // Размер в тайлах
    public var w:Int;
    public var h:Int;
    // Флаг курица это или нет
    public var isPointObject:Bool;
    // Стоит ли курица на стене или нет
    public var isUp:Bool;
    // Если курица стоит, то на ком
    public var parentObject:TileInfo;
    // AABB
    public var minX:Float;
    public var maxX:Float;
    public var minY:Float;
    public var maxY:Float;
    public var minZ:Float;
    public var maxZ:Float;
    // Флаг, нужный для топологической сортировки
    public var isoVisitedFlag:Int;
    // Тайлы, которые должны отображаться позади
    public var tilesBehind:Array<TileInfo>;
    // Результат топологической сортировки
    public var isoDepth:Int;

    public function new() {
    }
}

Сам сортировщик с комментариями:

class IsoSorter {
    private var _sortDepth:Int;

    public function sortTiles(gameObjectTiles:Array<TileInfo>) {
        // Сравниваем все объекты друг с другом
        // и отмечаем куриц
        var pObjects = new Array<TileInfo>();
        for (i in 0...gameObjectTiles.length) {
            var a = gameObjectTiles[i];
            var behindIndex = 0;

            for (j in 0...gameObjectTiles.length) {
                // С собой не сравниваем
                if (i == j) {
                    continue;
                }

                var b = gameObjectTiles[j];

                // TODO: На самом деле isBehind и intersects можно объединить
                // Проверяем находится ли объект позади
                var isBehind = isBehind(a, b);
                // Проверяем пересечение объектов
                var isIntersect = intersects(a, b);

                // Если объект пересекаются и это курица, то запоминаем стену
                if (a.sortData.isPointObject && !b.sortData.isPointObject && isIntersect) {
                    a.sortData.isUp = true;
                    a.sortData.parentObject = b;
                    pObjects.push(a);
                }
                // Иначе запоминаем что тайл b позади a
                else if (isBehind && (!b.sortData.isPointObject || !isIntersect)) {
                    a.sortData.tilesBehind[behindIndex++] = b;
                }
            }

            // Сбрасываем флаг посещения a для дальнейшей сортировки
            a.sortData.isoVisitedFlag = 0;
        }

        // Заготавливаем куриц
        for (a in pObjects) {
            // Для корректных вычислений приподнимаем куриц
            // Здесь бы стоило написать tileLength / tileHeight,
            // но я забыл
            a.x -= 4;
            a.y -= 4;

            // Стена, на которой стоит курица, всегда находится позади
            if (a.sortData.parentObject != null) {
                a.sortData.tilesBehind.push(a.sortData.parentObject);
            }

            for (b in gameObjectTiles) {
                // С другими курицами не сортируем!
                // Курица может быть в курице
                // Да, мне нравится слово курица
                if (b.sortData.isPointObject) {
                    continue;
                }

                if (isBehind(a, b)) {
                    a.sortData.tilesBehind.push(b);
                }
            }

            // Возвращаем курицу на место
            a.x += 4;
            a.y += 4;
        }

        // Посещаем каждый тайл и ищем индекс для сортировки
        _sortDepth = 0;
        for (i in 0...gameObjectTiles.length) {
            visitNode(gameObjectTiles[i]);
        }

        // Sort by depth
        gameObjectTiles.sort(function(a, b) {
            return a.sortData.isoDepth - b.sortData.isoDepth;
        });
    }

    function intersects(as:TileInfo, bs:TileInfo):Bool {
        var a = as.sortData;
        var b = bs.sortData;

        return a.x < b.x + b.w &&
        a.x + a.w > b.x &&
        a.y < b.y + b.h &&
        a.y + a.h > b.y;
    }

    // По хорошему убрать бы здесь рекурсию
    private function visitNode(tile:TileInfo):Void {
        // Посещаем все тайлы и присваиваем isoDepth
        // Те тайлы что позади посещаются первыми
        // таким образом гарантируется их порядок
        var n = tile.sortData;
        if (n.isoVisitedFlag == 0) {
            n.isoVisitedFlag = 1;

            var behindLength:Int = n.tilesBehind.length;
            for (i in 0...behindLength) {
                if (n.tilesBehind[i] == null) {
                    break;
                } else {
                    visitNode(n.tilesBehind[i]);
                    n.tilesBehind[i] = null;
                }
            }

            n.isoDepth = _sortDepth++;
        }
    }

    private function isBehind(as:TileInfo, bs:TileInfo):Bool {
        // Это оказалось одной из самых сложных частей
        // Проверяем какой тайл позади благодаря ряду условий
        var a = as.sortData;
        var b = bs.sortData;
        return
            (
                b.maxX <= a.minX &&
                b.maxY > a.minY && b.minY < a.maxY &&
                b.maxZ > a.minZ && b.minZ < a.maxZ
            ) ||
            (
                b.maxY <= a.minY &&
                b.maxX > a.minX && b.minX < a.maxX &&
                b.maxZ > a.minZ && b.minZ < a.maxZ
            ) ||
            (
                b.maxZ <= a.minZ &&
                b.maxX > a.minX && b.minX < a.maxX &&
                b.maxY > a.minY && b.minY < a.maxY
            ) ||
            (
                b.maxX <= a.maxX &&
                b.maxY <= a.maxY
            );
    }
}

Всё! Сортировка завершена - осталось создать объекты:

for (i in 0...gameObjectTiles.length) {
    var tileInfo = gameObjectTiles[i];
    var sortData = tileInfo.sortData;

    // Создаем курицу
    if (sortData.isPointObject) {
        var go = objectFactory.createPointObject(sortData.x, sortData.y, sortData.isUp);
        if (go == null) {
            continue;
        }

        // Для будущих механик я решил запомнить куриц, стоящих на стене
        if (sortData.parentObject != null) {
            sortData.parentObject.addPointObject(go);
        } else {
            // И куриц, которые находятся на земле
            // Тут стоит обратить внимание, что несколько куриц могут быть на одном тайле
            var list = unparentPointObjects[go.y][go.x];
            if (list == null) {
                list = [];
                unparentPointObjects[go.y][go.x] = list;
            }

            list.push(go);
        }

        // С помощью viewport из MainScene я отключаю
        // объекты, находящиеся вне экрана при перерисовки сцены
        renderObjects.push(go);
        continue;
    }

    // Создаем стену
    var instance = objectFactory.createObject(sortData.x, sortData.y, sortData.w, sortData.h);
    if (instance == null) {
        continue;
    }

    renderObjects.push(instance);

    // Сохраняем в глобальную карту типа Array<Array<GameObject>>
    // где ее размеры это mapWidth/mapHeight
    if (!sortData.isPointObject) {
        for (h in 0...instance.height) {
            var y = instance.y + h;
            for (w in 0...instance.width) {
                var x = instance.x + w;
                map[y][x].go = instance;
            }
        }
    }
}

Часть 5. Зона видимости (туман войны)

К изначальному заданию прилагался алгоритм зоны видимости. Так что это довольно простая часть (хотя проверить ее достаточно проблемно).

visibleX и visibleY - позиция, где находится "игрок" - всегда видимая точка

В игре также присутствует зона блокировки - эти просто набор тайлов, заданый вручную, которые блокируют обзор.

// Основной метод, который вычисляет 
public function calculateVisibility(map:Array<Array<TileInfo>>):Void {
    // Игрок всегда видит себя
    map[visibleY][visibleX].visibility = TileVisibility.VISIBLE;

    // Выполняем поиск в ширину начиная с исходной клетки
    var queue = [{x: visibleX, y: visibleY}];
    while (queue.length > 0) {
        var current = queue.shift();
        // Рассматриваем соседние клетки
        for (n in getNeighbors(current.x, current.y)) {
            var nTile = map[n.y][n.x];
            if (n.x < 0 || n.x >= mapWidth || n.y < 0 || n.y >= mapHeight) continue;
            if (nTile.visibility != TileVisibility.INVISIBLE) continue;

            var visibility = calculateTileVisibility(nTile, map);
            nTile.visibility = visibility;

            // Добавляем в очередь видимый или полувидимые клетки
            if (visibility == TileVisibility.VISIBLE || visibility == TileVisibility.SEMIVISIBLE) {
                queue.push({x: n.x, y: n.y});
            }
        }
    }
}

// Просто 4 клетки по бокам. Диагональные не учитывем.
private function getNeighbors(x:Int, y:Int):Array<{x:Int, y:Int}> {
    var neighbors = [
        {x: x - 1, y: y},
        {x: x + 1, y: y},
        {x: x, y: y - 1},
        {x: x, y: y + 1}
    ];

    return neighbors.filter(function(n) {
        return n.x >= 0 && n.x < mapWidth && n.y >= 0 && n.y < mapHeight;
    });
}

public function calculateTileVisibility(tile:TileInfo, map:Array<Array<TileInfo>>):TileVisibility {
    var x = tile.x;
    var y = tile.y;

    // Игрок всегда виден
    if (x == visibleX && y == visibleY) {
        return TileVisibility.VISIBLE;
    }

    // 1. В зоне блокировки
    if (tile.isLocked) {
        return TileVisibility.BLOCKED;
    }

    var go = tile.go;

    // 2. Касается занятого заблокированного тайла и сам занят тем же объектом – заблокирован
    for (n in getNeighbors(x, y)) {
        var nTile = map[n.y][n.x];
        if (!nTile.hasVisibility || nTile.visibility != TileVisibility.BLOCKED) {
            continue;
        }

        if (nTile.go != null && nTile.go == go) {
            return TileVisibility.BLOCKED;
        }
    }

    // 3. Касается свободного видимого тайла – видимый
    for (n in getNeighbors(x, y)) {
        var nTile = map[n.y][n.x];
        if (!nTile.hasVisibility || nTile.visibility != TileVisibility.VISIBLE) {
            continue;
        }

        if (nTile.go == null) {
            return TileVisibility.VISIBLE;
        }
    }

    // 4. Касается занятого видимого тайла и сам занят тем же объектом – видимый
    for (n in getNeighbors(x, y)) {
        var nTile = map[n.y][n.x];
        if (!nTile.hasVisibility || nTile.visibility != TileVisibility.VISIBLE) {
            continue;
        }

        if (nTile.go != null && nTile.go == go) {
            return TileVisibility.VISIBLE;
        }
    }

    // 5. Касается занятого видимого тайла – полувидимый
    for (n in getNeighbors(x, y)) {
        var nTile = map[n.y][n.x];
        if (!nTile.hasVisibility || nTile.visibility != TileVisibility.VISIBLE) {
            continue;
        }

        if (nTile.go != null) {
            return TileVisibility.SEMIVISIBLE;
        }
    }

    // 6. Касается занятого полувидимого тайла и сам занят тем же объектом – полувидимы
    for (n in getNeighbors(x, y)) {
        var nTile = map[n.y][n.x];
        if (!nTile.hasVisibility || nTile.visibility != TileVisibility.SEMIVISIBLE) {
            continue;
        }

        if (nTile.go != null && nTile.go == go) {
            return TileVisibility.SEMIVISIBLE;
        }
    }

    // 7. Тайл невидимый
    return TileVisibility.INVISIBLE;
}

Здесь особо нечего рассказывать - есть последовательный алгоритм и его надо просто реализовать.

Часть 6. Интерактив

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

Честно признаюсь - здесь можно было написать лучше, но уже было лень.

private function onClick(event:OnClickEvent):Void {
    // Находим объект, по которому кликнули
    var n = Math.round(Constants.TILE_LENGTH / Constants.TILE_HEIGHT);
    var target = findGameObjectForClick(event.tileX, event.tileY);
    if (target == null || target.go == null) {
        return;
    }

    // Если у объекта есть родитель, то это курица на стене
    // Уничтожаем курицу и удаляем связь стены с ней
    // Также удаляем из очереди на рендер - больше нет курицы!
    if (target.parent != null) {
        objectFactory.destroyObject(target.go);
        target.parent.removePointObject(target.go);
        renderObjects.remove(target.go);
        return;
    }

    // Уничтожаем стену или курицу на полу
    destroyObject(target.go);
}

// Уничтожение стены и одиноких куриц
private function destroyObject(go:GameObject) {
        if (go == null) {
            return;
        }

        // Уничтожаем первую курицу на полу (их может быть несколько)
        var pointerObjectList = unparentPointObjects[go.y][go.x];
        if (pointerObjectList != null && pointerObjectList.length > 0) {
            var go = pointerObjectList[pointerObjectList.length - 1];
            renderObjects.remove(go);
            objectFactory.destroyObject(go);
            pointerObjectList.remove(go);

            // Обновляем видимость на карте если требуется по логике игры
            // updateVisibility();
            return;
        }

        // Удаляем стену
        // Обращаю внимание, что всю информацию можно получить из главного
        // тайла - у точки, где насполагается стена (go.x; go.y)
        // В остальных тайлах информации о курицах нету
        var root = map[go.y][go.x];
        for (go in root.getPointObjects()) {
            renderObjects.remove(go);
            objectFactory.destroyObject(go);
        }

        renderObjects.remove(go);
        objectFactory.destroyObject(go);

        // Вычищаем информацию о стене из каждого тайла
        for (h in 0...go.height) {
            var y = root.y + h;
            if (y < 0 || y >= map.length) {
                continue;
            }

            for (w in 0...go.width) {
                var x = root.x + w;
                if (x < 0 || y >= map[y].length) {
                    continue;
                }

                var t = map[y][x];
                t.go = null;
                t.clearPointObjects();
            }
        }

        // Обновляем видимость на карте
        updateVisibility();
    }

Самый некрасивый код - найти объект для удаления. Он некрасив в основном из-за куриц, стоящих на стене, хотя логика довольно проста:

• Проверь курицу на стене - от +8 до 0 тайлов от текущего (две высоты) и вниз

• Проверь стену - от +4 до 0 (одна высота) тайлов вниз.

private function findGameObjectForClick(tileX:Int, tileY:Int):{ go: GameObject, parent:TileInfo } {
    var n = Math.round(Constants.TILE_LENGTH / Constants.TILE_HEIGHT);
    // Ищем курицу на стене
    var parentedObject = tryFindParentedPointObject(tileX, tileY, n);
    if (parentedObject != null) {
        return parentedObject;
    }

    // Раз курица не найдена, то ищем стену или курицу на полу
    for (i in 0...n + 1) {
        var x = tileX + n - i;
        var y = tileY + n - i;

        if (y < 0 || y >= map.length) {
            continue;
        }

        var row = map[y];
        if (x < 0 || x >= row.length) {
            continue;
        }

        // Проверяем что это курица на полу
        var tile = row[x];
        var po = unparentPointObjects[y][x];
        if (po != null && po.length > 0) {
            // Возвращаем первую попавшуюся в тайле курицу
            destroyObject(po[0]);
            return { go: po[0], parent: null };
        }

        // Тайл пустой - идем дальше
        if (tile.go == null) {
            continue;
        }

        // Найдена стена
        return { go: tile.go, parent: null };
    }

    return null;
}

private function tryFindParentedPointObject(tileX:Int, tileY:Int, n:Int):{ go:GameObject, parent:TileInfo } {
    // Ищем курицу на стене
    for (i in 0...n) {
        var x = tileX + n * 2 - i;
        var y = tileY + n * 2 - i;
        if (y < 0 || y >= map.length || x < 0 || x >= map[0].length) {
            continue;
        }

        var tile = map[y][x];
        if (tile.go == null) {
            continue;
        }

        var rootTile = map[tile.go.y][tile.go.x];
        var childs = rootTile.getPointObjects();
        for (child in childs) {
            if (child.x == x && child.y == y) {
                return { go: child, parent: rootTile };
            }
        }
    }

    return null;
}

Послесловие

Игра выдает стабильные 60fps, но не стоит делать тестовое, если оно не оплачиваемое потому что сейчас давать фидбек - не модно. Вот какой фидбек я получил:

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

Мы оцениваем тестовое по нескольким параметрам:

1. Все ли требования задания удовлетворены

2. Насколько корректно написан алгоритм сортировки: объекты на сцене расположены на верных местах и в правильном порядке

3. Насколько правильно реализован алгоритм распространения видимости

4. Производительность демо-сцены: показывает ли она достаточный fps, в том числе при изменении масштаба и перемещении камеры

5. Общий подход к решению задачи и его совместимость с нашими подходами к работе

6. Чистота и эффективность кода

7. Насколько легко удалось запустить сцену, требовались ли правки для запуска

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

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

PS Может кто-то в комментариях подскажет что не так :)

Ссылка на проект: https://github.com/truenoob141/haxe_game