# Polyanya, an any-angle path planner for Rust that returns optimal paths on a navmesh

> polyanya is a Rust implementation of the Polyanya algorithm for any-angle path planning over navigation meshes, with multi-layer navmesh support for overlapping floors, one-way layers and per-layer traversal costs. It suits game developers who need short diagonal paths rather than grid-aligned ones, and it expects you to supply the navmesh rather than bake one from a level.

**vleue/polyanya** — Pathfinding using Polyanya

- Repository: https://github.com/vleue/polyanya
- Stars: 522 · Forks: 44
- Language: Rust
- License: Apache-2.0
- Published: 2026-10-22 · Updated: 2026-10-22 · Language: en
- Canonical page: https://hysenlabs.com/projects/vleue-polyanya

## Any-angle paths, and what that changes about a move

polyanya is a Rust implementation of Polyanya, the algorithm described in a 2017 IJCAI paper, and the README describes Polyanya as an any-angle path planning algorithm.

Any-angle is the whole point. Most navigation approaches quantise the world into a grid or into a set of convex polygons, and a path through that structure is constrained to travel along the edges of the cells. An agent walking such a path moves in what is effectively a small set of directions, and the result is the classic diagonal staircase across a room. An any-angle planner works directly on the polygonal geometry and produces a path whose corners can sit anywhere, so an agent walking from a door to a desk takes a straight line rather than a series of grid steps.

That matters in a game because the visual difference between the two is obvious to players. A grid-constrained path also constrains movement code, since the agent's heading snaps to the discrete directions, and it constrains animation, since the same stair-stepping shows up in the walk cycle.

The other part of the promise is optimality rather than approximation. The Cargo.toml describes the crate as fast, optimal any-angle pathfinding on navigation meshes, and the crate is categorised under game-development and algorithms.

There are also WebAssembly demos made with Bevy, linked from the README, which give you a way to see the algorithm's output without wiring it into a project first. The homepage of the crate is vleue.github.io/vleue_navigator.

## Building a mesh from its outer edges, then asking for a path

The README's primary example builds a navigation mesh by specifying its outer edges, then asks for a path between two points.

```rust
let mesh = triangulation.as_navmesh();

// Get the path between two points
let from = vec2(12.0, 0.0);
let to = vec2(3.0, 1.0);
let path = mesh.path(from, to);

assert_eq!(
    path.unwrap().path,
    vec![
        vec2(7.0, 4.0),
        vec2(4.0, 2.0),
        vec2(3.0, 1.0)
    ]
);
```

The preceding part of that example constructs a Triangulation from a list of outer edge points and converts it with as_navmesh(). The points are given with glam's vec2, so the crate expects two-dimensional geometry as glam vectors, which is the same type the Bevy engine uses, and that is why the WASM demos can be built with Bevy without a conversion layer.

The API shape is worth noting. mesh.path(from, to) returns an Option, and the path is a sequence of points rather than a list of indices into a waypoint graph. The assertion in the example shows the expected result for that mesh: three points, from the start through an intermediate corner to the destination.

The Option is the part to design around. A path can fail, and the README does not describe the failure modes in detail, so a caller needs to decide what happens when a point is outside the mesh or when no route exists. Since the assertion unwraps, the example only covers the success path.

## Manual vertices and polygons, when the edges are not enough

The README notes that meshes can also be built by manually specifying vertices and polygons for complete control, and that the following produces the same mesh as the outer-edge example.

The polygon list is the part that shows the data model:

```rust
    vec![
        Polygon::new(vec![0, 1, 2, 3, 4], true),           // 0
        Polygon::new(vec![5, 22, 6, 7, 8, 9], true),       // 1
        Polygon::new(vec![1, 9, 8, 10, 11, 12, 2], false), // 2
        Polygon::new(vec![12, 11, 13, 14], true),          // 3
        Polygon::new(vec![10, 15, 16, 17, 11], false),     // 4
        Polygon::new(vec![15, 18, 19, 16], true),          // 5
        Polygon::new(vec![11, 17, 20, 21], true),          // 6
    ],
).unwrap();
```

Two things are encoded here. Each polygon references vertices by index, and the whole mesh is a vertex table plus a polygon table. The boolean argument on Polygon::new distinguishes the two kinds of polygon in the set, and the example mixes them, with polygons 2 and 4 marked false and the rest true.

The vertices in the earlier part of the example carry a similar structure. Each Vertex::new takes a position and a list of neighbouring vertex indices, with u32::MAX used as the terminator. So adjacency is explicit in the data rather than derived, which is what makes a hand-built mesh possible without running a triangulation step.

Mesh::new returns a Result and the example unwraps it, which tells you the construction validates its input. The cost of the manual route is that you are responsible for the consistency of those tables: a polygon referencing a vertex index that does not exist, or an adjacency list that contradicts the geometry, is a validation error rather than a silently wrong path.

