Перемещение кораблей между двумя планетами вдоль безье, пропуская некоторые уравнения для ускорения

Хорошо, я уже опубликовал это на math.stackechange.com, но не получил никаких ответов :(

Сначала приведу картину моей проблемы, описание следует потом:

Итак, я настроил все пункты и ценности.

Корабль начинает двигаться по левой планете P1с S=0.27 Degreesкаждой игровой меткой, когда он достигает Point Aего, начинает следовать по кривой Безье до тех пор, пока не достигнет Point D, затем он движется вокруг правой планеты P2с тактом S=0.42 Degreesза игру. Разница в Sтом, что путешествуйте с одинаковой скоростью движения вокруг планет.

Пока все хорошо, у меня все получилось, теперь моя проблема.

Когда S P1и S P2сильно отличаются, корабль прыгает между двумя скоростями, когда он достигает пункта назначения, что выглядит довольно плохо. Поэтому мне нужно , чтобы ускорить корабль между Point Aи Point Dот S P1к S P2.

Вещи, которые я пропускаю, в фиолетовом, это:

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

• И способ найти положение на кривой Безье на основе T, опять же с учетом ускорения.

Я рассчитываю длину безье, рассчитывая расстояние между Nего точками. Так что я думаю, что мне нужно, это способ масштабирования того, что Tмне нужно включить в мои вычисления Безье, в соответствии с ускорением.

Хорошо, у меня все работает, это заняло вечность, поэтому я опубликую свое подробное решение здесь.
Примечание: все примеры кода в JavaScript.

Итак, давайте разберем проблему на основные части:

1. Вам нужно вычислить длину, а также точки между 0..1на кривой Безье

2. Теперь вам нужно настроить масштаб, Tчтобы ускорить корабль с одной скорости до другой

Правильно понять Безье

Найти некоторый код для рисования кривой Безье легко, хотя есть несколько различных подходов, один из них - алгоритм Де-Кастельхау , но вы также можете просто использовать уравнение для кубических кривых Безье:

// Part of a class, a, b, c, d are the four control points of the curve
x: function (t) {
    return ((1 - t) * (1 - t) * (1 - t)) * this.a.x
           + 3 * ((1 - t) * (1 - t)) * t * this.b.x
           + 3 * (1 - t) * (t * t) * this.c.x
           + (t * t * t) * this.d.x;
},

y: function (t) {
    return ((1 - t) * (1 - t) * (1 - t)) * this.a.y
           + 3 * ((1 - t) * (1 - t)) * t * this.b.y
           + 3 * (1 - t) * (t * t) * this.c.y
           + (t * t * t) * this.d.y;
}

С этим теперь можно нарисовать кривую Безье, вызвав xи yс tдиапазонами 0 to 1, давайте посмотрим:

Э-э ... это не совсем равномерное распределение очков, не так ли?
В связи с характером кривой Безье точки 0...1имеют разные точки arc lenghts, поэтому сегменты вблизи начала и конца длиннее, чем те, которые находятся ближе к середине кривой.

Равномерное отображение T на кривой AKA Параметризация длины дуги

Так что делать? Говоря простым языком, нам нужна функция для отображения нашего Tна tкривую, чтобы наши T 0.25результаты tбыли на 25%длине кривой.

Как мы это делаем? Ну, мы в Google ... но оказывается, что этот термин не так уж гугл , и в какой-то момент вы попадете в этот PDF . Это, безусловно, отличное чтение, но в случае, если вы уже забыли все математические вещи, которые вы изучали в школе (или вам просто не нравятся эти математические символы), это довольно бесполезно.

Что теперь? Ну, иди и Google еще немного (читай: 6 часов), и ты, наконец, найдешь отличную статью по этой теме (включая красивые картинки! ^ _ ^ "):
Http://www.planetclegg.com/projects/WarpingTextToSplines.html

Делать фактический код

Если вы просто не смогли устоять перед загрузкой этих PDF, хотя вы уже давно потеряли свои математические знания (и вам удалось пропустить великолепную ссылку на статью), вы можете подумать: «Боже, это займет сотни строк кода и тонны процессора »

Нет, не будет. Потому что мы делаем то, что делают все программисты, когда дело касается математики:
мы просто обманываем.

Параметрирование длины дуги, ленивый путь

Посмотрим правде в глаза, нам не нужна бесконечная точность в нашей игре, не так ли? Поэтому, если вы не работаете в Nasa и не планируете отправлять людей на Марс, вам не понадобится 0.000001 pixelидеальное решение.

Так, как мы наносим Tна карту t? Это просто и состоит только из 3 шагов:

1. Вычислите Nточки на кривой, используя tи сохраните arc-length(или длину кривой) в этой позиции в массив

2. Чтобы отобразить Tна tпервую умножить Tна общую длину кривой , чтобы получить , uа затем искать массив длин для индекса наибольшего значения , которое меньшеu

3. Если у нас был точный результат, вернуть значение массива по этому индексу, разделенное N, если не интерполировать немного между найденной точкой и следующей, разделить вещь еще раз Nи вернуть.

Вот и все! Итак, теперь давайте посмотрим на полный код:

function Bezier(a, b, c, d) {
    this.a = a;
    this.b = b;
    this.c = c;
    this.d = d;

    this.len = 100;
    this.arcLengths = new Array(this.len + 1);
    this.arcLengths[0] = 0;

    var ox = this.x(0), oy = this.y(0), clen = 0;
    for(var i = 1; i <= this.len; i += 1) {
        var x = this.x(i * 0.05), y = this.y(i * 0.05);
        var dx = ox - x, dy = oy - y;        
        clen += Math.sqrt(dx * dx + dy * dy);
        this.arcLengths[i] = clen;
        ox = x, oy = y;
    }
    this.length = clen;    
}

Это инициализирует нашу новую кривую и вычисляет arg-lenghts, а также сохраняет последнюю из длин в total lengthкачестве кривой, ключевым фактором здесь this.lenявляется наша N. Чем выше, тем более точным будет сопоставление, поскольку кривой размера на рисунке выше 100 pointsкажется достаточным, если вам просто нужна хорошая оценка длины, что-то вроде 25этого уже выполнит свою работу, когда у нас всего 1 пиксель. Например, но тогда у вас будет менее точное отображение, что приведет к неравномерному распределению Tпри сопоставлении t.

Bezier.prototype = {
    map: function(u) {
        var targetLength = u * this.arcLengths[this.len];
        var low = 0, high = this.len, index = 0;
        while (low < high) {
            index = low + (((high - low) / 2) | 0);
            if (this.arcLengths[index] < targetLength) {
                low = index + 1;

            } else {
                high = index;
            }
        }
        if (this.arcLengths[index] > targetLength) {
            index--;
        }

        var lengthBefore = this.arcLengths[index];
        if (lengthBefore === targetLength) {
            return index / this.len;

        } else {
            return (index + (targetLength - lengthBefore) / (this.arcLengths[index + 1] - lengthBefore)) / this.len;
        }
    },

    mx: function (u) {
        return this.x(this.map(u));
    },

    my: function (u) {
        return this.y(this.map(u));
    },

Фактический код отображения: сначала мы делаем простую binary searchс нашими сохраненными длинами, чтобы найти наибольшую длину, которая меньше targetLength, затем мы просто возвращаем или выполняем интерполяцию и возвращаем.

    x: function (t) {
        return ((1 - t) * (1 - t) * (1 - t)) * this.a.x
               + 3 * ((1 - t) * (1 - t)) * t * this.b.x
               + 3 * (1 - t) * (t * t) * this.c.x
               + (t * t * t) * this.d.x;
    },

    y: function (t) {
        return ((1 - t) * (1 - t) * (1 - t)) * this.a.y
               + 3 * ((1 - t) * (1 - t)) * t * this.b.y
               + 3 * (1 - t) * (t * t) * this.c.y
               + (t * t * t) * this.d.y;
    }
};

Опять же, это вычисляется tна кривой.

Время для результатов

Теперь, используя mxи myвы получите равномерное распределение Tпо кривой :)

Разве это не сложно? Еще раз, оказывается, что простого (хотя и не идеального решения) будет достаточно для игры.

Если вы хотите увидеть полный код, есть доступный Gist:
https://gist.github.com/670236

Наконец, ускорение кораблей

Таким образом, все, что осталось сейчас, - это ускорить корабли вдоль их пути, отображая положение, в Tкотором мы затем используем их для нахождения tна нашей кривой.

Сначала нам нужно два уравнения движения , а именно ut + 1/2at²и(v - u) / t

В реальном коде это будет выглядеть так:

startSpeed = getStartingSpeedInPixels() // Note: pixels
endSpeed = getFinalSpeedInPixels() // Note: pixels
acceleration = (endSpeed - startSpeed) // since we scale to 0...1 we can leave out the division by 1 here
position = 0.5 * acceleration * t * t + startSpeed * t;

Затем мы уменьшаем это до 0...1:

maxPosition = 0.5 * acceleration + startSpeed;
newT = 1 / maxPosition * position;

И вот, корабли теперь плавно движутся по пути.

Если это не работает ...

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

Если вы еще не забыли про картинку в исходном вопросе, я упоминаю sтам, оказывается, что sэто скорость в градусах , но корабли движутся по пути в пикселях, и я забыл об этом факте. Поэтому в этом случае мне нужно было преобразовать смещение в градусах в смещение в пикселях, и оказалось, что это довольно просто:

function rotationToMovement(planetSize, rotationSpeed) {
    var r = shipAngle * Math.PI / 180;
    var rr = (shipAngle + rotationSpeed) * Math.PI / 180;
    var orbit = planetSize + shipOrbit;
    var dx = Math.cos(r) * orbit - Math.cos(rr) * orbit;
    var dy = Math.sin(r) * orbit - Math.sin(rr) * orbit;
    return Math.sqrt(dx * dx + dy * dy);
};

Так вот и все! Спасибо за чтение ;)

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

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

