$ show vleue/polyanya
This is a Rust library implementing the Polyanya any-angle pathfinding algorithm on navigation meshes. It provides a core `Mesh` struct that supports 2D and 3D pathfinding with multiple overlapping layers, agent radius, and path simplification. The library includes several input formats: custom `.mesh` files (v2/v3), Recast JSON navigation meshes, triangulated meshes from outer edges and obstacles (via CDT), and trimesh files. It features an optimized A* search with chained expansions, geometric predicates for cone clipping and vertex snapping, and precomputed BVH for efficient point location. The repository contains extensive benchmarks, fuzz tests, and example binaries (including a scenario runner and traced profiling examples). It is structured as a reusable library with optional features like async, serde, stats, tracing, and Recast import. The code demonstrates strong engineering practices with careful handling of floating-point edge cases and performance-critical sections using `SmallVec` and `unsafe` indexing.
The LLM identified 2 files worth highlighting for reuse:
A collection of geometric helper functions (side, mirror, on_segment, heuristic, intersection_time, clip_to_cone, lands_on, snap_to_edge_end) used in the pathfinding search. These functions are self-contained, depend only on standard Vec2 and math, and implement non-obvious geometric reasoning (e.g., wedge narrowing, vertex tolerance). They can be extracted and reused in any geometric or pathfinding project without internal dependencies.
A module that builds a navigation mesh triangulation from an outer boundary polygon and a list of obstacle polygons using Constrained Delaunay Triangulation (via the `spade` crate). It supports agent radius inflation (shrinking/expanding obstacles) and simplification. The logic is isolated, parameterized, and produces a `Triangulation` struct that can be converted into a navmesh. This pattern is reusable for any project needing to convert 2D polygonal maps into triangulated navigation meshes.