Pathfinding on grids using jumping point search and connected components.

Thom van der Woude

Last update: Dec 12, 2022

Related tags

Command-line rust grid astar pathfinding 2d jps

Overview

grid_pathfinding

A grid-based pathfinding system. Implements Jump Point Search with improved pruning rules for speedy pathfinding. Pre-computes connected components to avoid flood-filling behaviour if no path exists.

Example

Below a simple example is given which illustrates how to set a basic problem and find a path.

use grid_pathfinding::PathingGrid;
use grid_util::grid::Grid;
use grid_util::point::Point;

// In this example a path is found on a 3x3 grid with shape
//  ___
// |S  |
// | # |
// |  E|
//  ___
// where
// - # marks an obstacle
// - S marks the start
// - E marks the end

fn main() {
    let mut pathing_grid: PathingGrid = PathingGrid::new(3, 3, false);
    pathing_grid.set(1, 1, true);
    pathing_grid.generate_components();
    println!("{}", pathing_grid);
    let start = Point::new(0, 0);
    let end = Point::new(2, 2);
    let path = pathing_grid
        .get_path_single_goal(start, end, false)
        .unwrap();
    println!("Path:");
    for p in path {
        println!("{:?}", p);
    }
}

See examples for finding paths with multiple goals and generating waypoints instead of full paths.

🕺 Run React code snippets/components from your command-line without config

Run React code snippets/components from your command-line without config.

11 Dec 30, 2022

Components of Fornjot that are no longer actively maintained. Pull requests still welcome!

Fornjot - Extra Components About These are extra components from the Fornjot repository, that are no longer actively maintained. Fornjot's goal was to

4 Jun 6, 2023

Transform jsx/tsx files to reactive views in js/ts to use in Web Components, insert into DOM or integrate with other libraries/frameworks

viewmill Features | Installation | Getting Started | Notes | Examples viewmill is aimed to create complex UIs from a simple form of JSX. It statically

6 Sep 4, 2023

Supercharge your markdown including RSCx components.

rscx-mdx Render Markdown into HTML, while having custom RSCx components inside. Usage use rscx::{component, html, props}; use rscx_mdx::mdx::{Mdx, Mdx

4 Oct 21, 2023

AskBend: SQL-based Knowledge Base Search and Completion using Databend

AskBend: SQL-based Knowledge Base Search and Completion using Databend AskBend is a Rust project that utilizes the power of Databend and OpenAI to cre

87 Apr 7, 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

1 Dec 24, 2021

Navigating around TUM with excellence – An API and website to search for rooms, buildings and other places

NavigaTUM NavigaTUM is a non-official tool developed by students for students, that aims to help you get around at TUM. Feel free to contribute. Featu

21 Dec 22, 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

🔭 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

Comments

Can't restrict diagonals

Hello! I appreciate this crate's straightforward interface, but it would be most useful to me if there were some way to restrict the paths so that diagonals movements were never considered. I tried replacing all moore_neighbourhood with neuman_neighbourghood and move_distance with manhattan_distance, but I got stuck on the use of moore_neighbour, so it seems like the diagonal assumption is pretty baked in right now.

opened by jdm 0

Differing paths for different directions

Hello!

I'm very new to Rust and game development and this crate seemed like a good way to get started. I am however running into issues as the paths generated by the library are different when going in different directions.

As an example:

Computing path from Point { x: 14, y: 10 } to Point { x: 14, y: 25 }
Found Some(461v0) at Point { x: 14, y: 11 }
Found Some(462v0) at Point { x: 14, y: 12 }
Found Some(463v0) at Point { x: 14, y: 13 }
Found Some(464v0) at Point { x: 14, y: 14 }
Found Some(465v0) at Point { x: 14, y: 15 }
Found Some(498v0) at Point { x: 15, y: 16 }
Found Some(499v0) at Point { x: 15, y: 17 }
Found Some(500v0) at Point { x: 15, y: 18 }
Found Some(501v0) at Point { x: 15, y: 19 }
Found Some(502v0) at Point { x: 15, y: 20 }
Found Some(503v0) at Point { x: 15, y: 21 }
Found Some(504v0) at Point { x: 15, y: 22 }
Found Some(505v0) at Point { x: 15, y: 23 }
Found Some(506v0) at Point { x: 15, y: 24 }
Computing path from Point { x: 14, y: 25 } to Point { x: 14, y: 10 }
Found Some(506v0) at Point { x: 15, y: 24 }
Found Some(505v0) at Point { x: 15, y: 23 }
Found Some(504v0) at Point { x: 15, y: 22 }
Found Some(503v0) at Point { x: 15, y: 21 }
Found Some(502v0) at Point { x: 15, y: 20 }
Found Some(501v0) at Point { x: 15, y: 19 }
Found Some(500v0) at Point { x: 15, y: 18 }
Found Some(467v0) at Point { x: 14, y: 17 }
Found Some(434v0) at Point { x: 13, y: 16 }
Found Some(433v0) at Point { x: 13, y: 15 }
Found Some(432v0) at Point { x: 13, y: 14 }
Found Some(431v0) at Point { x: 13, y: 13 }
Found Some(398v0) at Point { x: 12, y: 12 }
Found Some(397v0) at Point { x: 12, y: 11 }
Found Some(396v0) at Point { x: 12, y: 10 }
Found Some(427v0) at Point { x: 13, y: 9 }

Here are two images displaying the different paths. As you can see, one of them is pretty strange. Just thought I'd let you know.

Thanks!

opened by bjrnt 0

crisscross: similar crate just linking in case you find it useful

Hey, I just saw this, nice crate!.

I did something similar a while ago. crisscross was never published as a crate, but I used it in one of my games to have AI find the shortest path to a target + know when they have a clear shot at the player or not.

I figured it wouldn't hurt to link this here so you may find something useful in there.

opened by thlorenz 0

Releases(v0.1.1)

v0.1.1(Aug 15, 2022)

Source code(tar.gz)
Source code(zip)
v0.1.0(Aug 15, 2022)

Source code(tar.gz)
Source code(zip)

Owner

Thom van der Woude

GitHub https://crates.io/crates/grid_pathfinding

Adds back-and-forth jumping between current and previous focused windows to Sway.

sway-focus-back-and-forth Implements back-and-forth movement between the current and the previous focused windows. It also can be seen as a fix to thi