bracket-pathfinding

This crate is part of the overall bracket-lib system, and (in conjunction with bracket-algorithm-traits) provides pathfinding functionality. A-Star (A*) and Dijkstra are supported. It also provides field of view (FOV) functionality.

Trait Implementation

As a minimum, you need to define get_available_exits and get_pathing_distance (from the BaseMap trait) for your map. is_opaque is needed for field-of-view. These come from the bracket-algorithm-traits crate, but are exposed as part of the prelude for convenience. These in turn can benefit from implementing Algorithm2D (from the same crate). These serve to provide an interface to your map format for the library: the library tries very hard to not be opinionated about how you should store your map data.

Most of the Algorithm2D can be derived by just providing dimensions if you are happy with the simple striding offered by the bracket-lib:

impl Algorithm2D for Map {
    fn dimensions(&self) -> Point {
        Point::new(MAP_WIDTH, MAP_HEIGHT)
    }
}

For field-of-view, you need to indicate whether a tile blocks visibility or not. For example:

impl BaseMap for Map {
    fn is_opaque(&self, idx: usize) -> bool {
        self.tiles[idx as usize] == '#' // Change this to your map definition!
    }
}

Dijkstra and A-Star need to know what exits are valid from a tile, and the "cost" of moving to that tile (most of the time you can use 1.0). For example:

impl BaseMap for Map {
    fn is_opaque(&self, idx: usize) -> bool {
        self.tiles[idx as usize] == '#'
    }

    fn get_available_exits(&self, idx: usize) -> SmallVec<[(usize, f32); 10]> {
        let mut exits = SmallVec::new();
        let location = self.index_to_point2d(idx);

        if let Some(idx) = self.valid_exit(location, Point::new(-1, 0)) {
            exits.push((idx, 1.0))
        }
        if let Some(idx) = self.valid_exit(location, Point::new(1, 0)) {
            exits.push((idx, 1.0))
        }
        if let Some(idx) = self.valid_exit(location, Point::new(0, -1)) {
            exits.push((idx, 1.0))
        }
        if let Some(idx) = self.valid_exit(location, Point::new(0, 1)) {
            exits.push((idx, 1.0))
        }

        exits
    }
}

A-Star also need to know a distance to the objective for a given tile. If you don't provide a useful number for this, it will become a very inefficient search. You can vary the behavior of the search by using Pythagoras, Manhattan or other algorithms to specify the distance heuristic. For example:

impl BaseMap for Map {
    fn get_pathing_distance(&self, idx1: usize, idx2: usize) -> f32 {
        DistanceAlg::Pythagoras.distance2d(
            self.index_to_point2d(idx1),
            self.index_to_point2d(idx2)
        )
    }
}

A-Star (A*) Pathing

Bracket-lib includes a high-performance A* system. It uses a binary-heap to optimize open/closed storage. By default, it cancels the search after 65,536 iterations.

Actually performing the A Star search is very simple:

let path = a_star_search(
        map.point2d_to_index(START_POINT),
        map.point2d_to_index(END_POINT),
        &map
    );
    if path.success {
        // Do something with it! path.steps has the whole path.
    }

The example astar demonstrates this.

Dijkstra Mapping

Bracket-lib also includes Dijkstra maps, that can include as many search targets as you want. See The Incredible Power of Dijkstra Maps for some ideas as to what you can do with this.

To generate a Dijkstra map, you need a vector of target tile indices. You can then make the map:

let mut search_targets : Vec<usize> = Vec::new();
search_targets.push(map.point2d_to_index(START_POINT));
search_targets.push(map.point2d_to_index(END_POINT));
let flow_map = DijkstraMap::new(MAP_WIDTH, MAP_HEIGHT, &search_targets, &map, 1024.0);

Once you have the map, you can access individual distances at flow_map.map - or you can use various helper functions such as find_highest_exist and find_lowest_exit to help with path-finding.

The example dijkstra demonstrates this.

Field of View (2D only for now)

With is_opaque defined for your BaseMap trait, obtaining a set of all visible tiles is easy:

let fov = field_of_view_set(START_POINT, 6, &map);

You can see this in action with the example fov.

Feature Flags

If you enable the threaded feature, some Dijkstra functions will use a multi-threaded algorithm.

Examples

There are three examples (ignore common.rs - it's shared code):

• astar (cargo run --example astar), demonstrating A-Star pathing across a random map.
• dijkstra (cargo run --example dijkstra), demonstrating Dijkstra mapping to two targets.
• fov (cargo run --example fov), demonstrating field-of-view generation.

These use crossterm for rendering to your terminal.