Интерполяция, экстраполяция и аппроксимация

Интерполяция, экстраполяция, аппроксимация — замечательные слова, которые звучат как магия и делают её. Однако иногда юные разработчики путают названия заклинаний, что иногда мешает в коммуникации или даже разработке. Так что же это такое и как используется в разработке игр? Сейчас разберемся на примерах.

Небольшая математическая вводная, которая необходима для плодотворного диалога:

• Функция — правило зависимости одной величины от другой.
• Полином (многочлен) — выражение, состоящее из переменных и коэффициентов, которое включает только операции сложения, вычитания, умножения, деления и возведения переменных в степень.

Например, y = x^2 - 5x + 25 — функция и полином второй степени.

Теперь можно переходить к сути.

Интерполяция

Предположим, что мы делаем простенький point-and-click. Игрок сейчас находится в точке A, и щелкает в B. Как плавно его переместить из A в B? Необходимо построить какую-то функцию, которая обязательно проходит через точки начало и конца и находит значения между ними. Вот и есть простой пример интерполяции.

Интерполяция — приближенное нахождение промежуточных значений между известными.

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

1. (0, 1);
2. (1, 1);
3. (2, 0.5);
4. (3, 0.3).

Если применить метод линейной интерполяции, то получится ломанная:

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

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

Полезные видео по интерполяции и чуть более углубленно, почему оно работает так:

1. Lagrange Interpolation
2. Cosine Interpolation
3. The Beauty of Bézier Curves

Вот, вы когда-нибудь задумывались что такое Lerp и Slerp в Unity? Это же просто Linear Interpolation и Spherical Linear Interpolation.

Экстраполяция

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

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

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

Ещё несколько полезных ссылок:

1. Интерполяция и экстраполяция на примере Planteside 2
2. Using Pre and Post Extrapolation in Timeline (Unity)
3. Серия из 4 статей про мультиплеер в быстрых играх (перевод)

Аппроксимация

Аппроксимация — приближенное представление сложной функции более простой, имеющей минимальное отклонение от исходной.

Такую операцию можно легко сделать в Google Sheets / Excel:

1. Выбираем необходимый диапазон данных;
2. Строим по этим данным диаграмму;
3. Включаем линию тренда в настройках диаграммы.

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

Выбора типа линии остаётся за исследователем, также как и особые настройки конкретного типа (например, порядок полиномиального приближения).

Два важных свойства линии тренда:

1. Ярлык > уравнение покажет уравнение функции, что в последствии можно (и нужно) использовать;
2. R2 (Коэффициент детерминации) — значение, которое измеряется от 0 до 1 и показывает, как хорошо линия тренда описывает имеющиеся значения.

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

По итогу получается вот такой график:

Коэффициент детерминации — единичка, значит функция проходит через все имеющие точки и может заодно выступать интерполяцией. Если задуматься, то на самом деле получился просто «приведенный» полином Лагранжа.

Рассмотрим другой пример, пусть наши точки имеющие следующие координаты:

1. (0, 1);
2. (1, 2.05);
3. (2, 2.9);
4. (3, 4.1).

Если приглядеться и подумать, то они практически образуют линейную зависимость. Метод Лагранжа естественно выдаст полином 3 степени, а вот аппроксимировать можно линейно, тогда R-квадрат будет 0.93. В точности почти не теряем, но выиграем за счет значительного упрощения функции.

Что использовать остаётся на откуп исследователю. Здесь было бы логичнее пренебречь простотой, так как в абстрактном примере мы строим функцию пролета камеры, а ей нужны красивые «виражи», а не просто прямой пролёт.

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

PS Как можно было догадаться, интерполяция и экстраполяция — особые виды аппроксимации.

Заключение

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

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

Напоследок:

1. Интерполяция — внутри;
2. Экстраполяция — вовне;
3. Аппроксимация — примерно везде.