游戏中碰到个有点棘手的算法问题

月下临风

是关于寻路的,但和平常的有点不大一样.
现在的问题是:
地图非常的大,>=2048*2048,资源非常的多,服务器端不可能全部载入.
当客户端发来寻路请求的时候,服务器端要计算出路线来
在无法加载整个地图的情况下,又是这么大的地图,怎么样在很短时间内,得到结果呢?
有没好的想法?
[em24]

紫涩雪

只 加载 遮挡 信息就好了~~

月下临风

恩,然后呢?

sea_bug

在客户端算好，把结果发给服务器，服务器再把结果简单的验证一下就行了。

hyzboy

服务器不计算路线，客户端将计算每个点的路线传给服务器。
服务器只验证路线是否合法就行了，合法不管它，不合法就随你便了。

月下临风

这个问题我做不了主,我只是一个客户端小程,负责实现功能.
反正就算在客户端,那有什么可以非常高效的算法呢?

PassByYou

你自己设计的系统？


//
科学的数据结构做法

地图数据结构按分片处理，根据坐标来加载分片。然后cache几个最近常用的分片，比如20个分片，然后再结合一下压缩的预读。

寻路，不管是根据顶点和A*来，按分片预读+Cache，非常高效的。

PassByYou

eye,look red text

月下临风

第一.我不会把地图都载入.
第二,我也不会把地图分割,即使一次性载入少了,但这样代价更大.
第三,我也不会用传统的A*,因为效率太低了.
有改进增强型的A*么?

PassByYou

如果地图达到2048*2048，即使每个pane只使用一个byte，那么地图的size也是2048*2048=4M。
换种情况，如果每个pane，达到了64个byte，那么地图size是多大？
地图肯定是不能都载入的。如果做成预读（载入前重组数据结构），这是很绕的。

从你描述中，感到你现在的确有点麻烦。我是你的话，既然是全权负责客户端，索性就大改一下构架了。没什么代价不代价，半年之内出个能玩得游戏，就是代价。

另：没有增强型A*，只有经过了改良的A+V，A*+顶点。这并不会增强效率，效率可能反而会降低，只是用A*+顶点更符合物理原理。