Вам просто нужно установить свои константы: масса P1, P2, корабль

С каждым тактом игры (время: t) вы делаете 3 вещи

1. Рассчитайте гравитацию p1 на корабле и p2 на корабле, добавьте результирующие векторы к вектору тяги.

2. Рассчитайте вашу новую скорость на основе вашего нового ускорения с шага 1

3. Переместить корабль в соответствии с вашей новой скоростью

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

Если вам нужна помощь с физикой, дайте мне знать.

Я нашел отличную статью, объясняющую возможное решение этой проблемы с помощью примера кода, написанного на javascript. Он работает, «подталкивая» значение t в правильном направлении.

Вместо этого мы можем использовать тот факт, что средняя длина участка d_avg для любого распределения точек практически идентична длинам участков, которые будут иметь равномерно распределенные точки (это сходство увеличивается с увеличением n). Если мы вычислим разницу d_err между фактической длиной участка d и средней длиной участка d_avg, то временной параметр t, соответствующий каждой точке, можно сместить, чтобы уменьшить эту разницу.

На этот вопрос уже есть много интересных ответов, но я нашел, что это решение стоит отметить.

Спасибо за отличную страницу с описанием того, как вы решили эту проблему. Я сделал что-то несколько отличное от вас в одной детали, так как у меня были большие ограничения памяти: я не строю массив или не ищу его для правильного «сегмента» с помощью двоичного поиска. Это потому, что я всегда знаю, что перехожу с одного конца моей кривой Безье на другой: поэтому я просто запоминаю «текущий» сегмент, и если я увижу, что я собираюсь выйти за пределы этого сегмента, чтобы вычислить мой следующий положение, я вычисляю следующий (или предыдущий) сегмент (в зависимости от направления движения). Это хорошо работает для моего приложения. Единственный сбой, который мне пришлось решить, заключался в том, что на некоторых кривых размер сегментов был настолько мал, что мой следующий график, который нужно было указать, был в редких случаях более чем на один сегмент впереди текущего, поэтому вместо того, чтобы просто идти к

