Здравствуйте. Пишу 2Д игру. Стала задача: двигаются в пространстве два объекта с разной скоростью. Нужно найти точку пересечения их траекторий. Просто геометрией здесь не обойдусь, так как объекты двигаются в пространстве, поэтому нужно учитывать их скорость. Это уже не посильная задача. Есть ли какие нибудь алгоритмы для решения такой задачи? Если нет - подскажите с чего начинать.

Присоединённый файл ( Кол-во скачиваний: 15 )
 trajectory.jpg 20,05 Kb

Именно геометрией и можно обойтись. Находишь точку пересечения траекторий (найти точку пересечения 2-х прямых). Затем считаешь момент времени когда там будет первый и второй объекты, если в одно время ±дельта - столкнулись, иначе разошлись.

А так гугли "алгоритмы обнаружение столкновений".

Спасибо за ответ. На самом деле все просто. Но столкнулся с другой проблемой. Если объект В (на картинке) пока не знает с какой траекторией двигаться. Он знает лишь свою скорость. Ему нужно указать угол под которым двигаться чтобы столкнуться с объектом А.
Наглядно: объект А - самолет, который летит прямолинейно с равномерной скоростью. Объект В - снаряд, который должен попасть (перехватить) самолет на лету. Нужно найти угол, под которым снаряд должен сбить самолет


Это сообщение отредактировал(а) anmig - 17.5.2016, 13:13

Присоединённый файл ( Кол-во скачиваний: 9 )
 trajectory.jpg 23,50 Kb

То есть составить одно уравнение и решить его - проблема?

Координаты точек А и В известны. Скорости известны. Расстояния АС и ВС в зависимости от угла считаются элементарно. Осталось найти угол, при котором соотношение этих расстояний равно соотношению скоростей.

Akina, спасибо, но я не очень силен в математике. Да я могу найти расстояния AB, BC в зависимости от угла, но не умею создать уравнение.
Есть:
Точка A
координаты  (ax; ay)
скорость (va)
угол (alpha)

Точка B
координаты  (bx; by)
скорость (vb)
угол - ? (x)

Какая зависимость должна быть между всеми этими данными? И могут ли они пересечься вообще?

Присоединённый файл ( Кол-во скачиваний: 14 )
 trajectory.jpg 27,65 Kb

Картинка мешает решить.
Нужно нарисовать треугольник ABC и отпустить из точки С перпендикуляр на AB. Получится точка X. Длины AX и BX будут пропорциональны скоростям соответствующих снарядов. Вычисляются статически. Длина самого перпендикуляра - тангенс угла CAX умножить на AX. Итого - осталось вычислить угол треугольника XBC, зная оба катета.  Котангенс.
Осталось перевести решение в твою систему координат ... 

Чёблин? Если длины гипотенуз соотносятся как va/vb, и длина одного из катетов равна, то отсель никоим образом не следует, что длины вторых катетов имеют то же соотношение.

Действительно, блин... Если рассмотреть "клинический" случай, когда ABC имеет практически прямой угол В, то это становится очевидно и мне ... 

Ну, тогда получается просто  система уравнений.
Сумма катетов(AX и XB) пары треугольников равна |AB| , катеты выражены через коcинусы углов на гипотенузы, и катеты СХ обоих треугольников  равны, катет выражен через синусы углов на длины гипотенуз. Длины гипотенуз - скорости на подлетное время. Получаются 2 переменные - время и угол выстрела.

ksnk, я правильно понял?

cos(alpha)/x + cos(betha)/y = AB
sin(alpha)/x = sin(betha)/y

Это сообщение отредактировал(а) anmig - 18.5.2016, 07:24

Присоединённый файл ( Кол-во скачиваний: 11 )
 Рисунок1.jpg 43,14 Kb

косинус -это отношение прилежащего катета к длине гипотенузы. То есть длина этого самого катета получится умножением косинуса на длину гипотенузы. 
так что
гипотенузы - a*t и b*t - a и b - скорости цели и снаряда, t  -неизвестное "подлетное" время.
система

cos(alpha)*a*t + cos(betha)*b*t = AB
sin(alpha)*a*t = sin(betha)*b*t

Блин   Получается первое уравнение не нужно, как и 'подлетное время', как и расстояние между целями. Забавно...
betha=arcsin(sin(alpha)*a/b)

О господи... 

