为什么矩形的两个角之间的路径看起来很奇怪？

Question

我写了一个小程序，用A* algorithm找到两点之间的最短路径。

我将矩形中的每10个像素设为一个节点（宽度：100个节点，高度：50个节点），并将其与周围的4个节点（顶部，左侧，底部，右侧）连接起来。该程序必须找到从左上角到右下角的最快方式。结果如下：

起初我想知道为什么如果这实际上是最快的方式，但后来我认为我应该添加对角连接。以下是它的表现：

花了100个节点到达终点并且大约有。 1193px。这让我更加恼火，现在我想知道我的程序是错的还是实际上是最短路的。

你怎么看？

像第一张照片一样走这条路是不是更快，最后只是斜着走？

Answer 1

没有对角线移动，最快的路径将采取(width-1)+(height-1)移动到达终点。但对于对角线，它会少一些。但是我们只能使min(width-1,height-1)对角线移动，其余的移动必须是非对角线的（在这种特殊情况下朝右）。所以这两张图片确实显示了你的代码看起来正确的最短路径。