Линейная траектория на поверхности ториодальной сетки с препятствиями и ограничениями по углу

Question

У меня есть сетка. Если что-то сходит с одного края, оно появляется с другой стороны так же, как на склеивающей диаграмме тора. Есть две произвольные точки на сетке, я хочу найти прямую линию между использованием алгоритма. Линия должна полностью избегать прохождения любых квадратов препятствий. Он также должен находиться в указанном диапазоне углов от оси x. Он должен вернуть наклон найденного линейного пути. Начальная позиция уже известна, поэтому необходим только уклон. Если такого пути не существует, алгоритм должен вернуть какое-то исключительное значение данных, указывающее на отсутствие возможного пути. Это также должно быть чем-то лучшим, чем поиск во всех ракурсах, которые может обработать программа. Как мне сделать этот алгоритм? Я пробовал просто искать все углы, которые программа способна обрабатывать и расширять линию, пока она не достигнет чего-то или не достигнет некоторой максимальной длины, но это довольно неэффективно, и я не хочу, чтобы была максимальная длина. Это не обязательно для пути, который найден, чтобы быть кратчайшим путем. Это просто должен быть путь, который является линейным, имеет определенный диапазон угла от оси X и не сталкивается ни с какими квадратами препятствий.

Answer 1

Это изображение может помочь

Зеленый - отправная точка, красный - цель, коричневый квадрат - препятствие, а серые области. области, заблокированные препятствием.

Обратите внимание, что есть только одна цель и одно препятствие. Цель и препятствие повторяются, чтобы показать, что происходит, когда вы go выходите за правый край сетки и возвращаетесь к левому краю.

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

---

Добавьте еще одно препятствие (фиолетовое), и все углы заблокированы еще раньше.

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

И только для полноты препятствия над целью могут быть игнорируются. Угол к цели всегда будет меньше угла к препятствию.