@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.
Если есть идеи, как реализовать подобный алгоритм по-другому я буду рад узнать.
  • Вопрос задан
  • 4909 просмотров
Решения вопроса 1
wataru
@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 вдоль луча и дальше получите то же самое квадратное уравнение.
Ответ написан
Пригласить эксперта
Ответы на вопрос 5
@Vlad_hex
1) Бортовой компьютер ракеты рассчитывает вектор упреждения, она почти никогда не идет на цель точно, а в некую точку встречи.
2) У ракеты есть энергия или дельта V, ракетный двигатель разгоняет ракету и дальше отключается. Ракета расходует запасенную энергию на какие то маневры и корректировки курса, на этом факте основаны большинство противоракетных маневров.
3) Ракета поражает не точно цель, а некую область возле нее облаком осколков при срабатывании взрывателя.
Все выше написанное относится к ракетам из серьезных авиасимуляторов таких как DCS.
Если вы делаете аркадный симулятор, то ваши ракеты скорее всего будут вести себя как акустические торпеды. То есть двигатель постоянно работает, постоянно идет корректировка курса.
Пример из игр ColdWater, если неуправляемые Silent Hunter.
каким образом оптимально находить вектор скорости MSL_VEL

Я бы взял алгоритм для неуправляемой торпеды из Silent Hunter.
0) Известна скорость торпеды и пеленг цели
1) Вычисляется расстояние до цели
2) Вычисляется угол под которым мы видим цель
3) Вычисляется скорость цели (в игре это делается по секундомеру, у вас можно допустить игровую условность в виде радара доплера)
4) На основе полученных данных автоматически вычисляется точка рандеву и угол под которым должна быть запущена ракета/торпеда
5) Выполняется пуск и смотрим результат на сколько точно мы (или бортовой компьютер) выполнил расчеты.
Ответ написан
politon
@politon
HTML5,CSS3,JS,PHP,SQL,API,canvas,animation...
метод градиентного спуска попробуй
Ответ написан
Комментировать
Griboks
@Griboks
Если вы рассматриваете ракету как материальную точку, то вектор скорости задаётся как |TGT_POS-MSL_POS|*MSL_VEL.

Но для реальных ракет это будет смотреться не очень красиво из-за отсутствия поворота.
Ответ написан
Комментировать
Vindicar
@Vindicar
RTFM!
Уточню, 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, то нужно выяснить почему.
Ответ написан
@APh
В журнале Квант за 1973 год (номер не помню), который недавно читал, была статья со всеми формулами. Там на лису наводились. Ищите в подшивке статьи про лису.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы