C #: 2D пересечение под-плитки линии - PullRequest
Новая
       33

C #: 2D пересечение под-плитки линии

3 голосов
/ 03 мая 2010

У меня есть некоторые проблемы с запуском алгоритма для моей игры, и я надеюсь, что кто-то здесь может мне помочь. Похоже, 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 все равно можно пропустить препятствие.

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

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

Есть подсказки?

Спасибо.

1 Ответ

5 голосов
/ 06 мая 2010

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

  1. Рассчитать строку eqn (y = .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, но, может быть, кто-то другой может предоставить лучший справочник.

...