Аппроксимация кривой в траекторию стрелы для игры St.Val
В этом посте я расскажу, как создать в мобильном приложении управление c помощью рисования траектории. Такое управление используется в Harbor Master и FlightControl: игрок пальцем рисует линию, по которой движутся корабли и самолеты. Для моей игры St.Val потребовалась аналогичная механика. Как я её делал и с чем пришлось столкнуться — читайте ниже.
Пара слов об игре. В St.Val основная цель соединять сердца по цвету с помощью стрел. Задача игрока: построить траекторию полета стрелы так, чтобы она соединяла сердца в полете. Игра создавалась на базе Cocos2D 2.1 под iOS, ниже видео игровой механики.
[embedded content]
Основные задачи Для создания управления нужно решить три задачи: Считать координаты Сгладить и аппроксимировать их Запустить по ним стрелу Плюс отдельно я опишу алгоритм обнаружения петель в траекториях, который мне понадобился для расширения механики игры.
Под катом решение этих задач и ссылка на демонстрационный проект.
Код демо-проекта доступен тут: 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 } } Что делать с координатами Координаты придется отфильтровать и аппроксимировать, чтобы линия выглядела гладкой и объекты по ней двигались равномерно.Для сглаживания кривой используется фильтр по расстоянию: все точки должны быть друг от друга на расстоянии не меньше 20 px. Это в полтора раза меньше, чем палец на экране, поэтому фильтрация скрыта. При расстоянии фильтрации в 20 px, количество обрабатываемых точек уменьшается на 50–70%, в пределе это 95%, когда палец движется по экрану пиксель за пикселем.
Полученную цепочку точек необходимо аппроксимировать кривой, для этого используется сплайн Катмулла-Рома. Он проходит через заданные 4 точки, сглаживает ступеньки и прост для вычисления.
Чтобы кривая начиналась с первой точки, добавляем граничные условия: точки добавляются по прямой к первому и последнему сегментам. Тогда для N точек мы получаем N-1 сегмент.
Пост получился объемным, поэтому не буду подробно рассказывать про саму кривую, ниже будет код для вычисления её сегментов.
Подводный камень 2 В описанной кривой движение в координатах экрана будет неравномерным. Для того, чтобы сгладить движение, каждый сегмент разбивается на прямые отрезки по 10 px. Такой размер был выбран по двум причинам: это круглое число, поэтому легко определить, сколько нужно сегментов, чтобы разместить на кривой объект с заданной нормальной координатой (расстояние, пройденное по кривой); это достаточно маленький размер, чтобы ступенчатость не давала о себе знать, при этом количество точек разбиения сокращается на порядок. Механика разбиения на отрезки достаточно проста. Для каждого сегмента в цикле перебираются точки с таким шагом, чтобы проходить расстояние в 1 px, каждая точка сравнивается с последней сохраненной точкой сплайна. Если расстояние больше 10 px, вычисляется, на сколько оно больше, вносится поправка по прямой и новая точка добавляется в массив сплайна. Для оптимизации эта операция выполняется только для новых точек. В итоге получаем массив из точек, которые отстоят друг от друга на расстоянии 10 px и повторяют траекторию движения пальца.
В игре нельзя нарисовать бесконечную траекторию, поэтому было добавлено условие конца рисования по длине.
Движение объектов В игре траектория отображается движущимися точками («следами»). Они расположены на кривой каждые 20 px и движутся равномерно к концу траектории. Чтобы создать эффект движения и упростить анимацию, точки движутся в пределах двух отрезков по 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
В результате все точки движутся «гуськом».
Запуск стрелы Запуск стрелы сделан с помощью Actions из Cocos 2D. Он состоит из следующих этапов: Задание начального положения стрелы Последовательное перемещение и вращение стрелы по сегментам кривой Скрытие стрелы В игре этих этапов больше, но суть не меняется.
Для сбора очередности действий и запуска их выполнения, все действия последовательно добавляются в 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
Алгоритм работает хорошо, но на длинной кривой медленно. Поэтому проверка была доработана так, чтобы проверять не каждый отрезок из пяти, а один большой. Число пять магическое и было подобрано эмпирически. Берется начальная точка блока из пяти точек, пропускаются первые четыре, и пятая берется как конечная, она же будет следующей начальной точкой. Точность определения снижается, но потери допустимы. Можно повысить точность, если проверять маленькие сегменты внутри пересекающихся больших.
Все найденные петли сохраняются в массив как номера начального и конечного сегментов кольца. Из них получались точки многоугольника UIBezierPath, который обладает штатными средствами определения, попадает ли в него точка.
[path containsPoint: position] Вот и все!
Код демо-проекта доступен тут: github.com/AndreyZarembo/TouchInput
p.s. В процессе подготовки поста код был немного изменен и оптимизирован.
