三维体积的空间哈希

Rust中的通用空间哈希网格。

允许将空间请求高效地转换为包含内容的单元格。实现不关心单元格中存储的内容，只要它是Sized。所有存储都在一个内存块中，以实现最佳可能的缓存局部性。

使用方法

use spatial_hash_3d::SpatialHashGrid;
use cgmath::Vector3;
// create spatial hash grid of size 5x10x20 filled with None.
let mut sh: SpatialHashGrid<Option<u64>> = SpatialHashGrid::new(5, 10, 20, ||{None});
// fill the cube at coordinates (1,2,3) with content 42
sh[Vector3::new(1, 2, 3)] = Some(42);

// iterate by mutable reference over all filled boxes within a given bounding volume
for (c, _idx, elem) in sh.iter_cubes_mut(Vector3::new(1, 2, 3), Vector3::new(4, 5, 4)) {
    match elem{
        Some(e)=> *e += 1,
        None=>{}
    }
}

// retrieve coordinates and references to contents of all filled boxes within a given volume
for (c,elem) in sh.iter_cubes(Vector3::new(1, 2, 3), Vector3::new(4, 5, 4)).filter_map(|(c, e)| Some((c,e.as_ref()?))) {
    println!("{c:?} {elem}");
}

创建空间哈希时，您可以传递任何闭包，因此您可以在创建时为单元格提供不同的内容。

# use spatial_hash_3d::SpatialHashGrid;
# use cgmath::Vector3;
// create spatial hash grid of size 5x10x20 filled with different numbers.
let mut cnt:u64 = 42;
let mut sh: SpatialHashGrid<u64> = SpatialHashGrid::new(5, 10, 20, ||{cnt +=1; cnt});

设计考虑

此实现针对速度进行了优化，而不是内存效率。

• 读写复杂度为O(1)。
• 在网格创建时，整个体积的矩阵将始终预先分配，因此内存使用量与体积成比例。
• 没有预见到对此进行动态调整大小的能力，因为大多数关注此的用例不需要它。
• 您可能想在一个更灵活的数据结构内部放置一个更密集的空间哈希，而不是更多的单元格，例如一个树

迭代器

提供了迭代器来访问给定轴对齐体积内的内容。所有迭代器的复杂度与它们选择的体积成比例，即体积越大，迭代器运行时间越长。

在迭代过程中，可能有用“缓存”空间哈希中的引用以供进一步使用。为此，提供了一个平面u64索引（可以由任何迭代器返回或从有效坐标获取）。

# use spatial_hash_3d::SpatialHashGrid;
# use cgmath::Vector3;
# let mut sh: SpatialHashGrid<u64> = SpatialHashGrid::new(5, 10, 20, ||{0});

// construct iterator that returns indices
let cubes_iter = sh.iter_cubes(Vector3::new(1, 2, 3), Vector3::new(4, 5, 4)).with_index();
// vec to hold interesting cube references
let mut interesting = vec![];
// go over the iterator saving references
for (c,idx, elem) in cubes_iter {
    println!("{c:?} {idx} {elem}");
    if *elem == 42{
        interesting.push(idx);
    }
}

for i in interesting {
    let v = sh[i];
    println!("Selected {v} @ idx {i}");
}

这通常比直接持有存储中的引用更安全，并且也会让借用检查器满意，并使您的游戏免于段错误。

依赖关系

• cgmath是Vector3的便利依赖项（如果您使用此库，您可能已经有它了）
• itertools用于体积迭代器