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

Question

[atapi086]

Вводная:
Нужно реализовать алгоритм самонаведения для ракеты в трёхмерном игровом пространстве.
Дано в каждый момент времени:

• скорости цели TGT_VEL
  
• местоположение цели TGT_POS
  
• местоположение ракеты MSL_POS
  

Идея алгоритма: берётся вектор направления на цель (TGT_DIR = TGT_POS - MSL_POS), нормализуется, а затем перебором ищется скорость ракеты MSL_VEL такая, чтобы выполнялось TGT_DIR == (MSL_VEL - TGT_VEL).normalized().
Иными словами, вектор скорости сближения всегда указывает на цель (вроде бы такой алгоритм называется алгоритмом пропорционального сближения)

Вопрос: каким образом оптимально находить вектор скорости MSL_VEL? Я очень сильно ограничен в количестве операций на каждый игровой тик, так что идеальное решение было бы за O(1) или с максимальным количеством итераций во всех циклах около 50.
Если есть идеи, как реализовать подобный алгоритм по-другому я буду рад узнать.

Comments

[Rsa97]

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

Answer 1

[Wataru]

Тут квадратное уравнение зарыто.

Обозначьте |MSL_VEL - TGT_VEL| за t.

Получите уравнение TGT_DIR = (MSL_VEL-TGT_VEL)/t

Преобразуйте: TGT_DIR*t = (MSL_VEL-TGT_VEL)

Но тут неизвестные вектор MSL_VEL и t. Но они связаны, ведь t - это длина вектора. Обозначим неизвестный вектор MSL_VEL как (x, y, z) Значит:

t^2=(x - TGT_VEL_x)^2 + (y - TGT_VEL_y)^2 + (z - TGT_VEL_z)^2

Ну и еще вы знаете, что скорость ракеты фиксированная же:
x^2+y^2+z^2 = MSL_SPEED^2

У вас тут 4 неизвестных и аж 5 уравнений (ведь первое - это векторное уравнение):

TGT_DIR_x*t = x - TGT_VEL_x
TGT_DIR_y*t = y - TGT_VEL_y
TGT_DIR_z*t = z - TGT_VEL_z
t^2=(x - TGT_VEL_x)^2 + (y - TGT_VEL_y)^2 + (z - TGT_VEL_z)^2
x^2+y^2+z^2 = MSL_SPEED^2

Раскройте скобки в 4-ом, подставьте туда пятое и из первых трех выразите x, y, z:

t^2 = MSL_SPEED^2+TGT_SPEED^2-2*TGT_VEL_x*(TGT_DIR_x -t*TGT_VEL_x)-... = MSL_SPEED^2+(1-2t)TGT_SPEED^2-2(TGT_DIR*TGT_VEL)

Там в конце векторное произведение векторов. Дальше сами раскройте и получите квадратное уравнение на t. Решите его по школьной формуле. Если дискриминант отрицательный, то решения тупо нет. Слишком быстро цель улепетывает. Потом не забудьте проверить, чтобы t получилось положительное. Потом подставьте t в первые 3 уравнения и найдите искомые x, y, z.

Еще можно так себе это все представить. Свяжем систему координат с целью. Тогда множество точек, куда может смотреть скорость ракеты - это сфера с центром в TGT_VEL и радиусом MSL_SPEED. Вам надо выбрать на этой сфере точку так, чтобы она была коллинеарна с вектором TGT_DIR. Т.е. у вас есть луч из центра координат вдоль векторо TGT_DIR. Вам надо найти где он пересечет сферу. Введите параметр t вдоль луча и дальше получите то же самое квадратное уравнение.

Comments

[atapi086]

Спасибо за развёрнутый ответ.

Написал вот такой код

def smart_homing_displacement_1() -> vec.vec:
    tgt_vel_vec = _get_tgt_vel_vec()
    dir_v = _get_curr_tgt_coords() - _get_curr_missile_coords(missile)

    A = dir_v.x
    B = dir_v.y
    C = dir_v.z

    alpha = tgt_vel_vec.x
    beta = tgt_vel_vec.y
    gamma = tgt_vel_vec.z

    a = (A**2 + B**2 + C**2)
    b = (A * alpha + B * beta + C * gamma)
    c = (alpha**2 + beta**2 + gamma**2 - missile_energy_speed**2)

    discr = b**2 - 4 * a * c

    if discr < 0:
        return vec.vec(0, 0, 0)

    half_power_discr = discr ** 0.5
    a_2 = a * 2

    t1 = (-b + half_power_discr) / a_2
    t2 = (-b - half_power_discr) / a_2

    t = max(t1, t2)

    if t < 0:
        print(f'WTF ?????? r<0')
        return vec.vec(0, 0, 0)

    x = dir_v.x * t
    y = dir_v.y * t
    z = dir_v.z * t

    msl_vel_dst = vec.vec(x, y, z)
    msl_vel_src = -tgt_vel_vec

    return (msl_vel_dst - msl_vel_src).normalized() * missile_energy_speed

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


