前段时间遇到一个跨地图寻路的需求,需要在任意两个地图之间自动寻路。我们的寻路算法用的是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 i = 0; i < g.n; i++) { g.edges[i] = new int[MAXV]; for (int j = 0; j < g.n; j++) { //计算i到j的权值 int mapI = mapNodeList[i]; int mapJ = mapNodeList[j]; if (linkDic.ContainsKey(mapI)) { if (linkDic[mapI].ContainsKey(mapJ))//判断地图I到地图J能不能走通 { g.edges[i][j] = 1;//默认给权值都为1 continue; } } g.edges[i][j] = INF; } }
3.生成所有地图之间的最短路径作为一个静态配置,这样在运行时就不需要运算Dijkstra算法去查询了,直接进入游戏的时候解析配置,后面就可以随便查询都不影响性能。
/// <summary> /// 所有路径放这里保存 /// </summary> public Dictionary<string, List<int>> allPathDic = new Dictionary<string, List<int>>(); public void ExportPath() { float time = Time.realtimeSinceStartup; for (int i = 0; i < MAXV; i++) { Dijkstra(g, i); } Debug.Log("跨地图数据生成耗时:" + ((Time.realtimeSinceStartup - time) * 1000) + "ms"); } void Dijkstra(MGraph g, int v) { int[] dist = new int[MAXV];//从原点v到其他的各定点当前的最短路径长度 int[] path = new int[MAXV];//path[i]表示从原点到定点i之间最短路径的前驱节点 int[] s = new int[MAXV]; //选定的顶点的集合 int mindis, i, j, u; u = 0; for (i = 0; i < g.n; i++) { dist[i] = g.edges[v][i]; //距离初始化 s[i] = 0; //s[]置空 0表示i不在s集合中 if (g.edges[v][i] < INF) //路径初始化 path[i] = v; else path[i] = -1; } s[v] = 1; //源点编号v放入s中 path[v] = 0; for (i = 0; i < g.n; i++) //循环直到所有顶点的最短路径都求出 { mindis = INF; //mindis置最小长度初值 for (j = 0; j < g.n; j++) //选取不在s中且具有最小距离的顶点u if (s[j] == 0 && dist[j] < mindis) { u = j; mindis = dist[j]; } s[u] = 1; //顶点u加入s中 for (j = 0; j < g.n; j++) //修改不在s中的顶点的距离 if (s[j] == 0) if (g.edges[u][j] < INF && dist[u] + g.edges[u][j] < dist[j]) { dist[j] = dist[u] + g.edges[u][j]; path[j] = u; } } PutBothpath(g, dist, path, s, g.n, v);//获取路径 } void PutBothpath(MGraph g, int[] dist, int[] path, int[] s, int n, int v) { int i; for (i = 0; i < n; i++) { if (s[i] == 1 && dist[i] < INF) { List<int> pathVexsList = new List<int>(4); pathVexsList.Add(g.vexs[v].mapID);//起点 Ppath(g, path, i, v, pathVexsList); pathVexsList.Add(g.vexs[i].mapID);//终点 //StringBuilder pathStr = new StringBuilder(); //for (int j = 0; j < pathVexsList.Count; j++) //{ // pathStr.Append(g.vexs[pathVexsList[j]].mapID); // if (j != pathVexsList.Count - 1)//不是结尾就加间隔符 // { // pathStr.Append("-"); // } //} string pathKey = g.vexs[v].mapID + "-" + g.vexs[i].mapID; if (!allPathDic.ContainsKey(pathKey))//不存在 { allPathDic.Add(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)); } } void Ppath(MGraph g, int[] path, int i, int v, List<int> pathVexsList) //前向递归查找路径上的顶点 { int k; k = path[i]; if (k == v) return; //找到了起点则返回 Ppath(g, path, k, v, pathVexsList); //找顶点k的前一个顶点v pathVexsList.Add(g.vexs[k].mapID); }
这样其他地方调用就只需要查询这个字典,就能查到最短路径了~
public Dictionary<string, List<int>> allPathDic = new Dictionary<string, List<int>>();
http://www.cnblogs.com/lijiajia/p/7150162.html