The rendered result is in the repository as example-mesh.png, with polygons marked in green and vertices in red, and the source of that artwork is example-mesh.aseprite at the repository root.

## Multi-layer navmeshes, one-way layers and per-layer costs

The second feature in the README's list is multi-layer navigation mesh support, and it is the part that separates this from a single-mesh planner.

Overlapping navmeshes for 3D navigation is the headline case. A level with a ground floor, a bridge and an upper storey is three overlapping meshes, and an agent needs to move between them, which means the planner has to know that a layer exists above and that a path can cross into it.

One-way layers cover directional movement, so a ledge can be traversable in one direction only. Conditional layer traversal with the ability to enable or disable layers means a layer's availability can depend on state, which is how a drawbridge or a lift gets modelled. And layers with different traversal costs allow more realistic pathfinding, where crossing a hazardous area or climbing a set of stairs carries a different cost from walking across a floor.

That last point is the one with the most design consequence. A single-cost mesh produces the shortest path in distance. A layered mesh with per-layer costs produces the cheapest path according to the costs you assign, and the two are not the same thing. Assigning a high cost to a dangerous or slow layer will route agents around it, which is a behaviour you cannot express with a flat mesh.

The feature list also notes that this crate can be used for pathfinding using Polyanya as an efficient any-angle path planning algorithm for navigation meshes, which is the core feature stated first.

The layers are also gated behind a Cargo feature. The manifest lists default = ["async", "recast"], with stats, verbose, async, no-default-baking, detailed-layers and serde as separate entries, and the serde feature pulls in serialisation support for glam, rstar and serde itself.

## Benchmarks, feature flags and the known rough edges

The README compares against the original C++ implementation, and the comparison is unusually candid.

The crate is an implementation of Polyanya in Rust, and the README points to the cpp implementation under the pathfinding repository on Bitbucket. The published output for the same scenario is:

```text
index;micro;successor_calls;generated;pushed;popped;pruned_post_pop;length;gridcost
0;4960.92;6974;4368;4313;3823;21;1123.222637572437;1199.73
```

The README's reading is that this crate seems to generate a few more nodes, but tends to be faster than the cpp implementation. So the trade is more nodes generated for less time spent, which is a reasonable outcome for a language with different inlining characteristics, and the node count is what an implementation detail trade usually looks like.

Compiling the crate with the feature stats will output almost the same level of information as the default cpp implementation output, and the crate's own numbers under that flag are:

```text
index;micros;successor_calls;generated;pushed;popped;pruned_post_pop;length
0;2990.083;6983;7748;4314;3828;21;1123.2228
```

The verbose feature gives the same output as setting verbose to 1 in the original C++ scenario runner, and the README shows what that looks like, a per-node trace of pushing and popping search nodes with their root, left and right interval points and their f and g values.

Then there are the four known cases the README says still need improvement. Collinear optimisation, when a search node root and interval are all on a same line. Triangle optimisation, when searching in a triangle polygon. When an intersection is very close to a vertex, it sometimes generates an extra slim search node. And searching start and end nodes is costlier.

That last one is worth internalising, because it lands exactly where a game loop feels it. A search that begins and ends on a node costs more than the same search in the middle of a mesh, which means the cost of a path request is not uniform across the level.

The repository layout backs up that this is a working library rather than a demo. There are benches/ with named benchmarks for path, no_path, is_in_mesh, baking, triangulation, merger and recast, scenarios/ with test scenarios, meshes/ with mesh data, examples/ including a scenario_runner.rs and an aurora.rs, and a separate workspace member at examples/traced. The dev dependencies include criterion through codspeed-criterion-compat, and tracing-tracy for a traced build.

## Adding polyanya to a Cargo project, and the feature flags that shape it

There is no install command to run here, because polyanya is a library crate rather than an application. The Cargo.toml at the repository root is the package manifest, and the crate is published on crates.io as polyanya with the API documentation on docs.rs.

The part of the manifest you need to decide on is the feature list, because the defaults are not neutral:

```toml
[features]
default = ["async", "recast"]
stats = []
verbose = []
async = []
no-default-baking = []
detailed-layers = []
serde = ["glam/serde", "rstar/serde", "dep:serde", "rerecast?/serialize"]
recast = ["dep:rerecast"]
```

The default set is async and recast. Turning off recast, either by disabling default features or by using the no-default-baking feature, removes the recast-based mesh baking dependency, which is what you want if your pipeline produces navigation meshes some other way. The stats and verbose features control the diagnostic output described earlier, and detailed-layers enables the finer-grained layer behaviour. The serde feature pulls serialisation support through glam, rstar and serde itself, and also through rerecast where that dependency is present.

The dependency list itself is small and tells you what the geometry is built on. glam provides the vector types, spade provides the spatial data structure, rstar provides the spatial index, geo provides the geometry primitives, hashbrown and smallvec provide the container types, and thiserror and log handle errors and diagnostics. rstar is behind the serde feature, which is why the feature lists it explicitly.

