I have multiple meshes that represents the various wall/barrier tiles in my tilemap. Currently, polyanya only accepts one mesh that represents the entire map.
It would be nice if we can input multiple meshes instead.

create a mesh format:

• fast and easy to load
• that can store all baking and optimisations already done

Polyanya should be able to read and write this format

Hi! Recently did a small test to measure the performance and got very surprising results. (on aurora merged)

Average time per 1000 runs per 34707 verts: 336ms 231us 70ns
Average time per 1000 runs per 1000 verts: 9ms 889us 149ns
Average time per 1000 runs per 34707 verts (async): 217us 79ns
Average time per 1000 runs per 1000 verts (async): 6us 384ns

Can someone explain if maybe I did something wrong (see code below) or how the async version is so much faster? It doesn't look multithreaded, so how?

#![feature(core_intrinsics)]

use std::sync::Arc;

use glam::Vec2;
use humantime::format_duration;
use polyanya::{Mesh, PolyanyaFile};
use tokio::sync::RwLock;

fn run_and_measure<F: FnOnce() -> R, R>(f: F) -> (R, std::time::Duration) {
    let start = std::time::Instant::now();
    let result = f();
    let elapsed = start.elapsed();
    (result, elapsed)
}

#[tokio::main]
async fn main() {
    let mesh: Mesh = PolyanyaFile::from_file("meshes/aurora-merged.mesh").into();
    let mesh_min_x = mesh
        .vertices
        .iter()
        .map(|v| v.coords.x)
        .fold(f32::INFINITY, |a, b| a.min(b));
    let mesh_max_x = mesh
        .vertices
        .iter()
        .map(|v| v.coords.x)
        .fold(f32::NEG_INFINITY, |a, b| a.max(b));
    let mesh_min_y = mesh
        .vertices
        .iter()
        .map(|v| v.coords.y)
        .fold(f32::INFINITY, |a, b| a.min(b));
    let mesh_max_y = mesh
        .vertices
        .iter()
        .map(|v| v.coords.y)
        .fold(f32::NEG_INFINITY, |a, b| a.max(b));
    let width = mesh_max_x - mesh_min_x;
    let height = mesh_max_y - mesh_min_y;

    let runs = 10_000;
    let duration = run_and_measure(|| {
        for _ in 0..runs {
            let start_x = rand::random::<f32>() * width + mesh_min_x;
            let start_y = rand::random::<f32>() * height + mesh_min_y;
            let end_x = rand::random::<f32>() * width + mesh_min_x;
            let end_y = rand::random::<f32>() * height + mesh_min_y;

            std::intrinsics::black_box(
                mesh.path(Vec2::new(start_x, start_y), Vec2::new(end_x, end_y)),
            );
        }
    });

    let duration_per_1000_runs = duration.1 / (runs / 1_000);
    let vertices = mesh.vertices.len();
    println!(
        "Average time per 1000 runs per {} verts: {}",
        vertices,
        format_duration(duration_per_1000_runs).to_string()
    );

    let duration_per_1000_runs_per_1000_verts = duration_per_1000_runs / (vertices as u32 / 1_000);
    println!(
        "Average time per 1000 runs per 1000 verts: {}",
        format_duration(duration_per_1000_runs_per_1000_verts).to_string()
    );

    // Now try the async version
    let runs = 1_000_000;
    let rw_lock_mesh = Arc::new(RwLock::new(mesh));
    let duration = run_and_measure(|| {
        let mut futures = vec![];
        for _ in 0..runs {
            let start_x = rand::random::<f32>() * width + mesh_min_x;
            let start_y = rand::random::<f32>() * height + mesh_min_y;
            let end_x = rand::random::<f32>() * width + mesh_min_x;
            let end_y = rand::random::<f32>() * height + mesh_min_y;

            let rw_lock_mesh = rw_lock_mesh.clone();
            futures.push(async move {
                let mesh = rw_lock_mesh.read().await;
                std::intrinsics::black_box(
                    mesh.get_path(Vec2::new(start_x, start_y), Vec2::new(end_x, end_y))
                        .await,
                );
            });
        }
        futures::future::join_all(futures)
    });

    let duration_per_1000_runs = duration.1 / (runs / 1_000);
    println!(
        "Average time per 1000 runs per {} verts (async): {}",
        vertices,
        format_duration(duration_per_1000_runs).to_string()
    );

    let duration_per_1000_runs_per_1000_verts = duration_per_1000_runs / (vertices as u32 / 1_000);
    println!(
        "Average time per 1000 runs per 1000 verts (async): {}",
        format_duration(duration_per_1000_runs_per_1000_verts).to_string()
    );
}

