Как рассчитать пути для объектов с ограниченным ускорением?

Например, скажем, у меня есть машина, а у автомобиля определенный минимальный радиус поворота, и я хочу проехать на этой машине из точки а в точку b, но автомобиль не направлен в точку b. Как мне вычислить путь к точке b? Было бы неплохо иметь возможность указать ориентацию в точке b (скажем, вы хотите ехать к подъездной дороге, а затем подъехать к своему гаражу - это не принесет особой пользы, если вы дойдете до своей подъездной дороги, проехав через газон и сталкиваются боком :)

Указатель на документацию (или даже просто имя) был бы в порядке - у меня проблемы с поиском чего-либо вообще.

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

Например, как бы вы определили путь, похожий на этот (жирный путь):

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

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

( Авто иконки через Кенни )

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

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

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

(Это предполагает, что нам не нужно искать пути между препятствиями, что не было упомянуто в вопросе. Ответ Штормграда объясняет, как мы можем использовать информацию навигационного графика для этих типов проблем. Как только мы получим последовательность узлов чтобы пройти, мы можем применить метод ниже для каждого сегмента плана.)

Если для простоты мы используем прямые линии, мы получим что-то вроде этого:

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

Вычисление этих путей

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

Центр нашего правого поворотного круга:

startRightCenter = carStart.position + carStart.right * minRadius

Давайте назовем угол прямого участка нашего пути (измеренный от положительной оси x) pathAngle

Если мы рисуем вектор из rightCenterточки, где мы покидаем поворотный круг (в этой точке мы должны смотреть на pathAngle), то этот вектор ...

startOffset = minRadius * (-cos(pathAngle), sin(pathAngle))

Это означает, что точка, где мы покидаем круг, должна быть ...

departure = startRightCenter + startOffset

Точка, в которой мы снова входим в поворот, зависит от того, хотим ли мы закончить поворот налево или направо:

// To end with a right turn:
reentry = endRightCenter + startOffset

// To end with a left turn: (crossover)
reentry = endLeftCenter - startOffset

Теперь, если мы сделали свою работу правильно, линия , соединяющая departureв reentryдолжна быть перпендикулярно startOffset:

dot(reentry - departure,  startOffset) = 0

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

Давайте заменим случай правого поворота на правый поворот в качестве примера:

dot(endRightCenter + startOffset - startRightCenter - startOffset, startOffset) = 0
dot(endRightCenter - startRightCenter, startOffset) = 0
pathAngle = atan2(endRightCenter - startRightCenter)

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

Изменить: пункт назначения внутри минимального радиуса поворота

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

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

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

Принимая аналогичный сценарий из системы дорожного движения на воде, и с предположением, что

• вы в игровом цикле
• у вас есть система путей узлов
• ваши машины ведут себя как автономные объекты, которые управляют собой «изнутри», используя собственную силу и рулевое управление
• ваши машины не двигаются как на рельсах

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

(Красные квадраты - это узлы, красные линии - это соединения узлов. Предположим, что вы использовали механизм поиска пути, который дал узлы 1-9 для проезда; узлы 4-9 показаны на рисунке, и вы хотите пройти через узлы, обозначенные зеленой линией в гараже на узле № 9, однако вы не хотите идти точно по зеленой линии, вместо этого оставайтесь естественно на правой боковой полосе и выполняйте плавные маневры).

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

В любом случае , транспортное средство должно знать о следующих двух точках узла P (следующий) и P (следующий + 1), и их положениях. Естественно, у машины есть и позиция. Автомобиль нацелен на касательную с правой стороны синего круга метаданных P (следующая). Так что машины едут в противоположном направлении, поэтому они не будут сталкиваться. Наведение на касательную означает, что машина может приближаться к кругу с любого направления и всегда держаться правее. Это грубый базовый принцип, который можно улучшить многими способами.

P (следующий + 1) необходим для определения расстояния - когда автомобиль достигает P (следующий) или попадает в радиус своих метаданных, он может регулировать угол поворота рулевого колеса в зависимости от того, как далеко P (следующий + 1). То есть. если это близко, поверните много, если это далеко, поверните мало. Очевидно, что должны быть и другие правила и граничные условия, например, вычисление расстояния между автомобилем и вспомогательной линией на основе тангенсов правой стороны P (next) и P (next + 1) и коррекция этим - желание остаться на пунктирной (вверху картинке) и пунктирной (внизу картинке) линии.

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

На твой вопрос. По-видимому, при достижении узла 7 (на рисунке выше, обозначенном как узел 2 на рисунке ниже), он не может повернуть достаточно .

Одно из возможных решений - построить несколько линий помощи и поддерживать цель все время , а затем заставить автомобиль двигаться в соответствии с собственными физическими настройками (ускоряться с заданной скоростью, замедлять движение назад, принимать во внимание ограничения скорости метаданных узла, тормозить с заданной или рассчитанной скоростью). И т. Д.). Как уже говорилось, автомобиль является автономным, самоописывающим, самонесущим объектом в этом сценарии.

