N37: grid_pathfinding (rust-gamedev#1154)

tbvanderwoude · 17cupsofcoffee · web-flow · commit 1602928f9514 · 2022-09-20T01:13:49.000+01:00
Co-authored-by: Joe Clay &lt;27cupsofcoffee@gmail.com&gt;
diff --git a/content/news/037/index.md b/content/news/037/index.md
@@ -614,6 +614,31 @@ similarly to [`bevy_ecs`].
 [`System`]: https://docs.rs/edict/0.2.0-rc.3/edict/system/trait.System.html
 [`bevy_ecs`]: https://crates.io/crates/bevy_ecs
 
+### [grid_pathfinding]
+
+[grid_pathfinding] is a new pathfinding crate aimed at providing a fast,
+out-of-the-box system for pathfinding on various types of grids. While the
+current 0.1.1 release is not very configurable yet, the idea is to make the
+crate more malleable working towards a 0.2.0 release so that it will support
+a range of grids (4-connected, 8-connected, weighted, etc.) as well as
+heuristics. Specifically, [grid_pathfinding] 0.1 assumes a uniform-cost
+8-grid with a Chebyshev cost metric and heuristic. More long-term goals are
+support for multi-tile and multi-agent pathfinding variants.
+
+The current implementation is based on [Jump Point Search] with
+[improved pruning rules]. On top of this, [connected components] are used to
+avoid flood-filling behaviour if no path exists - see the
+[documentation][gp-docs] and [examples][gp-examples] for information on
+how to manage these components. Especially when simulating many agents in
+real-time, using components can make a big difference.
+
+[grid_pathfinding]: https://github.com/tbvanderwoude/grid_pathfinding
+[gp-docs]: https://docs.rs/grid_pathfinding/0.1.1/grid_pathfinding/
+[gp-examples]: https://github.com/tbvanderwoude/grid_pathfinding/tree/main/examples
+[Jump Point Search]: https://en.wikipedia.org/wiki/Jump_point_search
+[connected components]: https://en.wikipedia.org/wiki/Component_(graph_theory)
+[improved pruning rules]: https://www.researchgate.net/publication/287338108_Improving_jump_point_search
+
 ## Popular Workgroup Issues in Github
 
 <!-- Up to 10 links to interesting issues -->
