lazy_pathfinding

This Deno library implements several pathfinding and graph algorithms.

Where possible, this library does not need an entire graph to be provided to it ahead of time. Many functions allow nodes and edges to be provided by a successor function executed for each node encountered, meaning that graphs are lazily initialized which allows for procedural and infinite graphs to be used.

Algorithms

The algorithms are generic over their arguments.

Directed graphs

• A*: find the shortest path in a weighted graph using an heuristic to guide the process.
• Dijkstra: find the shortest path in a weighted graph.

Undirected graphs

• connected components: find disjoint connected sets of vertices.

Documentation

See the generated docs at https://deno.land/x/lazy_pathfinding?doc.

Using this library

import { aStar } from "https://deno.land/x/lazy_pathfinding/directed/a_star.ts";

Related Projects

This project was ported from the Rust pathfinding library.

License

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

Contributing

You are welcome to contribute by opening issues or submitting pull requests.

Implementations of additional similar graph algorithms, especially those in the Rust pathfinding library, are welcome.