Возможно ли реализовать поиск путей A * с набором объектов, содержащих по четыре или более вершин?

Question

У меня есть набор объектов (прямоугольники с 4 вершинами (X, Y) каждый) нарисовать на карте с использованием OpenGL ES. Я хотел бы реализовать способ нахождения между каждым из них.

Например, у меня есть прямоугольники A, B, C, D, E

Структура:

A[Vertex(X,Y),Vertex(X,Y),Vertex(X,Y),Vertex(X,Y)] - Rectangle A 
.. 
.. 
E[Vertex(X,Y),Vertex(X,Y),Vertex(X,Y),Vertex(X,Y)] - Rectangle E 

И у меня нет никакой другой информации, кроме этого. Можно ли нарисовать путь от B до E, используя A * path find alogrithm.

Есть ли что-то еще для его реализации? Я искал реализацию поиска по звездам, но большинство из них говорит о картах на основе сетки, где они вычисляют затраты с соседними узлами и используют их для поиска карты? Есть ли способ, чтобы я мог рассчитать те, у кого есть данные?

Answer 1

Я могу думать о двух путях с головы, чтобы превратить ваши данные в нечто, с чем может работать A *, имея в виду, что A * может работать на графиках, а не только на сетках.

1. Простейшим было бы просто «свести» ваши данные. Придумайте достаточно высокую разрешающую сетку, покрывающую область, в которую вы хотите выполнить поиск пути, а затем отметьте ячейки как занятые или нет, основываясь на том, попадают ли они в ваши прямоугольники или нет. «достаточно высокое разрешение» может потребовать больше памяти, чем вам нужно потратить.
2. Примените polygon triangulation algorithm к многоугольнику, представляющему открытую, проходящую область вашей карты, а затем поверните треугольники в вершины графа. Вершины графа имели бы края между ними, когда их соответствующие треугольники касались друг друга. Определение весов для назначения краям графа для обеспечения оптимального поиска пути может быть сложным. Меньшие треугольники должны помочь.

В этом случае вам необходимо выполнить триангуляцию на многоугольнике с несколькими отверстиями в нем, что усложняет ситуацию. К счастью, объект уже появился здесь в stackoverflow, в «Polygon Triangulation with Holes». Они указывают на библиотеку под названием «Triangle», в которой есть фотография именно того, что вам нужно сделать, прямо на первой странице. Их демо-страница содержит еще несколько фотографий, в том числе эти полезные из них:

Предположим, вы делаете очень грубой триангуляции:

Дорожки происходит вокруг углов может оставаться довольно далеко от них, в зависимости от того, как конвертировать путь на графике к пути в вашем координатном пространстве. Но если вы сделаете гораздо тоньше триангуляции:

Тогда пути будут иметь возможность оставаться ближе к углам, стены и т.д.

Этот метод должен работать для почти любого рода «карту» с многоугольным контуром и многоугольными областями, которые невозможно пройти.