预运算地图寻路的一种方法

上次谈到服务器上寻路算法的优化。文末提到,其实,针对具体需求,我们实际上可以预运算所有的路径,把结果持久化在文件中,运行时用 O(1) 的时间就可以查询到任意路径。 对于半径为 N 的地图网格,选取任意两点作为起点和终点,一共有 N^4 数量级的路径,直接按起点和终点来缓存路径显然不现实。 但实际上,除非整张地图是个复杂的迷宫,大部分路径是重复的。这和人实际上行路是一样的。如果你从家中的卧室去到办公室的工位上,整条路径和你从客厅出发是高度重叠的;仅有出家门前的那一小段略有不同。 在服务器上寻路,通常解决的