Thanks for the answer in advance! Very interested in the details :P

For 2D pathfinding, the current Path type works fine, but if you want to do 3D pathfinding (with multiple overlapping floors etc.), the current interface is insufficient. In particular, I'm imagining that you project out the X and Y positions of each point in a mesh, which may result in duplicate points. Polyanya supports duplicate points and overlapping/zero-area triangles, at least from my experimentation, but since it only outputs a list of positions it's impossible to know which of many overlapping triangles a given element in a path is from (and therefore what its Z position is). If the indices of polygons traversed were included in the Path then this wouldn't be an issue.

I'm was getting errornous behaviour if error if obstacles overlap all of the initial outer boundary of the Polyana::Triangulation.
This resulted in an empty navmesh, because the merge_obstacle function has/had an error/wasn't intended to handle this case.
I think I solved this problem, althought I'm not sure if you want the changes there to be merged upstream, you might want some changes to be done.

Anyway if anyone has a similar problem, for the time beeing you can check if the branch/commit here is doing what you want: main...AnAverageGitUser:polyanya:aagu/myapp current commit 82f2ec7

It's not uncommon to have units of different sizes, and you might have areas of the navmesh that are accessible to smaller units but not larger units.

Ideally there'd be some way to pass in the unit radius when searching for a path, and it'd return a valid path for a unit of that size.

In the below image, a small unit would take the leftmost passage, a medium unit could go up, and a large unit has to go right and go all the way around.

