Function findRoute

packages/joint-core/src/routers/manhattan.mjs:560–743

(from, to, isPointObstacle, opt)

// finds the route between two points/rectangles (`from`, `to`) implementing A* algorithm
// rectangles get rect points assigned by getRectPoints()
function findRoute(from, to, isPointObstacle, opt) {

    var precision = opt.precision;

    // Get grid for this route.

    var sourceAnchor, targetAnchor;

    if (from instanceof g.Rect) { // `from` is sourceBBox
        sourceAnchor = round(getSourceAnchor(this, opt).clone(), precision);
    } else {
        sourceAnchor = round(from.clone(), precision);
    }

    if (to instanceof g.Rect) { // `to` is targetBBox
        targetAnchor = round(getTargetAnchor(this, opt).clone(), precision);
    } else {
        targetAnchor = round(to.clone(), precision);
    }

    var grid = getGrid(opt.step, sourceAnchor, targetAnchor);

    // Get pathfinding points.

    var start, end; // aligned with grid by definition
    var startPoints, endPoints; // assumed to be aligned with grid already

    // set of points we start pathfinding from
    if (from instanceof g.Rect) { // `from` is sourceBBox
        start = sourceAnchor;
        startPoints = getRectPoints(start, from, opt.startDirections, grid, opt);

    } else {
        start = sourceAnchor;
        startPoints = [start];
    }

    // set of points we want the pathfinding to finish at
    if (to instanceof g.Rect) { // `to` is targetBBox
        end = targetAnchor;
        endPoints = getRectPoints(targetAnchor, to, opt.endDirections, grid, opt);

    } else {
        end = targetAnchor;
        endPoints = [end];
    }

    // take into account only accessible rect points (those not under obstacles)
    startPoints = startPoints.filter(p => !isPointObstacle(p));
    endPoints = endPoints.filter(p => !isPointObstacle(p));

    // Check that there is an accessible route point on both sides.
    // Otherwise, use fallbackRoute().
    if (startPoints.length > 0 && endPoints.length > 0) {

        // The set of tentative points to be evaluated, initially containing the start points.
        // Rounded to nearest integer for simplicity.
        var openSet = new SortedSet();