关于固定地点寻路逻辑算法

ff1407

pri 发表于 2015-12-5 18:17
其实可以动态的建立路径表来减少计算量，先定义2个二维数组 as 整数，先设为A、B，一个用记录上标的变量  ...

没看得太懂，讨论的话说思路就好，或者贴伪代码的话就分下行，不然真的很难看懂。编辑器的话，我们根本不用关心内存，相对于运行起来上G的消耗的游戏本身，自定义所额外增加的消耗连零头都不够

ff1407

yxxiaobin 发表于 2015-12-5 17:31
这两天也稍微读了几篇入门级的寻路算法的文章，比如A星，比如最小堆等，其中也有一些提到了你所说的权值 ...

这个说起来有点复杂，但其实也简单。图的构造本身就是无方向的，说A点和B点连通，只需要添加个路径数据就可以了。但这需要你的算法架构在非网格状的数据结构上。就像飞机国际航路图一样，每个点都可以连N个其它机场，都记录下来用于搜索。只要支持了，接着修正下主体算法里的计算过程就OK。
程序很复杂，但说来简单，就是数据结构和算法两个东西。先扩展让数据结构能提供相应数据，接着在算法里使用这些数据来进行要想的操作。

pri

ff1407 发表于 2015-12-6 11:03
没看得太懂，讨论的话说思路就好，或者贴伪代码的话就分下行，不然真的很难看懂。编辑器的话，我们根本不 ...

就是每次找到路线之后都把路线记录下来，每次从这个点出发时都判断是否有记录的路径，如果有，则按照原来的路线走，如果没有，则再搜索路径。
唯一不好的地方就是更近的路线开通后还是会找原来的路走，直到原来的路走不通为止。

ff1407

pri 发表于 2015-12-6 13:07
就是每次找到路线之后都把路线记录下来，每次从这个点出发时都判断是否有记录的路径，如果有，则按照原来 ...

这样好多了。其实交流的是思路，除非研究细节，不然不必直接写算法伪代码的。
你用的方法很好，可以方便以后再查找时使用，不必重复计算。但如果路径的连接会变，那么在我看来除了重新搜索外，别无它法。至于更优的路线出现，你需要在地图路线连接变化时加个逻辑去去除可能过时（不是最优解）的路线。那寻路逻辑又会重新开始工作。不过我感觉这个东西应该不容易做就是，要做好的话，技术难度挺高的

yxxiaobin

ff1407 发表于 2015-12-9 20:24
这样好多了。其实交流的是思路，除非研究细节，不然不必直接写算法伪代码的。
你用的方法很好，可以方便 ...

同意这个看法，因为在连接变更时，你除了对每条路径重新做一下寻路，还真没什么方法知道旧路线是不是仍旧最优。
而且，结合星际2的实际情况，寻路算法就算不刻意去优化，也不会对运行产生太大障碍。所以，在复杂寻路不适合，不敢用的手段，这里可能是最优做法。一段程序总是在特定环境里最优，换个环境就未必了。我个人认为，在星际2中，应该不必过分的保守，一味追求运行效率，适当向表现力侧重可能会更好。