Аппроксимация кривой в траекторию стрелы для игры St.Val

в 8:12, , рубрики: game development

В этом посте я расскажу, как создать в мобильном приложении управление c помощью рисования траектории. Такое управление используется в Harbor Master и FlightControl: игрок пальцем рисует линию, по которой движутся корабли и самолеты. Для моей игры St.Val потребовалась аналогичная механика. Как я её делал и с чем пришлось столкнуться — читайте ниже.

Аппроксимация кривой в траекторию стрелы для игры St.Val

Пара слов об игре. В St.Val основная цель соединять сердца по цвету с помощью стрел. Задача игрока: построить траекторию полета стрелы так, чтобы она соединяла сердца в полете. Игра создавалась на базе Cocos2D 2.1 под iOS, ниже видео игровой механики.

Основные задачи

Для создания управления нужно решить три задачи:

  1. Считать координаты
  2. Сгладить и аппроксимировать их
  3. Запустить по ним стрелу

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

Под катом решение этих задач и ссылка на демонстрационный проект.

Код демо-проекта доступен тут: github.com/AndreyZarembo/TouchInput

Как считываются координаты

Чтение координат пальца — простая задача, поскольку в Cocos2D есть работа с отдельными Touch-событиями, разделенными по типу. Чтобы их получать, объект реализует протокол CCTouchOneByOneDelegate и регистрируется у диспетчера Touch-cобытий:

[[[CCDirector sharedDirector] touchDispatcher] addTargetedDelegate:self priority:0 swallowsTouches: YES];

Протокол CCTouchOneByOneDelegate включает методы:

// Палец коснулся экрана
- (BOOL)ccTouchBegan:(UITouch *)touch withEvent:(UIEvent *)event
// Палец переместился по экрану
- (void)ccTouchMoved:(UITouch *)touch withEvent:(UIEvent *)event
// Палец подняли
- (void)ccTouchEnded:(UITouch *)touch withEvent:(UIEvent *)event
// Палец куда-то внезапно пропал или случилось что-то не то
- (void)ccTouchCancelled:(UITouch *)touch withEvent:(UIEvent *)event

Для игры нужен всего один палец, поэтому достаточно при первом касании сохранить UITouch в переменную currentTouch. Если она не равна nil, значит движение уже отслеживается.

Когда палец отпущен, обнуляем переменную currentTouch, а в обработчике движения ccTouchMoved проверяем, тот ли это объект, за которым ведется наблюдение. Если да — записываются точки.

Подводный камень 1

Все это здорово работает, пока не используются жесты сворачивания игры и не всплывает панель центра управления. В этих случаях ccTouchCancelled не вызывается, но и событие ccTouchMoved уже не приходит. Исправить это можно проверкой phase у пальца. Если _currentTouch.phase == UITouchPhaseCancelled, то палец надо менять:

- (BOOL)ccTouchBegan:(UITouch *)touch withEvent:(UIEvent *)event {
    if (currentTouch == nil || currentTouch.phase == UITouchPhaseCancelled) {
        currentTouch = touch;
    }
    return YES;
}

- (void)ccTouchMoved:(UITouch *)touch withEvent:(UIEvent *)event {
    if (touch == currentTouch) {
	// Save point
    }
}

- (void)ccTouchEnded:(UITouch *)touch withEvent:(UIEvent *)event {
    if (touch == currentTouch) {
	// End trajectory
    }
}

- (void)ccTouchCancelled:(UITouch *)touch withEvent:(UIEvent *)event {
    if (touch == currentTouch) {
	// End trajectory
    }
}

Что делать с координатами

Координаты придется отфильтровать и аппроксимировать, чтобы линия выглядела гладкой и объекты по ней двигались равномерно.

Для сглаживания кривой используется фильтр по расстоянию: все точки должны быть друг от друга на расстоянии не меньше 20px. Это в полтора раза меньше, чем палец на экране, поэтому фильтрация скрыта. При расстоянии фильтрации в 20px, количество обрабатываемых точек уменьшается на 50-70%, в пределе это 95%, когда палец движется по экрану пиксель за пикселем.

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

Аппроксимация кривой в траекторию стрелы для игры St.Val

Чтобы кривая начиналась с первой точки, добавляем граничные условия: точки добавляются по прямой к первому и последнему сегментам. Тогда для N точек мы получаем N-1 сегмент.

Аппроксимация кривой в траекторию стрелы для игры St.Val

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

Подводный камень 2

В описанной кривой движение в координатах экрана будет неравномерным. Для того, чтобы сгладить движение, каждый сегмент разбивается на прямые отрезки по 10px. Такой размер был выбран по двум причинам:

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

