Как найти двумерные ячейки сетки, движущиеся по движущемуся кругу?

9

Я делаю игру, основанную на 2D сетке, где некоторые ячейки проходимы, а некоторые нет. Динамические объекты могут двигаться непрерывно, независимо от сетки, но должны сталкиваться с непроходимыми ячейками.

Я написал алгоритм трассировки луча по сетке, который дает мне все ячейки, которые пересекает луч. Однако фактический объект не имеет точечного размера; В настоящее время я представляю их как круги. Но я не могу найти эффективный алгоритм для отслеживания движущегося круга. Вот картина того, что мне нужно: введите описание изображения здесь

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

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

Ничего
источник
ммх почему 3 сталкиваются ДО 4?
FxIII
@FxIII Я на самом деле переместил круг на картинке, и он ударил 3 до 4. Только едва, но все же раньше.
Nevermind

Ответы:

6

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

Пусть C - ваш центр, а r - радиус, поэтому P ' = C + ( r , 0) и P " = C + (0, r).

Если D - ваш вектор направления (версор), у вас есть две линии:

R '= D · t + P' ,

R "= D · t + P"

Вам просто нужно найти пересечение этих линий с линиями уравнения:

y = i и y = i, которые являются краями вашей сетки!

Решение легко, потому что вы должны просто рассмотреть x или y компонент R 'и R ". Вы найдете значение t s для каждой вставки и точки для thous t s, просто отсортируйте эти точки по t, и вы сделаны.

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

Это работает, если r <1 (ширина и высота ячейки).

Это работает и для других случаев, просто делая некоторые соображения о P ' и P " . Мы выбираем TOP и LEFT, потому что направление, BOTTOM и RIGHT должны рассматриваться для противоположного направления, вы понимаете, почему.

Теперь посмотрите на это изображение: большой круг

Круг больше, чем одна ячейка, и мы предполагаем, что он движется в том же направлении, что и ваш рисунок. P1 - первая точка, которая будет касаться, P2 - вторая, P3 бесполезна, потому что находится в нижней половине. Что вам нужно сделать, это отлить лучи из P1 и P2, как мы видели ранее, и сделать то же самое для вертикальных линий.

В общем, у вас будут другие стартовые точки, помимо ТОПа и ЛЕВЫХ, с которых вы будете стрелять лучами, чем больше ваш круг, тем больше лучей будет наложено.

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

FXIII
источник
Да, я сам придумал точки P 'и P ", но не мог понять, что делать, когда круг больше, чем одна ячейка. Дополнительные точки действительно имеют смысл (и мне, очевидно, нужно только добавить лучи между P' и P ")
Nevermind
Геометрические соображения могут быть сделаны, что упрощает вычисления, но использование реализации может привести к тем же результатам на опыте.
FxIII
Понятно ли, что вам нужно тестировать горизонтальные и вертикальные линии сетки отдельно?
FxIII
Я думаю, что вы также должны проверить, когда окружность покрывает вершину сетки, потому что окружность столкнется с диагонально смежной ячейкой в ​​ее углу, но это не обязательно будет верхняя / левая / нижняя / крайняя правая точка на окружности, которая касается ее первой (и вы обнаружите столкновение слишком рано.) Пример: квадраты 3,4,5 на диаграмме примера в вопросе. Они попадают по порядку (3, затем 4, затем 5), но ваш алгоритм будет обнаруживать 4 и 5 одновременно.
finnw
@ finnw они касаются одновременно только в том случае, если клетка движется точно в направлении биссектрисы.
FxIII
1

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

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

TreDubZedd
источник
8 лучей, вероятно, будут гарантировать все пересечения, но они не приведут их в правильном порядке. И для столкновений мне нужен порядок, а не просто список ячеек.
Nevermind
Дополните свой алгоритм столкновения лучей, чтобы сохранить значение t для каждого столкновения. Когда вы получите объединение ячеек, вы можете отсортировать по t-значению, чтобы получить правильный порядок.
TreDubZedd
Но как я могу сравнить t-значение разных лучей?
Nevermind
Если вы всегда исходите из одного круга, ваши точки пересечения будут на расстоянии от этого круга. Когда вы подходите к ячейке, которую вы уже видели, если значение t текущего столкновения меньше, чем предыдущее, используйте его ... в противном случае откажитесь от пересечения (сохраняя оригинал).
TreDubZedd
1
Возможно, вам удастся выбраться всего двумя лучами по сторонам круга, перпендикулярным движению, затем вы сможете увидеть, какие плитки попали под лучи, и вы можете проверить остальные, чтобы увидеть, попадают ли их центры между двумя лучами. Единственное, что должно пропустить, - это столкновение в начале или конце круга, но это всего лишь два круга, и с ними можно легко справиться. Это может быть немного медленнее, чем восемь лучей, я не уверен; но вам не нужно масштабировать число в зависимости от размера круга.
Лунин
1

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

Райан
источник
Я тоже думал об этом, но, на мой взгляд, это не правильный алгоритм. Брезенхем выбирает только один пиксель, ему нужно все. И было бы трудно адаптировать bresenham к кругу, состоящему всего из одного пикселя.
zacharmarz
Трассировщик лучей, который я использую, на самом деле является своего рода своего рода алгоритмом Брезенхэма. У меня проблемы с обобщением его от тонкой линии к "толстой", особенно по кругу.
Неважно,