В продолжение моего более раннего вопроса о поиске наклона 2D-растрового ландшафта теперь мне нужно знать, как лучше всего найти точку на 2D-ландшафте, в которую попала ракета. Очевидно, я могу видеть, пересекаются ли какие-либо пиксели под ракетой, но говорят, что она переместилась довольно глубоко в местность.
Каков наилучший способ сделать шаг назад, чтобы найти, где он изначально столкнулся? Я мог бы сдвинуть назад X пикселей к предыдущему положению ракеты, но что было бы хорошим значением X? И есть ли умнее? Может быть, переезд на половину расстояния, затем на четверть и т. Д.?
Ответы:
Для тестирования столкновений вы не должны делать тиковое статическое тестирование, вы должны выполнять тесты трассировки / развертки.
Здесь приведен исчерпывающий список различных формул для различных видов примитивов: http://www.realtimerendering.com/intersections.html
Это, конечно, при условии, что вы можете разбить свою местность на некоторый набор примитивов, с которыми вы можете тестировать (то есть отрезки линий). Есть разные способы сделать это.
См. Также этот вопрос (только слегка связанный): каков хороший алгоритм для обнаружения столкновения между движущимися сферами?
источник
Бинарный поиск не поможет, если у вас есть тонкие пейзажи и быстро движущиеся снаряды - вы можете пропустить их.
Я думаю, что ваш лучший вариант - провести линию через переднюю часть снаряда по пути, который требуется, пиксель за раз. Вы можете сделать ограничительную проверку сначала на всем томе, чтобы не делать это на каждом шагу.
источник
Так как ракета вряд ли будет перемещать огромное количество пикселей в каждом кадре (это не будет гладко на экране), я не вижу причин не просто проверять каждый пиксель на пути. Алгоритм линии Брессенхэма - ваш друг, и убедитесь, что вы также получили локальную копию своего растрового изображения, поскольку вы обычно не хотите получать доступ к видеопамяти для каждого пикселя. Это предполагает, что ваша растровая местность полностью случайна (согласно разрушаемой местности червей). Если ваш мир основан на фишках, вы можете пропустить все фишки, которые, как вы знаете, для начала пустые, но, как уже упоминалось ранее, если у вас нет огромного количества ракет для проверки, я не мог бы подумать о платформе, которая будет нуждаться в слишком медленной скорости. просто тестировать пиксель за пикселем, и вам не нужно будет определять мир в примитивах (клон червей сделает это непросто)
источник
В дополнение к другим ответам, есть некоторые вещи, которые вы можете сделать, чтобы ускорить это, если вы хотите сделать небольшую бухгалтерию в отношении «сбора» группы пикселей в блоки «известного подобного состояния». Например, вы можете хранить высоту самого высокого куска местности, так что вы можете считать само собой разумеющимся, что ракета ничего не ударит, пока она выше этого. Вы также можете сохранить высоту самого низкого «воздушного» пространства, так что вы будете знать, что если ракета достигнет такой высоты, она должна что-то поразить (хотя это лучше всего использовать для проверки работоспособности). Пройдя дальше, вы можете хранить прямоугольники, представляющие области, которые представляют собой всю местность, и другие прямоугольники, которые являются воздушными, но это может быть больше работы, чем ценности.
В конечном счете, лучшим методом, вероятно, будет «запоминать высоту каждого столбца местности», а затем просто вычислять высоту ракеты на каждом этапе ее пути. Я не могу говорить о более современных играх, но я считаю, что когда вы сделали «пещеру» в Scorched Earth, местность над этой пещерой падала прямо вниз, не оставляя никаких выступов. Если вы хотите навесы, работа будет немного больше, но это будет расширение этой основной идеи. (Подсказка: сначала получите основную идею!)
Поскольку ваша местность, по-видимому, совершенно произвольна, ярлыков здесь нет. Даже если вы заставите свою местность быть сплайном или чем-то еще, это расстроится, как только вы начнете разрушать ее, и тесты пересечения линии-сплайна являются итеративными и не идеальными или исчерпывающими и бессмысленно медленными для вашего типа проблемы.
источник