donmccurdy / donmccurdy/three-pathfinding

Portals order in upside down poly make string pull algorithm not work as intended

Open
#319 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
JavaScript
Stars
1.4k
Forks
140
PR merge metrics
No merged PRs in 30d

Description

I read in the simple path test you have:

```
test('simple path', (t) => {
const pathfinding = new Pathfinding();
const geometry = new THREE.RingGeometry(5, 10, 8).applyMatrix4(ROTATE);
const zone = Pathfinding.createZone(geometry);
pathfinding.setZoneData(ZONE, zone);
const a = new THREE.Vector3(7.5, 0, 0);
const b = new THREE.Vector3(-7.5, 0, 0);
...
});
```

when re-creating the test, i found path-finding to return a 6 node path:
```
P1( 7.07, 0, 7.07)
P2( 7.07, 0, 7.07)
P3( 0, 0, 10)
P4( 0, 0, 10)
P5(-7.07, 0, 7.07)
P6( -7.5, 0, 0)
```

visualize:

Image

view from below:

Image

Not only does pathfinding return duplicate node but also a longer path (it follow the outter ring).
I belived this is cause by the order of portal created in [Builder.js](https://github.com/donmccurdy/three-pathfinding/blob/main/src/Builder.js):
```
static _getSharedVerticesInOrder (a, b) {
...
// it seems that we shouldn't have an a and b with <2 shared vertices here unless there's a bug
// in the neighbor identification code, or perhaps a malformed input geometry; 3 shared vertices
// is a kind of embarrassing but possible geometry we should handle
if (shared0 && shared1 && shared2) {
return Array.from(aList);
} else if (shared0 && shared1) {
return [a0, a1];
} else if (shared1 && shared2) {
return [a1, a2];
} else if (shared0 && shared2) {
return [a2, a0]; // this ordering will affect the string pull algorithm later, not clear if significant
} else {
console.warn("Error processing navigation mesh neighbors; neighbors with <2 shared vertices found.");
return [];
}
}
```

when the ring is navmesh is created, the order of portal is using the local up (which is pointing downward), but when running the string pull algorithm, channel is using the world up, which cause `pts` to take all the `portal.left`, hence the error.

if fix, this, the `simple path` test should also be fix to have 4 node on path.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.