Crate pathfinding_astar

Source
Expand description

An implementation of the A-Star pathfinding algorithm

Given a collection of nodes you can find the most optimal route from one node to another (if it exists) by providing:

  • Your starting node
  • Your end or target node
  • A map of nodes containing their weight heuristic and what neighbours they have with the respective distances to each one.
    • Note that weight is setup such that large weight values indicate a difficult node to traverse

If a route does not exist the library will return None, otherwise you’ll have Some(Vec<T>) containing the node labels of the best path, where the type T corresponds to what you’ve used to uniquely label your nodes. Note T must implement the Eq, Hash, Debug, Copy and Clone traits, typically I use i32 or (i32, i32) as labels which satisfy this.

Note that if your node weightings are very similar then the algorithm may give you the second or third highly optimal path rather than the best, tuning your weightings is how to ensure the best result but in most cases the second/third route is good enough - this arises from cases where multiple nodes end up having the same A-Star score and the first one of them which gets processed in turn generates a good A-Star score for your end node and that is returned.

So in general choose a type T to label each of your nodes, specify your starting node and ending node, and along with a map of all your nodes you can find a path with the following function:

pub fn astar_path<T>(
    start_node: T,
    nodes: HashMap<T, (Vec<(T, f32)>, f32)>,
    end_node: T,
) -> Option<Vec<T>>

Where nodes must also contain your start_node and end_node. The HashMap keys are also your chosen label to uniquely identify nodes and the value tuple has two parts:

  • A vector of neighbours with the same type label and the distance between that neighbour and the current key as an f32
  • An f32 weighting for the node which will guide the algorithm

Functions§

astar_path
Will find the most optimal path from start_node to end_node if it exists. The nodes data set uses the keys as labels to uniquely identify a node/travel point. The values take the form of a tuple containing: