我有一个带有非常大地图的游戏，我需要存储很多航点（数百万，如果不是数十亿），然后使用 A* 算法将它们用于寻路。
我需要的：
- 存储大量它们的有效方法
- 为 A* 算法直接访问它们的快速方法。
起初我想使用一个简单的向量，但这很快就会使用所有可用的内存。然后我想我应该使用 mysql，这也许是个好主意，因为我可以查询数据库中的航点区域。
最大的问题是，对于 A*，我需要尽快访问航路点，所以也许我需要每个航路点的唯一 ID。
实现这一目标的最佳方法是什么？
问问题
722 次
1 回答
0
我认为你应该考虑通过自己管理你的内存来稍微降低层次——为你的图表的每个节点调用new并显式地调用；delete并通过内存地址引用您的节点。如果您担心分配大量小块内存，可以考虑使用tcmalloc库。
节点应包含邻接列表。如果图形是静态的，我建议将邻接存储在每个节点中动态创建的数组中，该数组的大小与邻居的数量完全匹配。如果邻居的数量可以随时间变化，std::vector可能是下一个最好的事情。
注意：我假设图表是不规则的。对于常规图（例如 Potatoswatter 指出的网格），可以隐式学习节点的位置。
于 2013-01-11T08:31:53.430 回答