前段時(shí)間遇到一個(gè)跨地圖尋路的需求，需要在任意兩個(gè)地圖之間自動(dòng)尋路。我們的尋路算法用的是AStar,每個(gè)地圖都有一份格子數(shù)據(jù)，地圖之間有傳送門(mén)通過(guò)。

首先這是一個(gè)最短路徑問(wèn)題，常用的最短路徑算法有Dijkstra、Floyd。這里我的思路是選擇Dijkstra來(lái)實(shí)現(xiàn)。

具體的Dijkstar算法原理可以參考這兩篇文章：（反正我是學(xué)完就忘記了 笑哭~）

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

1.定義圖的數(shù)據(jù)結(jié)構(gòu)

    int MAXV;//最大頂點(diǎn)個(gè)數(shù)
    const int INF = int.MaxValue;    //INF表示∞ 無(wú)窮大

    struct MGraph                    //圖的定義
    {        public int[][] edges;       //鄰接矩陣
        public int n, e;             //頂點(diǎn)數(shù),弧數(shù)
        public VexterMapId[] vexs; //存放頂點(diǎn)信息
    };

把mapID設(shè)置到每個(gè)頂點(diǎn)數(shù)據(jù)里

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

2.根據(jù)傳送門(mén)配置，生成邊（連通頂點(diǎn)之間）。這里我是沒(méi)有計(jì)算AStar權(quán)值的，也就是默認(rèn)每張相鄰地圖連接邊的權(quán)值都是1。這樣其實(shí)是不精確的，如果你們游戲?qū)_度要求比較高的話(huà)，就要計(jì)算同一個(gè)地圖里的傳送點(diǎn)之間AStar路徑的權(quán)值。

        //建立圖的臨接矩陣
        for (int&nb