@tscircuit/routing - npm Package Compare versions

Comparing version 1.3.1 to 1.3.2

dist/index.d.ts

@@ -8,2 +8,3 @@ interface LogContextTree {
     info: any;
+    verbose?: boolean;
     start: (info: any) => void;
@@ -25,8 +26,6 @@ child: (name: string) => LogContextTree;
     y: number;
+    directionBias?: "up" | "down" | "left" | "right";
 };
 type Path = {
-    points: Array<{
-        x: number;
-        y: number;
-    }>;
+    points: Array<Point>;
     width: number;
@@ -56,3 +55,3 @@ };
 type PathFindingParameters = {
-    pointsToConnect: Point[];
+    pointsToConnect: readonly Point[];
     obstacles: Obstacle[];
@@ -59,0 +58,0 @@ grid: Grid;

dist/index.js

@@ -80,3 +80,4 @@ var __create = Object.create;
 var createLogContextTree = ({
-  loudEnd
+  loudEnd,
+  verbose
 } = {}) => {
@@ -101,3 +102,6 @@ const tree = {
     const child = createLogContextTree();
+    if (verbose)
+      console.log(`>${name}`);
     child.name = name;
+    child.verbose = verbose;
     tree.children.push(child);
@@ -270,2 +274,5 @@ return child;
   }
+  if (borderPoints.length === 0) {
+    return [];
+  }
   const contiguousBorderPoints = [[borderPoints[0]]];
@@ -400,2 +407,5 @@ for (let i = 1; i < borderPoints.length; i++) {
   if (remainingSegDist <= grid.maxGranularSearchSegments) {
+    console.log(
+      "skipping mixed granularity, route is within max granular search segments"
+    );
     const granRoute = findTwoPointGranularRoute({
@@ -528,2 +538,23 @@ pointsToConnect,
 
+// src/lib/remove-unnecessary-points.ts
+var removeUnnecessaryPoints = (points) => {
+  if (points.length <= 3)
+    return points;
+  const newPoints = [points[0]];
+  for (let i = 1; i < points.length - 1; i++) {
+    const P = newPoints[newPoints.length - 1];
+    const A = points[i];
+    const B = points[i + 1];
+    if (P.x === A.x && A.x === B.x) {
+      continue;
+    }
+    if (P.y === A.y && A.y === B.y) {
+      continue;
+    }
+    newPoints.push(A);
+  }
+  newPoints.push(points[points.length - 1]);
+  return newPoints;
+};
+
 // src/lib/is-intersecting-obstacle.ts
@@ -580,24 +611,18 @@ var isIntersectingObstacle = (params) => {
 
-// src/lib/remove-unnecessary-points.ts
-var removeUnnecessaryPoints = (points) => {
-  if (points.length <= 3)
-    return points;
-  const newPoints = [points[0]];
-  for (let i = 1; i < points.length - 1; i++) {
-    const P = newPoints[newPoints.length - 1];
-    const A = points[i];
-    const B = points[i + 1];
-    if (P.x === A.x && A.x === B.x) {
-      continue;
-    }
-    if (P.y === A.y && A.y === B.y) {
-      continue;
-    }
-    newPoints.push(A);
-  }
-  newPoints.push(points[points.length - 1]);
-  return newPoints;
+// src/lib/remove-unnecessary-turns.ts
+var isAlignedWithDirectionBias = (A, B) => {
+  if (A.directionBias === "right")
+    return B.x > A.x;
+  if (A.directionBias === "left")
+    return B.x < A.x;
+  if (A.directionBias === "up")
+    return B.y > A.y;
+  if (A.directionBias === "down")
+    return B.y < A.y;
+  return true;
 };
-
-// src/lib/find-two-point-schematic-route.ts
+var getFlippedMiddlePoint = (A, B, C) => A.x === B.x ? { x: C.x, y: A.y } : {
+  x: A.x,
+  y: C.y
+};
 var removeUnnecessaryTurns = ({
@@ -613,3 +638,24 @@ points,
   }
-  const newPoints = [points[0], points[1]];
+  let newPoints = [points[0], points[1]];
+  if (points[0].directionBias) {
+    const [A, B, C] = points;
+    if (!isAlignedWithDirectionBias(A, B)) {
+      const flipped2ndPoint = getFlippedMiddlePoint(A, B, C);
+      if (isAlignedWithDirectionBias(A, flipped2ndPoint) && !isIntersectingObstacle({ obstacles, points: [A, flipped2ndPoint, C] })) {
+        newPoints = [A, flipped2ndPoint];
+      }
+    }
+  }
+  if (points[points.length - 1].directionBias) {
+    const [A, B, C] = points.slice(-3);
+    if (!isAlignedWithDirectionBias(C, B)) {
+      const flipped2ndLastPoint = getFlippedMiddlePoint(A, B, C);
+      if (isAlignedWithDirectionBias(C, flipped2ndLastPoint) && !isIntersectingObstacle({
+        obstacles,
+        points: [A, flipped2ndLastPoint, C]
+      })) {
+        points[points.length - 2] = flipped2ndLastPoint;
+      }
+    }
+  }
   for (let i = 1; i < points.length - 3; i++) {
@@ -628,12 +674,6 @@ const P = newPoints[i - 1];
     }
-    const B_opt = A.x === B.x ? { x: C.x, y: A.y } : {
-      x: A.x,
-      y: C.y
-    };
+    const B_opt = getFlippedMiddlePoint(A, B, C);
     const newPathPossible = !isIntersectingObstacle({
       obstacles,
-      points: [A, B_opt]
-    }) && !isIntersectingObstacle({
-      obstacles,
-      points: [B_opt, C]
+      points: [A, B_opt, C]
     });
@@ -650,2 +690,4 @@ if (newPathPossible) {
 };
+
+// src/lib/find-two-point-schematic-route.ts
 var findTwoPointSchematicRoute = ({
@@ -667,2 +709,19 @@ grid,
     return { pathFound: false };
+  for (const pointToConnect of pointsToConnect) {
+    if (!pointToConnect.directionBias)
+      continue;
+    const nearestPoint = route.points.reduce(
+      (nearest, point) => {
+        const dist = Math.hypot(
+          point.x - pointToConnect.x,
+          point.y - pointToConnect.y
+        );
+        if (dist < nearest.dist)
+          return { point, dist };
+        return nearest;
+      },
+      { point: route.points[0], dist: Infinity }
+    ).point;
+    nearestPoint.directionBias = pointToConnect.directionBias;
+  }
   let currentBest = route.points;
@@ -669,0 +728,0 @@ const tr_log = log.child("Remove Unnecessary Turns");

package.json

 {
   "name": "@tscircuit/routing",
-  "version": "1.3.1",
+  "version": "1.3.2",
   "description": "",
@@ -41,2 +41,3 @@ "main": "dist/index.js",
   "dependencies": {
+    "bs58": "^5.0.0",
     "pathfinding": "^0.4.18",
@@ -43,0 +44,0 @@ "react-error-boundary": "^4.0.11"

src/lib/find-best-border-target-paths.ts

@@ -77,2 +77,6 @@ import { computeGridTransform } from "./compute-grid-transform"
 
+  if (borderPoints.length === 0) {
+    return []
+  }
+
   // De-dupe border points that are contiguous
@@ -79,0 +83,0 @@ const contiguousBorderPoints: Array<typeof borderPoints> = [[borderPoints[0]]]

src/lib/find-two-point-granular-route.ts

@@ -11,2 +11,3 @@ import * as PF from "pathfinding"
 import { createLogContextTree } from "./logging/log-context"
+import { encodeDebugGridString } from "./logging/encode-debug-grid-string"
 
@@ -97,2 +98,12 @@ export const findTwoPointGranularRoute = ({
   )
+  // Logs a URL to inspect the input to the pathfinder
+  // console.log(
+  //   `http://localhost:6006/?path=/story/routerboard-debug-granular-route--primary&dgs=${encodeDebugGridString(
+  //     startNode.x,
+  //     startNode.y,
+  //     endNode.x,
+  //     endNode.y,
+  //     gridMatrix
+  //   )}`
+  // )
 
@@ -99,0 +110,0 @@ // If a path can't be found, return an empty path

src/lib/find-two-point-mixed-granularity-route.ts

@@ -62,2 +62,4 @@ import { computeGridTransform } from "./compute-grid-transform"
       if (startPath.pathFound && endPath.pathFound) {
+        // TODO If a route is found at a higher multiple, we still need to
+        // connect the beginning and end points at the original granularity
         log.end()
@@ -64,0 +66,0 @@ return {

src/lib/find-two-point-near-bias-route.ts

@@ -33,2 +33,5 @@ import { findBestBorderTargetPaths } from "./find-best-border-target-paths"
   if (remainingSegDist <= grid.maxGranularSearchSegments) {
+    console.log(
+      "skipping mixed granularity, route is within max granular search segments"
+    )
     const granRoute = findTwoPointGranularRoute({
@@ -35,0 +38,0 @@ pointsToConnect,

src/lib/find-two-point-schematic-route.ts

 import { findTwoPointNearBiasRoute } from "./find-two-point-near-bias-route"
-import { isIntersectingObstacle } from "./is-intersecting-obstacle"
-import { LogContextTree, createLogContextTree } from "./logging/log-context"
+import { createLogContextTree } from "./logging/log-context"
 import { removeUnnecessaryPoints } from "./remove-unnecessary-points"
-import {
-  Obstacle,
-  PathFindingParameters,
-  PathFindingResult,
-  Point,
-} from "./types"
+import { removeUnnecessaryTurns } from "./remove-unnecessary-turns"
+import { PathFindingParameters, PathFindingResult } from "./types"
 
-const removeUnnecessaryTurns = ({
-  points,
-  obstacles,
-  log,
-}: {
-  points: Point[]
-  obstacles: Obstacle[]
-  log?: LogContextTree
-}): Point[] => {
-  log ??= createLogContextTree()
-  if (points.length <= 3) {
-    log.end()
-    return points
-  }
-
-  const newPoints = [points[0], points[1]]
-
-  // Walk the route, if there's an unnecessary turn, check that the route
-  // doesn't hit an obstacle and move on
-  for (let i = 1; i < points.length - 3; i++) {
-    const P = newPoints[i - 1]
-
-    const A = newPoints[i]
-    const B = points[i + 1]
-    const C = points[i + 2]
-
-    // Are P -> A -> B all on the same line (the turn was changed?)
-
-    if (P.x === A.x && A.x === B.x) {
-      newPoints.push(B)
-      continue
-    }
-    if (P.y === A.y && A.y === B.y) {
-      newPoints.push(B)
-      continue
-    }
-
-    const B_opt =
-      A.x === B.x
-        ? { x: C.x, y: A.y }
-        : {
-            x: A.x,
-            y: C.y,
-          }
-
-    // The path to B_opt is more optimal because it has one less turn, but does
-    // it hit any obstacles?
-
-    const newPathPossible =
-      !isIntersectingObstacle({
-        obstacles,
-        points: [A, B_opt],
-      }) &&
-      !isIntersectingObstacle({
-        obstacles,
-        points: [B_opt, C],
-      })
-
-    if (newPathPossible) {
-      newPoints.push(B_opt)
-    } else {
-      newPoints.push(B)
-    }
-  }
-  newPoints.push(...points.slice(-2))
-  log.end()
-  return newPoints
-}
-
 /**
@@ -110,2 +36,22 @@ * Find a the optimal route between two points with as few unnecessary turns
 
+  // Copy over directionBiases by finding
+  // any original point with a direction bias, then adding the bias to the
+  // nearest point on the path
+  for (const pointToConnect of pointsToConnect) {
+    if (!pointToConnect.directionBias) continue
+    const nearestPoint = route.points.reduce(
+      (nearest, point) => {
+        const dist = Math.hypot(
+          point.x - pointToConnect.x,
+          point.y - pointToConnect.y
+        )
+        if (dist < nearest.dist) return { point, dist }
+        return nearest
+      },
+      { point: route.points[0], dist: Infinity }
+    ).point
+    nearestPoint.directionBias = pointToConnect.directionBias
+  }
+
+  // Remove unnecessary turns (this makes it schematic-like)
   let currentBest = route.points
@@ -112,0 +58,0 @@ const tr_log = log.child("Remove Unnecessary Turns")

src/lib/logging/log-context.ts

@@ -8,2 +8,3 @@ export interface LogContextTree {
   info: any
+  verbose?: boolean
 
@@ -29,3 +30,4 @@ start: (info: any) => void
   loudEnd,
-}: { loudEnd?: boolean } = {}): LogContextTree => {
+  verbose,
+}: { loudEnd?: boolean; verbose?: boolean } = {}): LogContextTree => {
   const tree: Partial<LogContextTree> = {
@@ -50,3 +52,5 @@ name: "root",
     const child = createLogContextTree()
+    if (verbose) console.log(`>${name}`)
     child.name = name
+    child.verbose = verbose
     tree.children.push(child)
@@ -53,0 +57,0 @@ return child

src/lib/types.ts

@@ -9,6 +9,10 @@ import { LogContextTree } from "./logging/log-context"
 
-export type Point = { x: number; y: number }
+export type Point = {
+  x: number
+  y: number
+  directionBias?: "up" | "down" | "left" | "right"
+}
 
 export type Path = {
-  points: Array<{ x: number; y: number }>
+  points: Array<Point>
   width: number
@@ -41,3 +45,3 @@ }
 export type PathFindingParameters = {
-  pointsToConnect: Point[]
+  pointsToConnect: readonly Point[]
   obstacles: Obstacle[]
@@ -44,0 +48,0 @@ grid: Grid

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

110466

increased by15.06%

Number of package files

54

increased by12.5%

Lines of code

3723

increased by14.91%

Worsened metrics

Dependency count

3

increased by50%

Dependency changes

• + Addedbs58@^5.0.0

• + Addedbase-x@4.0.0(transitive)

• + Addedbs58@5.0.0(transitive)