Совокупность точек, отстоящих от двух заданных точек на расстояниях, соотношение которых задано (va/vb) представляет собой тупо эллипс. По имеющимся данным построить его характеристическое уравнение - секундное дело. Найти точки пересечения эллипса и прямой, если их уравнения известны - тоже задачка на две минуты. 

Можно поподробнее про отношение расстояний?

Как-то привыкли все к сумме расстояний до фокусов

Я это знаю, ступил. Должно было быть так:
cos(alpha)*x + cos(betha)*y = AB
sin(alpha)*x = sin(betha)*y
Но суть не в том. ksnk, не хочу ставить под сомнение ваше решение, но мне кажеться - там все сложнее. Так как по вашему решению - я всегда найду угол. Но ведь задача может не иметь решения. Пуля может никогда не догнать самолет.
На одном форуме в инете я нашел рассчет перехвата, но там люди обошлись лишь фразами типа "создай уравнение и реши" без конкретного алгоритма что за чем делать. С тригонометрией у меня до сих пор не возникало проблем, а вот высшую математику забыл, учил 10 лет назад и никогда не сталкивался. Суть решения задачи там така: Непонятно каким образом, непонятно с какими данными создается квадратное уравнение. Через дискриминант как-то решается. И наименьшее значение - это минимальное время до столкновения. Если решения нет - объекты никогда не столкнутся. По времени я уже смогу найти угол.
Спасибо всем за внимание к этой теме. Но здесь так же - все лишь говорят - сделай то, или сё, все просто, это секундное дело и т.д. Если мои знания слишком малы для вашего форума, тогда буду искать дальше. Или же отнеситесь с пониманием и помогите шаг за шагом построить этот алгоритм.

Это сообщение отредактировал(а) anmig - 18.5.2016, 10:16

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

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

Если у тебя идиосинкразия на радикалы - то сразу пиши соотношение квадратов расстояний, оно тоже в описанных условиях константа.

Просто в таком описании эллипса точки А и В не являются фокусами эллипса - и всё.


Угу.. эллипс и прямая на плоскости вполне себе могут и не иметь общих точек...

Это сообщение отредактировал(а) Akina - 18.5.2016, 10:23

Хм Разве любое уравнение второго порядка соответствует эллипсу?

Контрпример для твоего утверждения: оба "фокуса" совпадают (вырожденный такой случай ) ) и a/b = 1 - дает всю плоскость. Т.е под это подходит любая точка. Кстати для a/b != 1 решений не существует в этом случае. Так что, как минимум, должны быть какие-то дополнительные условия. 

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

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


Мля...

A (xa, ya)
B (xb, yb)
C (x,y)

xa,xb,ya,yb,k=va/vb - константы, x,y - переменные.

|AC|^2 = (x-xa)^2 + (y-ya)^2
|BC|^2 = (x-xb)^2 + (y-yb)^2
|AC| = k * |BC|
(x-xa)^2 + (y-ya)^2 = k^2 * ((x-xb)^2 + (y-yb)^2)

Раскрытие скобок и перенос всего в левую часть уравнения проделаешь самостоятельно.

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

Это сообщение отредактировал(а) Akina - 18.5.2016, 12:15

Akina, А мое решение, с парой синус-косинус чем не устраивает? Вроде, на этот раз все правильно? 

Точность ниже, вычислительная ёмкость выше. Само решение не проверял... 
Но главным образом - не вижу смысла в вычислении УГЛА. Более разумно вычислять точку пересечения, а потом по двум точкам строить прямую полёта снаряда.

Не всегда. Функция arcsin определена на значениях от -1 до +1. Тоесть для бОльших 1 значений функции от угла-скоростей пуля не догонит самолет.

Добавлено через 10 минут и 8 секунд


Это звучало в условии   

 Akina,  cпасибо!

Да Тогда сразу все ОК. 

Даже думать не надо - типичный случай. Не только задача уже поставлена, но даже выбран путь решения... а то, что путь выбран неправильный (точнее, не самый рациональный) - да какие, право, мелочи.
Сам подумай - зачем ему угол? да чтобы строить прямую полёта! А о том, что прямую на экране быстрее и проще строить, имея две точки (во всех граф. библиотеках есть такая процедура, а вот насчёт точки и угла вряд ли), он даже не подумал.

Ну, оператору установки ПВО нужен именно угол, чтобы стрелять с упреждением. Если моделируется логика "стрелка", то вполне разумно получать именно его. Просто стрельнуть и продолжить тикать real-time таймером игры...
Хотя как оно на самом деле - знает только автор.  

