algorithm - 是否可以使用一组包含 4 个或更多顶点的对象来实现 A* 路径查找？

Question

我有一组对象(每个矩形有 4 个 (X,Y) 顶点)使用 OpenGL ES 在 map 上绘制。我想在他们每个人之间实现寻路。

例如我有矩形 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

除此之外我没有其他信息。是否可以使用 A* 路径查找算法绘制从 B 到 E 的路径。

它的实现还需要什么吗？我已经查找了星形搜索实现，但其中大多数都是基于网格的 map ，他们在哪里计算附近节点的成本并使用它们来查找 map ？有什么方法可以用我拥有的数据来计算这些值吗？

Answer 1

我可以想到两种方法将您的数据转换为 A* 可以处理的内容，请记住 A* 可以处理图形，而不仅仅是网格。

1. 最简单的方法就是“网格化”您的数据。提出一个足够高分辨率的网格，覆盖您要在其中执行寻路的区域，然后根据它们是否落在您的矩形内，将单元格标记为已占用或未占用。 “足够高的分辨率”可能需要比您愿意花费的更多的内存。
2. 申请polygon triangulation algorithm到代表 map 的开放、可穿越区域的多边形，然后将三角形变成图形的顶点。只要相应的三角形相互接触，图形顶点之间就会有边。确定分配给图边的权重以确保最佳寻路可能很棘手。较小的三角形应该有所帮助。

在这种情况下，您需要对其中有许多孔的多边形执行三角测量，这会使事情变得复杂。幸运的是，这个主题已经出现在 stackoverflow 上，在“Polygon Triangulation with Holes”中。他们指向一个名为“Triangle”的库，它在首页上有一张准确说明您需要做什么的图片。他们的演示页面有更多图片，包括这些有用的图片:

假设你做了一个非常粗略的三角测量:

绕过拐角的路径可能离它们很远，这取决于您如何将图形上的路径转换为坐标空间中的路径。但是如果你做一个更精细的三角测量:

然后路径将能够更靠近角落、墙壁等。

这种技术应该适用于几乎任何类型的具有多边形轮廓和无法遍历的多边形区域的“ map ”。