前段时间遇到一个跨地图寻路的需求，需要在任意两个地图之间自动寻路。我们的寻路算法用的是AStar,每个地图都有一份格子数据，地图之间有传送门通过。

首先这是一个最短路径问题，常用的最短路径算法有Dijkstra、Floyd。这里我的思路是选择Dijkstra来实现。

具体的Dijkstar算法原理可以参考这两篇文章：（反正我是学完就忘记了 笑哭~）

透彻理解迪杰斯特拉算法
最短路径—Dijkstra算法和Floyd算法

1.定义图的数据结构

    int MAXV;//最大顶点个数
    const int INF = int.MaxValue;    //INF表示∞ 无穷大

    struct MGraph                    //图的定义
    {        public int[][] edges;       //邻接矩阵
        public int n, e;             //顶点数,弧数
        public VexterMapId[] vexs; //存放顶点信息
    };

把mapID设置到每个顶点数据里

        for (int i = 0; i < MAXV; i++)
        {
            g.vexs[i].mapID = mapNodeList[i];
        }

2.根据传送门配置，生成边（连通顶点之间）。这里我是没有计算AStar权值的，也就是默认每张相邻地图连接边的权值都是1。这样其实是不精确的，如果你们游戏对精确度要求比较高的话，就要计算同一个地图里的传送点之间AStar路径的权值。

        //建立图的临接矩阵
        for (int&nb
        
        	

        		
延伸阅读

        		
        		
        		学习是年轻人改变自己的最好方式-Java培训,做最负责任的教育,学习改变命运,软件学习,再就业,大学生如何就业,帮大学生找到好工作,lphotoshop培训,电脑培训,电脑维修培训,移动软件开发培训,网站设计培训,网站建设培训学习是年轻人改变自己的最好方式