Алгоритм расчета пути пули к цели с макс. 2 рикошета

21

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

Так что есть удивительная игра от Nintendo (да!) На Wii под названием WiiPlay . В ней 9 мини-игр, а моя любимая называется Tanks! , Это уничтожение вражеских танков СОМ без уничтожения себя. Вот скриншот уровня:

введите описание изображения здесь

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

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

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

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

введите описание изображения здесь

HOR-VER означает, что пуля сначала попадает в горизонтальную стену, а затем в вертикальную стенку.

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

Кроме того, я не уверен в общем потоке алгоритма. Принимает ли алгоритм какую-либо из следующих двух структур, или, может быть, я ошибаюсь в обеих?

  • Продолжайте определять возможные пути и всегда отмечайте один из них как лучший (может быть самый короткий, самый непонятный, самый неизбежный или комбинированный и взвешенный анализ, основанный на множестве критериев) и забудьте об остальных. Лучше всего взять тот, который остался после всех расчетов.
  • Сначала определите все стены, в первую очередь достижимые пулей (пуля не должна рикошетить по отношению к любой другой стене, чтобы достичь каждой из этих стен), затем определите все достижимые диапазоны на каждой из этих стен (иногда невозможно достичь удаленной точки на стена без рикошета, если рядом с вами стоит другая стена), затем снова определите все достижимые стены рикошетом и все диапазоны, достижимые на этих стенах. Эти 4 процесса могут быть выполнены способом, подобным трассировке лучей. Во время каждого процесса, если танк игрока поражен каким-либо лучом, определите путь пули в соответствии с этим лучом.

На мой взгляд, этот алгоритм трудно понять, потому что:

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

Но люди Nintendo сделали это в любом случае, так что ... кто-нибудь с идеей?

всем привет
источник
Просто чтобы проверить, вы спрашиваете, как это можно сделать, а не то, как Nintendo решила это сделать, верно?
Иксрек,
@lxrec вы правы, просто интересуетесь возможным способом, а не тем, как они это сделали .
Привет всем
В игре не нужно искать решение. Когда вы нажимаете кнопку стрельбы, игра уже знает ваше положение и направление, в котором вы находитесь, тогда она использует только эту информацию. Он будет отслеживать траекторию, и если он обнаружит вражеский танк на пути, вы попадете по нему, иначе нет.
Мандрил
2
Хотя «бесконечно» много углов, вы можете легко уменьшить их до нескольких классов эквивалентности. Nicky Case Sight and Light - это классная демонстрация рендеринга теней между полигонами - это как раз ваша проблема, за исключением того, что вы используете пути пули, а не лучи света, и что ваши лучи могут отражаться два раза. Обратите внимание, что отражение не имеет значения для ИИ - отражение просто расширяет линию обзора, хотя это означает, что один и тот же объект может быть виден под разными углами.
am
@ Mandill Боюсь, ты не совсем понял мой вопрос. Я спрашивал, как вражеский танк может придумать путь пули, который попадет в танк игрока.
Привет всем

Ответы:

9

При прямой видимости проблема, очевидно, тривиальна. Однако мы имеем дело с отражением. Правильно определить, какие части сцены можно увидеть, сложно при реализации отражения как части трассировщика лучей, поскольку это может пропустить некоторые отверстия. «Бинарный поиск» между двумя многообещающими углами также не является жизнеспособным: из-за отражений фактически видимое пространство не является непрерывным, поэтому эвристическое «если это справа от A и слева от B, должна быть цель Решение между А и В » недопустимо , и в нем будут отсутствовать« креативные »решения. Вместо этого я бы порекомендовал реализовать рефлексию, перезапустив трассировщик из виртуальной позиции - позиции, в которой наш огневой резервуар, кажется, находится при зеркале:

target |obstacle
   X   |
    \  |  X real position
     \   /
      \ /
   ----------- mirror surface
        \
         \
          X virtual position

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

стрельба по углам

X отмечает огневую позицию, (X) цель. Цветные области видны.

  1. Прямая видимость: цель не видна. Тем не менее, мы можем поразить поверхности (1) и (2).

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

  3. Два отражения: верхняя виртуальная позиция от первого отражения может видеть часть нижнего препятствия через его зеркальную поверхность. Поскольку допускаются два отражения, мы можем отразить это положение в нижнем препятствии. Позиции помечены как (I) реальная позиция, (II) виртуальная позиция из первого отражения и (III) виртуальная позиция из второго отражения.

    Из (III) у нас есть прямой LOS к цели (X), поэтому мы нашли другое решение для стрельбы. Путь пули проходит по линии X – III до второй точки столкновения зеркала, затем по линии III – II между точками столкновения зеркала и, наконец, по линии II – I от первой точки столкновения зеркала до реального положения I.

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