Не знаю, имеет ли это смысл, но это, безусловно, помогло мне.

Такое моделирование странно и может привести к странным нелогичным результатам. Особенно, если скорость стартовых планет очень мала.

Моделируйте корабли с силой тяги.

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

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

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

Если я правильно понимаю, ваша проблема слишком ограничена.

Я полагаю, что вы хотите, чтобы космический корабль путешествовал по заданному пути между орбитами в течение некоторого времени t , и вы также хотите, чтобы он ускорялся со скорости s1 до скорости s2 в то же время t . К сожалению, вы не можете (в общем) найти ускорение, которое удовлетворяет обоим этим ограничениям одновременно.

Вам нужно немного ослабить свою проблему, чтобы она разрешилась.

Я столкнулся с этим ответом, потому что я стремлюсь распределить точки равномерно вдоль пути SVG, который использует кривую Безье.

Несмотря на то, что MDN утверждает, что это устарело, вы можете использовать path.getPointAtLengthправильный результат. https://developer.mozilla.org/en-US/docs/Web/API/SVGPathElement/getPointAtLength

В настоящее время он работает в Chrome / Safari / Firefox и должен работать в IE / Edge, но я не проверял эти 2.

Проблема с принятым решением

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

Поскольку решение Ivo линейно интерполирует между этими начальными экспоненциальными выборками, неточности будут сильно смещены к концам / середине (обычно кубической) кривой, где эти дельты самые большие; поэтому, если частота выборки не Nбудет значительно увеличена, как он предполагает, ошибки будут очевидны, и при некотором уровне масштабирования всегда будут очевидными для данного N, то есть смещение является внутренним для этого алгоритма. Не подходит, например, для векторной графики, где масштабирование может быть неограниченным.

