为 A* 算法获取 2 个坐标的启发式

Question

对于我的学校项目，我正在使用 A* 算法制作 2D 瓦片地图，以找到通过障碍物的最短路径。我使用公式从 http://www.growingwiththeweb.com/2012/06/a-pathfinding-algorithm.html

中获取下一个图块的启发式分数

这是启发式函数

    public static int geth(int cx, int cy, int ex, int ey)
    {
        //cx = current position x
        //cy = current position y
        //ex = end (goal) position x
        //ey = end (goal) position y

        int c = 14;
        int d_min = Math.Min(cx - ex, cy - ey);
        int d_max = Math.Max(cx - ex, cy - ey);
        int h = c * d_min + (d_max - d_min);
        if (h < 0) //make h positive in case it's negative
        {
            h = h * -1;
        }

        return h;
    }

这在 y 轴上的起点高于终点时有效，但当起点在 y 轴上较低时找不到最有效的路径。

我已经添加了我的问题的控制台版本。最高效的应该是对角向上，但是走错了路

（蓝色'C'是检查过的节点，绿色'P'路径已经完成，红色'N'待检查，其他还没到）

Answer 1

在链接文章中，我看到了这个算法：

差异周围的管道符号 | 是 absolute value function，这在 C# 中表示为 Math.Abs。

距离没有附加符号。当 ex 大于 cx 时，cx - ex 将为负数（对于 cy - ey 也是如此），这会导致您的 Math.Min 和 Math.Max 选择d_min 和 d_max 的尺寸错误。您应该使用 Math.Abs 从被比较的数量中删除符号。

例如

    int d_min = Math.Min(Math.Abs(cx - ex), Math.Abs(cy - ey));

（对于 d_max 也是如此。）

为 A* 算法获取 2 个坐标的启发式

Getting Heuristic of 2 coordinates for A* algorithm

c#

path-finding