图论，导航图基础（c#版）_图论在导航中的应用

前言

依然在公司实习，但是待在一个比较成熟的项目组（战地风暴invasion），没什么机会着手项目代码，只能拿着项目代码自己琢磨，学习，然后由于最近玩莉莉丝的art of conquest，被它的垃圾寻路气哭了，所以想自己写写寻路系统，此版本的代码是为了unity而设计的，但是其实因为unity有成熟的navigation插件，所以权当练手了。

图论基础

我们抛开图的数学理论不谈，在计算机数据结构中的图是一种树链的扩充结构，图的遍历和树非常相似，如果你对树或者链表算法非常熟悉，那么恭喜你，图的结构你也能很快熟悉。

1、储存方式

图的储存主流的有两种储存方式，一种是矩阵

如果你要使用矩阵，那么推荐你使用eigen作为c++的矩阵运算库

另一种是邻接表

其实这两种储存方式都不是最佳的，因为矩阵法储存了大量的0，对于边很少的图（稀疏图）造成了很大的浪费。而邻接表法每条边都储存了两次，所以在稠密图（边很多的图）中，有一半的空间都用来储存重复的边了。

算法提要

本系列主要研究的是游戏中的导航图，所以算法都是基于稀疏图。
主要有：深度搜索，广度搜索，A star,其他的算法会在后面补充

应用

导航图常见于AI算法中的寻路，以及基于导航图的行为树或者状态机

---

无向稀疏连通图的实现

通用性的考虑

为了提高算法的通用性，我们不使用c++中的指针来表示邻接表中的链式结构，而是通过储存数组，和数组索引的方法来获取元素，这样我们不仅很容易扩展到各种不可直接操作内存的语言中，而且这样也便于拷贝操作（直接拷贝数组），析构操作（直接施放数组）。

索引节点

为了将实体数据（比如unity中想将图实例化，我们需要存一些实体）和索引分开，我们需要有一种类，它不存放实体数据，其本身是一种索引，我们需要实体数据时，通过索引在实体表中寻找。

public class NodeBase : IComparable
    {
        public int Index { set; get; }

        Dictionary<int, object> _refMap;

        public NodeBase(Dictionary<int, object> refMap)
        {
            _refMap = refMap;
        }

        public object Data
        {
            set
            {
                _refMap[Index] = value;
            }
            get
            {
                return _refMap[Index];
            }
        }

        public int CompareTo(object other)
        {
            return Index.CompareTo((other as NodeBase).Index);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Index属性就是它的索引，我们放一个实体表的引用_refMap，然后通过需要访问Data数据时，我们就通过Index得到装箱过后的object实体。
此处继承了IComparable便于我们根据Index进行排序。

图的顶点

顶点是图的关键数据，它继承于NodeBase便于将实体和结构分开

public class VertexBase : NodeBase
    {
        public VertexBase(Dictionary<int, object> refMap) :
            base(refMap)
        {
            //注意，unity不支持property的初始化器，必须在构造函数中实现
            Edges = new List<EdgeBase>();
        }

        public List<EdgeBase> Edges { set; get; }

        public bool AddEdge(EdgeBase e)
        {
            if (e.From != Index)
                return false;

            foreach (var old in Edges)
            {
                if (old == e)
                    return false;
            }

            Edges.Add(e);
            Edges.Sort();
            return true;
        }

        //extra info
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

顶点类的主要属性为Index（继承于NodeBase），然后存放了该顶点相连的边EdgeBase（稍后会讲解）注意！c#中的List和c++中的std::list很不相同，我们可以理解为数组链表或者std::vector，有很好的随机存取性能

图的边

public class EdgeBase : IComparable
    {
        public int From { set; get; }
        public int To { set; get; }
        public float Cost { set; get; }

        public static bool operator ==(EdgeBase self, EdgeBase other)
        {
            return ((self.From == other.From) && (self.To == other.To))
                || ((self.From == other.To) && (self.To == other.From));
        }

        public static bool operator !=(EdgeBase self, EdgeBase other)
        {
            return !(self == other);
        }

        public int CompareTo(object other)
        {
            return Cost.CompareTo((other as EdgeBase).Cost);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

边表示的一种关系，所以我们不让它成为索引类型。不过如果你想在unity中渲染一条光线作为边的实体，那么你可以让他继承于NodeBase。

我们重载了等于判断，当然你可以重载Equal方法，此处用不到，所以不重载了。
重载的理由是我们的图是无向图，所以起点和终点相反的边是相等的，是同一条边。

稀疏图类

这一块是一个很大的类，我们先写出它将要实现的功能，作为一个接口用来给使用者调用

interface GraphRemote
    {
        //图的结构是很复杂的，不可能用代码来实现，所以我们从xml加载它
        bool LoadFromFile(string xmlname);
        //图变化了（比如某条边断了），保存下来以供下次调用
        void SaveToFile();

        //添加一个顶点
        bool AddVertex(TestNode refTn, VertexBase vert, int idx);
        //移除顶点
        bool RemoveVertex(int idx);

        //渲染出来实体
        void Render();

        //作为一种容器或者说集合，必备方法
        void Clear();

        //通过点的index或者说id访问点
        VertexBase GetVertByIdx(int index);

        // advanced algorithm ...
    }  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

此处的Render方法是为了unity中渲染写的，我们将它实现为virtual，供使用者自由编写。

To be continued…