Между прочим, логика стрелка-то как раз заключается в прогнозировании той точки, в которой снаряд встретится с объектом. А углами он занимается только в том случае, когда он траекторию объекта знает, но не видит.

Логика стрелка заканчивается выстрелом - генерацией нового объекта в пространстве игры,"снаряда". Снаряд имеет угол и скорость полета и начальное положение... Ну или "точку попадания", но так моделировать немного сложнее...

Добавлено через 3 минуты и 17 секунд
Хотя это уже вряд ли по теме   

Разве две точки в пространстве не дают угол отрезка? И наоборот, имея угол, нельзя получить две точки?
Мне без разницы что мы ищем - угол, координаты точки, или время столкновения. Имея любой из этих параметров я смогу построить траекторию. О чем спор?
Объект класса Пули не знает про точку столкновения потому что ее может и не существовать (но об этом позднее). У объекта есть константа "speed" и переменные "speedX" и "speedY". Последние две вычисляются по углу и гипотенузе "speed". Имея эти две переменные, пуля в каждом кадре смещает свою позицию на speedX и speedY. Ей не нужно знать точку "куда двигаться".

Буду дома - обязательно попробую.

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

Но ведь тригонометрия нужна лишь один раз перед выстрелом. Когда нужно найти смещение пули за еденицу времени по оси х и по оси у. Потом в каждом кадре (цикле) программы вызывается лишь две строчки кода в классе Bullet:

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

Можно пример?

Это сообщение отредактировал(а) anmig - 18.5.2016, 15:31

Угу... и из-за ошибки округления снаряд попадает в цель, находясь на десяток пикселов левее - красотишша...
Не, дело твоё... 

Если будет лететь полдня на расстояние 10^10 пикселов и цель размером с один пиксел, то возможно вы правы. Но я за все время еще не сталкивался с такими грубыми вычислениями. Плюс я никакие округления не делаю. Все данные хранятся в переменных и точность их зависит лишь от точности методов класса Math. Может сам класс Math что-то округляет в своих методах?
Извините, но действительно хотелось бы пример вычисления без тригонометрии. Т.к. у меня есть класс ракеты, которая преследует самолет (самонаводящийся снаряд). Вот ту-то в каждом кадре производится пересчет траектории в зависимости от положения самолета. И хотелось бы уменьшить количество рассчетов.

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


Надеюсь, мои выкладки выше убедили, что для расчёта точки "встречи" достаточно решить одно квадратное уравнение, для чего придётся один раз извлечь квадратный корень, а все остальные вычисления - чисто арифметика? ну так это оно и есть... координаты точки С получены. А дальше, зная расстояние BC (и соответствующие дельты по осям) и пройденный снарядом путь, считаем местоположение снаряда тупо пропорцией - опять сплошная арифметика.

А самолеты не маневрируют?

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

Проверил, работает. Спасибо, ksnk, то что нужно. Кстати, заметил, что если скорость пули меньше скорости самолета, она никогда не догонит самолет. Потому, что a/b всегда будет давать меньше еденицы. А умножив на sin(alpha) то значение будет больше 1, что неприемлемо для arcsin. И на практике так же - обе траектории будут стремиться к паралельности.
Теперь второй вопрос. Как построить логику выстрела, что делать если решения нет. Ведь самолеты в некоторое время могут маневрировать, в некоторых случаях летят равномерно прямолинейно. Если пуля знает что никогда не столкнется с самолетом, но она должна все равно выстрелить. Как ей лететь приблизительно в район самолета (+- некоторое отклонение)?
Как в эту формулу внести погрешность? Ведь самолет и пуля - это не точки, а объекты с размерами. Учитывая, что у них есть размеры - гараздо больше шансов что они столкнутся.

Это сообщение отредактировал(а) anmig - 19.5.2016, 10:53

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

Вообще-то прицеливание в "точку попадания", если цель обязательно будет маневрировать - не самая удачная стратегия. Если самолет начнет уклонение в момент выстрела - это будет заметно.
Изменения вектора скоростей у самолета и пули моментальны или инерция какая-то есть? 

Удачная стратегия - это прицеливание в "точку попадания" и выстрел именно в момент, когда поражение произойдёт на минимальном расстоянии от орудия. Собственно описанный мной алгоритм и есть попытка приблизиться к такой стратегии в расчёте на максимально эффективные действия цели по уклонению и при условии единственности выстрела. Просто надо его дорихтовать до рабочего состояния.

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

