• 1. 地图寻路网页游戏地图
  • 2. 简介各种AI(Artificial Intelligence,简称AI)技术被引入到游戏中,提高游戏的可玩性,如遗传算法、人工神经网络计算、地形分析技术、团队寻径算法、A*算法等,这些技术出色地解决了游戏中一些基本问题。 简单的随机寻路算法(适合模拟游戏中没有什么头脑的生物,漫无目的地走来走去)、跟踪算法(警戒区域中控制NPC对象移向被跟踪的对象)。改进优化后的A*算法可以很好地胜任游戏中的路径搜索,被游戏界认为是最好、最成熟的寻路算法之一,由于A*算法是按照寻找最低耗费的路径来设计,A*寻路会避开障碍物找到最短路径。
  • 3. 目录Waypoint 路点寻路 NavMesh 导航网格寻路 Waypoint 与 NavMesh 比较 A*寻路算法 A*注意事项 A*扩展及动态障碍物处理 区域寻路及路径缓存 相关话题
  • 4. Waypoint 路点寻路http://blog.csdn.net/menuconfig/article/details/7987687
  • 5. Waypoint 路点寻路一些复杂的游戏地图需要的WayPoint数量过于庞大 有时会使角色走“Z”型路径 不能进行动态修正,如果地图中有动态障碍,处理起来会很困难 如要实现即时战略游戏中,一辆在路上行走的坦克会挡住你军队的去路,这个移动的坦克就是一个动态障碍。 不能根据角色的特性(不同宽度、高度等)改变路径 如一个狭窄的通道,普通的人能够通过,而一辆马车的宽度超过通道宽度,应该不能通过。 不能保存地形的附加信息,如地表高度、地面特征(水面、沙地等) 比如一个游戏中的角色在走到沙地上时会降低移动速度,或走在一个斜坡上时人物会发生倾斜等。几个WayPoint的不足之处:
  • 6. NavMesh导航网格寻路nav寻路一般包含两部分,首先是使用工具根据地图信息生成寻路用的nav mesh,接下来就是在游戏中根据生成的nav mesh来自动寻路。
  • 7. NavMesh导航网格寻路生成路径点 nav寻路最常用的就是光照射线法 怎么计算是否在多边形范围内 另一种方法就是拐角点法
  • 8. NavMesh导航网格寻路多边形的临边
  • 9. NavMesh导航网格寻路首先找到起始点所在的多边形和穿出边的两个端点,由起点连接两个端点,形成两个线段lineLeft 和lineRight。绿色圈表示左点,红色表示右点(左点、右点是根据多边形顶点保存顺序而来)
  • 10. NavMesh导航网格寻路继续找到下一个穿出边的两个端点,判断新的左点是否在lineLeft 和lineRigh之间,如果在,则更新lineLeft,同样处理新穿出边的右点
  • 11. NavMesh导航网格寻路继续找到下一个穿出边的两个端点
  • 12. NavMesh导航网格寻路矢量加减法矢量叉积折线段的拐向判断判断两线段是否相交Voronoi图及对偶图涉及到的 计算几何 知识设二维矢量P = ( x1, y1 ),Q = ( x2 , y2 ),则: P + Q = ( x1 + x2 , y1 + y2 ), P - Q = ( x1 - x2 , y1 - y2 )。设矢量P = ( x1, y1 ),Q = ( x2, y2 ),则矢量叉积定义为由(0,0)、p1、p2 所组成的平行四边形的带符号的面积点在凸多边形中的判断假设多边形是凸的,而且顶点p0,p1,...,pn按顺时针方向排列, 则点在多边形任意一边 pi-1, pi 的右面
  • 13. Waypoint 与 NavMesh 比较红线是wayPoint寻路,蓝线是nav,nav寻路路径更自然。无法计算动态阻挡,navmesh信息需要提前计算存入文件,遍历生成mesh比寻路更耗时。 路点网格图形可用多变形、菱形、正方形,网格图形越小 那么A Star的节点就会大大增加,处理时间也会相应增大
  • 14. A*寻路算法   A*算法是Dijkstra算法和贪婪算法的综合,Dijkstra算法的缺点在于从起点全方位360地向外做广度优先搜索,导致遍历节点太多,速度较慢,优点是能够保证找到最优路径。贪婪算法总是选择看起来最优的路线前进,优点是速度很快,缺点是有可能掉入陷阱,而走冤枉路。而A*算法采用启发式的方式,综合了二者的优点,且依然能够保证找到最优路径。
  • 15. A*寻路算法G是从开始网格到达目标网格的移动量 H值是从当前网格到终点网格的移动量估算值 F是G+H得到的值。 F(方块的和值):图中格子的左上角数 G(从A点到方块的移动量):左下角 H(从方块到B点的估算移动量): 右下角 红色方块表示closed列表,绿色方块表示open列表。
  • 16. A*寻路算法移动量估算值的计算方法(H值)曼哈顿估价法 Manhattan distance 几何估价法 Euclidean distance, squared对角线估价法 Diagonal distance
  • 17. A*寻路算法1曼哈顿估价法:这种方法计算方法简单,但遍历节点最多。直来直去,像曼哈顿城市的大街。从起点到终点计算横走和竖走的路径的总和 2几何估价法:使用勾股定理计算此节点到终点的直线距离。两直角边的平方和等于斜边的平方 3对角线估价法:遍历节点最少,先走对角线,到终点那一行或列后,再走直线123
  • 18. A*注意事项排序链表哈希表索引数组跳转列表数据结构 排序数组二叉堆可中断算法团队运动山地,湿地等影响因子平滑路径孤岛寻路
  • 19. A*扩展及动态障碍物处理双向搜索 跳点搜索A* 变体位置方向存储 计算出的路点 有限路径长度 预先 计算重新计算路径 路径拼接 预测运动障碍动态 障碍物
  • 20. 区域寻路及路径缓存区域寻路 路径缓存
  • 21. 地图交涉运动成本人工智能技术应用 最短路径的用户体验相关话题海拔 ,上坡或下坡 森林,山岭,丘陵 道路 ,障碍 敌人和友军单位 勘探 间谍 道路建设 地形分析 城市建设 智能运动 ,多线程 ,多个单位 神经网络 遗传算法 强化学习 管理复杂性 ,导航网格 混合运动,分级 环绕式地图 ,路线图
  • 22. 你对上面所讲的有什么疑问? 你有更好的建议吗? 你是不是也想说说你的想法?易娱网络http://www.eyugame.com/谢谢观赏Thanks for your time@live711c@minihai.comAuthor:邹志胜