# 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`: ```rust 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: ```rust 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: ```rust 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: ```rust 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: ```rust 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](http://www.roguebasin.com/index.php?title=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: ```rust let mut search_targets : Vec = 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: ```rust 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.