用 Dijkstra 做跨地图寻路：把最短路全部预先算好
游戏里的地图是一张一张独立的，玩家想去别的地图，只能走传送点。
策划配表的时候会给每个地图配一组「跳转」：jumpmap，
里面写着某个传送点的坐标，以及它通往哪张地图。
玩家点一下自动寻路，引擎得告诉他「先走到哪个传送点」。
这个问题本质上是「有向图上求两点间最短路」，用 Dijkstra 就够了。
但关键在于什么时候算：地图是静态配置，进游戏之后不会变，
那么与其每次点击都跑一遍，不如在初始化时把所有地图对的最短路径一次性算完存起来，
运行时只做一次字典查询。这就是下面这个 PortalModel 的做法。
数据结构
_mapSceneDic：<地图 id, 可以传送到哪些地图 id[]>，建图用的邻接表_mapPortalDic：<地图 id, <目标地图 id, 传送点数据>>，查「该走哪个门」用的_FinPathdDic：<"起点-终点", 途经地图 id 数组>，预计算的结果缓存_edgesArr：临时的邻接矩阵，两个地图之间连通记 1，不连通记Max = 99
完整实现
/**
* 跨地图寻路模块
*/
class PortalModel extends BaseSystem {
/**
* 场景传送到 某个场景列表 <地图id,可传送到地图id[]>,
* */
private _mapSceneDic: Dictionary<number, number[]>;
/**
* 传送点列表 <地图id,传送点[]>,
*/
private _mapPortalDic: Dictionary<number, Dictionary<number, PortalData>>;
/** 寻路列表 */
private _FinPathdDic: Dictionary<string, number[]>;
/** 一共的地图数量 */
private _mapList: number[];
private _edgesArr: Dictionary<number, Dictionary<number, number>>;
private Max: number = 99;
public constructor() {
super()
this._mapSceneDic = new Dictionary<number, number[]>();
this._mapPortalDic = new Dictionary<number, Dictionary<number, PortalData>>();
this._FinPathdDic = new Dictionary<string, number[]>();
}
public Init() {
let allConfig = GameGlobal.Config.MapConfig;
let nowData: PortalData;
for (let configKey in allConfig) {
if (allConfig[configKey].jumpmap) {
let jumpmap = allConfig[configKey].jumpmap;
let mapId = allConfig[configKey].mapid;
for (let key in jumpmap) {
let jumpConfig = jumpmap[key]
nowData = new PortalData(jumpConfig[0], jumpConfig[1], jumpConfig[2]);
if (this._mapSceneDic.ContainsKey(mapId) == false) {
this._mapSceneDic.Set(mapId, []);
}
this._mapSceneDic.Get(mapId).push(nowData.gotoMapId);
if (this._mapPortalDic.ContainsKey(mapId) == false) {
this._mapPortalDic.Set(mapId, new Dictionary<number, PortalData>());
}
this._mapPortalDic.Get(mapId).Set(nowData.gotoMapId, nowData);
}
}
}
/** 总地图数量 */
this._mapList = this._mapPortalDic.GetKeys();
this.initDiJkStar();
}
/** 通过dijk算法 预先计算所有的行走路径 */
private initDiJkStar() {
this.initEdges();
let mapNum: number = this._mapList.length;
for (let i = 0; i < mapNum; i++) {
this.diJkStar(i);
}
}
/**
* 初始化连接
* 这里主要是 初始化 两个地图之间 是否有链接,如果有的话 那么他们之间的距离是就1 如果没有链接,暂时把它们的距离设定为99
*/
private initEdges() {
let mapNum: number = this._mapList.length;
let mapI: number;
let mapJ: number;
this._edgesArr = new Dictionary<number, Dictionary<number, number>>();
for (let i = 0; i < mapNum; i++) { //遍历所有的地图
mapI = this._mapList[i];
this._edgesArr.Set(mapI, new Dictionary<number, number>())
for (let j = 0; j < mapNum; j++) { //遍历一个地图 和其他地图之间的关系
mapJ = this._mapList[j];
if (this._mapSceneDic.ContainsKey(mapI) && this._mapSceneDic.Get(mapI).indexOf(mapJ) > -1) {
this._edgesArr.Get(mapI).Set(mapJ, 1);
} else {
this._edgesArr.Get(mapI).Set(mapJ, this.Max);
}
}
}
}
private diJkStar(index: number) {
/** 地图与地图之间距离的列表 */
let dist: number[] = [];
/**
* 已经完成遍历的地图
*/
let comPath: number[] = [];
/**
* path[i]表示从原点到地图i之间最短路径的倒数第二个 节点
* 例如A->B->C->D 倒数第二个要经过的节点 那么这里就是C
* */
let pathLastPortal: number[] = [];
let mapNum: number = this._mapList.length;
let nowIndexMapId: number = this._mapList[index];
for (let i = 0; i < mapNum; i++) {
//距离初始化,一开始 就是按照 initEdges 的值,也就是不连接的都是max,连接的都是1
dist[i] = this._edgesArr.Get(nowIndexMapId).Get(this._mapList[i]);
//chooseEdges[]置空 0表示i不在chooseEdges集合中
comPath[i] = 0;
//路径初始化
if (dist[i] < this.Max) {
pathLastPortal[i] = index;
} else {
pathLastPortal[i] = -1;
}
}
//把当前地图自己,标记为已完成,无须遍历
comPath[index] = 1;
pathLastPortal[index] = 0;
/** 最小长度 */
let mindis: number;
let shortdis: number; //
let shortdisMapId: number;
//循环直到所有地图与地图之间的最短路径都求出
for (let i = 0; i < mapNum; i++) {
//mindis置最小长度初值
mindis = this.Max;
//选取不在chooseEdges中且具有最小距离的地图shortDis
for (let j = 0; j < mapNum; j++) {
if (comPath[j] == 0 && dist[j] < mindis) {
shortdis = j;
mindis = dist[j];
}
}
//已经遍历的节点,并且拿到了最短路径,那么这个 最短路径的节点,标记为已完成
comPath[shortdis] = 1;
shortdisMapId = this._mapList[shortdis];
//遍历一遍,所有还没有 赋值的 传送点,也就是 chooseEdges[j] == 0
//如果通过当前最短距离地图,也就是 shortdisMapId 到达 该地图nowMap 可以比 当前地图nowIndexMapId 直接去这个地图nowMap近.
//那么就直接给 dist 中的 nowMap 赋值新的 Dist (最短距离)dist[shortdis] + jDist(最短地图去这个地图的距离)
//每一次都会遍历 所有 未被标注的 地图 ,所以 就能 把A->b->c连接起来.
let nowMap: number;
for (let j = 0; j < mapNum; j++) {
if (comPath[j] == 0) {
nowMap = this._mapList[j];
let jDist = this._edgesArr.Get(shortdisMapId).Get(nowMap);
//先判断是否联通,其次判断(最短距离)dist[shortdis] + jDist(最短地图去这个地图的距离) 是否小于 当前地图nowIndexMapId 直接去这个地图nowMap
if (jDist < this.Max && dist[shortdis] + jDist < dist[j]) {
dist[j] = dist[shortdis] + jDist;
pathLastPortal[j] = shortdis;
}
}
}
}
this.putBothpath(dist, pathLastPortal, mapNum, index);
}
/**
* 获得地图与地图间的路径
* @param dist
* @param path
* @param mapNum
* @param index
*/
private putBothpath(dist: number[], path: number[], mapNum: number, index: number) {
let pathVexsList: number[];
for (let i = 0; i < mapNum; i++) {
if (dist[i] > 0 && dist[i] < this.Max) {
pathVexsList = [];
//起点
pathVexsList.push(this._mapList[index]);
this.findpath(path, i, index, pathVexsList);
//终点
pathVexsList.push(this._mapList[i]);
let pathKey: string = this._mapList[index] + "-" + this._mapList[i];
//不存在
if (this._FinPathdDic.ContainsKey(pathKey) == false) {
this._FinPathdDic.Set(pathKey, pathVexsList);
}
//Debug.Log(string.Format(" 从 {0} 到 {1} 的最短路径长度为:{2}\t路径为:{3}", g.vexs[v].mapID, g.vexs[i].mapID, dist[i], pathStr));
}
//else
// Debug.Log(string.Format("从{0}到{1}不存在路径\n", v, i));
}
}
/** 通过地图在 MapList 中的 Index 来获取 当前 地图 到 指定地图的 路径 */
private findpath(path: number[], i: number, index: number, pathVexsList: number[]) //前向递归查找路径上的地图
{
let k: number = path[i];
if (k == index) {
return; //找到了起点则返回
}
//找地图k的前一个地图v
this.findpath(path, k, index, pathVexsList);
pathVexsList.push(this._mapList[k]);
}
/**
* 想要去到某个地图,这里返回 当前地图的寻路,如果没有路径或者就是当前地图,那么返回空
* @param goMapId 想要到达的mapId
*/
public goToMapid(goMapId: number): PortalData {
let nowMapId = GameGlobal.RaidMgr.GetCurMapRaid().GetMapId();
let pathList: number[] = this._FinPathdDic.Get(nowMapId + "-" + goMapId);
if (pathList && pathList.length > 0) {
if (this.mapPortalDic.Get(nowMapId)) {
return this.mapPortalDic.Get(nowMapId).Get(pathList[1]);
}
}
return null;
}
public get mapSceneDic(): Dictionary<number, number[]> {
return this._mapSceneDic;
}
public get mapPortalDic(): Dictionary<number, Dictionary<number, PortalData>> {
return this._mapPortalDic;
}
}
/**
* 传送门数据
*/
class PortalData {
x: number;
y: number;
/** 可以去那个地图 */
gotoMapId: number;
orderId: number;
constructor(x: number, y: number, gotoMapId: number) {
this.x = x
this.y = y
this.gotoMapId = gotoMapId
this.orderId = MoveConst.ORDER_PORTAL_BEGIN_ID + x * y
}
GetOrderId() {
return this.orderId
}
}分步说明
建图（initEdges）。
把邻接表摊平成邻接矩阵：两张地图之间有传送点，距离记 1；没有，先记 Max。
这里用 1 而不是真实距离，是因为我们只关心「经过几张地图」，不关心地图内的路程——
地图内部怎么走是另一套格子寻路要管的事，两者分开更清楚。
单源最短路（diJkStar）。
三个数组各司其职：dist 存当前已知最短距离，
comPath 标记已经确定的地图，
pathLastPortal 存「最短路径上的前一个地图」，专门用来事后回溯。
每轮从没确定的地图里挑一个 dist 最小的，用它去松弛其他地图，就是教科书版的 Dijkstra。
回溯路径（putBothpath + findpath）。
外层跑完 Dijkstra 之后，对每个可达终点从 pathLastPortal 一路往前找，递归到起点就返回，
于是拿到一条完整的地图序列，以 "起点-终点" 为键存进 _FinPathdDic。
运行时查询（goToMapid）。
玩家点一下，拿当前地图和目标地图拼出 key 去查表，取出路径里的第二个元素——
也就是「下一张该去哪张地图」，再顺着 _mapPortalDic 拿到那个传送点的坐标。
整个过程是两次字典查询，和地图数量无关。
复杂度划不划算
单次 Dijkstra 是 O(V²)，对每张地图各跑一次，总共 O(V³)。
地图数量 V 一般也就几十张，三十张地图大概是两万多次基本运算，初始化阶段跑完是毫秒级的。
用一次性的初始化开销，换来运行时 O(1) 的查询，这笔买卖很划算。
代价是 _FinPathdDic 的空间：最坏情况下 V² 条路径、每条最多 V 个元素，
也就是 O(V³) 个数字。V = 50 时大概是十几万个 int，几兆内存，还能接受；
但如果以后地图数涨到几百张，就得考虑改成「只存下一跳」而不是存完整路径——
其实 goToMapid 只用到 pathList[1]，完整的路径数组目前是存了但没怎么用上的。
几个留了记号的地方
-
Max = 99这个哨兵值有前提。 它假设最短路径最多 98 条边，也就是地图总数不超过 99 张。 地图数量一旦逼近这个数，真实距离就会撞上「不可达」的标记，Dijkstra 会算错。 稳妥的写法是用Infinity，或者干脆用「地图总数 + 1」动态生成。 -
剩余地图全不可达时
shortdis没被赋值。 内层挑最小值的循环如果一次都没命中，shortdis还是undefined， 下一行comPath[shortdis] = 1就写到了comPath[undefined]上。 因为那些地图本来就不可达，最终结果不受影响，但建议加一个「找不到就 break」的兜底， 免得以后排查问题时看着这一行犯嘀咕。 -
dist[i] > 0这个过滤挺巧。 它顺手把「自己到自己」（距离 0）排除了，省了一次i == index的判断。 不过这也意味着代码依赖「起点到起点距离为 0」这个前提，改的时候要留意。 -
边是有向的。
邻接表只记录
mapId → gotoMapId，所以单向传送门能被正确处理； 但如果策划漏配了回程，玩家就会「有去无回」，而且这种问题在配置表上很难肉眼发现。 我现在的做法是初始化时顺手打一份「只有出边没有入边」的地图清单出来。 -
PortalData.orderId = ORDER_PORTAL_BEGIN_ID + x * y有撞号风险。 用坐标乘积当唯一 id，遇到(2, 6)和(3, 4)这种乘积相同的组合就会重复。 换成自增计数器更保险。
本文为个人开发笔记，代码来自实际项目，已做脱敏处理；文中提到的问题点是我自己的记录，供以后改动时参考。