路网中路径的储存
我们正在制作的游戏中，交通和物流是基于公路网的。公路网其实是以路口为顶点，路为边构成的（无向）图。因为我们有大量的车辆行驶在这个路网中，所以，我需要一个空间高效的方法储存这些车辆的路径。
在大部分情况下，我们的车辆都选择唯一的最短路径，也就是说如果从 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
A群和B群寻路算法，用pascal（奥赛的标准语言，现在可以用C和C++，pascal从语言的词法上跟C是等价的）表达为，就是集合（set），在C语言中可以表达为枚举或者指针数组。
Posted by: rawa459 | (3) November 21, 2022 02:29 AM
这个问题，还记得当年的红警98吗？比如1000辆坦克，你用鼠标框选后，然后让他们奔向目的地，如果按照国内RPG的寻路，那么这1000量坦克会排成一条线（一字长蛇奔向目标），这样根本行不通，太low了。
于是，在1995年，美国的高手发明了，群轮解决这个问题，现在叫A*寻路，这个问题其实很简单，设计两个群，A和B，如果1000个坦克，比如1号坦克撞了2号，那么好，主动撞人的这个坦克延时50毫秒移动，这种坦克叫B群，1号坦克叫A群，利用这种技术，可以大致的让坦克像一团蜜蜂一样抵达目的地。
关于A*算法细节，现在都公开了。
Posted by: rawa459 | (2) October 31, 2022 05:39 AM
看起来和路由表是等效的吧。
如果图的最大出度很小的话，烘培结果为啥不压缩成密实的二维数组呢（表现为一维的bitset）。这样的话给定当前点和终点可以直达数据，不需要多次二分查找。
如果最大出度可能很大，也可以根据出度分组，3~4一组、5~8一组、9~15一组等等，每组都对应一个密实二维数组。根据当前点的出度找到对应的数组(和index)，也是可以立刻找到数据。比上面多了一步找二维数组的步骤。
另外在二分查找的方法上，我还有一个优化的小想法：把所有顶点排布在某种带有局部性的分形曲线上，根据在曲线上的位置对顶点进行排序（类似geohash）。利用这个局部性，排序好后，某一个大方向上的很多终点，路由大多是相同的，可以将连续的数组变为线段树进行压缩，节约时间和空间。
Posted by: misdake | (1) September 2, 2022 04:58 PM