承接各种算法类脚本。

hitlerson

要不给做个能打败 深蓝 的算法

link006007

感觉上选择适合的算法比写算法难得多

雷欧纳德

不知道兽兄接不接A*算法结果路径平滑优化算法？

美兽

以下引用雷欧纳德于2008-6-21 21:23:04的发言：

不知道兽兄接不接A*算法结果路径平滑优化算法？

路径之所以弯折在于拐点的存在，可以避免拐点的出现，例如设定转弯比直行消耗的G权值要高，对于RM大格子形式的游戏路径，可很大程度平滑路径，而且增加的消耗很小。

稍微复杂一些则可以先生成最短路径，之后前一拐点保持直行，依次寻找后面拐点与该拐点延长线的交点是否可通（逆序搜索），建议在前期搜索时建立拐点记录，相对第一个方法效果较好，但开销可能大些。

雷欧纳德

呵呵，并不是拐弯这种平滑

我说的平滑路径是指在整个寻路结束后，再次对结果路径进行的一种优化算法

在3D环境中，使用导航网络寻路，就会发现不管如何寻路，结果总会出现冗余路径

最合理的做法是对每一个点进行直线碰撞检测，如果能直线抵达目标点，则抛弃该点之前的所有点，反复检测知道到达目的地

但是实际上3D游戏不可能这么做，因为碰撞检测的消耗不亚于寻路，所以我们把碰撞检测改为利用几何学原理来修正路径



如图，红色路径是寻路所得的结果，绿色是我们用人脑计算出的最优路径
显然，我们无法优化出绿色的那条路径，但是我们的目标是由红色路径优化出蓝色的那条





另外再问一个问题：
基于A*算法寻路的一个特点，从一个大区域向一个小区域寻路时，会耗费大量时间检测无用路点。这种情况有个很简单的解决办法，就是逆转，从小区域向大区域寻路的话则不会发生这种情况。那么如何来检测、并且决定是应该正向寻路还是应该逆向寻路呢？


呵呵，我也不要求写算法，一起探讨探讨～

司马睿风

这个难哦雷子

link006007

npc 弱智拉直线的飘过{/gg}
期待你们的成果{/se}

小传子

以下引用link006007于2008-6-23 18:16:10的发言：

npc 弱智拉直线的飘过
期待你们的成果

这个有点像CS的Z.ROBOT自动生成寻找MAP路点一样

yangff

对a*完全理解不能的人飘过

猫哥哥

以下引用雷欧纳德于2008-6-23 16:09:28的发言：

基于A*算法寻路的一个特点，从一个大区域向一个小区域寻路时，会耗费大量时间检测无用路点。这种情况有个很简单的解决办法，就是逆转，从小区域向大区域寻路的话则不会发生这种情况。那么如何来检测、并且决定是应该正向寻路还是应该逆向寻路呢？

为什么不用空间换时间呢（虽然这种方法比较奔-_-b）：
事先做地图的时候把坐标划为大小两个区域，同区域或小区域向大区域用正向，大区域往小区域的则用逆向，开销就只一次比较。用布尔值来做标记（反正只有大小两种情况），空间也不会增加多少吧。

另外个人觉得，根据地图复杂情况设置一个合适的H值，或许能减少无用点的搜索……