路网中路径的储存

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

在大部分情况下，我们的车辆都选择唯一的最短路径，也就是说如果从 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 号数组里。

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

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

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

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

在大部分情况下，我们的车辆都选择唯一的最短路径，也就是说如果从 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 号数组里。

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

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

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