В рамках подготовки к реализации условной игры Mage Rage был написан метод для пересечения линии и прямоугольника.
Начнём знакомиться с методом бросания лучей, или Ray Casting, который широко применяется в играх. Он хорошо известен и описан. Я не буду повторять его описание. Вместо этого мы придём нему через серию мысленных упражнений, которые показывают, как из первых примитивных решений появляются более оптимальные. Отмечу, что Ray Casting используется в основном для рендеринга пространств а-ля Wolfenstein 3D, до которого мы ещё доберемся. Но сейчас задача немного другая.
Есть карта местности, представленная пустыми и заполненными клетками. На карте находятся игрок и монстр. Монстр хочет пройти к игроку. Для этого он строит линию от себя и до обеда игрока, и проверяет, пересекается ли эта линия с какой-то из заполненных клеток. Если пересекается, значит нужно применять алгоритм обхода препятствия.
Так как мы заранее не знаем, с каким из препятствий произойдёт пересечение линии, остаётся только полный перебор.
Это ещё не всё. Линия может пересечь несколько препятствий, но нам нужно только ближайшее к монстру – ведь именно в него он упрётся. Значит, найденные пересечения нужно ещё и отсортировать по расстоянию.
Полный перебор плюс сортировка – вполне рабочий метод, но медленный. Возможно, скорости компьютера хватит для нашей конкретной задачи, а возможно нет.
Когда программист видит полный перебор, он чувствует боль. И тогда он приступает к оптимизации.
Как бы мы действовали, если бы не видели препятствий? Мы бы просто шли вперёд, вытянув руку. Сделали шаг – проверили. Сделали ещё шаг – проверили. И так далее, пока не столкнёмся с препятствием.
Алгоритм оптимизируется: зная направление линии от себя и до цели, наращивать отрезок в этом направлении маленькими шагами и проверять уже не линию, а лишь точку (конец отрезка) – попала она внутрь препятствия или нет.
На первый взгляд стало лучше: препятствие, с которым мы столкнёмся, будет ближайшим к нам. Необходимость в сортировке отпала. И проверка точки вместо линии существенно проще.
Но возникли две проблемы:
- Проверку теперь надо делать после каждого приращения дистанции. Если раньше полный перебор требовался один раз (все препятствия сравнить с одной линией), то теперь полный перебор нужно сделать столько раз, сколько будет шагов приращения.
- Сделав очередной шаг, мы можем просто "перешагнуть" через препятствие.
Чтобы избавиться от второй проблемы, можно уменьшить размер шага. В идеале это будет совсем маленький шаг, длиной, грубо говоря, в 1 пиксел. Но тогда количество шагов и количество проверок станет очень большим.
Представим ещё раз, как мы определяем наличие препятствия с помощью руки. У руки есть длина. Всё, что дальше этой длины, проверять бессмысленно, мы просто туда ещё не дотянемся.
Поэтому хорошо бы проверять не все препятствия, а только те, которые находятся вокруг нас на расстоянии вытянутой руки. То есть – внутри круга определенного радиуса.
Для этого нужно на каждом шаге вычислять дистанцию до каждого препятствия. Если она больше заданного радиуса – пропускаем. Но дистанцию-то всё равно надо считать. Мы избавились от полного перебора на проверках пересечения, но теперь имеем полный перебор на вычислении дистанций.
Ещё раз представим наш поиск вслепую. Что, если мы находимся в комнате, одной из многих? Тогда нас интересуют только те препятствия, которые находятся в этой комнате.
Но ведь наше представление карты состоит из квадратов, то есть можно сказать, из комнат. И мы всегда находимся в каком-то квадрате. Значит, нужно проверять только те препятствия, которые находятся в этом квадрате. Но ведь у нас нет информации, какое препятствие принадлежит какому квадрату?
Эту информацию можно составить заранее, и только один раз. Далее она будет храниться вместе с картой. Тогда для каждого квадрата будет известен список препятствий, которые в нём находятся полностью или частично. Этот метод подходит для карты любого типа – просто наложите на неё сетку из квадратов и вычислите для каждого квадрата, какие элементы карты в него попадают.
В нашем случае всё даже проще. Сам по себе квадрат (клетка карты) либо считается препятствием, либо нет.
Таким образом, если мы находимся в каком-то квадрате, это автоматически означает, что данный квадрат свободен. Нам нужно продолжить линию к следующему квадрату. Следующий квадрат будет смежным с текущим. Таких смежных квадратов 8:
В грубом приближении это тот самый радиус вытянутой руки, только теперь никакие дистанции вычислять не надо. Достаточно проверить 8 квадратов вокруг себя, но на самом деле проверка диагональных квадратов не нужна, так как луч всегда пересекает либо горизонтальную, либо вертикальную стенку, даже если направлен точно в угол:
Значит, проверочных квадратов остаётся только 4. А так как мы знаем направление линии, останется только 2:
Так как монстр всегда находится внутри какого-то квадрата, то выпущенный луч должен в первую очередь пересечь стенку текущего квадрата с внутренней стороны:
Поэтому вместо проверки двух смежных квадратов мы вычисляем пересечение с одной из стенок текущего квадрата:
А зная, что это за стенка (с какой она стороны), мы легко получаем смежный с ней квадрат.
Если этот квадрат пуст, мы продолжаем луч изнутри этого квадрата в том же направлении, вычисляя пересечение с одной из двух возможных стенок:
Затем мы находим новый смежный квадрат, и так далее, пока не попадём в квадрат-препятствие:
Итак, мы избавились от сортировки и полного перебора. На каждом шаге проверяется ровно один квадрат, а всего шагов нужно максимум 2*N, где N – длинная сторона карты. Скорость обработки абсолютно не зависит от количества препятствий и взаимного расположения монстра и игрока.
Это существенно лучше, чем то, с чего мы начали. Но мы всё еще должны находить пересечения линии со стенками квадрата, для чего требуются операции умножения. Можно ли и это улучшить? Можно. В следующем выпуске. А пока вот код, который работает неоптимально, но уже значительно лучше, чем полный перебор.