(image from https://www.jdxdev.com/blog/2021/07/06/rts-pathfinding-2-dynamic-navmesh-with-constrained-delaunay-triangles/)

It might be possible to just compare the interval size against the unit radius, and reject intervals that are too small, but that might end up being too pessimistic (or I might be misremembering how polyanya works)?

It would be nice to support non-uniform cost pathfinding. For instance, agents would be able to avoid crossing water or other difficult terrain.

I don't know much about the algorithm inner workings, but I would imagine this would require being able to compute movement cost along any given line, which may or may not need another acceleration structure, and will certainly hurt performance. To avoid that, navmeshes could be made generic over the movement cost, with () being default.

Another option would be to support pathfinding over multiple navmeshes, connected by links, where each navmesh would have its own movement cost. This would have an added benefit of supporting chunked worlds, as well as multiple 3d levels.

Goal

Provide an example showcasing pathfinding interactivity.

Something as simple as possible, 2D, working on wasm should be the objective.

Existing work

Below showcases a 3d interactivity, which code might be relevant: https://github.com/Vrixyz/meshquisse)

I tried to build a project with polyanya as the dependency on a new machine and I got this error:

error: failed to select a version for the requirement `bvh2d = "^0.3"`
candidate versions found which didn't match: 0.4.0
location searched: Git repository https://github.com/mockersf/bvh2d
required by package `polyanya v0.4.0 (https://github.com/vleue/polyanya?branch=radius-baking#17e68a44)`       
    ... which satisfies git dependency `polyanya` of package `bevy_pathmesh v0.5.0 (https://github.com/vleue/bevy_pathmesh?branch=interactive#70d3c5f4)`

Checking the toml on polyanya shows, that it uses 0.3 and the git repository seems to be 0.3, but the cargo.toml show 0.4.

• find the biggest polygon in a mesh
• try to merge with its neighbour, keeping everything convex
• repeat until all done

In some circumstances I'm hitting an infinite loop when trying to generate a path. It seems to be related to the delta.

For example, with this mesh and a delta of 0.01:

mesh
2
10 8
3.775000 2.675000 2 -1 5
3.775000 1.175000 4 -1 4 5 7
2.125000 1.175000 6 -1 0 1 3 4 6
2.125000 1.275000 2 -1 0
1.775000 1.275000 3 -1 0 1
1.775000 1.175000 4 -1 1 2 3
0.375000 1.175000 2 -1 2
0.375000 0.375000 4 -1 2 3 6
4.075000 0.375000 4 -1 4 6 7
4.075000 2.675000 3 -1 5 7
3 4 2 3
3 5 2 4
3 7 5 6
3 5 7 2
3 1 2 8
3 0 1 9
3 7 8 2
3 8 9 1

These path fails to generate:

Creating path from Vec2(2.0705771, 1.2326102) to Vec2(2.074013, 1.0023998)
Creating path from Vec2(2.0911932, 1.2326102) to Vec2(2.7302842, 1.0573754)
Creating path from Vec2(1.8231869, 1.2119944) to Vec2(1.9846778, 0.93711627)

With a delta of 0.1, I can't get the infinite loop to happen on this mesh but these paths are wrong:

# should be direct but goes via a vertex
Creating path from Vec2(1.9406888, 1.1835598) to Vec2(2.0856483, 0.85704863)

# goes outside grid
Creating path from Vec2(2.1137958, 1.2623727) to Vec2(3.8983479, 1.3031867)

With all that said, I'm assuming there is something wrong with the mesh but as far as I can tell, it is valid based on the documentation. For reference it looks like this with the failures generally happening with polygons 0 and 1:

Hi, your link to the WASM demo links back to the static web page, no WASM demo.

https://vleue.github.io/bevy_pathmesh/

I'm curious about what are the requirements for a given polygon.

To clarify, why not just create a single polygon containing all of the points for the example in the README? I presume this is invalid somehow.

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

Right now, from and to in the path finding can be off by up to 0.1 from any vertex in the path mesh. This value seems arbitrary, as the size of the mesh can vary greatly by use case. It seems it would be useful to change this offset, e.g. you could set it to 1 if you knew that your mesh is guaranteed to have a vertex every 1 unit.

possible solution from recast: steps 3 to 5 of https://9631ec60-a-62cb3a1a-s-sites.googlegroups.com/site/recastnavigation/MikkoMononen_RecastSlides.pdf

• watershed partitioning to find regions
• contour the regions to get polygons
• triangulate the polygons to get a trimesh

When creating a mesh file using PolyanyaFile it creates the file mostly to spec but doesn't include the polygon neighbours as defined here.

Using the same example, instead of the expected

mesh
2
4 2
0.0 0.0 2 0 -1
1.5 0.0 3 0 1 -1
1.5 1.5 2 1 -1
0.0 1.5 3 -1 1 0
3 0 1 3 -1 -1 1
3 1 2 3 0 -1 -1

it writes

mesh
2
4 2
0.0 0.0 2 0 -1
1.5 0.0 3 0 1 -1
1.5 1.5 2 1 -1
0.0 1.5 3 -1 1 0
3 0 1 3
3 1 2 3

Loading this file then fails this assert

assert!(data.len() == nb * 2);

While removing this assert does allow the file to be loaded, the one-way flag is wrong as it defaults to true when there are no neighbours.

I saved the file with this code:

        let mut mesh = PolyanyaMesh::new(vertices, polygons);
        let file: PolyanyaFile = mesh.clone().into();
        file.to_file(&"nav_mesh.mesh");