The version in the manifest is 0.17.1, the edition is 2021, and the licence is MIT OR Apache-2.0 with both LICENSE-APACHE and LICENSE-MIT in the repository.

## Where polyanya is the wrong choice

There are clear cases where this crate does not fit, and they come down to what you have to supply and what you need back.

The first is if you need the mesh baked for you from level geometry. The crate's default features include recast, which is the recast navigation mesh generator, so a baking path exists through the rerecast dependency. But the README's own examples construct meshes by hand from outer edges or from explicit vertex and polygon tables, and there is a no-default-baking feature for those who want to bring their own. A project whose designers author levels in a level editor and expect a pipeline from that format to a mesh has work in front of it, and the recast integration is the thing to investigate first rather than assume.

The second is dynamic geometry. A navmesh is static structure, and a crate that plans paths over it does not move the geometry. A game with destructible walls or doors that open and close needs either a layer toggle, which the conditional layer support gives you, or a mesh rebuild.

The third is if you are not on a navmesh problem at all. Polyanya plans over polygonal surfaces in two dimensions. A project whose navigation is genuinely three dimensional, with vertical movement and stacked geometry that is not layered navigation, is a different problem.

The fourth is the C++ comparison itself. The README says the Rust crate tends to be faster but generates a few more nodes, and it lists four cases still to improve. If you are porting an existing C++ pipeline, the honest read is that the Rust implementation is a reasonable target with known gaps, not a drop-in with a guarantee.

For comparison, the alternatives differ in approach. A grid-based A* with a string-pulling pass afterwards produces near-optimal paths too, at the cost of a quantisation step and a post-process that is itself a source of bugs. A visibility graph over the polygon's vertices gives optimal any-angle paths in simple scenes, but the graph grows with the vertex count and needs its own handling for dynamic geometry. Recast gives you a baked mesh from a level and a tiled pathfinder that is fast but grid-aligned.

Polyanya's position is the one where you already have clean polygonal geometry and want the path to be optimal and diagonal without a post-process.

## Conclusion

Adopt polyanya if your Rust project needs optimal any-angle paths over a navigation mesh and you already have, or can produce, mesh geometry, since the algorithm returns paths that cut corners diagonally instead of following grid lines. Do not adopt it if you need the mesh baked from a level, since the crate's own default features bring in a recast-based baking path but the README shows construction from explicit edges or vertices, and the algorithm's own limits are documented. Before you commit, read the Original Work section, which lists four known cases that still need work, including collinear optimisation and searching start and end nodes being costlier. The licence is MIT OR Apache-2.0, the crate version is 0.17.1, the latest release is polyanya-v0.17.1 from 2026-08-25, and the last push was on 2026-10-13.

## FAQ

### What is polyanya and what does it do?

It is a Rust implementation of the Polyanya algorithm for any-angle path planning over navigation meshes, and the Cargo.toml describes it as fast, optimal any-angle pathfinding on navigation meshes. It is aimed at game development and is categorised under game-development and algorithms.

### How do I build a navigation mesh in polyanya?

Either from its outer edges with Triangulation::from_outer_edges followed by as_navmesh(), or manually by specifying vertices and polygons with Mesh::new. The manual route gives complete control, with each vertex carrying its position and neighbour indices and each polygon referencing vertices by index.

### What does multi-layer navmesh support give me in polyanya?

Overlapping navmeshes for 3D navigation such as floors and bridges, one-way layers for directional movement, conditional layer traversal that can be enabled or disabled, and layers with different traversal costs for more realistic pathfinding.

### How does polyanya compare with the original C++ implementation?

The README says the Rust crate seems to generate a few more nodes but tends to be faster than the cpp implementation, and it lists four known cases still to improve: collinear optimisation, triangle optimisation, an extra slim search node when an intersection is very close to a vertex, and searching start and end nodes being costlier.

### What do the stats and verbose Cargo features do in polyanya?

Compiling with the stats feature outputs almost the same level of information as the default cpp implementation output, and the verbose feature gives the same output as setting verbose to 1 in the original C++ scenario runner, printing a per-node trace of pushed and popped search nodes.

### What licence is polyanya released under?

MIT OR Apache-2.0, as set in the Cargo.toml license field, with LICENSE-MIT and LICENSE-APACHE files in the repository root. The crate version is 0.17.1 and the latest published release is polyanya-v0.17.1 from 2026-08-25.

## Sources

- [Issues](https://github.com/vleue/polyanya/issues)
- [License: Apache-2.0](https://github.com/vleue/polyanya/blob/main/LICENSE)
- [README](https://github.com/vleue/polyanya/blob/main/README.md)
- [Releases](https://github.com/vleue/polyanya/releases)
- [vleue/polyanya on GitHub](https://github.com/vleue/polyanya)

---

Hysen Labs editorial analysis, written from the project's own repository and release notes. Cite the canonical page: https://hysenlabs.com/projects/vleue-polyanya