返回

云风兄，借时间请教一个关于寻路算法的问题。

您好！为了不耽误您的时间，我尽量简短。
我是个大二的学生。计算机专业，但是学校教给我们的知识不足以应用，于是自学。
学习A*之前，我想过地图寻路算法的问题，借助平时经验想到了一种算法。希望您能给个评价与建议，关于算法速度与优化。谢谢您。

下面是图。

　　　　　　　　●Ｓｔａｒｔ


　　　Ａ＊＊＊＊＊＊＊＊＊Ｂ


Ｃ＊＊＊＊＊＊Ｄ　Ｅ＊＊＊＊＊Ｆ


　　　　　　　　●ＥＮＤ　 

假如从Start出发要去End，最短路线应该是Start到End的线段。于是联结两点。

然后在中间遇到障碍物AB。这个时候线段被阻隔。于是向顺逆时针两方向旋转直到Start-A，Start-B。此时再向外旋转则与障碍脱离，（也就是说此时Start出发的两条射线与AB相切），记录Start-A，Start-B。

递归该方法，得Start-A-C-End，Start-A-D-End，Start-B-E-End，Start-B-F-End。

逆向顺序判断纪录下来的点，以观察是否可以省略中间某些点，使得路程更近。这样Start-A-C-End变成Start-C-End。

将得到的所有路径对比得到最短路径。


按照这个方法，加以少量修改，可以实现最短路径的寻路方法，似乎不同于A*方法。

另外还考虑过目标点不可到达的情况。如：

　　　　｜
　　　　Ｓ
　＊＊＊＊＊＊＊
＊　　　｜　　　＊
＊　　　Ｅ　　　＊
＊　　　｜　　　＊
　＊＊＊＊＊＊＊
　　　　｜

也可实现。即：用S-E将障碍物分割成左右（顺逆时针旋转）两部分。一旦左方向旋转得到的点到达了S-E直线所分割的障碍物的右侧，则该路线被剪枝。

谢谢。

名字: 自动排版 密码:

回复 | (1568) | IceoFire | 2007-07-22 09:30:37