Version 0.11.0
This marks the official release of two new modules for pathfinding and FOV calculations. It also adds support for toroidal (wrapping) geometry for grid::Grid<T>. The pathfinding and fov modules have been available in the repo for a month or two already, but hadn't been published in an official release yet.
pathfinding module
Contains types and functions used for... you guessed it... finding paths. These use Grid from the grid module to represent the available space.
Dijkstra maps
These calculate the distance from every point on the map to the nearest of a set of targets, or goals. They can be used to find a guaranteed optimal path from any point to a goal, but are sometimes also used to represent things like radiation of heat or scent.
A MoveSet, which is a set of PointDelta relative to a start point, tells the Dijkstra and other pathfinding algorithms in the module about valid moves, so the result is correct whether the mover can go in cardinal directions, or diagonal, or both, or any arbitrary pattern including jumping other spaces (like a knight in chess, for example.)
A Star
No pathfinding module would be complete without it. Several different versions are made available here: Standard A*, Weighted A*, and Dynamically Weighted A*. Weighted A* uses a weight to adjust the influence of the heuristic on the algorithm. Heavier reliance on the heuristic helps to narrow the search space but also tends to lead to less optimal paths. Zero weight on the heuristic would cover the entire search space and yield the guaranteed optimal path -- but at that point is identical to Dijkstra. Dynamically weighted A* changes the heuristic weight as the path nears the goal as a way to balance these approaches.
fov module
These are functions for calculating the field of view or line of sight from any point on a Grid<T>. A boolean visibility grid must be provided, indicating which cells in the grid are opaque. A FovMap is returned, which is a boolean map indicating which cells can be "seen" from the origin cell. Each algorithm has an _into() version that will reuse an existing FovMap, avoiding need for any allocation when the FOV is changing rapidly in a hot loop. Three different algorithms are included:
Perimeter Raycasting
One of the more common algorithms used for this. Walks cells around a defined perimeter and casts a "ray" from the viewpoint to each one, marking cells behind an opaque cell as invisible. Straightforward and perfectly useful on small maps.
Recursive Shadowcasting
Another very common algorithm, useful on small to moderate sized maps. It optimizes a bit over direct raycasting by recursively splitting the surroundings into octants and skipping cells in angular "shadowed" regions behind blockers.
Rectangular FOV
This is one I haven't seen in other pathfinding crates and should perform well on much larger maps. It's based on an algorithm presented in a 2021 paper by Debenham and Solis-Oba. It utilizes pre-processed blocking rectangles, then recalculates shadows cast by those rectangles on each FOV call. Being pre-processed, the rectangles must be regenerated whenever there are any changes to visibility geometry.
Enhanced Grid
Grid now supports use of toroidal (wrapping) geometry (and also a regular bounded grid, as before). The top / bottom and left / right edges of the grid connect in the toroidal case, effectively wrapping the grid over the outside of a "donut".
Toroidal Pathfinding -- but not FOV
The pathfinding algorithms are implemented to work correctly on the toroidal geometry, but not FOV. Most lines of sight could conceptually spiral around the "donut" and cover every point on the grid from any angle and continue infinitely. I have no idea how you'd tackle that problem.