Jump Point Search Implementation for Path Finding, in Rust

Last update: Dec 15, 2022

Related tags

Command-line jps

Overview

jps : Jump Point Search in Rust.

Jump Point Search Algorithm Implementation in Rust.

Current implementation status

JPS Implementation

3D case ✅

Lifetime

Currently no lifetime notation is used, and hence a few unnecessary copies have to be performed. Lifetime is needed to be considered for improving the speed/efficiency.

Usage

Add this to your Cargo.toml:

[dependencies]
jps = "1.0"

Two steps to use JPS:

create a GraphSearch using either new_v1 or new_v2
call plan_main to plan a path from start to goal.

/* 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,
        ydim: i32,
        zdim: i32,
        eps_: f32,
    )-> Self

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

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

Example & Test

cargo test -- --show-output

the output shows:

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)

Reference

Logic follows the C++ version (https://github.com/KumarRobotics/jps3d)

Also NOTE that some functions havn't been thoroughly tested, so please let me know if there is any error.

A path-normalization pentesting tool.

pathbuster A path-normalization pentesting tool Todos • Installation • Usage • Examples • Contributing • License • Join Discord Todos Implement --filt

9 Mar 24, 2023

lace up GFA files using panSN path name sub-ranges to coordinate the lacing

gfalace gfalace is a Rust-based tool designed to process a collection of GFA (Graphical Fragment Assembly) files. It aims to interpret the path names

3 Mar 14, 2024

🔭 Search Dash.app from Neovim with Telescope. Built with Rust 🦀 and Lua

Dash.nvim Query Dash.app within Neovim with a Telescope picker! The theme used in the recording is lighthaus.nvim. Note: Dash is a Mac-only app, so yo

193 Dec 28, 2022

CLI search and replace | Space Age seD

SAD! Space Age seD What does it do? Basically sad is a Batch File Edit tool. It will show you a really nice diff of proposed changes before you commit

986 Dec 29, 2022

Like grep, but uses tree-sitter grammars to search

tree-grepper Works like grep, but uses tree-sitter to search for structure instead of strings. Installing This isn't available packaged anywhere. That

219 Dec 25, 2022

full text search manpages

buke full text search manpages cargo run --release -- --build builds an sqlite3 database out of all manpages in your $MANPATH cargo run --release -- "

29 Oct 28, 2022

Search PyPI for packages from the command line.

PPS -- Python Package Index Search Search the PyPI for packages by name, which was done by pip search in the past. This was heavily inspired by pip_se

5 Nov 2, 2021

Grep with human-friendly search output

hgrep: Human-friendly GREP hgrep is a grep tool to search files with given pattern and print the matched code snippets with human-friendly syntax high

345 Jan 4, 2023

fas stand for Find all stuff and it's a go app that simplify the find command and allow you to easily search everything you nedd

fas fas stands for Find all stuff and it's a rust app that simplify the find command and allow you to easily search everything you need. Note: current