C#: пересечение двухмерной подплиточной линии

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

В игре юниты могут занимать разные позиции внутри плитки, т.е. они могут быть в верхнем левом углу, в центре, внизу справа, ... позиция плитки (2/3), т.е. (2,2/3,1), (2,5/3,5 ), (2,8/3,9).

Если они перемещаются из положения (2.2/3.1) в (5.7/4.1), мне требуется проверка, чтобы увидеть, есть ли препятствие на пути.

Мой текущий алгоритм:

  1. Начиная с (2.2/3.1)
  2. Рассчитайте угол движения (т.е. 70 градусов)
  3. Переместиться на 0,1 шага в этом направлении
  4. Проверьте, на какой плитке я нахожусь (этаж (p.X)/этаж (p.Y))
  5. Повторить с 2

Этот алгоритм работает, но мне он кажется не очень эффективным, так как препятствием может быть только целая плитка, а не часть плитки (юниты не сталкиваются). Если я увеличу размер шага, я начну пропускать плитки, которые лишь слегка пересекаются (т.е. вы пересекаете только нижний левый угол). Даже при размере шага 0,1 все еще можно пропустить препятствие.

Я попытался найти решение, чтобы взять дополнительную карту (все плитки с углами (пол (начало.X)/этаж (начало.Y)) и (потолки (начало.X)/потолки (начало.Y)), переместить через каждую плитку и проверить математически, если он пересекается.К сожалению, мне не хватает необходимых математических знаний для этой проверки.

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

Любые подсказки?

Спасибо.


c# 2d intersection tiles line-intersection
person Morfildur    schedule 03.05.2010    source источник

Ответы (1)


arrow_upward
5
arrow_downward

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

  1. Рассчитайте уравнение линии (y = 0,286x + 2,471)
  2. Вы начинаете с плитки 2,3 и двигаетесь к плитке 5,4. Итак, вычислите значение y, когда x станет равным 3 (граница плитки сразу справа). Это 3,329.
  3. Затем вычислите значение x, когда y станет равным 4 (граница плитки непосредственно выше). Это 5,346.
  4. Начиная с 2,3 и двигаясь вправо, получаем 3,3,329. При движении вверх получается 5.346,4. Вы пересекаетесь справа (перемещение 2 -> 3 по x не перемещает плитку по y). Вы не пересекаетесь выше, пока не окажетесь на плитке 5 в x.
  5. Плитка, вычисленная в 4, становится вашим новым сравнением (3,3). Повторите с шага 2.

Этот процесс требует только одного вычисления для каждой перемещенной плитки (независимо от вашей точности или размера плитки) и является точным. Обратите внимание, что рассчитанные значения можно сохранять и использовать повторно вместо того, чтобы слепо вычислять оба пересечения снова и снова. В приведенном выше примере мы знаем (шаг 4), что мы не двигаемся вверх на плитку, пока x=5. Таким образом, весь путь можно вывести без дополнительных вычислений (2,3 -> 3,3 -> 4,3 -> 5,3 -> 5,4).

Также возможно предварительно рассчитать все переходы вместо того, чтобы делать их пошагово, хотя это было бы полезно, только если вам всегда нужен весь путь (вы не должны, поскольку вы хотите остановить обработку, как только обнаружите препятствие).

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

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

person ktharsis    schedule 06.05.2010
comment
Отличный ответ, спасибо. Я приму его, как только SO позволит это (осталось 13 часов) - person Morfildur; 06.05.2010
comment
Конечно! Это очень умно. Я пытаюсь реализовать это, но не могу найти способ закодировать 4-й шаг (я не могу найти идеальное условие if/else, которое определяет, какая новая точка сравнения). Вы помните название этого алгоритма, чтобы я мог поискать пример реализации? - person XPac27; 08.03.2011