我需要一种算法，它可以为我提供有关两点之间最短路径的信息。路径应该有尽可能少的边缘，因为每个航路点，每个转弯都需要时间和时间 - 在我的情况下 - 是昂贵的。
应该计算路径以绕过某些形状（主要是圆形或矩形）的障碍物。
存储路径的信息应该是路径路径点的笛卡尔坐标或极坐标（这是我的单元执行的命令，如转向角度 alpha，移动距离 b）。但是，我更喜欢每个航点的笛卡尔坐标。
没有导航网或其他东西，只有坐标系和有关障碍物和其他禁区的信息，其中一些是固定的，有些可能（并且很可能会）移动。
啊，所有这些都应该以某种方式在 .NET 中可用。
谢谢
//编辑：为了让事情更清楚一点，这是我打算做的图片：https ://dl.dropbox.com/u/8802336/path.png
Your question can be interpreted two ways.
1. I want to find the shortest path, breaking ties by choosing the one(s) with the least number of edges
You can do this by adding some very small number ε to the weight of every edge of the graph. The number must satisfy ε < 1/numberOfEdges. This will increase the length of every path by edges*ε, meaning shorter paths will be preferred. This works even with negative-weight edges. Be careful of floating-point inaccuracies.
2. I want to find the path with the least number of turns, breaking ties by choosing the one(s) with the shortest path
You can do this by adding some large number E to the weight of every edge on the graph. The number must satisfy E > sumOfAllEdgeWeights. This will ensure that only paths with the least possible number of edges are considered. This does not work with negative-weight edges. Be careful of integer overflows.
如果目标是：
1) 最小化边数。
2) 最小化距离。
按照这个顺序，你可以尝试这样的一件事：
1) 从头到尾画一条线。
2）计算你的线碰撞的每个对象。
3) 对于这些对象中的每一个，计算垂直于对象的两个点，以便将路径分成两个路径段。您可以通过将线分成两段来对矩形执行此操作，对于段 A，查看它可以通过的四个角中的哪个，对于段 B，查看它可以通过的四个角中的哪个并尝试所有组合，直到找到位移最小的两个。对于圆圈，我忘记了怎么做，但是在两侧只有一个解决方案，两个路径段与圆圈齐平，所以你可以使用三角函数或其他东西来做（我会试着弄清楚:)）
对于两条新路径，以递归分支方式调用 4)。
4) 对于你生成的两条线段，重复计算直到没有碰撞。与 A* 类似，您应该首先计算看起来最好的路径（剩下的碰撞最少，或者如果太难，就先做最浅的碰撞）。
5）通过您喜欢的任何指标选择最佳路径。以 A* 方式，您应该对列表进行排序，以便通过您的指标的最佳路径位于顶部，因此您可以选择第一条路径来完成。
我无法在脑海中证明这将永远有效，但我以前见过类似的东西。
编辑
要计算两个线段在一个方向上绕圆的最近路径，请对每个线段执行
-A 面：从行首（或行尾）xs,ys 到圆心 xc,yc，长度 = a
-B 面：从中心 xc,yc 到圆周上的某处，所以长度 = r
-C 面：从 B 面的端点到 xs,ys（斜边）
A和B形成的角是直角，我们知道A和B的长度，所以我们可以计算C的长度为sqrt(A^2+B^2)
最后，我们知道 C 的长度 = A 的长度/sin(角度(B 到 C)) = B 的长度/sin(角度(A 到 C))，这意味着我们可以做三角函数来找出角度 A 到 C 和角度 B对 C。
这让我们可以完全构建路径段的一侧。对另一侧重复，我们将路径分成两部分，在两个部分上都与圆齐平 -> 最小化添加的距离。
