Emit polygon path

[taktoa]

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.

[taktoa]

Hmm, looks like I was mistaken and Polyanya only supports duplicate points and zero-area triangles, but not overlapping triangles.

[gmorenz]

Polyanya with overlapping meshes!

output.webm

This is on a local fork where I've converted everything to use indices to uniquely identify points instead of Vec2s. The purpose of this demo was actually just to double check that that was working as expected.

[mockersf]

I also have something working for overlapping meshes in #62

layers.mp4

This is still working with Vec2s. @gmorenz did you continue with your demo? Did you put it somewhere on GitHub?

[gmorenz]

I didn't continue with my demo. The math I thought would work to generalize this to non-uniform-cost movement didn't pan out as I expected (which was actually what I was more interested in at the time), and after hitting a dead end there I moved on for the time being.

I'm happy to push the non-planar demo to github tomorrow

[mockersf]

The math I thought would work to generalize this to non-uniform-cost movement didn't pan out as I expected (which was actually what I was more interested in at the time), and after hitting a dead end there I moved on for the time being.

I have something that works for that now, see this test:

polyanya/src/stitching.rs

Line 899 in c74391b

fn path_with_different_scales() {

it's setting up a navmesh with 5 layers like so:

00
13
23
44

with layers 1 and 2 having a higher cost of traversal than layer 3, then for 20 points equally distributed in a line in layer 0, find the path to the corresponding points in layer 4. The path correctly goes either through slower layers or around them depending on the cost.

@taktoa to support overlapping polygons I added the notion of "layer" that can be connected at some of their vertices. The path with the layer information can be retrieved when feature detailed-layers is enabled, as it can be costly

polyanya/src/lib.rs

Lines 64 to 66 in c74391b

	/// Coordinates for each step of the path, including when changing layer. The destination is the last step.
	#[cfg(feature = "detailed-layers")]
	pub path_with_layers: Vec<(Vec2, u8)>,

Does that work for you?