请选择 进入手机版 | 继续访问电脑版

TW寻路最优实践2

[复制链接]
盛夏丨光年丶 发表于 2021-1-1 18:29:07 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
 


  • 配景
上次完成了初步的寻路设计方案之后,可以顺利的进行静态寻路了,但是对动态避障寻路支持并不好。颠末跟项目设计者仔细研究,发现ROV等算法并不能满意现有需求,原因如下:

  • 我们的动态障碍物是突然出现的,不是从某个其他方向走过来的
  • 每个对象,都需要每隔一小段时间,就要查抄一下自己前进的方向是否有阻挡
  • 我们不能由前端运算,因为有时差问题,只能由后端运算。
据此,我们需要另辟蹊径,找到一个适合自己的算法。


  • 算法形貌
由于我们的障碍物是大概突然出现在前方的,我们并不能像ROV那样预先盘算,选择一个别的路径,所以我们躲避障碍物的方式为:不会提前改变路径,而是到障碍物眼前后才改变。
下图是ROV避障算法,蓝点方阵知道障碍物(红球)的存在,会与红球相撞的蓝点会提前改变路径

         ROV避障算法
下图是我们的动态避障算法,原来obj要从C点移动到K点,但是由于有障碍物的出现,于是到快与障碍物相撞的D点时转向,走D-E-F-H-K各点,到达目的点与障碍物困绕圆切线位置时走直线奔向目的点

此算法依赖于如下几点前提条件:

  • 障碍物都可以被圆困绕,不会无限大,按照圆(折线)躲避不会违和。
  • 紧贴着障碍物的周围是可以走的,也就是障碍物不能连起来形成更大的障碍。


  • 详细算法

原来要从N走到P点,效果走到O点时发现障碍物A。

  • 将A的困绕圆分成12份,每份30度。
  • 由于已知A点位置,圆半径(根本都是固定半径),AB与AC夹角度数(30度),所以可知B,C,D,E,,,M等12个点的位置
  • 由于绕开障碍物只需要绕最多90度,所以最多只需要走3个点。
  • 当对象走到O点,发现障碍物时,首先盘算A点在直线NP的位置,如果A点在直线下方,则从上面绕;相反如果A点在直线上方,则从下面绕
  • 盘算AO夹角如果小于AD角则走折线OD,其他以此类推
  • 盘算C点在直线DP的上方,则需要走折线DC
  • 盘算B点在直线CP的上方,则需要走折现CB
  • 此时已经走了3个点了,可以直接走BP奔向目的地。如果不满3个点,则盘算下一个点M在直线BP下方,则不需要走M了。


  • 复杂度分析

  • 当A已知时,由于困绕圆的半径是固定值,所以B,,M点通过加减法就可以得到
  • 接下来在盘算一次AO夹角(两次浮点数乘法)
  • 接下来最多盘算3此点与直线的关系(每次是两次浮点数乘法)
由此可见运算量是很低的,此算法支持服务器大规模运算。

来源:https://blog.csdn.net/scabo/article/details/112043955
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )