« 空间优先的 protobuffer / json 解码器 | 返回首页 | 多线程串行运行 Lua 虚拟机 »

路网中路径的储存

我们正在制作的游戏中,交通和物流是基于公路网的。公路网其实是以路口为顶点,路为边构成的(无向)图。因为我们有大量的车辆行驶在这个路网中,所以,我需要一个空间高效的方法储存这些车辆的路径。

在大部分情况下,我们的车辆都选择唯一的最短路径,也就是说如果从 A 路口到 B 路口存在一条制定好的路径的话,所有的车都会走这条路。基于这一点,我们可以对多条路径合并储存。

我选择用当前路口 id 和目的地路口 id 做 key ,把下一站路口 id 作为 value ,保存在一张 hash 表中。这样,先用 dijkstra 算法求出起点到终点的最短路线后,再把每一段路线用该结构保存下来即可。

当车辆到达某个路口,只需要用当前路口和它自己的目的地就可以索引到应该往哪个方向开。这个结构很适合保存在 Lua table 中,用元表触发尚未计算过的路径。而且这样一个路径表只是一个 cache ,随时可以清理重建。

如果路网已经稳定,那么还可以选择一个内存更紧凑的结构保存它们。

对于每个路口,连接的路是有限的。在我们的游戏中,其实只有十字路口( 4 叉)和 T 字路口( 3 叉)两种。我们可以对路口连接的路编号为 1-4 。我们用 4 个数组就能储存下所有的路径信息。

驶向同一编号出口的路径可以储存在一起。比如,如果从 42 号路口去向 100 号路口的车需要在 42 号路口的第 2 出口驶出,我们就把 (42,100) 记录在 2 号数组里。

每个数组都是有序的,这样可以用二分查找确定一段路径是否在该数组中。因为最复杂的路口只有四个出口,而车在我们的规则中,不准在路口调头,原路折返。所以在一个路口查询下一阶段的去向,最多只需要做两次二分查找就可以确定(在起点出做四次查询可以知道是否可达)。

当路网固定,不会动态增删时,这四个数组可以储存在一片连续内存中。它储存了在这个路网中,任意两个路口间的最短路径。

以上,我作了一个简单的实现

Comments

看起来和路由表是等效的吧。

如果图的最大出度很小的话,烘培结果为啥不压缩成密实的二维数组呢(表现为一维的bitset)。这样的话给定当前点和终点可以直达数据,不需要多次二分查找。
如果最大出度可能很大,也可以根据出度分组,3~4一组、5~8一组、9~15一组等等,每组都对应一个密实二维数组。根据当前点的出度找到对应的数组(和index),也是可以立刻找到数据。比上面多了一步找二维数组的步骤。

另外在二分查找的方法上,我还有一个优化的小想法:把所有顶点排布在某种带有局部性的分形曲线上,根据在曲线上的位置对顶点进行排序(类似geohash)。利用这个局部性,排序好后,某一个大方向上的很多终点,路由大多是相同的,可以将连续的数组变为线段树进行压缩,节约时间和空间。

Post a comment

非这个主题相关的留言请到:留言本