【教程】【GC七段】魔兽自动寻路之一：关于躲避障碍物的理论探讨

老胡

看了醉骚在群里发的躲避障碍物示例，感觉有点意思，也想了一下大概是怎么实现的。

我觉得大概两种思路：
一是根据障碍物去判断，因为之前看过老猫发的障碍物划线，所以障碍物应该是可以获取的，然后根据障碍物的大小做文章
二是根据坐标，找到一个（或多个）中介点，通过中介点连接源和目标，本次探讨的主要是这种。

1、一个简单的例子
举个简单的例子，下图中，比如B想到A去，遇到障碍物，这时直走肯定是不行的。办法是取AB的中心点A-B作为中介点，然后中介点向右位移（实际判断中要左右同时判断）5码

然后对A-B的新位置做判断，如果该点同时可以达到A和B，就可以以该点做为中介点，如下图，先从B位移到A-B，再位移到A
如果A-B点对A和B仍不可见，则A-B点继续向右位移，直到A-B点对A点、B点同时有视野为止




2、一个稍微复杂一点的例子

下图是一个比上面稍微复杂一点的场景，基于上面的方法，不论A-B位移多远，都无法得到一个可以同时到达A点、B点的中介点。

所以我们不能蛮干的一直移动，假设我们向左、向右移动30码（我们暂定这个为我们能忍受的极限）之后，都没有找到我们需要的点，如果不考虑多个障碍物的情况，那么只能是下图的情况，就是A处在一个特殊的位置（U型），或者B处在一个特殊的位置，那么我们考虑取一个更远的位置，以排除这种情况，就是A1点，然后根据A1点和B点进行判断

如果A1、A可见，A1、A1-B可见，A1-B、B可见，则我们就找到了想要的中介点

当然我们也要有一个忍受的极限，比如A1离A30码，还是不行，就考虑远离B，再不行就放弃了


3、多个障碍物的例子
楼主还没想，如果想到再补充

根据龙套提供的线索，看了几个最短路径的算法，感觉还是要首先清楚障碍物的模型，只是用上面的方法，如果多障碍物，比较看脸了，应该经常会绕远。

4、上下两层的情况，例如刀锋山竞技场
楼主还没想，如果想到再补充，这个估计只能写死固定的路径

龙套哥

原来构思过一个用回溯法解决这类走位问题的函数，但是苦于fh着急的moveto函数和wow本身的问题，估计还是有实现上的困难。
可以通过某些方法识别出模型的边缘位置，确定边缘的形状，就可以得到空间上的一个方程。B(x,y,z)边缘
Bxyz在z平面投影B(x,y,0)可以得到平面上的方程和梯度向量。之后只要找一个边缘上的点并且最接近目标点就可以实现贴着边去找目标。（大概）
多目标问题感觉也可以用类似的方法，但是感觉效率捉急，而且自带的facedirection有时候会卡掉线。
刀锋山那个只要改变z的值就可以实现，可以做出斜坡的空间方程斜坡(x,y,z)，根据偏导数确定梯度，也可以获取切面的面方程，最后只要改变move到一个xy合乎变化大小的z值高度就可以实现上坡了。
具体方格走位你可以 参考 。 如果方格划分得当，最后的结果也是近似的。

狗血编剧男

诶哟，还构图，不得不佩服！

2812059513

谢谢谢谢，谢谢谢谢谢谢谢谢。。。

feng3498

这么牛B的东西要顶起来

leonokok