Противодействие смещению посредством управляемого отбора

Альтернативным решением является линейно переназначить , distanceчтобы tпосле того, как противодействие естественный уклон , что функция Безье производит.

Предполагая, что это то, что мы в идеале хотим:

curve length = 10

t      distance
0.2    2
0.4    4
0.6    6
0.8    8
1.0    10

но это то, что мы получаем из функции положения Безье:

t      distance
0.2    0.12
0.4    1.22
0.6    2.45
0.8    5.81
1.0    10.00

Посмотрев на Nвзятые выборки, мы можем увидеть, где дельты расстояния являются самыми большими, и пересчитать («разделить») на полпути между двумя соседними расстояниями, увеличившись Nна 1. Например, разделив на t=0.9(который находится на полпути в самой большой дельте), мы могли бы получить:

0.8    5.81
0.9    7.39
1.0    10.00

Мы повторяем этот процесс для следующего наибольшего интервала расстояний до тех пор, пока максимальная дельта между любыми двумя расстояниями во всем наборе не станет ниже некоторой minDistanceDelta, а более конкретно, меньше, чем на epsilonрасстоянии от определенных расстояний, которые мы хотим отобразить на шагах t; тогда мы можем линейно отобразить наши желаемые tшаги на соответствующие distances. Это создает хеш-таблицу / карту, к которой вы можете получить дешевый доступ и значения которой вы можете перемещать между во время выполнения, без смещения.

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

В итоге получается что-то вроде того, что мы в идеале хотели:

epsilon: 0.01

t            distance
0.200417     2.00417
0.3998132    3.9998132
0.600703     6.00703
0.800001     8.00001
0.9995309    9.995309

Так как мы принимаем догадки на каждом шаге, мы не получим точные точные расстояния 2и 4т. Д. , Которые мы хотели, но с помощью повторной итерации они достаточно приблизятся к желаемым значениям расстояний, поэтому вы сможете tс достаточной точностью отобразить ваши шаги, устраняя смещение из-за почти равноотстоящей выборке.

Затем вы можете получить, например t=0.5, как это делает Иво в своем ответе, т.е. путем интерполяции между двумя ближайшими значениями выше ( 3.9998132и 6.00703).

Заключение

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

Обратите внимание, что разделение может быть выполнено стохастически, а не делением по середине каждый раз, например, мы могли бы разделить этот первый примерный интервал на, t=0.827а не на t=0.9.