Самолетом управляет игрок, пушкой - компьютер. Сначала я делал выстрел прямо в точку положения самолета на момент выстрела. Смотрелось очень дико: самолет уже был на большом расстоянии когда пуля достигала этой точки. Эти пушки настолько тупыми выглядели что играть вообще было бессмысленно. Если пушка всегда будет идеально попадать в цель - игра тоже будет неинтересна и непроходима.
Поэтому в идеале должно быть так:
Пушка вычисляет угол перехвата. Выстреливает. Пока пуля летит - игрок имеет шанс изменить курс самолета, если не успел -  попадание.
По формуле с арксинусом вычисляю угол перехвата. Если решение есть - стреляю (попаду, не попаду - зависит от умения игрока). Если решения нет, то высчитываю приблизительный район столкновения и стреляю туда (вдруг игрок сам наткнется на пулю). Но как высчитать этот "приблизительный" угол, если формулы дадут лишь точный угол (точку столкновения), или вообще ничего не дадут.
К сожалению алгоритм Akina не могу осилить, поэтому решение от ksnk для меня единственное рабочее

anmig, Я вообще не очень понимаю, зачем при таком моделировании с самонаводящимися снарядами, вообще решать сложные задачи с квадратными уравнениями или арксинусами.
У нас есть самолет со стартовым положением и скоростью. Нужно определить "точку попадания".
Будем приблизительно вычислять "подлетное время".
За первое приближение возьмем текущее положение самолета. Подлетное время снаряда - `расстояние до точки`/`скорость снаряда`. За это время самолет улетит в точку, которая вычисляется двумя операциями сложения и умножения. Время, за которое снаряд туда долетит - второе значение "подлетного времени". 
Вычисляем разницу между временами. Если разница велика - повторить.
По подлетному времени вычисляем точку и туда стреляем.   Больше 2х итераций, скорее всего, не нужно.

Зачем точное решение, если снаряд подруливает?...

Добавлено @ 15:30
Кстати, это решение всегда дает направление выстрела, так что если по формуле не получается - можно стрелять так - вдруг юзер испугается...

P.S  Да, вычисление расстояния - это еще и корень квадратный, так что простой арифметикой не обойтись...

Это сообщение отредактировал(а) ksnk - 19.5.2016, 15:37

Внесу точность:
Самонаводящиеся снаряды - это ракеты. О них речь не шла. Они в каждом кадре смотрят где самолет и преследуют его. У них есть своя скорость и свой радиус разворота (скорость реагирования на маневры самолета).  
А говорим мы о пуле, которая летит равномерно и прямолинейно. Пушка должна выстрелить в самолет, а тот должен уворачиваться от нее. Если столкновение возможно - стрелять в точку, высчитанную по формуле. Если столкновение невозможно - все равно выстрелить приблизительно в место где игрок мог бы наткнутся на пулю (вдруг он ее не заметит и сманеврирует как раз в ее сторону). Если не наткнется, то пуля летит, пока не вылетит за екран.

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

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

Ну, высчитал, допустим, два времени. А что повторить? Как дальше?

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

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

Решили, если расстояние между соседними точками N-1 и N станет меньше радиуса поражения снаряда.
Не решили, если за M итераций не получили решения.



Это сообщение отредактировал(а) ksnk - 20.5.2016, 14:08

Выкопал свой староглиняный проект, уж не помню какого года. Немножко сдул пыль и исправил накопившиеся ошибки.
Делалось все это как проверка возможностей анимации на Javascript, с планетами и снегом. Заодно и что-то там про ооп на javascript. Тогда мне это показалось слишком тяжелым для IE6, хотя на FF2.0 бегало достаточно шустро   
Добавил в список сценариев еще один вариант - "расстрел вертолета", с расчетом точки попадания посредством арксинусов. Вроде попадает, точности хватает.

И у меня работает без проблем. Кстати, на практике почти всегда решение есть, т.к. пуля всегда быстрее самолета, так что решил не заморачиваться и поставил условие, если значение передаваемое в asin вне предела -1:1 то просто не стреляю. Правда пока не поймал такого случая.
ksnk, спасибо еще раз, и спасибо всем, кто помогал

Akina, Кстати - про эллипс - слишком осторожно, похоже что геометрическое место точек попадания - окружность. Аналитически это можно увидеть из формулы на второй странице. Если уточнить коэффициенты у x^2 и y^2 - они окажутся равны.  

А если объекты недвижимые.. где точку найти?

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