Блог

Я следую этому руководству по обработке столкновений в моей 2d игре, в этом руководстве объясняется о столкновении, используемом в одной из моих любимых игр «N». Как они более эффективно использовали теорему о раздельной оси для столкновения между AABB против AABB и AABB против Circle. http://www.metanetsoftware.com/technique/tutorialA.html . Я понимаю реализацию обработки столкновений AABB и AABBB, но я не мог понять обнаружение столкновений AABB и Circle, особенно в областях Вороного.Совершенно запутался, как / с чего начать.

Обнаружение столкновений AABB vs AABB

1. Найдите ось вдоль всего ребра, найдя нормаль к каждому ребру.
2. Спроецируйте все вершины на результирующую ось, конечным результатом должно быть скалярное значение.
3. Результирующее скалярное значение, в свою очередь, используется для определения того, присутствует столкновение или нет.

Может кто-нибудь, пожалуйста, объяснить, как обрабатывать столкновение AABB vc Circle — наоборот?

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

Вы понимаете столкновения между ограничивающими рамками, выровненными по оси. Я предполагаю, что вы также понимаете столкновения между двумя кругами. Я предполагаю, что вы не понимаете области Вороного. Итак, с чего начать? Диаграммы Вороного. Я настоятельно рекомендую вам найти объяснение в виде диаграммы. Эта ссылка довольно хорошая. Однако, в зависимости от того, насколько вы заблудились, возможно, немного дополнительной информации (серьезно, однако, никакое объяснение не может превзойти визуальное):

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

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

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

Это вообще помогает? Обратная связь приветствуется. Я буду рад прояснить что-либо. Объяснение диаграмм Вороного без визуальных элементов, вероятно, плохая идея.