AStar.cs

这里只显示每个文件的开头 60 行。登录后可以解锁完整代码。

微信扫码关注公众号，代码整理好后第一时间通知你。

using System;
using System.Drawing;
using System.IO;

namespace GemTD {
    public class AStar {
        static double multiple = 10000;                         // 距离扩大系数，越大结果越精确，同时有溢出的风险
        static int unitD1 = (int)(multiple * 1);                // 单元格的边长
        static int unitD2 = (int)(multiple * Math.Sqrt(2));     // 单元格对角线长

        int nodeSerial = 0;                                     // 加入最小堆的序号，当F相同时，nodeIndex越大则优先
        Node[,] nodes;                                          // AStar算法的地图
        Heap<Node> openList;                                    // Node的Open链表，使用最小堆
        Point pointStart;                                       // 起点
        Point pointEnd;                                         // 终点
        int rowSize;                                            // 地图行宽
        int colSize;                                            // 地图列宽

        // Node状态，初始为Init状态，加入openList变为Open状态，从openList移除后变为Close状态
        public enum NodeStatus {
            NodeStatusInit = 0,
            NodeStatusClose,
            NodeStatusOpen
        }

        // Node节点
        public class Node {
            public Point point;             // Node的位置信息
            public NodeStatus nodeStatus;   // Node的状态
            public bool passable;           // 是否阻塞道路
            public int F;                   // AStar算法中的F值 F = G + H
            public int G;                   // AStar算法中的G值 G为从start到当前Node的实际cost
            public int H;                   // AStar算法中的H值 H为当前节点到end的估计cost
            public int serialNumber;        // 点加入openList的序号，当F相同时，序号越大优先级越高
            public Node fatherNode;         // 当前Node的父Node
            public int index;               // 在最大堆中的索引，便于节点Remove
        }

        private int CalcPointH(int x, int y, Point end)
        {
            int d1 = Math.Abs(x - end.X);
            int d2 = Math.Abs(y - end.Y);

            int length = Math.Max(d1, d2);
            int width = Math.Min(d1, d2);

            // 短边的根号2+长边-短边
            return width * unitD2 + (length - width) * unitD1;
        }

        private int NodeCompare(Node node1, Node node2)
        {
            if (node1.F < node2.F) {
                return -1;
            } else if (node1.F > node2.F) {
                return 1;
            }

            if (node1.G > node2.G) {
                return -1;