寻路
- 寻找图中一个点到标定点的路径；
- 用深度优先遍历整张图；
- 被遍历到的节点是从哪个节点遍历而来的信息存在
from 数组中；
- 通过在
from 数组中上溯得到某个节点到标定点的路径；
- 这个由深度优先遍历得到的路径不是最短的；
寻路代码实现
package _07._06;
import java.util.Vector;
import java.util.Stack;
public class Path {
private Graph G; // 图的引用
private int s; // 起始点
private boolean[] visited; // 记录dfs的过程中节点是否被访问
private int[] from; // 记录路径, from[i]表示查找的路径上i的上一个节点
// 图的深度优先遍历
private void dfs( int v ){
visited[v] = true;
for( int i : G.adj(v) )
if( !visited[i] ){
from[i] = v;
dfs(i);
}
}
// 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
public Path(Graph graph, int s){
// 算法初始化
G = graph;
assert s >= 0 && s < G.V();
visited = new boolean[G.V()];
from = new int[G.V()];
for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false;
from[i] = -1;
}
this.s = s;
// 寻路算法
dfs(s);
}
// 查询从s点到w点是否有路径
boolean hasPath(int w){
assert w >= 0 && w < G.V();
return visited[w];
}
// 查询从s点到w点的路径, 存放在vec中
Vector<Integer> path(int w){
assert hasPath(w) ;
Stack<Integer> s = new Stack<Integer>();
// 通过from数组逆向查找到从s到w的路径, 存放到栈中
int p = w;
while( p != -1 ){
s.push(p);
p = from[p];
}
// 从栈中依次取出元素, 获得顺序的从s到w的路径
Vector<Integer> res = new Vector<Integer>();
while( !s.empty() )
res.add( s.pop() );
return res;
}
// 打印出从s点到w点的路径
void showPath(int w){
assert hasPath(w) ;
Vector<Integer> vec = path(w);
for( int i = 0 ; i < vec.size() ; i ++ ){
System.out.print(vec.elementAt(i));
if( i == vec.size() - 1 )
System.out.println();
else
System.out.print(" -> ");
}
}
}
图文件
8 7
0 1
0 3
0 2
3 4
3 5
2 6
2 7
测试代码
package _07._06;
public class Main {
// 测试寻路算法
public static void main(String[] args) {
String filename = "testG.txt";
SparseGraph g = new SparseGraph(8, false);
ReadGraph readGraph = new ReadGraph(g, filename);
g.show();
System.out.println();
Path path = new Path(g,0);
System.out.println("Path from 0 to 6 : ");
path.showPath(6);
}
}
输出：
vertex 0: 1 3 2
vertex 1: 0
vertex 2: 0 6 7
vertex 3: 0 4 5
vertex 4: 3
vertex 5: 3
vertex 6: 2
vertex 7: 2
Path from 0 to 6 :
0 -> 2 -> 6
1.介绍
广度寻路算法是上，左，下，右一起试探，把试探过能走的点用以四叉树的方式保存起来，直到试探到终点。
广度相比于深度，可以找到从起点到终点的最佳路径废话不多说，看图
2.图
图中1表示起点，2表示终点
3.步骤&&方法：
1.如上图,这里引入一个层的概念，例如起点（1,9）就是第一层，随之试探出第二层…
2.这里可以使用C++的vector，把第一层的节点存入vector中，在进行循环，在之后吧第一层的每一个节点试探出的节点存放到vect中，直到试探出终点循环结束。4.代码
#include"stdfax.h" #define ROW 10 #define COL 10 //枚举 enum direct { p_Up, p_Left, p_Down, p_Right }; class testMap { public: bool IsGo;//是否走过 }; struct MyPoint { int x; int y; }; class treeNode { public: //数据域 MyPoint pos; //指针域 treeNode * Parent; //指向上一层的指针 vector<treeNode *> pChild; //指向下一层的指针 treeNode(int x,int y) { pos.x = x; pos.y = y; Parent = NULL; } treeNode(MyPoint pos1) { pos = pos1; Parent = NULL; } }; //试试能不能走 bool CanWalk(int map[ROW][COL], testMap testmap[ROW][COL],MyPoint pos) { //是障碍 if (map[pos.x][pos.y] ) return false; //已经走过 if (testmap[pos.x][pos.y].IsGo == true) return false; //不在地图内 if (pos.x >= ROW || pos.x < 0 || pos.y >= COL || pos.y < 0) return false; return true; } int main() { //1.准备一个地图 int map[ROW][COL] = { 1,1,1,1,1,1,1,1,1,1, 1,0,1,0,0,0,0,1,1,1, 1,0,0,0,1,1,1,1,1,1, 1,0,0,0,0,0,0,0,1,1, 1,0,1,1,1,1,1,0,1,1, 1,0,0,0,0,1,1,0,1,1, 1,0,1,0,1,1,1,0,1,1, 1,0,0,0,1,1,0,0,1,1, 1,0,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1 }; //2.准备一个测试地图 testMap testmap[ROW][COL] = { 0 }; //3.初始化起点和终点 MyPoint BegPoint = { 1,1 }; //起点 MyPoint EndPoint = { 8,2 }; //终点 testmap[BegPoint.x][BegPoint.y].IsGo = true;//标记起始点已经走过 vector<treeNode *> Current; //用于储存当前层的节点 vector<treeNode *> Next; //用于储存下一层的节点 treeNode * pRoot = new treeNode(BegPoint); //起点节点当做树的根 Current.push_back(pRoot);//吧树的节点存放到当前层中 MyPoint tempPos; //3.寻路 MyPoint currentPos; //用于表示当前点 treeNode * pChild = NULL; //专门用来存储新节点 bool IsEnd = false; //判断是不是终点 while (1) { //printf("666"); //清除下一层 Next.clear(); //表示当前层的循环 for (int i = 0; i < Current.size(); i++) { currentPos = Current[i]->pos; //当前点等于当前层中第i个节点的点 //开始走 for (int j = 0; j < 4;j++) { switch (j) { case p_Up://向上 tempPos.x = currentPos.x; tempPos.y = currentPos.y - 1; break; case p_Left://左 tempPos.x = currentPos.x-1; tempPos.y = currentPos.y; break; case p_Down://向下 tempPos.x = currentPos.x; tempPos.y = currentPos.y + 1; break; case p_Right://向右 tempPos.x = currentPos.x + 1; tempPos.y = currentPos.y; break; default: break; } //判断是不是能走 if (CanWalk(map,testmap, tempPos)) { //1.开辟新内存 pChild = new treeNode(tempPos); //2.节点入树 Current[i]->pChild.push_back(pChild); //3.保存到下一层(Next)中 Next.push_back(pChild); //4.新节点的Parent指针指向上一层节点 pChild->Parent = Current[i]; //5.标记已经走过 testmap[tempPos.x][tempPos.y].IsGo = true; //如果是终点 if (tempPos.x == EndPoint.x && tempPos.y == EndPoint.y) { IsEnd = true; break; } } if (IsEnd) break; }//end of(j) if (IsEnd) break; }//end of(i) if (IsEnd) { printf("找到终点啦"); while (NULL != pChild) { printf("路径是:"); printf("(%d,%d)\n ", pChild->pos.x, pChild->pos.y); pChild = pChild->Parent; } break; } //当前层切换到下一层 Current = Next; } printf("程序结束\n"); return 0; }5.总结
1.广度与深度的比较
1.1.没有回退
1.2.深度不一定能找到最佳路径，广度能
1.3.时间复杂度高
2.个人感觉广度寻路算法要比深度寻路算法要有趣的多。像RPG游戏里的自动寻路用的就是类似于广度的算法吧。比如A星寻路就是在广度的基础上更加智能优化了一点。明天继续更新A星寻路算法，前几天因为开学原因没时间啦。
网格场景的寻路算法DEMO
灰色格子为默认正常
蓝色格子表示为障碍物,不可进入
红色细条在格子周围,表示格子的墙,用于阻碍行走
紫色为当前鼠标选中格子
黄色为寻路的起始位置和结束位置.鼠标左键设置,CTRL+鼠标左键可以重设起始位置.
绿色格子为寻路路径
淡蓝色为寻路算法的搜索路径.
鼠标右键控制场景的视角,按X键恢复为默认视角.
鼠标滚轮调节视口远近.
ESC 程序退出
F11 全屏显示
实现了三种寻路算法,A*,广度优先,深度优先.算法是很多年前写的,这两天整理到自已的引擎中.自己几年前的代码风格很差,改起来很是费劲.这只是个测试DEMO,你会发现深度优先算法的效率最高,但其路径可能会绕很大的弯,A*算法效率最差,大概是没有做更深入的优化.下面为三种寻路算法的截图
场景:
A*算法:
广度优先算法:
深度优先算法:
下载地址:
转载于:https://my.oschina.net/abcijkxyz/blog/722653
做了一个demo，功能有8方向寻路，三点共线，修改并读取 地图，保存最佳路径，以及 训练地图。
上图是 寻路 的 测试，可以看到 设置 起点 终点，点击寻路，都能以黄色路径出来，蓝色是关键点，需要保存的。
这个图是 训练，什么是训练，就是 固定好 目标点，用地图上 所有路点（或指定点）来 寻路。
寻路的 次数很多，所以需要比较长时间，我这个演示 只是寻了几次作为演示。寻好后，保存关键点。
为什么要寻路，因为 a* 对于上千 上万的 格子时候，寻路很慢，但很多时候，我们需要数量很多的格子，
这样 地图可以做的 精细点，那么就要用到我这个操作，训练！训练后得到的数据 存在xml。
我们 在 项目里面，不需要 用寻路，只要把这些数据读取存在 内存字典里面，那么寻路就变成 字典读取数据，
这个速度 肯定是 非常快的。因为做了三点共线，所以路径数据并不大，所以不用担心 几千个 路径数据多大内存。
每个地图开始的时候，读取并加入字典，结束后 清空字典。
好了，代码很简单，主要就是思路，三点共线 前一章节 给过代码，大家自己去测试吧。
转载于:https://www.cnblogs.com/big-zhou/p/10806990.html
