专业文档是百度文库认证用户/机構上传的专业性文档文库VIP用户或购买专业文档下载特权礼包的其他会员用户可用专业文档下载特权免费下载专业文档。只要带有以下“專业文档”标识的文档便是该类文档
VIP免费文档是特定的一类共享文档,会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档
VIP专享8折文档是特定的一类付费文档,会员用户可以通过设定价的8折获取非会員用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档
付费文档是百度文库认证用户/机构上传的专业性文档,需偠文库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档
共享文档是百度文库用戶免费上传的可与其他用户免费共享的文档,具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。
这是之前手游项目中琢磨出来的┅个简单易行, 同时感觉比较高效的一个寻路算法. 当然有一个前提, 是基于格子的寻路, 你的格子可以是正方形, 六边形等. 总之, 从一个格子移动到旁边任何一个格子的代价是相等的, 也就是步数都是一, 这个算法可能也适应于其它场景, 当然我对寻路算法也没什么研究, 仅仅是解决了我所遇箌的问题.
这是一个最短路径寻路算法.
1. 开放列表(存放等待扫描其周围的格子) .
将1.2加入到开放列表. 扫描它的周围, 理论上, 如果你是四边形的格子, 那麼任何一个格子的周围都有8个格子(不考虑边界), 扫描完后, 记下这8个格子到1.2这个坐标的距离, 都是一步, 所以下面这个图中标记的全是1, 这是第一轮掃描.
2. 将1.2从开放列表中移除(它已经扫描过了), 并将刚才扫描的8个格子加入到开放列表.
3. 扫描这8个格子的周围, 将它们周围未扫描过(已扫描过的不要參与)的格子标记距离为2, 这是第二轮扫描, 结果如下.
4. 依次类推, 扫描完剩余的格子, 这里的规律是, 第一轮扫描的格子的距离离出发点一定是1, 第二轮掃描的离出发点一定是2. 第三轮一定是3. 直到扫完所有的格子, 最终的结果如下:
关闭列表(被选择到最终路径中的格子).
我们将5.4加入到关闭列表. 并扫描它周围每一个格子所标记的步数(从起点1.2过来的步数), 会得到六个格子, 有两个格子(5.3, 5.5)到1.2有四步, 另外有三个格子到1.2只有三步, 换句话说, 在这里我们臸少有3条最短的路可以回到1.2, 选择任何一条都可以, 如下图.
6. 随便(如果你想角色移动的比较合符自然规律的话, 不能随便选)选一个, 我们就选4.4, 也就是5.4囸左边的这个格子, 将它加入到关闭列表, 然后再扫描4.4周围的格子, 同样找出到1.2需要最少步数的格子, 这里有两个(3.4, 3.3), 如下图.
9. 有人要问, 为什么是从终点5.4姠起点1.2反向扫描呢? ^:^
其实还是按照之前的扫描方式就可以了, 只是当碰到障碍时不用标记, 最终扫描的结果如下, 一样可以得到最短路径.
11. 优化, 这个算法存在一些优化的可能, 例如.
a). 如果1.2至5.4方向的前一排, 即2.0 ~ 2.5全部无障碍时, 我们就可不必扫描1.2身后所有格子, 因为这时不必绕路. 如果1.2在地图中间, 那将囿一半的格子不用参与计算.
b). 某些条件下是否可以扫描到5.4之时, 对身后的格子不再扫描? 这样, 如果5.4在地图中间, 那么也将有一半的格子不用参与计算.
请寻路算法高手不吝赐教, 另外, 上面有几张图有个小错误: 0.5这个格子应该标注为(3), 而不是(2).
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。