公司网站备案申请,鹤山做网站,应用镜像 wordpress,广州公司注册名称查询游戏AI
navigation(导航系统) 地图的表达形式#xff0c; 寻路#xff0c;路径优化
Map representation#xff1a; 1.可行走区域#xff08;物理碰撞#xff0c;跳跃距离#xff0c;攀爬高度#xff09; 2.表达形式#xff1a;waypoint networks(路点网络图)#…游戏AI
navigation(导航系统) 地图的表达形式 寻路路径优化
Map representation 1.可行走区域物理碰撞跳跃距离攀爬高度 2.表达形式waypoint networks(路点网络图)grid(网格)navigation mesh(寻路网格)sparse voxel octree(八叉树) Waypoint Networks 设置关键点在关键点之间通过算法插值一些过路点过路点插值往两边扩散因为可行走区域并非一条线。 任务一条路径从起点开始寻找路网中最近的点在走到离终点最近的点类似地铁 寻路只能发生在路点和路点之间在计算机中表示为一张连通图。点的密度可以代表寻路精度 优点 1.易实现 2.内存和计算机开销低(路点寻路只是使用到了真是可行走区域的一小部分与格子相比牺牲了路线的灵活性换取交第的内存和计算机开销只要两个点之间是连通的那么角色就可以按照点所在的位置到达目标点的位置) 缺点 1.需要手动插值不灵活 2.并且表现上npc路径相比于较宽的可行走区域往往是走中间 Grid 优点 1.易实现 2.容易动态修改 缺点 1.内存和计算机开销大 2.不适用3d地图。例如桥上桥下都能行走 3.需要额外的平滑处理角色行走路线可能出现多个90度的拐角 Navigation Mesh 划分必须要凸多边形不能凹多边形。否则穿过polygon时可能走到该polyhon之外的区域。并且形成多边形走廊时穿过的每个凸多边形之间有且只有一条公共边portal
优点 1.支持3d可行走区域 2.灵活性高 3.可动态修改 4.内存和计算机开销小一个polygon可能就能全表达一大片可行走区域 5.寻路效率高 缺点 1.生成非常复杂 2.不支持3d空间例如空战游戏 Sparse Voxel Octree 对空间进行八叉树划分把所有可通行区域用八叉树结构表示。如果区域是整个联通的用一个很大的Voxel表达如果是一个边界则不断地细分 所有的地图表达形式连接关系都是形成一个图。最终在图上寻找路径
dfs时间换空间 bfs空间换时间 dfs和bfs没有办法计算加权最短路径。并且很多时候会找出许多没必要的路径 迪杰斯特拉算法找的一定是最短路径
a星算法相对迪杰斯特拉算法增加了启发函数。当走到一个点时不仅考虑过去花费的路径成本还会猜想从当前位置到目标点所需距离。 在选择explored点时优先选择现在已走过的距离加上预计要走的距离中最近的点来优先搜索。 并且只要达到目标点不需要将目标点explored就停止搜索。 Steering 根据目标位置确定加速度 通过积分反向推导加速度
计算角速度的加速度
Crowd Simulation Microscopic Models 微观模型 定义每一个的行为然后合在一起就行了 Macroscopic Models 宏观模型 宏观定义大的运动趋势每个个体按照这个运动即可 Mesoscopic Models 中观模型 上面两种的混合可以定义更加复杂的情况 Separation 如果一条鱼离我太近了我就分开 Cohesion 如果鱼群离我太远了我就接近 Alignment 和鱼群方向保持一致 微观的结果是不可控的且不受人影响 定义行走的轨迹然后生成zone graph 主要表达有规则的行为比如人类人群行为 把群体分成一个个小族群小族群受到一个大的指向控制每个小个体自己的行为仍走微观模型的方向。例如rts寻路 避免碰撞 两个物体太近时产生斥力太远时产生吸力 对所有的障碍物加距离场当物体里离障碍物越来越近时距离场的值越来越小产生的反向斥力越来越大然后给个大致的方向。群体便会模拟真实的行为 速度障碍法生成碰撞检测 VO两个物体运动时一个物体会在另一个物体的速度域上产生一个障碍如果我在当前速度上会和障碍形成碰撞则调整速度
RVO双方都让 ORCA整体判断
Sensing Navigation Data寻路数据 Tactical Map战术地图也就是战术价值很高的点 Smart Object 指的是AI可以交互的物体 如可以破坏的墙梯子等 Cover Point掩护点 Influence Map 热力图 对于战场态势的感知 Sight Area 指的是AI的可见区域 引擎端通常开放 1.sensing精度的选择 2.sensing结果的共享 FSM (有限状态机)和 BT(行为树) 都是Forward 算法走一步算一步。 Backward的算法以目标为驱动的反向算法 Hierarchical Tasks Network HTN 任务层次网络 Goal Oriented Action Planning 基于目标驱动行为规划 Monte Carlo Tress Search 蒙特卡洛搜索树 Deep Learning 深度学 当state非常多时每个state间的设定会非常复杂 层级有限状态机 一种缓冲之举增加了可读性的同时方便管理。但是子state不好添加额外条件或者飞线所以反应速度比较慢 状态机是对AI逻辑的抽象。整个世界AI的逻辑就是在状态里来回切换 分为条件判断节点和动作执行节点 动作节点会返回成功失败和运行中
Sequence顺序执行。当走到该条件时要依次把子树全部执行一遍。如果有任何一个子树返回running时sequence节点被访问时也是返回running
Selector根据条件去尝试所有的子节点优先执行在前面的子节点。前面的子节点成功了Selector节点也执行成功。
Paraller并行执行 每次需要从根节点开始Tick是BT效率低的地方同时Running的节点会不止一个。 并且Running的节点需要有被打断的能力。 BT每次Tick的成本很高所以有些引擎通过添加Event来激活部分或者整个Tree达到效率优化的效果缺点是设计师必须要非常清楚自己在做什么否则非常容易出Bug
Decorator优化行为树 Precondition 装饰器对BT优化 Blackboard用于不同分支交换信息