Механика разбиения на отрезки достаточно проста. Для каждого сегмента в цикле перебираются точки с таким шагом, чтобы проходить расстояние в 1px, каждая точка сравнивается с последней сохраненной точкой сплайна. Если расстояние больше 10px, вычисляется, на сколько оно больше, вносится поправка по прямой и новая точка добавляется в массив сплайна. Для оптимизации эта операция выполняется только для новых точек. В итоге получаем массив из точек, которые отстоят друг от друга на расстоянии 10px и повторяют траекторию движения пальца.

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

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

В игре траектория отображается движущимися точками («следами»). Они расположены на кривой каждые 20px и движутся равномерно к концу траектории. Чтобы создать эффект движения и упростить анимацию, точки движутся в пределах двух отрезков по 10 пикселей, от 0 до 20, затем опять возвращаются в 0. За счет синхронного движения кажется, что они движутся непрерывно от начала до конца.

Если в кривой N+1 точек, то N отрезков, по которым движутся следы, соответственно, нужно разместить N/2 следов. Для всех точек задается смещение T, в пределах [0,2], которое используется для вычисления координаты каждого из следов.

При T от 0 до 1, положение вычисляется как

Pt = Pt0*t+(1-t)*Pt1

При T от 1 до 2 положение вычисляется как

Pt = Pt1*(t-1)+(2-t)*Pt2

Аппроксимация кривой в траекторию стрелы для игры St.Val

В результате все точки движутся «гуськом».

Запуск стрелы

Запуск стрелы сделан с помощью Actions из Cocos 2D. Он состоит из следующих этапов:

  1. Задание начального положения стрелы
  2. Последовательное перемещение и вращение стрелы по сегментам кривой
  3. Скрытие стрелы

В игре этих этапов больше, но суть не меняется.

Для сбора очередности действий и запуска их выполнения, все действия последовательно добавляются в NSMutableArray и передается объекту ССSequence для запуска цепочки действий.

Первым добавляется CCCallBlock для задания начального положения — это координаты первой точки кривой. Здесь же стреле задается полная непрозрачность.

CCCallBlock *setInitialPosition = [CCCallBlock actionWithBlock:^{
    _arrow.position = pointVal.CGPointValue;
    _arrow.opacity = 255;
}];
[moves addObject: setInitialPosition];

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

Подводный камень 3

Элементы кривой получаются почти по 10 пикселей, но не точно, поэтому для равномерного движения стрелы нужно уточнять длину сегмента и определять время движения по каждому сегменту на основании скорости стрелы.

CGPoint point = pointVal.CGPointValue;
CGPoint prevPoint = prevPointVal.CGPointValue;
CGPoint diff = CGPointMake(point.x-prevPoint.x, point.y-prevPoint.y);
        
CGFloat distance = hypotf(diff.x,diff.y);
CGFloat duration = distance / arrowSpeed;
lastDirectionVector = CGPointMake(diff.x/distance, diff.y/distance);
            
CGFloat angle = -atan2f(diff.y,diff.x)*180./M_PI;
            
CCMoveTo *moveArrow = [CCMoveTo actionWithDuration: duration position: point];
CCRotateTo *rotateArrow = [CCRotateTo actionWithDuration: duration angle: angle];
CCSpawn *moveAndRotate = [CCSpawn actionWithArray: @[ moveArrow, rotateArrow ]];
            
[moves addObject: moveAndRotate];

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

CCFadeTo *hideArrow = [CCFadeTo actionWithDuration: hideEffectDuration opacity:0];
CCMoveBy *moveArrow = [CCMoveBy actionWithDuration: hideEffectDuration position: CGPointMake(lastDirectionVector.x*arrowSpeed*hideEffectDuration, lastDirectionVector.y*arrowSpeed*hideEffectDuration)];
CCSpawn *moveAndHide = [CCSpawn actionWithArray: @[ moveArrow, hideArrow ]];
[moves addObject: moveAndHide];

После добавления всех элементов стрела отправляется в полет.

[_arrow runAction: [CCSequence actionWithArray: moves]];

Обнаружение петель

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

Для этого набор отрезков просматривается последовательно и проверяется, не пересекается ли отрезок сегмента с отрезком предыдущих сегментов. Пересечение определяется с помощью метода «Ориентированная площадь треугольника», т.к. сама точка пересечения не важна, а номера пересекающихся сегментов известны из цикла. Алгоритм взят отсюда:
e-maxx.ru/algo/segments_intersection_checking

Подводный камень 4

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

Аппроксимация кривой в траекторию стрелы для игры St.Val

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

[path containsPoint: position]

Вот и все!

Код демо-проекта доступен тут: github.com/AndreyZarembo/TouchInput

p.s. В процессе подготовки поста код был немного изменен и оптимизирован.

Автор: shadow_of_irbis

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js