Как только вы сможете выяснить, какие части препятствий видны (и, следовательно, их можно использовать для отражения маркера), внедрение зеркалирования с помощью поиска в глубину может показаться простым. Чтобы найти подходящие зеркальные поверхности, можно использовать методы, описанные в Sight & Light от Nicky Case : вместо того, чтобы опробовать 360 векторов - которые могут пропустить отверстия, а также расточительны - мы запускаем лучи только по краям препятствий.

Амон
источник
Я не понимаю, как работает "запуск лучей только до границ препятствий". Вы хотите начать запускать лучи к концу стен и постепенно внутрь, пока мы не найдем решение? Если так, я понимаю, что с этим правилом решение может быть найдено быстрее.
Привет всем
После некоторого рассмотрения, я думаю, что это лучший ответ, потому что, очевидно, с математическим ответом, который я пометил как лучший прежде, не может напрямую иметь дело с решениями с одним отскоком и без отказов.
Привет всем
Это великолепно! Какой-нибудь совет о том, как создать зеркальное представление вашего уровня, не слишком требовательный к вашей игре?
ретровиус
7

Просто расширяя идею Карла Билефельдта для отражения двух стен:введите описание изображения здесь

А и Б даны (танки). Сначала вы должны перечислить все стены, которые A может видеть, и список всех стен, которые B может видеть. Затем вы создаете пары, в которых первая стена находится в первом списке, а вторая отличается от первой стены и находится во втором списке. Вы должны сделать этот тест для всех возможных пар стен (если вы не найдете способ устранить кандидатов). Как только вы найдете R и S для данной пары стен, вы проверяете

1) если А имеет прямое видение R

2) если R принадлежит стене1 (стена - это просто сегмент, а не целая линия)

3) если R имеет прямой доступ к S

4) если S принадлежит wall2 (стена - это просто сегмент, а не целая линия)

5) если S имеет прямой доступ к B.

Чтобы найти R и S : Так как вы знаете wall1, вы можете определить уравнение линии, касательное к wall1, так как R принадлежит линии, касательной к стене 1, у вас есть отношение между двумя координатами R (заканчивая с одной степенью свободы для R) Аналогично S (у вас есть связь между S-координатами, так как эта точка принадлежит линии tanget к wall2). Итак, теперь у вас есть 2 степени свободы, и вы должны иметь 2 дополнительных независимых уравнения для определения решения. Одно уравнение:

(AA')/(RA')=(SS')/(RS')

другое уравнение:

(BB')/(SB')=(RR')/(SR')

Обратите внимание, что в приведенных выше уравнениях A, A ', B, B' известны или могут быть вычислены непосредственно. R 'и S' являются функцией координат R и S и уравнений стенки. Я не закончил математику, поэтому я не знаю, как будут выглядеть уравнения.

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

Вы можете воспользоваться тем, что угол, выходящий из рикошета, должен совпадать с углом, который входит в него. Для заданной горизонтальной стены с координатой y cи двух неподвижных резервуаров с координатами (a,b)и (d,e)существует только один угол, который удовлетворяет приведенному ниже уравнению.

схема уравнения

Просто решите, xчтобы получить расстояние вдоль стены, на которое вы должны прицелиться. Две стены работают одинаково. У вас просто два уравнения и два неизвестных.

Карл Билефельдт
источник
1

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

Давайте называть поверхность , которая должна быть поразить первую поверхность А , а второй, B .

Попробуйте попасть (видимый) края B стреляя в A . Другими словами, определить точки , где можно было бы увидеть отражения концов B , если смотреть на зеркальной отделкой A . Это должно быть легко сделать, у вас есть только одна точка отражения для обработки.

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

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

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

Вот картинка:

лучи

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

9000
источник
Нет, не обязательно! Подумайте о своей диаграмме, если где-то прямо между путями красной и синей пули лежало дополнительное препятствие. Если вы выстрелите из пули под углом между красным и синим углами, вы можете получить более сильный удар по танку игрока, но вы также можете пропустить полностью, потому что некоторые пули могут рикошетить от случайного препятствия, лежащего между ними. Пожалуйста, смотрите ответ @ амона, где он обсуждает эту возможность.
Привет всем
Upvoted ответ @ амона; Мне нравится идея прямого зеркалирования. Также я предполагаю, что алгоритм должен проверить, что путь попадания действительно проходим, после нахождения его таким упрощенным способом. Еще более интересна возможность, когда цель только частично закрыта (возможно, даже разделена на две видимые области). Метод Амона более поддается обработке.
9000
-3

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

JavaFreak
источник
1
Я понимаю принципы отражения. Вы можете увидеть мой ответ на комментарий @ amon. Вы правы, что нужно учитывать движение игрока, но я думаю, что его можно оставить одним из критериев выбора одного оптимального пути из множества возможных путей на основе оценки. Тем не менее, это может быть проигнорировано, потому что это зависит от расстояния пути пули, то есть , чем длиннее путь, тем больше игрок может двигаться, прежде чем пуля достигнет пункта назначения.
Привет всем,