Я делаю некоторый элементарный ИИ для своего бокового скроллера, и мне нужно знать, может ли ИИ-подразделение достичь точки В из точки А, просто сделав прыжок.
Траектория полета моих персонажей немного необычна, так как они могут применять силу в воздухе (как, например, в Jazz Jackrabbit 2), так что в отличие от классической траектории снаряда, которая примерно ...
путь, по которому брошенный или запущенный снаряд пойдет (...) без движения.
... Я полагаю, что моя проблема больше касается снаряда с движителем (например, ракеты).
Чтобы проиллюстрировать это, вот как выглядит кривая полета моего персонажа, если я прыгаю и постоянно нажимаю «левую кнопку» (на левом конце она выглядит по-другому, именно здесь я выполнял маневры в воздухе):
Сила, применяемая во время полета, всегда параллельна оси X, поэтому F = (-f, 0), если я держу «влево», и F = (f, 0), если я держу «вправо».
Он может двигаться очень как прыгун с трамплина:
Так что он сильно отличается от классической траектории, которая представляет собой просто параболу (источник: wikipedia ):
Чтобы сделать это более сложным, я моделирую простое сопротивление воздуха, чтобы мои персонажи могли ускоряться только до некоторого максимального значения скорости.
Это делается путем приложения небольшой силы в противоположном направлении движения :
b2Vec2 vel = body->GetLinearVelocity();
float speed = vel.Normalize(); //normalizes vector and returns length
body->ApplyForce( AIR_RESISTANCE_MULT * speed * speed * -vel, body->GetWorldCenter() );
AIR_RESISTANCE_MULT - это константа, которая в моем случае равна 0,1.
Давайте предположим, что мой персонаж - бесконечно малая точка.
И я НЕ принимаю во внимание препятствия, поэтому мой вопрос звучит так ...
Как определить (по крайней мере, надежно угадать), учитывая начальную скорость V, импульс J = (0, -j), который я применяю к персонажу при прыжке, гравитацию G = (0, g) , силу F = (+ -f , 0) постоянно применяется во время полета и AIR_RESISTANCE_MULT, если мы действительно решили принять во внимание сопротивление воздуха (это необязательно) , лежит ли точка ниже кривой, проведенной путем, по которому будет идти мой персонаж?
Я буквально не знаю, с чего начать с расчетов, и на самом деле, я не обязательно заинтересован в точном ответе; хорошо работающий хак / аппроксимация был бы хорош, поскольку ИИ ни в коем случае не должен действовать идеально.
редактировать: я решил решить эту проблему с помощью моделирования, как предлагает Джейсон, но как справиться с таким случаем?
Должен ли я нарисовать отрезок от C до D и проверить, находится ли желаемая точка ниже этого отрезка?
Или мне следует выполнить двоичный поиск по временным шагам между C и D, чтобы найти точку, которая достаточно близка на горизонтальном расстоянии к желаемой точке, и только затем проверить вертикальную разницу? (кажется немного излишним для меня)
источник
Ответы:
Как вы утверждаете, лучший выбор - приблизить, в этом случае использовать числовую схему. Разделите время на большие временные шаги (скажем, 100-300 мс) и используйте параболическое приближение для каждого временного шага. Силы везде одинаковы, кроме сопротивления воздуха. Параболический путь в основном для постоянного ускорения, но с сопротивлением воздуха ускорение изменяется, потому что сила зависит от скорости. Разумное приближение - рассматривать сопротивление воздуха постоянным на каждом временном шаге. Но использование квадратичной (то есть параболической) аппроксимации при интегрировании позволяет обрабатывать гораздо большие временные шаги. Затем вы просто вычисляете, пока парабола не пересечет нужную точку в горизонтальном направлении, а затем сравните высоты.
РЕДАКТИРОВАТЬ: немного подробнее о сравнении. Вы знаете, что за промежуток времени (который может быть много в игровых кадрах), что игрок пересекает цель
<targetx,targety>
. Их путь описывается положением,<ax*t^2 + bx*t + cx, ay*t^2 + by*t + cy>
где:t
время через временной шаг (0 <= t <= dt
) и аналогично дляy
. Поэтому, когдаt=0
персонаж находится на предыдущей позиции, а когдаt=dt
- на следующей. Обратите внимание, что это в основном обновление Эйлера сdt
заменой на,t
так что мы можем рассчитывать в любом месте вдоль траектории. Теперь мы знаем, что x-позиция является квадратичной функцией, поэтому мы можем решитьax*t^2 + bx*t + cx = targetx
и получить (до) два раза за шаг, на котором персонаж находится прямо над или под целью. Затем мы выбрасываем любые решения, которые не находятся в диапазоне [0,dt
], поскольку их нет в текущем временном шаге. (Для надежности добавьте небольшую константу к концам диапазона, чтобы у вас не было проблем с округлением). Теперь у нас не могло быть решений (после фильтрации), и в этом случае мы не достигли цели на этом временном шаге. В противном случае мы оцениваемay*t^2 + by*t + cy
решения и сравниваем это сtargety
. Обратите внимание, что вы можете быть выше цели в одной точке вашей траектории и ниже ее позже (или наоборот). Вам нужно будет интерпретировать такие ситуации в соответствии с тем, что вы хотите сделать.Рассмотреть кучу временных шагов гораздо проще, чем найти аналитическое решение исходной проблемы, и гораздо более гибко, поскольку вы можете изменить модель движения, и это все равно будет работать приблизительно.
Бонусные баллы за использование переменных шагов, например, 100 мс за первую секунду (десять баллов), 200 мс за следующие два (еще десять баллов), 400 мс за 4 секунды и т. Д. Фактически, когда ваш персонаж приближается к предельной скорости, изменение в сопротивление падает, и вам все равно не нужны большие временные шаги. Таким образом, вы можете обрабатывать действительно длинные прыжки без слишком большой обработки, поскольку сложность для T секунд составляет O (log T), а не O (T).
Вы также можете смоделировать то, что происходит, когда персонаж перестает ускоряться на полпути через свой прыжок или начинает усиливать другой путь. С вышеупомянутым трюком сложность O ((log T) ^ 2), что не так уж и плохо.
источник
x'= x + v*dt
. Вместо этого используйтеx' = x + v*dt + 1/2*a*dt*dt
. Когдаdt
оно маленькое,dt^2
оно крошечное, поэтому обычно оно не учитывается в традиционной интеграции Эйлера в играх. Здесьdt
не маленький, поэтому вам нужен срок ускорения. Посколькуdt
возводится во вторую степень, это квадратичное интегрирование, а путь - это парабола, следовательно, параболическое приближение. RK4, по существу, рассчитывает высшие производные и, следовательно, может дать кубическое, квартичное, квинтическое и т. Д. Приближения. RK4 для этого, скорее всего, перебор, так как стабильность не важна.v' = v + a*dt
Ура! Я это сделал!
Я использую простое моделирование, которое занимает первую позицию, чтобы приземлиться за вертикальной осью целевой точки - оттуда я беру предыдущую имитированную позицию и делаю сегмент. Теперь я проверяю, находится ли целевая точка ниже этого сегмента. Если это так - мы можем прыгнуть туда.
Это персонаж, управляемый игроком на гифке. Розовый - это прогнозируемый путь, желтые сегменты - это прогнозируемые последующие позиции шага, а последний сегмент становится белым, если целевая точка лежит ниже него, в противном случае - красным. Красная кривая - фактическая траектория полета. Есть некоторые небольшие неточности из-за включенной интерполяции состояния физики.
Расчеты оказались на удивление легкими, однако заставить мою среду работать так же, как эти чистые вычисления ... было огромной болью в заднице. По крайней мере, я решил некоторые серьезные ошибки, так что это было полезное упражнение.
Вот полный код на Lua, использованный для решения исходной проблемы (код предполагает, что у вас есть собственная подпрограмма "debug_draw" и собственный векторный класс с базовыми методами, такими как "length_sq" (длина в квадрате), "normalize" или операторы +, * :
Accept идет к Джейсону за то, что он направил меня в правильном направлении! Спасибо!
источник
Возможно, вы захотите «просто рассчитать» ответ, но я уверен, что он окажется недостаточным, как только вы его получите, из-за высокой интерактивности вашей физики «свободного падения».
Попробуйте использовать другой подход: поиск. Вот как это делается для AI Super Mario: http://aigamedev.com/open/interview/mario-ai/
Поиск возможных путей для перехода от A к B обеспечивает неограниченную интерактивность в воздухе, в то же время обеспечивая высокую вычислительную эффективность.
источник