寻路_寻路算法 - CSDN
精华内容
参与话题
  • 与传统的A*寻路算法相比,本文提出的B*寻路算法具备更高的效率。在网络游戏中,寻路已经成为一种自然的AI需求,但在游戏服务器端,除非有独立的AI处理线程或独立的AI服务器模块,否则无法允许可能消耗大量时间的寻路搜索,...
  • A*寻路算法

    千次阅读 2019-04-25 16:38:47
    A*寻路算法是一种用于静态位置高效搜索算法。他是在平面中两点之间去寻找一条可以到达的最短路径算法。 二维平面之中两个点,寻找可以抵达的最短路径。首先明确三个概念,H值,目前点到终点的曼哈顿距离(曼哈顿...

            A*寻路算法是一种用于静态位置高效搜索算法。他是在平面中两点之间去寻找一条可以到达的最短路径算法。

           二维平面之中两个点,寻找可以抵达的最短路径。首先明确三个概念,H值,目前点到终点的曼哈顿距离(曼哈顿距离,就是两个位置长度差值和高度差值的和),G值,目前点到起点的消耗代价值,如果只是寻找路径,可以将该值也看成是这两点的曼哈顿距离,F值,H值和G值的和。

            今天我这里讨论的寻路算法,暂时不考虑八个方向,仅仅考虑某个点所对应的上下左右四个方向可以移动。G值处理为距离起点的曼哈顿距离。接下来可能有点绕,但是是该算法的内容核心。

            首先定义两个集合,openlist和closelist。openlist用于存放接下来可能会去的点的位置,closelist用于存放已经去过,不会再去的点的位置。然后,选定起点,将起点周边(上下左右)符合要求的点加入openlist,符合的要求需要可以达到,即没有阻挡物并且不存在于closelist中的点。在所有的openlist中找到F值最小的点,然后以该点为下一步行进点,在继续查找该行进点的上下左右符合要求的点。重复操作。结束条件,当openlist为空,没有找到终点,则不存在可以到达的路线,当行进点为终点时,则找到了最小路径。

           结合下图,屌丝找女朋友的图来看下。

     

            首先定义openlist和closelist。因为openlist每次需要查找最小F值,所以使用multimap结构,将F值作为键值。

    struct stInfo
    {
        int iF = 0;
        int iG = 0; //到起点
        int iH = 0;
        int iPosx = -1;
        int iPosy = -1;
        int iFPosx = -1;
        int iFPosy = -1;
    };

    std::multimap<int, stInfo> mapOpenList;

            closelist因为需要查找某个位置是否存在于closelist中,如果存在则不能在使用该点,所以以x坐标和y坐标用作键值:std::map<std::pair<int, int>, stInfo> mapCloseList;

            查找过程类似于一棵树的广度和深度遍历的集合,在屌丝的行进点的时候,先进行广度遍历,将所有可能的结果存放到openlist中,然后进行深度遍历,找到F值最小的一个分支,作为下一个该屌丝的行进点。同时将上一个行进点加入closelist中,以后将不再考虑该点。至于最后怎么将整条路径打印出来,上边的结构体中定义两个变量iFPosx, iFPosy,他们存放父节点的位置,比如行进点的子节点有四个,那么他们四个的父节点都是该行进点。这里可以将上边的屌丝找女朋友的图,理解成为一棵四叉树。最后结束条件:一种情况是openlist为空,那么该屌丝已经将所有的路都完了,还没有找到女朋友,即该屌丝永远找不到女朋友。另一种情况是行进点是女朋友的点,那么该屌丝找到了女朋友。

    代码:

    #include <iostream>
    #include <map>
    #include <vector>
    #include <iterator>
    #include <set>
    #include <cmath>
    #include <unordered_map>
    #define _CRT_SECURE_NO_WARNINGS
    using namespace std;
    
    
    struct stInfo
    {
    	int iF = 0;
    	int iG = 0; //到起点
    	int iH = 0;
    	int iPosx = -1;
    	int iPosy = -1;
    	int iFPosx = -1;
    	int iFPosy = -1;
    };
    /*
    *  brief 获取两个点的曼哈顿距离
    */
    int getDistanceTwoPoint(int iPosxFrom, int iPosyFrom, int iPosxTo, int iPosyTo)
    {
    	return abs(iPosxFrom - iPosxTo) + abs(iPosyFrom - iPosyTo);
    }
    /*
    *  brief 构建stInfo
    */
    void buildStInfo(stInfo &stTmp, int iPosx, int iPosy, std::pair<int, int> posBegin, std::pair<int, int> posEnd, int iFPosx = -1, int iFPosy = -1)
    {
    	stTmp.iPosx = iPosx;
    	stTmp.iPosy = iPosy;
    	stTmp.iFPosx = iFPosx;
    	stTmp.iFPosy = iFPosy;
    	stTmp.iG = getDistanceTwoPoint(iPosx, iPosy, posBegin.first, posBegin.second);
    	stTmp.iH = getDistanceTwoPoint(iPosx, iPosy, posEnd.first, posEnd.second);
    	stTmp.iF = stTmp.iG + stTmp.iH;
    	//cout << "iposx:" << iPosx << " iposy:" << iPosy << " iG:" << stTmp.iG << " iH:" << stTmp.iH << " iF:" << stTmp.iF << endl;
    }
    /*
    *  brief 检查位置合法
    */
    bool isLegalPos(int **pstAr, int iPosx, int iPosy)
    {
    	//cout << "isLegalPos  " << iPosx << "  " << iPosy << endl;
    	return (iPosx >= 0 && iPosx < 5 && iPosy >= 0 && iPosy < 5) && (pstAr[iPosx][iPosy] != 1);
    }
    /*
    *  brief 检查某个点不在openlist
    */
    bool notInOpenList(int iPosx, int iPosy, int iF, std::multimap<int, stInfo> &mapOpenList)
    {
    	int iCount = mapOpenList.count(iF);
    	auto it = mapOpenList.find(iF);
    	while (it != mapOpenList.end() && iCount)
    	{
    		if (it->second.iPosx == iPosx && it->second.iPosy == iPosy)
    			return false;
    		++it;
    		--iCount;
    	}
    	return true;
    }
    /*
    *  brief 某个位置周围四个符合要求的点插入openlist
    */
    bool insertPointToOpenList(int **pstAr, const std::pair<int, int> &posNow, std::multimap<int, stInfo> &mapOpenList, std::map<std::pair<int, int>, stInfo> &mapCloseList,
    	const std::pair<int, int> &posBegin, const std::pair<int, int> &posEnd)
    {
    	if (isLegalPos(pstAr, posNow.first - 1, posNow.second) && mapCloseList.find(std::make_pair(posNow.first - 1, posNow.second)) == mapCloseList.end())
    	{
    		stInfo stTmp;
    		buildStInfo(stTmp, posNow.first-1, posNow.second, posBegin, posEnd, posNow.first, posNow.second);
    		if (notInOpenList(posNow.first - 1, posNow.second, stTmp.iF, mapOpenList))
    		{
    			mapOpenList.insert(std::make_pair(stTmp.iF, stTmp));
    			if (stTmp.iH == 0)
    				return true;
    		}
    	}
    	if (isLegalPos(pstAr, posNow.first, posNow.second-1) && mapCloseList.find(std::make_pair(posNow.first, posNow.second-1)) == mapCloseList.end())
    	{
    		stInfo stTmp;
    		buildStInfo(stTmp, posNow.first, posNow.second-1, posBegin, posEnd, posNow.first, posNow.second);
    		if (notInOpenList(posNow.first, posNow.second-1, stTmp.iF, mapOpenList))
    		{
    			mapOpenList.insert(std::make_pair(stTmp.iF, stTmp));
    			if (stTmp.iH == 0)
    				return true;
    		}
    	}
    	if (isLegalPos(pstAr, posNow.first + 1, posNow.second) && mapCloseList.find(std::make_pair(posNow.first + 1, posNow.second)) == mapCloseList.end())
    	{
    		stInfo stTmp;
    		buildStInfo(stTmp, posNow.first+1, posNow.second, posBegin, posEnd, posNow.first, posNow.second);
    		if (notInOpenList(posNow.first+1, posNow.second, stTmp.iF, mapOpenList))
    		{
    			mapOpenList.insert(std::make_pair(stTmp.iF, stTmp));
    			if (stTmp.iH == 0)
    				return true;
    		}
    	}
    	if (isLegalPos(pstAr, posNow.first, posNow.second+1) && mapCloseList.find(std::make_pair(posNow.first, posNow.second+1)) == mapCloseList.end())
    	{
    		stInfo stTmp;
    		buildStInfo(stTmp, posNow.first, posNow.second+1, posBegin, posEnd, posNow.first, posNow.second);
    		if (notInOpenList(posNow.first, posNow.second+1, stTmp.iF, mapOpenList))
    		{
    			mapOpenList.insert(std::make_pair(stTmp.iF, stTmp));
    			if (stTmp.iH == 0)
    				return true;
    		}
    	}
    	return false;
    }
    /*
    *  brief A*寻路
    */
    void findRoad(int **pstAr, std::pair<int,int> posBegin, std::pair<int,int> posEnd)
    {
    	std::multimap<int, stInfo> mapOpenList;
    	std::map<std::pair<int, int>, stInfo> mapCloseList;
    	std::pair<int, int> posNow = posBegin;
    
    	//起点加入Openlist
    	stInfo stTmp;
    	buildStInfo(stTmp, posNow.first, posNow.second, posBegin, posEnd);
    	mapOpenList.insert(std::make_pair(stTmp.iF, stTmp));
    
    	while (1)
    	{
    		auto itopen = mapOpenList.begin();
    		if (itopen == mapOpenList.end())   //openlist为空,无路径      如果不为空,取第一个就是iF最小值
    		{
    			cout << "无路径" << endl;
    			return;
    		}
    
    		posNow = std::make_pair(itopen->second.iPosx, itopen->second.iPosy);
    		//cout << "====" << posNow.first << "  " << posNow.second << endl;
    
    		stInfo stTmp = itopen->second;
    		mapOpenList.erase(itopen);
    		mapCloseList.insert(std::make_pair(std::make_pair(stTmp.iPosx, stTmp.iPosy), stTmp));
    
    		if (stTmp.iH == 0)
    		{
    			cout << "找到了" << endl;
    			break;
    		}
    
    		insertPointToOpenList(pstAr, posNow, mapOpenList, mapCloseList, posBegin, posEnd);
    		//if (insertPointToOpenList(pstAr, posNow, mapOpenList, mapCloseList, posBegin, posEnd)) //周围坐标加进去
    		{
    		//	mapCloseList.insert(std::make_pair(std::make_pair(posEnd.first, posEnd.second),stInfo()));
    		//	cout << "找到了" << endl;
    		//	break;
    		}
    	}
    
    	posNow = std::make_pair(posEnd.first, posEnd.second);
    	while (1)
    	{
    		auto it = mapCloseList.find(std::make_pair(posNow.first, posNow.second));
    		if (it == mapCloseList.end())
    			break;
    		if (it->first.first == -1 && it->first.second == -1)
    			break;
    		cout << it->first.first << " " << it->first.second << " -> ";
    		posNow = std::make_pair(it->second.iFPosx, it->second.iFPosy);
    	}
    }
    int main()
    {
    	int **pstAr = new int *[5];
    	for (int i = 0; i < 5; ++i)
    		pstAr[i] = new int[5];
    	
    	for (int i = 0; i < 5; ++i)
    		for (int j = 0; j < 5; ++j)
    			pstAr[i][j] = 0;
    
    	//pstAr[0][2] = 1;
    	pstAr[1][2] = 1;
    	pstAr[2][2] = 1;
    	pstAr[3][2] = 1;
    	//pstAr[4][2] = 1;
    	pstAr[1][1] = 1;
    	pstAr[3][0] = 1;
    	pstAr[4][0] = 1;
    	findRoad(pstAr, std::pair<int,int>(1,0), std::pair<int,int>(4,4));
    	//findRoad(pstAr, std::pair<int, int>(1, 0), std::pair<int, int>(0, 3));
    	return 0;
    }

    以上这份代码里的屌丝,最终找到了女朋友。

     

            昨天是A*寻路算法发明人Nilsson去世的日子,谨以此文致敬。

    展开全文
  • Unity3D 高效A*寻路

    千次阅读 2019-04-12 09:56:30
    随着手机游戏不断发展, 我们需要在手机做更多的表现, 但手机的性能是有限的。每个重要模块都应尽可能地有很好的性能来提升整个...这已作为简单的工具类使用即可, 插件中包括阻挡数据的生成工具, 寻路算法的使用Demo...

    Unity Asset Store URL: http://u3d.as/1ud5

    随着手机游戏不断发展, 我们需要在手机做更多的表现, 但手机的性能是有限的。每个重要模块都应尽可能地有很好的性能来提升整个表现效果。寻路算法中, 普通的a*在比较大的地图时, 消耗性能也是具大, 因此, 我把a*作了很好的改良。这已作为简单的工具类使用即可, 插件中包括阻挡数据的生成工具, 寻路算法的使用Demo。

    本文介绍了高性能”寻路”的基本用法及其应用。

     

    Quick Start

    首先, 打开展示场景Demo/DemoSearch1并运行。

    你可以看到如下图:

    多个对象在随机地自由寻路。也可以自由点击场景, 让主角对象(红点)作寻路运行。

    主角寻路时, 会在输出面板, 输出寻路的用时。

    从图中可见, 20多个寻路对象, 在不断执行寻路逻辑的情况下, 帧率还是很高的。

     

    DemoSearch1中Inspector面板的说明参数说明:

    Scene Prefab是要加载的寻路场景预制体。

    Block Data Json是工具生成的寻路数据。

    Cell Prefab 是阻挡格用到的预制体。

    Move Count 是除主角外的移动对象数量。

    Move Speed 是全局的移动速度。

    Hero Prefab 是主角用到的预制体。

    Player Prefab 是其他移动对象的预制体。

    Hero Tail Prefab 是主角移动时, 产生拖尾的预制体。

    Player Tail Prefab 是其他移动对象移动时, 产生拖尾的预制体。

    S Camera 是主摄像机, 主要用于点击场景的处理。

     

    阻挡数据生成工具说明。

    打开Demo/Tools场景

    主要关注在Hierarchy中PlaneScene的。

    PlaneScene下有LocationGO和Plane

    LocationGO主要用于标注绘制阻挡数据的左下角起始点。

    Plane是具体展现的场景。

    其中在PlaneScene的组件有两个,BoxColider和ABlockTools。

    BoxColider的Size必须是需要绘制阻挡数据场景的大小。

    ABlockTools的一些配置属性:

    Scale Speed: 绘制阻挡数据时, 滚动鼠标中轴对场景进行缩放的速度。

    Move Speed: 按着键盘Ctrl+鼠标左键, 移动鼠标时, 场景平移的速度。

    Map W和Map H: 是地图的宽高, 必须要跟BoxColider的Size保持一致。

    Map Org V2: 就是用于确定阻挡数据的左下角起始点,参考LocationGO的坐标。

    Height Of Overlook: 是摄像机开始时, 离场景的高度距离。

    Cell W: 是每阻挡格的边长。

    Cell Prefab: 是阻挡格的预制体。

    Frame Line Prefab: 是边框线条的预制体。

     

    Tools场景运行后, 即可进行阻挡数据的绘制,如果ABlockTools组件挂的GameObject中已在AJ_Pathfinding/Resources/AJ_BlockData中有生成阻挡数据,即会读取其数据,在这基础上进行绘制。

    有右键点击PlaneScene中ABlockTools组件, 弹出工具框, 选择”Start drawing blockades” 开始进行阻挡绘制; 此时如果已绘制过阻挡路径并保存的话, 会加载已有的阻挡数据并呈现出来。

    在绘制中, 在场景上按着鼠标左键并移动生成阻挡数据; 点击鼠标右键删除阻挡数据;鼠标中轴对场景进行缩放; Ctrl+鼠标左键, 移动鼠标对场景进行平移。

    绘制完成后, 右键点击PlaneScene中ABlockTools组件, 选择”Save the blockades data”进行保存。如果不满意,可以选择”Clear the blockades data”来清空当前阻挡数据。

     

    DemoSearch2中的说明:

    打开Demo/DemoSearch2场景并运行。跟DemoSearch1类似, 此Demo中加入摄像机跟随, 更好的体现移动中的效果。

    另外送上两个人物模型, 包括站立和行走的动作。

     

    API说明:

    主要类是:JOMapGrid2DDataAJFindRoad

    JOMapGrid2DData是阻挡数据管理类

    其中提供网格坐标和世界坐标的转换

    AJFindRoad是寻路算法类

    其中提供一个寻路api

    Eg.

    创建两个主体对象

    JOMapGrid2DData mapGridData = new JOMapGrid2DData();

    AJFindRoad ajSearch = new AJFindRoad();

    设置网格的基本信息

    mapGridData.SetMapData(float mapW,float mapH,float mapOffsetX,float mapOffsetY,int cellW);

    mapW和mapH是地图的宽高。

    mapOffsetX和mapOffsetY是开始设置网格的左下角坐标。

    cellW是每格的边长。

    通过网格下标设置阻挡

    mapGridData.SetBlockIdx(int blockIdx, bool isBlock);

    通过网格的xy坐标设置阻挡

    mapGridData.SetBlock(int cellx, int celly, bool isBlock)

     

    调用寻路算法,返回路径。

    List<JOIntV2>

    ajSearch.Search(int beginX, int beginY, int endX, int endY, JOMapGrid2DData mapData);

    其中beginX, beginY和endX, endY分别是寻路的开始和结束的网络坐标。

    mapData就是以上包括阻挡信息的数据。

    函数会返回List<JOIntV2>, 如果是null即此路不通, 找到即返回网络路径。

     

    也可以参考

    Demo/Scrips/DemoSceneBase中对JOMapGrid2D的设置处理。

    Demo/Scrips/MoveGO中对JOMapGrid2D和AJFindRoad 的调用。

     

    Unity Asset Store URL:

    https://assetstore.unity.com/packages/slug/142391

    展开全文
  • 动态寻路

    千次阅读 2015-07-10 13:22:30
    动态寻路 目标  在一个所有物体都在动态移动的场景中,调用物理引擎现有的能力让一个实体从任意一点走到另一点的同时能够逼真地躲开所有可能与此物相撞的物体。 在这个话题上可说的很多。当你看下面的视频的时候你...

    动态寻路

    目标

           在一个所有物体都在动态移动的场景中,调用物理引擎现有的功能让一个实体从任意一点走到另一点的同时能够逼真地躲开所有可能与此物相撞的物体。

    在这个话题上可说的很多。当你看下面的视频的时候你也会意识到这是一个挺难的任务,因为此实体是在几十个一直移动的物体中尝试寻路。


    视频连接

     

    为什么要用物理引擎?

           如果分析一个有AI(人工智能)元素的游戏场景,你会发现你需要:

    • 一个分隔空间的方法,能够检查什么在哪儿,从而减少CPU使用
    • 一个让实体在你的控制下移动、又看上去很合理的方法
    • 一个在碰撞发生时通知并让相关物体采取行动的方法

             Box2D物理引擎有上述所有特点。它的模型也相对容易使用,执行速度也挺快。写一写格子空间隔离(cell space partition)和基础物理系统(basic physics system)也许会有趣,但用那个时间可以做很多更好的事情。

     

    什么是“逼真地躲避”?

        在《星球大战之帝国反击战》中,当汉·索罗驾驶着千年隼号穿过小行星带时,他的经典台词是“永远别跟我说几率!”。当然我们也都知道,几率并不高。所以“逼真地躲避”算是有点夸张的说法,因为如果那艘船真的做得到的话,那就超出你的所知范围了。

          我们在找的效果是让物体穿越障碍物时“没有明显地作弊”,然后让它遵循物理规律(质量、动量等)移动。

    • 碰撞不应该被类似“岩石直接穿过船体”、“船瞬间移动”等的“魔法”避免
    • 岩石的速度不能被减小到基本不动
    • 岩石不能永远在预设轨道上前行(尽管这是一个有趣的选择)……如果被撞了,它们就该表现得和现实中的岩石一样

          这个实体既要能够在附近的岩石中找出一条路径,又有一条能抵达目的地的大致路径,如果它最终能抵达的话。

          如果这个实体正无所事事地坐着,而一块岩石猛冲过来,若实体有时间躲开的话,它就应能够躲开并逃到安全的地方。

          有时碰撞会发生。这时候,AI不应该(也多半不可能)完全不操纵岩石躲开,或者说“作弊”。注意:“作弊”并不一定是一件坏事,我们的最终目标是让效果好看,只要玩家开心了,他们通常不在乎这个效果是怎么来的。

     

    整体情况 


     

     

    主要场景

          图中左侧的类和Cocos2d-x框架合起来就是这个MVC框架中的视图(View)部分。主要场景是控制器(Control)部分,把用户输入的东西发送到图片右侧模型(Model)部分。

          这种视口方法在别的博客(英文版)中有讨论。在之前的版本中,视口(Viewport)在主窗口的内部操作(上下滑动、挤压、缩放)。在这个版本中,一个“摄像头”被创造出来隐藏这个过程的细节,也让它更容易应用于其他程序。

          在此文中我们不会过细讨论视图和控制器的问题。

     

    总体方法

         Box2D引擎既可以让物体变成“固体”并有普通碰撞的反应,也可以让物体以其他方式路过彼此(此链接此链接上有关于这个的好教程)。Box2D上有一个无形的特殊类,叫“传感器”。如果你将一个固定装置标记为传感器,那么物体会穿过它,而你同时会得到物体与它“相撞”的通知。

          根据以上情况,这是我们的总体方法:

    1. 排好一些被标记为传感器的闭合凸多边形。我们此回用的是坐标方格,但圆、六边形和长方形也是可以的。它们也不一定要成坐标,可以是任何你需要的格式。但它们要能基本覆盖你想要用到的地区。
    2. 创造一个特殊的接触处理器,使得它在每个传感器与物体接触时开始计数、在接触结束时倒数。如果这些数字排成一行(而且看起来也像),那么,当数字是0时传感器的空间就是“空的”,其他情况下则“不是空的”。

          如果你看了那个视频,你会发现在小行星带的下方有很多方格随着小行星的移动出现或消失。这就是图像传感器接触层,它会显示“不空”的传感器并隐藏空的那些。当然,实体上会有标志告诉处理器要“忽略我”。这样下来,实体,比如那艘船,就可以到处飞而不会让传感器工作了(这在图像搜索中很重要)。

          所以,当小行星运动时我们就有了一个坐标格的传感器,那些可穿过的区域就被动态、即时地更新着。

          传感器被创造出来时即被导入一个图像中,同被导入的还有关于哪些传感器相互毗邻的信息,和它们的欧氏距离。

          这些东西加起来就给了你一幅你要走过的区域的图。这幅图通过物理引擎自动更新,它会告诉你图中的哪些部分可以通过。

          最后的部分就是要开发一系列的能够利用这幅图并知道在节点“不是空的”之时跳过它们的搜索算法。这个只需在节点上(也可以是边缘上,尽管考虑到是哪个方向的边缘可能会让搜索变复杂)做一个简单的“限制”标志。

     

    其他部分的功能

         MVC的模型部分一半是Box2D引擎,在那之上是以下提到的其他主要成分,每一个都有其不同的功能。这些都是在执行模型中有着明确责任的单例模式(singleton)。其中一些只跟某些其他同类相互配合,另一些会跟所有同类相互配合。

     

    通知器

          通知器已被运用在很多其他设计中(参见其他博客文章,英文版)。这个单例模式是此系统中一个有效的整体性一对多的消息通讯装置。只要你把抽象的基础类发展出一个应用的界面,你所登记的事件就能被任意物体收到。

     

    实体管理器

          “实体”就是指游戏/系统中被实例化或进一步开发的部分。这个类是一个给实体的(有销毁责任的)组合容器以及实体ID索引的字典。在更复杂(更逼真)的系统中,实体的指针并不为其他实体所有。它们都有自己对应的ID或参考码,在你需要与它交流时只需给ID发送信息,这样就避免了指针引起的崩溃。


    实体调度器

           在这个代码库刚被开发时,小行星需要每帧都更新一次它们的AI。这就导致了很多浪费的CPU周期,因为每秒更新一次就足够了。“实体调度器”是一个安排小行星更新的时间的类。每帧,它都会对被安排那帧更新的实体执行Update(…)方法。通过把小行星的更新分散到多帧上,系统的总负载就减少了。


    图像传感器管理器

          图像传感器管理器会将传感器的信息加载到一副传感器图中,随后Box2D框架会(通过系统接触监听器)更新传感器附近物体的情况。此单例模式原是为了更大的目的而造,但最终在瞄准的范围上大大减小,现在多用于排除装置内传感器的故障。在未来的设计中,这个东西多半会被抹去(或改变成其他东西)。

          在这里,我们讨论这个管理器的信息是为了强调一个非常重要的设计或开发考量:

          在脑海中看来很棒的东西并不一定在设计上也很好。你需要永远记得反思你的设计并问自己“这真的能给我想要的东西吗?”、“是不是有另一种方法(也许在未来)能让它变得更好?”。

     

    系统接触监听器

          最后一个重要的部件就是这个“系统接触监听器”。这是Box2D使用的回调函数(callback),用来标记哪些物体被撞了。根据格子的大小,有很多(对于小型传感器来说甚至更多)撞击会在每次物理更新间发生。这就是你的CPU用得最多的地方,也是在未来设计中最需要监督和检查的地方。

     

     

    代码

          这篇文章中讨论到的源代码可以再GitHub此处找到。

     

    总结

          这篇文章呈现了一项技术(一个视频和一个可以下载到代码的网址):使用一个物理引擎和寻路系统来动态地避开一个变化环境中的障碍物。初期的测试显示它未来的应用前景非常光明。唯一的美中不足是它的CPU负载(CPU load)比我预想的要高,不过也不是无法容忍的高。

     

    原文:Dynamic Pathfinding

    展开全文
  • unity中寻路

    2018-12-13 16:04:52
    常见寻路方法: 路点寻路:在地图中手动设置多个点然后在点间移动 单元格寻路 网格寻路:自动寻路 实现网格寻路步骤: 将场景中不动的物体勾选static, 到window中调出 视窗,点击Bake,形成寻路(蓝色)网格...

    常见寻路方法:

    1. 路点寻路:在地图中手动设置多个点然后在点间移动

    2. 单元格寻路

    3. 网格寻路:自动寻路

    实现网格寻路步骤:

    1. 将场景中不动的物体勾选static,
      到window中调出 视窗,在这里插入图片描述点击Bake,形成寻路(蓝色)网格。
    2. 需要自动寻路的物体,添加自动寻路组件。
      在这里插入图片描述
    3. 添加脚本
         private void Start()
        {
            agent = this.GetComponent<NavMeshAgent>();
        }
        private void Update()
        {
            agent.SetDestination(target.position);
       }
    
    

    NavMeshAgent属性

    Radius      		  寻路的碰撞半径
    Height      		  寻路的碰撞高度
    BaseOffset 		寻路碰撞的位置
    Speed 			寻路物体的速度
    Acceleration 		转弯时的加速度
    AngularSpeed 	转弯时物体的角速度
    StoppingDistance 	停止的距离
    AvoidancePriority 	躲避系数
    

    寻路路径烘焙属性

    Radius 		是指寻路区域与障碍物之间半径
    Height 		是指寻路区域与地面之间的高度
    MaxSlope 	是指寻路区域烘焙的最大坡度
    StepHeight 	是指台阶高度
    

    寻路系统区域遮罩:

    1. 分别添加自定义区域,如Red、Blue区域.
      在这里插入图片描述
    2. 选择场景中的静态路面 在这里插入图片描述 指定到相应寻路区域 在这里插入图片描述
    3. Bake寻路路面。
    4. 找到需要寻路的物体,设置可在寻路路面行走的区域。
      在这里插入图片描述在这里插入图片描述

    (PS:Cost:寻路区域消耗度,数值越大,从此寻路区域消耗越大。
    寻路物体在区域消耗数值一样的情况下,会选择最优(最近)路面寻路,但如果寻路区域的消耗数值不同,会根据消耗的数值,越小越最优进行寻路。)
    通过代码实现勾选不同的寻路区域:
    GetComponent().areaMask =9;
    寻路区域每一区域都是2的幂

    9则为Walkable区域(1)+red区域(8) = 9
    Everything所有区域-1
    Nothing任何区域都不能寻路 0
    在这里插入图片描述
    计算寻路曲线距离

    using UnityEngine;
    using System.Collections;
    
    /// <summary>
    /// 计算寻路曲线距离
    /// </summary>
    public class NavPath : MonoBehaviour
    {
        private NavMeshAgent agent;
        private NavMeshPath path;
        public Transform target;
        private void Start()
        {
            agent = this.GetComponent<NavMeshAgent>();
            path = new NavMeshPath();
        }
        private void Update()
        {
            agent.SetDestination(target.position);
            print("曲线距离 : " + NavPathFunc(target.position));
        }
        private float NavPathFunc(Vector3 pathTarget)
        {
            agent.CalculatePath(target.position, path);
            if (path.corners.Length < 2)
                return 0;
            Vector3 previousCorner = path.corners[0];
            float lengthSoFar = 0.0F;
            int i = 1;
            while (i < path.corners.Length)
            {
                Vector3 currentCorner = path.corners[i];
                lengthSoFar += Vector3.Distance(previousCorner, currentCorner);
                previousCorner = currentCorner;
                i++;
            }
            return lengthSoFar;
        }
    
     
    }
    
    
    展开全文
  • A*寻路 -- 更加真实 的路径(一)

    千次阅读 2018-03-22 16:26:49
    转自:http://bbs.9ria.com/thread-86464-2-1.html 对于A*寻路算法,可能是游戏开发者讨论最多的话题之一,很多游戏都会用到它来实现游戏角色的寻路。那么我这篇帖子的价值何在呢?先来看看传统A*算法存在的问题:1...
  • A*寻路算法浅析

    万次阅读 2015-06-02 15:43:27
    A*算法:A*(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法。估价值与实际值越接近,估价函数取得就越好。(像这种专业的概念的解释,我们还是交给度娘来做吧)
  • 深入理解游戏中寻路算法

    万次阅读 2017-07-28 20:49:08
    摘要: 看似寻常的路径行走,在程序看来就需要一定的寻路算法来解决,如何在最短时间内找到一条路径最短的路线,这是我们首要考虑的问题。 如果你玩过MMOARPG游戏,比如魔兽,你会发现人物行走会很有趣,为了...
  • 第四章 Dijkstra和A*寻路算法

    千次阅读 2018-08-18 10:17:17
    寻路 寻路希望ai中的角色能够计算一条从当前位置到目标位置合适的路径,并且这条路径能够尽可能的合理和短。 在我们的ai模型中,寻路在决策和移动之间。游戏中大多数寻路的实现是基于a星算法,但是它不能直接使用...
  • Unity自动寻路功能的实现(一)

    千次阅读 2018-08-11 23:25:07
    Unity自动寻路功能的实现 在Unity中,要实现自动寻路功能,其实是有很多办法的,今天我就介绍三种比较简单的办法,入手即会。 方法一:使用自带的Navigation寻路组件 操作如下:打开Unity,新建项目,新建一个...
  • ue4中寻路设置navmesh

    万次阅读 2015-12-12 04:02:03
    修改Level 中寻路区域 修改Level 中寻路区域,增加跳跃线 有些区域不能连接起来,比如楼上到楼下,可以增加寻路连接点     输入navlink,拖动到场景中,拖动两个连接点   实时重建寻路范围 ...
  • 自动寻路步骤: ① 把场景中不动的物体勾选static ② 烘焙寻路网格 ③ 添加NavMeshAgent组件 ④ 给需要寻路的物体添加脚本 实现: ① 搭一个简易场景 放上enemy和player: 把场景设为静态 ...
  • 外挂学习之路(7)--- 寻路call

    千次阅读 2017-02-17 21:00:28
    寻路call的查找方式有很多,先来看看常见的一种,根据寻路状态回溯找到call 一般游戏会把人物分成若干种状态,比如站着不动、寻路中、战斗中等等,我们就根据状态的切换用CE工具找到这个表示的地址。 1. 用CE搜索...
  • Unity3d NavMeshAgent自动寻路组件

    万次阅读 2017-10-23 19:24:55
    我们常见的有三种寻路方式 1.路点寻路 2.单元格寻路 3.网格寻路 简单介绍一下 1.路点寻路 如下图,物体从 point位置出发依次经过(point1 、point2、point3、point4、point5)进行移动 代码如下 using System....
  • Unity中自动寻路的几种方法(一)

    万次阅读 2014-11-19 19:03:58
    在游戏中,我们经常会用到角色自动寻路这个功能,
  • Unity中目前提供的基于Navmesh的网格寻路,如果仅仅是单机游戏,其实功能还是能满足的,当然,如果你做的是大规模兵海流的 rts游戏,Unity的网格寻路还是会碰到多人寻路相互挤压的问题。  由于我们目前的工作...
  • 寻路的方法如下步骤1、将场景中的地面以及障碍物勾选Static,调出Navigator视窗,点击Bake,形成寻路网格。2、给需要自动寻路的物体添加寻路组件——Nav Mesh Agent3、添加脚本给自动寻路的物体:public Transform ...
  • 一种高效的寻路算法 - B*寻路算法

    万次阅读 2017-04-13 10:13:12
    在此把这个算法称作B* 寻路算法(Branch Star 分支寻路算法,且与A*对应),本算法适用于游戏中怪物的自动寻路,其效率远远超过A*算法,经过测试,效率是普通A*算法的几十上百倍。  通过引入该算法,一定程度上...
  • 【Unity3D】自动寻路

    千次阅读 2017-05-17 17:24:13
    因此自《【iTween】指定路径位移》(点击打开链接)之后,自动寻路的需求应运而生。不过,Unity3D自带的功能,就能完成这个看起来高大上的功能。下面举一个例子说明这个问题。 如下图,摆了4个cube当作墙,然后摆一...
  • 一种接近最优的导航网格生成算法以及基于导航网格的寻路算法   关键词:导航网格、A*寻路、3D环境中的寻路   提出背景: 长距离寻路会出现掉帧现象,为了提高寻路速度,并为3D环境...
1 2 3 4 5 ... 20
收藏数 13,105
精华内容 5,242
关键字:

寻路