计算的路径使用空间
有时，计算路径所需的时间不是限制因素，而是路径所使用的数百个单位的空间。探路者需要空间来运行算法，加上空间来存储路径。算法运行所需的临时空间（带有 A*、开集和闭集）通常大于存储结果路径所需的空间。通过限制您的游戏一次仅计算一条路径，您可以最大限度地减少所需的临时空间量。此外，为您的 OPEN 和 CLOSED 集合选择数据结构可以对最小化临时空间产生很大的影响。本节将重点关注最小化结果路径使用的空间。
位置与方向#
路径可以是位置或方向。位置占用更多空间，但其优点是无需遍历路径即可轻松确定路径中的任意位置或方向。存储方向时，只有方向才能轻松确定；位置只能通过沿着指示走遍整个路径来确定。在典型的网格地图中，位置可能用两个 16 位整数存储，使每个步骤占用 32 位。但是，方向要少得多，因此它们可以占用更少的空间。如果单元只能向四个方向移动，则每一步只需要 2 位；如果单元可以向六个或八个方向移动，则每一步需要 3 位。与在路径中存储位置相比，这两者中的任何一个都显着节省了成本。Hannu Kankaanpaa 建议您可以通过存储相对方向（“右转 60 度”）而不是绝对方向（“向北”）。对于某些类型的单位，某些相对方向可能没有意义。例如，如果您的单位正在向北移动，则下一步不太可能向南移动。在六个方向的游戏中，您只有五个有意义的方向。在某些地图上，这些方向中可能只有三个方向（直线、左 60 度、右 60 度）有意义，但在其他地图上，右转 120 度可能是一个有效的动作（例如，当走上陡峭的山路时，折返）。
路径压缩#
一旦找到路径，就可以以某种方式对其进行压缩。可以使用通用压缩算法，但这里不讨论。特定于路径的压缩算法可用于缩短基于位置的路径或基于方向的路径。在决定之前，请查看游戏中的典型路径，以确定哪种压缩效果最好。此外，还要考虑实现（和调试）的难易程度、代码的大小以及它是否真的很重要。如果你有 300 个单位的限制，并且每次只有 50 个在行走，并且路径很短（100 步），那么总内存需求可能只有 <50k，而且不值得担心压缩。
位置存储#
在障碍物而不是地形是确定路径的主要影响的地图中，路径中可能有许多直线段。如果是这种情况，那么路径只需要包含这些线段的端点（有时称为航点）。移动包括检查路径上的下一个点并沿直线朝它移动。
方向存储#
存储方向时，可能会出现连续多次遵循特定方向的情况。您可以利用这种常见模式将路径存储在更小的空间中。
存储路径的一种方法是同时存储一个方向和一个数字，该数字表示该单元应在该方向上移动多少次。与位置存储的优化不同，如果一个方向没有连续多次使用，这种优化会使事情变得更糟。此外，对于位置压缩有用的许多直线，方向压缩不是，因为该线可能与步行方向之一不对齐。使用相对方向，您可以消除“继续前进”作为可能的方向。Hannu Kankaanpaa 指出，使用 8 个方向图，您可以消除向前、向后和 135 度左右转弯（假设您的地图允许），然后您可以仅用两位存储每个方向。
另一种存储路径的方法是使用可变长度编码。这个想法是在最常见的步骤中使用单个位 (0)：直行。使用 1 来标记转弯，并在 1 后面跟随一些位来表示转弯。在四向地图中，您只能向左或向右转，因此您可以使用 10 向左转和 11 向向右转。
可变长度编码更通用，并且对于混合路径可能比行程长度编码压缩得更好，但对于长直线路径则没有那么好。序列（北，直六步，左转，直三步，右转，直五步，左转，直两步）表示为[(NORTH, 6), (WEST, 3), (NORTH, 5 ), (WEST, 2)] 与运行长度编码。如果每个方向是两位，每个距离是八位，那么这条路径需要40位来存储。对于可变长度编码，每一步使用一位，每轮使用两位——[NORTH 0 0 0 0 0 0 10 0 0 0 11 0 0 0 0 0 10 0 0]——总共24位。如果初始方向和每转意味着一步，则每转可以保存一位，从而产生 20 位来存储路径。但是，使用可变长度编码，更长的路径可能会占用更多空间。序列（北，直两百步）是[(NORTH, 200)]，带游程编码，共10位。与变长编码相同的序列是[NORTH 0 0 ...]，共202位。
计算的航点#
一个航点是沿着一条路径的一个点。不是存储沿途的每一步，在寻路之后，后处理步骤可以将多个步骤折叠成一个单一的航点，通常是在路径改变方向的地方或城市等主要位置。然后移动算法将遵循航路点之间的路径。
有限的路径长度#
鉴于地图条件或顺序可能会发生变化，存储长路径可能没有意义，因为在某些时候，路径的其余部分可能没有任何用处。每个单元可以在路径的开始处存储固定数量的步数，然后在几乎遍历路径时使用路径重新计算。这种方法允许控制每单位使用的数据量。
概括#
路径可能会在游戏中占用大量空间，尤其是当路径很长并且存在许多单位时。路径压缩、航路点和信标通过在少量数据中存储许多步骤来减少空间需求。航路点依赖于常见的直线段，因此我们只需要存储端点，而信标依赖于在地图上特殊标记的位置之间预先计算出众所周知的路径。如果路径仍然占用太多空间，则可以限制路径长度，从而导致经典的时空权衡：为了节省空间，信息可以被遗忘并在以后重新计算。