Вопрос: в чём тут может быть проблема?

P.S. геометрическое решение выглядит так:

[Wataru]

atapi086, В формулах где-то ошиблись. У переменной b вы потеряли множитель 2, ведь вы там квадраты раскрываете. И, кажется, знак "-" еще там должен быть в b, у вас же там квадрат разности. Так что попробуйте сначала домножить на 2, если не поможет, то еще и на -1.

Answer 2

[Vlad_hex]

1) Бортовой компьютер ракеты рассчитывает вектор упреждения, она почти никогда не идет на цель точно, а в некую точку встречи.
2) У ракеты есть энергия или дельта V, ракетный двигатель разгоняет ракету и дальше отключается. Ракета расходует запасенную энергию на какие то маневры и корректировки курса, на этом факте основаны большинство противоракетных маневров.
3) Ракета поражает не точно цель, а некую область возле нее облаком осколков при срабатывании взрывателя.
Все выше написанное относится к ракетам из серьезных авиасимуляторов таких как DCS.
Если вы делаете аркадный симулятор, то ваши ракеты скорее всего будут вести себя как акустические торпеды. То есть двигатель постоянно работает, постоянно идет корректировка курса.
Пример из игр ColdWater, если неуправляемые Silent Hunter.

каким образом оптимально находить вектор скорости MSL_VEL

Я бы взял алгоритм для неуправляемой торпеды из Silent Hunter.
0) Известна скорость торпеды и пеленг цели
1) Вычисляется расстояние до цели
2) Вычисляется угол под которым мы видим цель
3) Вычисляется скорость цели (в игре это делается по секундомеру, у вас можно допустить игровую условность в виде радара доплера)
4) На основе полученных данных автоматически вычисляется точка рандеву и угол под которым должна быть запущена ракета/торпеда
5) Выполняется пуск и смотрим результат на сколько точно мы (или бортовой компьютер) выполнил расчеты.

Comments

[atapi086]

Спасибо за предложение.
Такой алгоритм уместен и работоспособен, но неэффективен с точки зрения расхода энергетики ракеты.
В моём случае игра претендует на некоторую серьёзность (но, конечно, не является симулятором).
1) Двигатель ракеты работает ограниченное (и очень небольшое) время, ракета сначала ускоряется, затем замедляется и обладает баллистикой
2) Манёвренность ракеты прямо зависит от скорости
3) У ракеты есть предел перегрузок
4) У ГСН ракеты ограниченное поле зрения и в случае срыва захвата она теряет цель навсегда (игровая условность)
5) Ракета имеет возможность подрываться по команде или при обнаружении цели в радиусе R
6) Вектор скорости цели/ракеты и вектор позиции цели/ракеты всегда известен и точен (игровая условность)
На эти факторы я не могу влиять.
Описанный в вопросе алгоритм хочется реализовать просто из интереса к предметной области, а не из острой необходимости.

По этим причинам предложенное решение не подходит

Answer 3

[Олег]

метод градиентного спуска попробуй

Answer 4

[Griboks]

Если вы рассматриваете ракету как материальную точку, то вектор скорости задаётся как |TGT_POS-MSL_POS|*MSL_VEL.

Но для реальных ракет это будет смотреться не очень красиво из-за отсутствия поворота.

Answer 5

[Vindicar]

Уточню, velocity - это обычно вектор скорости, а speed - скалярная величина, модуль этого вектора.
У тебя есть пара вариантов:
а)

MSL_VEL = (TGT_POS - MSL_POS).normalize() * MSL_SPD

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

MSL_VEL = (TGT_POS + TGT_VEL * GAME_TICK - MSL_POS).normalize() * MSL_SPD

для ракеты с упреждением на один игровой тик.

Если на нормализацию вектора не хватает CPU, то нужно выяснить почему.

Comments

[atapi086]

Спасибо за ответ.
Дело не в ограничении CPU, а в ограничении самой игры. Каждый игрок сервера может создавать свои программы и выполнять их (вся программа выполняется один раз за игровой такт на сервере, не на клиенте). Чтобы избежать лагов, у программ игроков есть очень серьёзные квоты на процессорное время.
Суть вопроса заключается в реализации алгоритма пропорционального сближения. При варианте A ракета всегда будет пролетать перед целью, при варианте Б ракета истратит свою энергетику задолго до попадания по цели из-за недостаточного упреждения

[Vindicar]

atapi086, Space Engineers?

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

[atapi086]

Vindicar, Garry's Mod с аддонами на вооружение (ACF). Я пробовал оба предложенных варианта, второй даже может работать (если делать упреждение обратно пропорциональным от расстояния цель-ракета).
Мне интересен на дилетантском уровне сам принцип наведения, приближенный к использующимся в реальной жизни.

[HiTechSpoon]

atapi086, в реальной жизни для предсказания положения цели применяют следящий фильтр Калмана.

Answer 6

[APh]

В журнале Квант за 1973 год (номер не помню), который недавно читал, была статья со всеми формулами. Там на лису наводились. Ищите в подшивке статьи про лису.