Gametools v0.11.0

announcements
1

Hi rust-lang --

I just published v0.11.0 of `gametools` (github) (crates), which is a library I've been gradually building to aggregate structures and algorithms I finding to be frequently useful in game and simulation programming.

This release's high points:

  1. pathfinding module, implementing Dijkstra maps, standard A*, weighted A*, and dynamically weighted A* over a Grid<T> (see #3 below). The pathfinders accept arbitrary move sets, so you can calculate paths for things that move irregularly (think chess knight) just as easily as those that can only move to a neighboring cell.

  2. fov module. The two most common algorithms (perimeter raycasting and recursive shadowcasting) for field-of-view are implemented over Grid<T>. A third algorithm using preprocessed blocking rectangles is also implemented, described in a 2021 paper by Debenham and Solis-Oba which is reported to be more performant at scale -- though I confess I haven't had a good platform to test that claim directly. At the scales I've been able to test, all three algorithms seem to behave similarly. I haven't seen the rectangular algorithm in other pathfinding crates, though I very well may have missed one somewhere.

  3. Toroidal geometry for Grid<T>. In previous versions Grid<T> could only represent bounded regions. It now supports wrapping geometry, and the pathfinding algorithms also work correctly either way.

I couldn't figure out how to make the FOV algorithms work over a toroid. In theory, almost any ray cast from any point would infinitely wrap around and cover every point on the toroid. You could see something behind an opaque object in front of you just by looking to the side.

So, I leave FOV over a toroid as an "exercise for the reader".

2 Likes