### 18 releases (5 breaking)

0.8.0 | Apr 21, 2023 |
---|---|

0.7.6 | Apr 16, 2023 |

0.6.2 | Apr 9, 2023 |

0.5.1 | Mar 31, 2023 |

0.3.5 | Mar 29, 2023 |

#**2039** in Algorithms

**58** downloads per month

**MIT**license

77KB

1.5K
SLoC

# Path finding library

This library will contain standard path finding algorithms and return the resulting graph object. You can search for paths in a graph based or grid based structure.

*Table of contents generated with
markdown-toc*

**Currently supported**:

- Construct graphs
- Graph operations
- Create grids
- Grid operations
- Create Minimum Spanning Tree (MST) from a graph
- Find path with Depth-First Search (DFS)
- With Breadth-First Search (BFS)
- With Bidirectional Breadth-First Search (BBFS)
- With the Dijkstra algorithm
- With the A* algorithm, with heuristic:
- Euclidean distance
- Manhattan distance

- TBC: with a Hierarchical Path-Finding A* (HPA*), with heuristic:
- Euclidean distance
- Manhattan distance

Download the crate: https://crates.io/crates/path-finding

## How to use

At the moment, we have following major concepts:

- Edge
- Node
- Graph
- Vec3
- Grid

You only need to pass edges to the graph. The nodes are generated automatically. Each pathfinding method will accept a graph, and return a graph that only contains the edges and nodes of the result.

Alternatively, you can also create a graph if you provide an adjacency matrix. Edges and nodes will be generated automatically.

If you want to use the A* path-finding algorithm, please make sure to provide positional information for each node.

Additionally, we work on a support for each of those algorithms based on a 2D grid based structure.

### Create Graph

- Create Edge

`pub` `fn` `your_function``(``)`` ``{`
`graph``::``Edge``::`from`(`
`0` `/*` edge index `*/``,`
`0` `/*` source node `*/``,`
`1` `/*` destination node `*/``,`
`0.``1``,` `/*` weight `*/`
`)``;`
`}`

- Create Graph from edges

`pub` `fn` `your_function``(``)`` ``{`
`graph``::``Graph``::`from`(``Vec``::`from`(``[`edge1`,` edge2`]``)``)``;`
`}`

- Create Graph from adjacency matrix

