c++ - 存储瓦片地图节点的最佳容器？

Question

我正在编写一个等距 2D 场景，其中我必须使用 A* 寻路。最好有一个向量来存储所有瓦片节点（每次我请求“西-南相邻节点”时计算它并检查它是否存在一些数学），或者我直接准备所有节点并指向 9 个相邻节点，如果有界则将它们归零？这个选项有点消耗内存，但值得吗？

一般来说，std::vector、std::list、自定义存储瓦片地图节点的最佳方法是什么？

Answer 1

使用网格图，一个（一维）数组/向量可以完成这项工作。计算/检查邻居的“数学”非常简单。

您可以在地图周围添加“假”图块以简化/优化检查。

因此，对于 3x3 地图，您构建了一个 5x5 地图，其边界上有无法通行的图块。

XXXXX
X...X
X...X
X...X
XXXXX

北/南：指数 +/- 5

东/西：指数 +/- 1

Answer 2

我建议使用您提供的每个节点存储 9 个指针的选项，每个指针指向一个邻居。除非您有大量节点，否则在今天的硬件上内存使用量可以忽略不计，如果您可以轻松地将邻居返回到节点，而不是搜索您必须找到的每个节点，那么寻路将会更快。

简而言之，内存使用不会那么高，并且寻路会比其他方案更快。