是否可以使用一组包含 4 个或更多顶点的对象来实现 A* 路径查找？
Is it possible to implement A* path finding with a set of objects containing 4 or more vertices each?
我有一组对象（每个矩形有 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
除此之外我没有其他信息。是否可以使用 A* 路径查找算法绘制从 B 到 E 的路径。
它的实施还有什么要求吗？我已经查找了星形搜索实现，但其中大多数都是基于网格的地图，他们在哪里计算附近节点的成本并使用它们来查找地图？有什么方法可以用我拥有的数据计算这些值吗？
我能想到两种方法将您的数据转换成 A* 可以处理的东西，请记住 A* 可以处理图形，而不仅仅是网格。
- 最简单的方法就是 "gridify" 您的数据。想出一个足够高分辨率的网格来覆盖您要在其中执行寻路的区域，然后根据它们是否落在您的矩形内将单元格标记为已占用或未占用。 "high enough resolution" 需要的内存可能超出您的预期。
- 将 polygon triangulation algorithm 应用于表示地图的开放、可穿越区域的多边形，然后将三角形转换为图形的顶点。只要相应的三角形相互接触，图形顶点之间就会有边。确定分配给图边的权重以确保最佳寻路可能很棘手。较小的三角形应该有所帮助。
在这种情况下，您需要对其中有许多孔的多边形执行三角测量，这会使事情变得复杂。幸运的是，这个主题已经出现在 Whosebug 上，在“Polygon Triangulation with Holes". They point to a library called "Triangle”中，它在首页上有一张准确说明您需要做什么的图片。他们的演示页面有更多图片，包括这些有用的图片：
假设你做了一个非常粗略的三角测量：
绕过拐角的路径可能离它们很远，这取决于您如何将图形上的路径转换为坐标中的路径 space。但是如果你做一个更精细的三角测量：
然后路径将能够更靠近角落、墙壁等。
这项技术应该适用于几乎所有具有多边形轮廓和无法遍历的多边形区域的 "map"。
我有一组对象（每个矩形有 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
除此之外我没有其他信息。是否可以使用 A* 路径查找算法绘制从 B 到 E 的路径。
它的实施还有什么要求吗？我已经查找了星形搜索实现，但其中大多数都是基于网格的地图，他们在哪里计算附近节点的成本并使用它们来查找地图？有什么方法可以用我拥有的数据计算这些值吗？
我能想到两种方法将您的数据转换成 A* 可以处理的东西，请记住 A* 可以处理图形，而不仅仅是网格。
- 最简单的方法就是 "gridify" 您的数据。想出一个足够高分辨率的网格来覆盖您要在其中执行寻路的区域，然后根据它们是否落在您的矩形内将单元格标记为已占用或未占用。 "high enough resolution" 需要的内存可能超出您的预期。
- 将 polygon triangulation algorithm 应用于表示地图的开放、可穿越区域的多边形，然后将三角形转换为图形的顶点。只要相应的三角形相互接触，图形顶点之间就会有边。确定分配给图边的权重以确保最佳寻路可能很棘手。较小的三角形应该有所帮助。
在这种情况下，您需要对其中有许多孔的多边形执行三角测量，这会使事情变得复杂。幸运的是，这个主题已经出现在 Whosebug 上，在“Polygon Triangulation with Holes". They point to a library called "Triangle”中，它在首页上有一张准确说明您需要做什么的图片。他们的演示页面有更多图片，包括这些有用的图片：
假设你做了一个非常粗略的三角测量：
绕过拐角的路径可能离它们很远，这取决于您如何将图形上的路径转换为坐标中的路径 space。但是如果你做一个更精细的三角测量：
然后路径将能够更靠近角落、墙壁等。
这项技术应该适用于几乎所有具有多边形轮廓和无法遍历的多边形区域的 "map"。