algorithm - 在多边形中找到成本最低的路径

Question

考虑到它的成本，我试图在多边形内找到一条路径。

在我的具体情况下，我有一个应该只相对直线移动的角色，也就是说，它与向北、向东、向南或向西移动的角度不应超过几度。

理想情况下，我会分配一个随偏差增加的成本。我假设这是一个图论相关的问题，但我不知道如何在多边形中做到这一点......

图中的红色虚线路径是常规算法产生的结果；绿色是我想要的。 编辑:我把图片弄乱了一点；澄清一下:红色路径意味着多边形内的最短路径，我确实希望绿色路径是给定角度约束的最短路径。

(澄清一下，如果我的多边形看起来像 (1)，我希望路径像 (2)，点之间不是简单的直线)

(1)   ,-------------------+      (2)   ,-------------------+
     /               (B)  |           /               (B)  |
    /                     |          /                /    |
+--+                      |  ->  +--+                /     |
|                       +-+      |                  /    +-+
| (A)                   |        | (A)-------------+     |
+-----------------------+        +-----------------------+

Answer 1

这实际上更像是评论，但我不能评论，因为它需要 50 声望... Otoh，我认为这个问题没有令人满意的答案，因为它没有明确定义。但是对一个有趣的问题 +1 :-)

给出红色虚线的算法从路径起点和终点之间的直线开始(不完全在多边形内。)然后沿着多边形的边缘滑动，直到碰到一个角并采取那是你的新起点。 (请注意，您绘制的红色虚线并不是真正的最短路径。)现在您的绿线基本上是红线，您用更长但出于某种原因的路径替换了您不喜欢的部分(错误的角度)更好(漂亮的角度。)这也是为您提供以下示例的“正确”答案的原因。从 (A) 到 (B) 的直线开始，这是最短路径，位于多边形内。现在用更有利的角度替换这条线。 (这可能会迫使你在一般情况下转很多圈……)

只是一些想法。