`pub` `fn` `your_function``(``)`` ``{`
`let` `mut` matrix`:` `&``[``&``[``f32``]``]` `=` `&``[`
`&``[``0.``0``,` `4.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `8.``0``,` `0.``0``]``,`
`&``[``4.``0``,` `0.``0``,` `8.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `11.``0``,` `0.``0``]``,`
`&``[``0.``0``,` `8.``0``,` `0.``0``,` `7.``0``,` `0.``0``,` `4.``0``,` `0.``0``,` `0.``0``,` `2.``0``]``,`
`&``[``0.``0``,` `0.``0``,` `7.``0``,` `0.``0``,` `9.``0``,` `14.``0``,` `0.``0``,` `0.``0``,` `0.``0``]``,`
`&``[``0.``0``,` `0.``0``,` `0.``0``,` `9.``0``,` `0.``0``,` `10.``0``,` `0.``0``,` `0.``0``,` `0.``0``]``,`
`&``[``0.``0``,` `0.``0``,` `4.``0``,` `14.``0``,` `10.``0``,` `0.``0``,` `2.``0``,` `0.``0``,` `0.``0``]``,`
`&``[``0.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `2.``0``,` `0.``0``,` `1.``0``,` `6.``0``]``,`
`&``[``8.``0``,` `11.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `1.``0``,` `0.``0``,` `7.``0``]``,`
`&``[``0.``0``,` `0.``0``,` `2.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `6.``0``,` `7.``0``,` `0.``0``]`
`]``;`
`graph``::``Graph``::`from_adjacency_matrix`(`matrix`)``;`
`}`

### Graph operations

You may want to get some information or mutate the graph in some way. Therefore, the graph currently supports three functions for convenience operations or to provide data for a heuristic function.

#### sorted_by_weight_asc

`pub` `fn` `your_function``(``)`` ``{`
`let` edges`:` `Vec``<`Edge`>` `=` graph`.``sorted_by_weight_asc``(``)``;` `//` will return a vector with edges ascending by weight
`}`

#### offer_positions

`pub` `fn` `your_function``(``)`` ``{`
`//` provide a hashmap, mapping the node id to a position - used for a* pathfinding heuristics
graph`.``offer_positions``(``HashMap``::`from`(``[``(``1``,` `Vec3``::`from`(``0.``1``,` `0.``2``,` `0.``3``)``)``]``)``)``;`
`}`

### Create Grid

- Create Grid from cost matrix

In some cases, such as 2D games, a grid based structure is advantageous. The grid can be created by passing a cost
matrix to the construction function

. At each entry of the matrix you provide an unsigned integer, indicating
the effort it takes
to move to this position from any neighbouring position. In the example below moving from position ` ::`from

`(``0``,` `0``)`

to position
`(``0``,` `1``)`

will require an effort, or require a cost, of 2. Equivalently, moving from `(``2``,` `2``)`

to `(``1``,` `1``)`

will incur a
cost of 1. Based on this information, we want to provide a support for grid based structures in each path finding
algorithm.`pub` `fn` `your_function``(``)`` ``{`
`let` grid `=` `grid``::``Grid``::`from`(``&``[`
`&``[``4.``0``,` `2.``0``,` `1.``0``]``,`
`&``[``2.``0``,` `1.``0``,` `0.``0``]``,`
`&``[``3.``0``,` `4.``0``,` `7.``0``]`
`]``)``;`
`}`

### Grid operations

#### outside

Check if a position is outside the grid. Pass a coordinate to the function below.

`pub` `fn` `your_function``(``)`` ``{`
grid`.``outside``(``(``0``,` `1``)``)``;`
`}`

#### within

Check if a position is within the grid. Pass a coordinate to the function below.

`pub` `fn` `your_function``(``)`` ``{`
grid`.``within``(``(``0``,` `1``)``)``;`
`}`

#### node_id

Convert your coordinate to a node_id

`pub` `fn` `your_function``(``)`` ``{`
grid`.``node_id``(``(``0``,` `1``)``)``;`
`}`

#### cost

Retrieve the cost required to move to a provided node id

`pub` `fn` `your_function``(``)`` ``{`
grid`.``cost``(``3``)``;`
`}`

### Minimum spanning tree

`pub` `fn` `your_function``(``)`` ``{`
`let` mst_graph `=` `graph``::`minimum_spanning`(`graph`)``;`
`}`

### Depth-first search

For graphs

`pub` `fn` `your_function``(``)`` ``{`
`let` dfs `=` `path``::`in_graph`(`
`4` `/*` source `*/``,`
`1` `/*` target `*/``,`
`&`graph`,`
`Box``::`from`(`DepthFirstSearch `{``}``)` `/*` used algorithm `*/`
`)``;`
`}`

For grids

`pub` `fn` `your_function``(``)`` ``{`
`let` dfs `=` `path``::`in_grid`(`
`4` `/*` source `*/``,`
`1` `/*` target `*/``,`
`&`grid`,`
`Box``::`from`(`DepthFirstSearch `{``}``)` `/*` used algorithm `*/`
`)``;`
`}`

### Breadth-first search

For graphs

`pub` `fn` `your_function``(``)`` ``{`
`let` bfs `=` `path``::`in_graph`(`
`4` `/*` source `*/``,`
`1` `/*` target `*/``,`
`&`graph`,`
`Box``::`from`(`BreadthFirstSearch `{``}``)` `/*` used algorithm `*/`
`)``;`
`}`

For grids

`pub` `fn` `your_function``(``)`` ``{`
`let` dfs `=` `path``::`in_grid`(`
`4` `/*` source `*/``,`
`1` `/*` target `*/``,`
`&`grid`,`
`Box``::`from`(`BreadthFirstSearch `{``}``)` `/*` used algorithm `*/`
`)``;`
`}`

### Bidirectional breadth-first search

For graphs

`pub` `fn` `your_function``(``)`` ``{`
`let` bi_bfs `=` `path``::`in_graph`(`
`4` `/*` source `*/``,`
`1` `/*` target `*/``,`
`&`graph`,`
`Box``::`from`(`BiBreadthFirstSearch `{``}``)` `/*` used algorithm `*/`
`)``;`
`}`

For grids

`pub` `fn` `your_function``(``)`` ``{`
`let` bi_bfs `=` `path``::`in_grid`(`
`4` `/*` source `*/``,`
`1` `/*` target `*/``,`
`&`grid`,`
`Box``::`from`(`BiBreadthFirstSearch `{``}``)``,` `/*` used algorithm `*/`
`)``;`
`}`

### Dijkstra path search

For graphs

`pub` `fn` `your_function``(``)`` ``{`
`let` dijkstra `=` `path``::`in_graph`(`
`4` `/*` source `*/``,`
`1` `/*` target `*/``,`
`&`graph`,`
`Box``::`from`(`Dijkstra `{``}``)` `/*` used algorithm `*/`
`)``;`
`}`

For grids

`pub` `fn` `your_function``(``)`` ``{`
`let` bi_bfs `=` `path``::`in_grid`(`
`4` `/*` source `*/``,`
`1` `/*` target `*/``,`
`&`grid`,`
`Box``::`from`(`Dijkstra `{``}``)``,` `/*` used algorithm `*/`
`)``;`
`}`

### A* path search

You can use the A* path-finding algorithm by providing either an existing heuristic function as shown below. Or you provide your own heuristic function. In case you use an existing heuristic function, make sure to provide the positional information for the nodes.

For graphs

`pub` `fn` `your_function_with_euclidean_distance``(``)`` ``{`
`let` a_star `=` `path``::`in_graph`(`
`4` `/*` source `*/``,`
`1` `/*` target `*/``,`
`&`graph`,`
`Box``::`from`(`AStar `{` heuristic`:` `Box``::`from`(`euclidean_distance`)` `}``)``,` `/*` used algorithm + euclidean distance heuristic function `*/`
`)``;`
`}`

`pub` `fn` `your_function_with_manhattan_distance``(``)`` ``{`
`let` a_star `=` `path``::`in_graph`(`
`4` `/*` source `*/``,`
`1` `/*` target `*/``,`
`&`graph`,`
`Box``::`from`(`AStar `{` heuristic`:` `Box``::`from`(`manhattan_distance`)` `}``)``,` `/*` used algorithm + manhattan distance heuristic function `*/`
`)``;`
`}`

For grids

`pub` `fn` `your_function_with_euclidean_distance``(``)`` ``{`
`let` a_star `=` `path``::`in_grid`(`
`4` `/*` source `*/``,`
`1` `/*` target `*/``,`
`&`grid`,`
`Box``::`from`(`AStar `{` heuristic`:` `Box``::`from`(`euclidean_distance`)` `}``)``,` `/*` used algorithm + euclidean distance heuristic function `*/`
`)``;`
`}`

`pub` `fn` `your_function_with_manhattan_distance``(``)`` ``{`
`let` a_star `=` `path``::`in_grid`(`
`4` `/*` source `*/``,`
`1` `/*` target `*/``,`
`&`grid`,`
`Box``::`from`(`AStar `{` heuristic`:` `Box``::`from`(`manhattan_distance`)` `}``)``,` `/*` used algorithm + manhattan distance heuristic function `*/`
`)``;`
`}`

### TBC: Hierarchical A* path search

Similar to the A* path-finding algorithm, you can provide either an existing heuristic function as shown in the previous section. Or you provide your own heuristic function. In case you use an existing heuristic function, make sure to provide the positional information for the nodes.

In addition to the functionality of A*, this algorithm will require you to pass the graph to the Hierarchical A* instance. The reason is simple, the algorithm will divide the graph into segments on creation and cache information required in the subsequent path-finding process.

`pub` `fn` `your_function_with_euclidean_distance``(``)`` ``{`
`let` a_star `=` `path``::`in_graph`(`
`4` `/*` source `*/``,`
`1` `/*` target `*/``,`
`&`graph`,`
`Box``::`from`(`HierarchicalAStar `{` heuristic`,` graph `}``)``,` `/*` used algorithm and graph `*/`
`)``;`
`}`

#### Dependencies

~3MB

~60K SLoC