pathfinding

This crate implements several pathfinding 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.
• Fringe: find the shortest path in a weighted graph using an heuristic to guide the process.

Those algorithms are generic over their arguments.

Using this crate

In your Cargo.toml, put:

[dependencies]
pathfinding = "0.1"

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

extern crate pathfinding;

use 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.

The first version uses an explicit type Pos on which the required traits are derived.

use pathfinding::bfs;

#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
struct Pos(i32, i32);

impl Pos {
  fn 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)]
  }
}

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

The second version does not declare a Pos type, makes use of more closures, and is thus shorter.

use pathfinding::bfs;

static GOAL: (i32, i32) = (4, 6);
let result = bfs(&(1, 1),
                 |&(x, y)| vec![(x+1,y+2), (x+1,y-2), (x-1,y+2), (x-1,y-2),
                                (x+2,y+1), (x+2,y-1), (x-2,y+1), (x-2,y-1)],
                 |&p| p == GOAL);
assert_eq!(result.expect("no path found").len(), 5);

License

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