Имейте зеленые линии помощи 1,2,3 . Когда машина достигает пурпурного круга , начинается поворот направо. К этому моменту вы уже можете рассчитать, что это не удастся (вы знаете максимальную скорость поворота и можете рассчитать кривую, и увидите, что она пересечет обе линии помощи 2 и 3). Поверните рулевое колесо до упора вправо и дайте ему двигаться вперед (с шагом по физике) и замедлите его, когда оно достигает линии помощи 3 (приближается к - используйте пороги, f (расстояние до линии помощи) и т.д.). Когда он окажется на линии помощи 3, перейдите в режим реверса , поверните рулевое колесо до упора в противоположную сторону . Дайте повернуть вспять, пока не достигнете справочной линии 4(Линия соединения между узлами 1 и 2 - Google для "точки на стороне алгоритма линии"). Замедлите, пока оно не достигнет, снова перейдите в режим движения вперед , поверните колесо. Повторяйте до тех пор, пока дорога не станет чистой - по-видимому, на этот раз было достаточно 1 дополнительного маневра.

Это общая идея: во время игрового цикла или при проверке игровой системы задач:

• Проверьте положение автомобиля, скорость, угол наклона и т. Д. Относительно текущих границ и цели ,
• Если вы еще не достигли , продолжайте то, что вы делали (пусть физика передвинет это; у машины есть обороты и передача). Вставьте новую проверку в свою систему que, например, через 0,1 с.
• Если достигнуто , вычислите новые условия, установите данные и начните . Вставьте новую проверку в систему que, например, через 0,1 с.
• Завершите цикл цикла - продолжайте, повторите.

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

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

Я закончил тем, что сделал то, что предложил DMGregory, и это работает хорошо. Вот некоторый соответствующий код (хотя и не автономный), который можно использовать для вычисления двух стилей касательных. Я уверен, что этот код неэффективен, и, возможно, он даже не корректен во всех ситуациях, но пока он работает для меня:

bool Circle::outer_tangent_to(const Circle & c2, LineSegment & shared_tangent) const {
    if (this->direction != c2.direction) {
        return false;
    }
    if (this->radius != c2.radius) {
        // how to add it: http://mathworld.wolfram.com/Circle-CircleTangents.html
        // just subtract smaller circle radius from larger circle radius and find path to center
        //  then add back in the rest of the larger circle radius
        throw ApbException("circles with different length radius not supported");
    }

    auto vector_to_c2 = c2.center - this->center;
    glm::vec2 normal_to_c2;
    if (this->direction == Circle::CW) {
        normal_to_c2 = glm::normalize(glm::vec2(-vector_to_c2.y, vector_to_c2.x));
    } else {
        normal_to_c2 = glm::normalize(glm::vec2(vector_to_c2.y, -vector_to_c2.x));
    }

    shared_tangent = LineSegment(this->center + (normal_to_c2 * this->radius),
                                 c2.center + (normal_to_c2 * this->radius));
    return true;
}


bool Circle::inner_tangent_to(const Circle & c2, LineSegment & tangent) const {

    if (this->radius != c2.radius) {
        // http://mathworld.wolfram.com/Circle-CircleTangents.html
        // adding this is non-trivial
        throw ApbException("inner_tangents doesn't support circles with different radiuses");
    }

    if (this->direction == c2.direction) {
        // inner tangents require opposing direction circles
        return false;
    }

    auto vector_to_c2 = c2.center - this->center;
    auto distance_between_circles = glm::length(vector_to_c2);

    if ( distance_between_circles < 2 * this->radius) {
//      throw ApbException("Circles are too close and don't have inner tangents");
        return false;
    } else {
        auto normalized_to_c2 = glm::normalize(vector_to_c2);
        auto distance_to_midpoint = glm::length(vector_to_c2) / 2;
        auto midpoint = this->center + (vector_to_c2 / 2.0f);

        // if hypotenuse is oo then cos_angle = 0 and angle = 90˚
        // if hypotenuse is radius then cos_angle = r/r = 1 and angle = 0
        auto cos_angle = radius / distance_to_midpoint;
        auto angle = acosf(cos_angle);

        // now find the angle between the circles
        auto midpoint_angle = glm::orientedAngle(glm::vec2(1, 0), normalized_to_c2);

        glm::vec2 p1;
        if (this->direction == Circle::CW) {
            p1 = this->center + (glm::vec2{cos(midpoint_angle + angle), sin(midpoint_angle + angle)} * this->radius);
        } else {
            p1 = this->center + (glm::vec2{cos(midpoint_angle - angle), sin(midpoint_angle - angle)} * this->radius);
        }

        auto tangent_to_midpoint = midpoint - p1;
        auto p2 = p1 + (2.0f * tangent_to_midpoint);
        tangent = {p1, p2};

        return true;
    }
};

Вот два фильма с кодом выше в действии:

Вот «внешний» путь: http://youtube.com/watch?v=99e5Wm8OKb0, а вот «перекрестный» путь: http://youtube.com/watch?v=iEMt8mBheZU

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