精华内容
下载资源
问答
  • 寻路

    2019-06-12 16:02:00
    寻路 寻找图中一个点到标定点的路径; 用深度优先遍历整张图; 被遍历到的节点是从哪个节点遍历而来的信息存在 from 数组中; 通过在 from 数组中上溯得到某个节点到标定点的路径; 这个由深度优先遍历得到的路径...
        

    寻路

    • 寻找图中一个点到标定点的路径;
    • 深度优先遍历整张图;
    • 被遍历到的节点是从哪个节点遍历而来的信息存在 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
    
    展开全文
  • 寻路-源码

    2021-03-02 01:35:18
    寻路
  • A星寻路寻路系统

    2018-12-28 08:59:42
    采用A星寻路,让任务自动采取路径寻路到敌人身边,以最近路径
  • 基于Unity5.4.4版本,随机障碍物,动态实现寻路,UnityA星寻路完整Demo
  • C++写的Recast Detour寻路 NavMeshScene-master 用于游戏服务器寻路
  • A*寻路代码 Astart寻路demo 用C#写的Astart寻路demo,方便易懂。下一赠一
  • 定点寻路插件

    2019-01-24 13:49:08
    一款好用的寻路插件,你可以自己选择路径和方式寻路
  • 寻路算法

    2011-03-18 08:52:53
    寻路算法 寻路封装
  • 易语言地图寻路源码

    2020-07-22 03:46:04
    易语言地图寻路源码,地图寻路,到坐标,到标签,可走,寻路
  • 点击寻路:我使用Pygame进行了可点击寻路的练习
  • 寻路算法:广度寻路

    2021-02-28 19:22:06
    广度寻路算法是上,左,下,右一起试探,把试探过能走的点用以四叉树的方式保存起来,直到试探到终点。 广度相比于深度,可以找到从起点到终点的最佳路径 废话不多说,看图 2.图 图中1表示起点,2表示终点 3.步骤&...

    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星寻路算法,前几天因为开学原因没时间啦。

    展开全文
  • EasyRoads寻路

    2012-08-27 11:31:17
    EasyRoads3D寻路 源码
  • 寻路DEMO

    2019-09-16 11:32:34
    网格场景的寻路算法DEMO 灰色格子为默认正常蓝色格子表示为障碍物,不可进入红色细条在格子周围,表示格子的墙,用于阻碍行走紫色为当前鼠标选中格子黄色为寻路的起始位置和结束位置.鼠标左键设置,CTRL+鼠标左键可以...

    网格场景的寻路算法DEMO


    灰色格子为默认正常
    蓝色格子表示为障碍物,不可进入
    红色细条在格子周围,表示格子的墙,用于阻碍行走
    紫色为当前鼠标选中格子
    黄色为寻路的起始位置和结束位置.鼠标左键设置,CTRL+鼠标左键可以重设起始位置.
    绿色格子为寻路路径
    淡蓝色为寻路算法的搜索路径.
    鼠标右键控制场景的视角,按X键恢复为默认视角.
    鼠标滚轮调节视口远近.
    ESC 程序退出
    F11 全屏显示


    实现了三种寻路算法,A*,广度优先,深度优先.算法是很多年前写的,这两天整理到自已的引擎中.自己几年前的代码风格很差,改起来很是费劲.这只是个测试DEMO,你会发现深度优先算法的效率最高,但其路径可能会绕很大的弯,A*算法效率最差,大概是没有做更深入的优化.

    下面为三种寻路算法的截图

    场景:

    A*算法:

    广度优先算法:

    深度优先算法:

    下载地址:

    http://files.cnblogs.com/WhyEngine/PathFinder.zip

    转载于:https://my.oschina.net/abcijkxyz/blog/722653

    展开全文
  • Unity自动寻路

    2017-03-15 20:08:45
    Unity3d 自动寻路
  • 训练寻路

    2019-05-03 22:52:00
    做了一个demo,功能有8方向寻路,三点共线,修改并读取 地图,保存最佳路径,以及 训练地图。 上图是 寻路 的 测试,可以看到 设置 起点 终点,点击寻路,都能以黄色路径出来,蓝色是关键点,需要保存的。 这...

    做了一个demo,功能有8方向寻路,三点共线,修改并读取 地图,保存最佳路径,以及 训练地图。

    上图是  寻路 的 测试,可以看到 设置 起点 终点,点击寻路,都能以黄色路径出来,蓝色是关键点,需要保存的。

     

    这个图是 训练,什么是训练,就是 固定好 目标点,用地图上 所有路点(或指定点)来 寻路。

    寻路的 次数很多,所以需要比较长时间,我这个演示 只是寻了几次作为演示。寻好后,保存关键点。

    为什么要寻路,因为 a* 对于上千 上万的 格子时候,寻路很慢,但很多时候,我们需要数量很多的格子,

    这样 地图可以做的 精细点,那么就要用到我这个操作,训练!训练后得到的数据 存在xml。

    我们 在 项目里面,不需要 用寻路,只要把这些数据读取存在 内存字典里面,那么寻路就变成 字典读取数据,

    这个速度 肯定是 非常快的。因为做了三点共线,所以路径数据并不大,所以不用担心 几千个 路径数据多大内存。

    每个地图开始的时候,读取并加入字典,结束后 清空字典。

     

    好了,代码很简单,主要就是思路,三点共线 前一章节 给过代码,大家自己去测试吧。

    转载于:https://www.cnblogs.com/big-zhou/p/10806990.html

    展开全文
  • 寻路 pathfinding

    2020-09-29 14:42:15
    A star Best First Search Beam Search DFS BFS Djkastra Jump Point Search-JPS 基于视野的寻路
  • 连连看寻路方法连连看寻路方法连连看寻路方法连连看寻路方法连连看寻路方法连连看寻路方法
  • 寻路算法-源码

    2021-02-07 20:09:17
    寻路算法 Tietorakenteet ja algoritmitharjoitustyö 资料库 Viikkoraportit
  • 代码中实现了3种寻路算法AStar,AStar_Direct,BStar() 在VS2019环境下运行,建议以release方式运行,DEBUG没有调会崩溃
  • 明星寻路算法-源码

    2021-02-18 11:14:09
    明星寻路算法
  • 寻路算法--迷宫寻路

    2020-08-18 12:15:13
    首先寻路算法属于图论算法,要想寻路先得有图,什么是图,这个就不细讲了,很多专门讲这个的文章,简单的说图就是一些点再加上连接这些点的边就构成了图,只要把迷宫抽象成图就能应用图论算法了。    ...
  • creator网格导航寻路

    2018-10-06 12:15:37
    网格寻路算法
  • 我要讨论一些在寻路中面临的问题,为了证明这些问题现在仍然存在,有必要来制作这个轻松幽默的视频。Can not load video正如你所看到的,距离拥有一套强壮的寻路算法还有很长的路要走,甚至在百万销量和三A认证的...
  • 导航寻路有关

    2015-08-23 15:18:51
    导航寻路有关
  • lua 寻路算法

    2016-07-26 16:20:54
    lua 写的 寻路算法
  • 易语言A_寻路源码

    2020-07-21 13:20:41
    易语言A_寻路源码,A_寻路,初始化地图,分析地图,自动寻路
  • Unity寻路

    2019-04-26 17:40:07
    现在的游戏玩家很多都需要一键寻路功能,主要是游戏地图越来越大,让玩家自己找路的话会耽误非常多的时间,带来不好的体验。 因此,只要场景不是非常简单,一般都会给玩家做一个自动寻路功能,保证玩家不会出现找不...
  • unity寻路

    2018-04-20 18:53:28
    最近被寻路给搞蒙了,由于我想做汽车的寻路,而且汽车速度什么的都定义好了,而unity自带的组件nav mesh agent自带了一些速度之类的值,搞得我很不开心,虽然值可以设为0,但后来还是发现有很多问题。不过,这个自带...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,422
精华内容 2,968
关键字:

寻路