jps : Rust中的跳跃点搜索。

Rust中的跳跃点搜索算法实现。

当前实现状态

JPS 实现

• 3D 情况✅

生命周期

目前没有使用生命周期注释，因此需要进行一些不必要的复制。为了提高速度/效率，需要考虑使用生命周期。

用法

将此添加到您的 Cargo.toml 中

[dependencies]
jps = "1.1"

使用 JPS 的两步

1. 使用 new_v1 或 new_v2 创建一个 GraphSearch
2. 调用 plan 来规划从 开始 到 目标 的路径。

/* using HashMap as the map input.
`fmap` can be `None` such that a grid will be regarded as free as long as it is not occupied and is within the legal boxed-boundary. */
GraphSearch::new_v1(
        fmap_: Option<HashSet<(i32, i32, i32)>>,
        omap_: HashSet<(i32, i32, i32)>,
        xdim: [i32; 2],
        ydim: [i32; 2],
        zdim: [i32; 2],
        eps_: f32,
    )-> Self

/* using a binary map as the map input */
GraphSearch::new_v2(
        map: &[bool],
        xdim: [i32; 2],
        ydim: [i32; 2],
        zdim: [i32; 2],
        eps_: f32,
        // goal: (i32, i32, i32),
        // use_jps_: bool,
    ) -> Self

/* path-finding */
plan(
        &mut self,
        start: (i32, i32, i32),
        goal: (i32, i32, i32),
        usejps: bool,
        max_expand: i32,
    ) -> bool

示例 & 测试

cargo test -- --show-output

输出显示

path is :
(0, 0, 0) ➡ (0, 1, 0)➡ (0, 2, 0)➡ (0, 3, 0)➡ (1, 4, 1)➡ (2, 4, 1)➡ (3, 4, 1)➡ (4, 3, 2)➡ (4, 2, 2)➡ (4, 1, 2)➡ (3, 0, 3)➡ (2, 1, 4)➡ (2, 2, 4)➡ (3, 3, 4)➡ (4, 4, 4)
turnings are :
(0, 0, 0) (0, 3, 0) (1, 4, 1) (3, 4, 1) (4, 3, 2) (4, 1, 2) (3, 0, 3) (2, 1, 4) (2, 2, 4) (4, 4, 4)

发布说明

版本 1.1.1

• API 已更改。

  xdim : i32 已替换为 xbound: [i32;2]. xbound[0] ≤ x < xbound[1] 定义了 x 轴的网格搜索空间。 (类似情况适用于 ydim 和 zdim)

• 添加了一个功能特性，即 decomp，用于查找椭球和分解。

  要使用此功能，在 Cargo.toml 中添加

  [dependencies]
  jps = { version = "1.1", features = ["decomp"] }
  

  您需要为体素化和去体素化实现 trait Voxelable。

  然后您可以 init 一个 Decomp，然后 decompose 它以执行分解。

  作为一个简单的例子，请查看测试中的示例，或输入

  cargo test --release --features=decomp -- --show-output