#路径查找 #2d-vector #2d #gamedev #vector #graphics #二维

bidivec

提供二维数组、向量和切片的库,包含电池(如路径查找、洪水填充等)

1 个不稳定版本

0.1.0 2022年1月29日

#1231 in 算法

MIT/Apache

600KB
12K SLoC

bidivec

提供二维数组、向量和切片的库,包含电池。该库力求尽可能通用,然后进行合理的优化。

特性

该库通过宏、迭代器和索引的组合,以简单易用的方式支持二维容器。

例如

use bidivec::*;

// Create a new BidiVec<i32> using a macro
let mut bvec = bidivec!{
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
};

// Overwrite cell (1,1) - the 5 - with 7+8
bvec[(1, 1)] = bvec[(0, 2)] + bvec[(1, 2)];

assert_eq!(bvec, bidivec!{
    [1, 2, 3],
    [4, 15, 6],
    [7, 8, 9]
});

// Using iterators, collect the items in a vec
let v = bvec.iter().copied().collect::<Vec<i32>>();

// Assert the result is the expected one
assert_eq!(v, vec![1, 2, 3, 4, 15, 6, 7, 8, 9]);

// Change the sign of all items in the 2x2 rect located at (1,1)
for item in bvec
    .iter_mut()
    .on_rect(&BidiRect::new(1, 1, 2, 2,))
{
    *item = -(*item);
}

assert_eq!(bvec, bidivec!{
    [1, 2, 3],
    [4, -15, -6],
    [7, -8, -9]
});

数据结构

所有数据结构都提供(如果适用)迭代器支持、快速随机访问任何特定二维位置、插入和删除列和行、旋转、转置和裁剪。

支持的数据结构包括

  • BidiVec:在 Vec<T> 上实现的二维包装器,以保持线性布局以实现与本地代码的最佳互操作性。可以使用 bidivec! 宏构建。
  • BidiArray:在 Box<[T]> 上实现的二维包装器,也保持线性布局以实现与本地代码的最佳互操作性,并且保持固定长度(但宽度和高度可能变化)。可以使用 bidiarray! 宏构建。
  • BidiGrowVec:在 Vec<Vec<T>> 上实现的二维包装器,牺牲内存布局和局部性以在集合中间插入时提供更好的性能。可以使用 bidigrowvec! 宏构建。
  • BidiMutSlice:在 &mut [T] 切片上实现的二维包装器,牺牲一些功能以支持外部提供的数据存储,包括就地转换。
  • BidiSlice:在&[T]切片上实现的双向包装器,具有与之前相同的注意事项,但不可变。

其他功能

当可能时,功能(有时通过适当的数据结构以优化方式实现)应用于由所有数据结构实现的BidiViewBidiViewMut特质,这些特质易于其他类型实现。

功能包括

  • 将一个数据结构的矩形复制(粘贴)到另一个数据结构中,通过CopyClone特质(使用editing::copyediting::clone_over方法)或使用自定义混合函数(editing::blend)。
  • 具有自定义操作和比较的洪水填充(editing::flood_fill)。
  • 实现转换以将数据结构视为转置、裁剪、旋转等。
  • 对可变数据结构进行就地转换以转置、旋转、裁剪等。
  • 迭代器,包括数据结构部分的迭代器,以及与项目一起枚举原始坐标的可能性。
  • 用于二维瓦片地图的路径查找算法,对单个源、多个目的地执行Djikstra算法,以及对单个源、单个目的地的Djikstra或A*。

性能

性能相当快,对于大多数算法,即使原始性能不是此crate的重点。

在移动Ryzen 9上,在2000x2000地图(400万个节点)的对角线之间进行路径查找(无启发式方法)需要约1500ms找到最短路径,相同的洪水填充需要110ms填充整个区域,70ms填充棋盘图案。

在5000x5000地图(2500万个节点)上,路径查找需要约10秒,洪水填充需要约500ms。

在200x200地图(20万个节点)上,这是一种更合理的算法大小,路径查找降低到10ms,洪水填充约为1ms。

依赖关系

~270–730KB
~17K SLoC