Skip to content

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

@dqnhat

Description

@dqnhat

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:

  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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions