softdevteam/pathfinding

Name: pathfinding

Owner: Software Development Team

Description: Pathfinding library for rust

Forked from: samueltardieu/pathfinding

Created: 2017-11-09 17:58:01.0

Updated: 2017-11-09 17:58:03.0

Pushed: 2017-11-10 00:09:46.0

Homepage: null

Size: 119

Language: Rust

GitHub Committers

User	Most Recent Commit	# Commits

Other Committers

User	Email	Most Recent Commit	# Commits

README

pathfinding

This crate implements several pathfinding, flow, and graph algorithms in Rust

• A*: find the shortest path in a weighted graph using an heuristic to guide the process.
• breadth-first search (BFS): explore nearest neighbours first, then widen the search.
• depth-first search (DFS): explore a graph by going as far as possible, then backtrack.
• Dijkstra: find the shortest path in a weighted graph.
• Edmonds Karp: find the maximum flow in a directed graph.
• Fringe: find the shortest path in a weighted graph using an heuristic to guide the process.
• IDA*: explore longer and longer paths in a weighted graph at the cost of multiple similar examinations.
• Kuhn-Munkres: find the maximum (or minimum) matching in a weighted bipartite graph.

Those algorithms are generic over their arguments.

Using this crate

In your Cargo.toml, put:

endencies]
finding = "0.2"

Or if you don't need the Edmonds-Karp or the Kuhn-Munkres algorithms you can specify this by disabling the default features. This prevents dragging in the ndarray dependency which takes a long time to compile.

endencies]
finding = { version = "0.2", default-features = false }

You can then pull your preferred algorithm (BFS in this example) using:

rn crate pathfinding;

pathfinding::bfs;

Example

We will search the shortest path on a chess board to go from (1, 1) to (4, 6) doing only knight moves.

pathfinding::bfs;

rive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
ct Pos(i32, i32);

 Pos {
 neighbours(&self) -> Vec<Pos> {
let &Pos(x, y) = self;
vec![Pos(x+1,y+2), Pos(x+1,y-2), Pos(x-1,y+2), Pos(x-1,y-2),
     Pos(x+2,y+1), Pos(x+2,y-1), Pos(x-2,y+1), Pos(x-2,y-1)]



ic GOAL: Pos = Pos(4, 6);
result = bfs(&Pos(1, 1), |p| p.neighbours(), |p| *p == GOAL);
rt_eq!(result.expect("no path found").len(), 5);

License

This code is released under a dual Apache 2.0 / MIT free software license.