Как найти, куда наложить луч, чтобы избежать столкновения в Bullet?
Скажем, у нас есть объект в точке A. Он хочет выяснить, может ли он двигаться в точку B. У него ограниченная скорость, поэтому он может двигаться только шаг за шагом. Он направляет луч в направлении, к которому движется. Луч сталкивается с объектом, и мы его обнаруживаем. Как получить способ безопасно пройти наш луч (избегая столкновений)?
Кстати, есть ли способ заставить такую вещь работать в случае приведения объекта, будет ли это так же быстро или почти как при обычном приведении лучей?
Есть ли способ найти оптимальный на каком-то пути?
Решение
То, о чем вы спрашиваете, на самом деле является поиском пути; более конкретно, это «проблема поиска пути под любым углом».
Если вы можете ограничить края препятствий для сетки, то популярным решением будет просто использовать A * на этой сетке, а затем применить сглаживание пути. Тем не менее, есть (сравнительно недавно) алгоритм, который проще в реализации / понимании и дает лучшие результаты, чем сглаживание пути. Это называется Theta *.
Есть хорошая статья, объясняющая Theta * (из которой я украл изображение выше) Вот
если ты не может ограничить ваши препятствия в сетке, вам придется генерировать навигационная сетка для вашей карты:
Есть много способов сделать это, различной сложности; смотри например Вот, Вот, или же Вот. Быстрый поиск в Google также обнаруживает множество доступных библиотек, таких как: этот или же этот.
Другие решения
Одним из подходов может быть использование веревки или нескольких веревок, где веревка состоит из нескольких точек, соединенных линейно. Вы можете инициализировать точки в произвольных местах в пространстве, но первая точка — это начальная позиция , и последний пункт является окончательным положением .
Изначально веревка будет очень плохим маршрутом. Для оптимизации перемещайте точки вдоль градиента энергии. В вашем случае функция энергии очень проста, то есть общая длина веревки.
Это не новая идея, но она используется в компьютерном зрении для обнаружения границ объектов, хотя энергетические функции намного сложнее. Тем не менее, посмотрите на «змей», чтобы дать вам представление о том, как перемещать каждую точку, учитывая ее двух соседей: http://en.wikipedia.org/wiki/Snake_(computer_vision)
В вашем случае, однако, просто получить направление для каждой точки из силы, действующей на соседей, будет очень хорошо.
Ваша проблема — это ограниченная проблема, когда вы рассматриваете столкновение. Я бы на самом деле согласился с идеей @ paddy использовать выпуклую оболочку или даже просто сферу для каждого объекта. В последнем случае не перемещайте точку в место, где ее расстояние до В меньше радиуса плюс радиус В плюс фактор выдумки, учитывая, что у вас нет бесконечного количества очков.
Действительное решение требует, чтобы наибольшее расстояние между любыми соседями было меньше порога, в противном случае соединительная линия между двумя точками будет пересекаться с препятствием.
Как насчет простого подхода для начала ….
Если это всего лишь один объект, вы можете вычислить выпуклую оболочку всех вершин препятствия, а также начальную и конечную точки. Затем вы должны изучить два направления, чтобы добраться от А до Б, пересекая корпус по часовой стрелке и против часовой стрелки. Выберите кратчайший путь.
Это немного сложнее, потому что форма, которую вы двигаете, это не просто точка. Вы не можете просто слепо перемещать его центр, иначе он столкнется. Ситуация становится еще сложнее, когда она проходит мимо вершины, потому что вам приходится прижимать край вашего объекта к вершине препятствия.
Но, надеюсь, это дает вам идею для размышления, это не является концептуально сложным для понимания.
Я сделал это изображение, чтобы рассказать мою идею достижения объекта до точки Б.
Объекты на изображении: —
Синяя точка представляет объект. Красные линии являются препятствиями. Серая точка и линия — это область, до которой можно добраться. Фиолетовая стрелка указывает направление точки B. Серая линия объекта — поле видимости.
Понимание изображения: —
Объект будет иметь определенное поле видимости. Это двумерная ситуация, поэтому я предположил, что поле видимости составляет 180 градусов. (для поля зрения человека см. http://en.wikipedia.org/wiki/Human_eye#Field_of_view ) Объект будет измерять расстояние, используя идею SONAR. С помощью SONAR объект может определить область, в которой он может достичь. Используя BACKTRACKING, объект может узнать путь к объекту. Если нет пути, объект должен изменить свое поле видимости
Один из способов взглянуть на это как на проблему отбрасывания теней. Делать A «источник света», а затем решить, находится ли каждая точка сцены в тени или вне ее. Те, кто не в тени, доступны лучам из A, Других областей нет. Если ты найдешь B находится в тени, тогда вам нужно только найти ближайшую точку в сцене, которая находится в свете.
Если вы преобразуете эту проблему в «пиксели», то вышеупомянутый подход имеет очень известные решения в огромной литературе по компьютерной графике по рендерингу теней. Например, вы можете использовать Карта теней закрасить каждый пиксель логическим флагом, который указывает, находится ли он в тени или нет. Найти ближайший светящийся пиксель — это просто поиск растущих концентрических кругов вокруг B, Обе эти операции могут быть выполнены чрезвычайно быстро с использованием аппаратного обеспечения графического процессора.
Еще одно замечание: общую проблему поиска пути объекта можно рассматривать как проблему точечного пути. Секрет в том, чтобы «нарастить» препятствия на соответствующую величину, используя различия Минковского. Смотри например эта работа по планированию пути робота.