find-shortest-path

Find shortest path between two nodes using A-star search.


Keywords
a-star, shortest-path
License
MIT
Install
npm install find-shortest-path@1.0.0

Documentation

find-shortest-path

Find shortest path between two nodes using A-star search.

npm i find-shortest-path pnpm add find-shortest-path yarn add find-shortest-path

Examples

# web

    Try it live

    # view source example/web.ts

    import { Line, Point, Polygon, Rect } from 'geometrik'
    import {
      findShortestPath,
      // findShortestPathBi,
      Heuristics,
      ShortestPath,
    } from 'find-shortest-path'
    
    const svg = document.createElementNS('http://www.w3.org/2000/svg', 'svg')
    const path = document.createElementNS('http://www.w3.org/2000/svg', 'path')
    
    let ri = 2392
    const rnd = () => Math.sin(++ri * 10e10 * Math.sin(ri * 10e10)) * 0.5 + 0.5
    const size = Math.min(window.innerWidth / 2, window.innerHeight / 2)
    const rects = Array.from({ length: 15 }, () => {
      return new Rect(
        rnd() * size + 50,
        rnd() * size + 50,
        rnd() * size / 3,
        rnd() * size / 3
      )
    })
    
    for (const rect of rects) {
      rect.draw()
    }
    
    const step = 30
    
    const a = new Rect(find-shortest-path.new Point(0, 0).gridRoundSelf(step), 10, 10)
    const b = new Rect(find-shortest-path.new Point(size, size).gridRoundSelf(step), 150, 150)
    
    const pa = a.topLeft
    let pb = b.bottomRight.gridRound(step)
    
    pa.draw()
    pb.draw()
    
    const big = Rect.combine([a, b]).zoomLinear(step * 4)
    big.draw()
    
    declare const console: Console & {
      edit: <T>(object: T, callback: (changed: T) => void) => void
    }
    
    const solve = () => {
      const intersects = (a: Point, b: Point) => {
        const line = new Line(a, b)
        for (const rect of rects) {
          if (line.intersectsRect(rect)) return true
        }
        return false
      }
      const acceptTolerance = 1 * step
      const points = findShortestPath({
        start: pa,
        goal: pb,
        hash: p => p.gridRound(step).toString(),
        strategies: [
          {
            accept: (a, b) => !intersects(a, b) && a.manhattan(b) <= acceptTolerance,
            distance: [Heuristics.Manhattan, 1.45],
            heuristic: [Heuristics.Chebyshev, 10],
            // distance: [Heuristics.Manhattan],
            // heuristic: [Heuristics.Chebyshev, 50],
            negativeHeap: true,
            maxIterations: 30,
          },
    
          {
            accept: (a, b) => !intersects(a, b) && a.manhattan(b) <= acceptTolerance,
            // distance: [Heuristics.Manhattan, multipliers.distance],
            // heuristic: [Heuristics.Chebyshev, multipliers.heuristic],
            distance: [Heuristics.Manhattan, 0.8],
            heuristic: [Heuristics.Euclidean, 10.65],
            // distance: [Heuristics.Manhattan, 0.45],
            // heuristic: [Heuristics.Euclidean, 20.65],
            maxIterations: 30,
          },
          {
            accept: (a, b) => a.manhattan(b) <= step * 1.5,
            distance: [Heuristics.Manhattan],
            heuristic: [Heuristics.Chebyshev, 50],
            maxIterations: 300,
          },
        ],
        neighbors(p) {
          return [
            p.translate(+step, 0),
            p.translate(0, +step),
            p.translate(-step, 0),
            p.translate(0, -step),
    
            p.translate(+step, +step),
            p.translate(+step, -step),
            p.translate(-step, +step),
            p.translate(-step, -step),
          ]
            .filter(p => p.withinRect(big))
            .filter(n => {
              const line = new Line(p, n)
              return rects.every(r => !line.intersectsRect(r))
            })
        },
      })
      return points
    }
    
    let points!: ShortestPath<Point>
    for (let i = 50; i--;) {
      points = solve()
      if (!points.length) break
    }
    console.table(points.meta)
    
    let followPointer = true
    document.onclick = () => {
      followPointer = !followPointer
    }
    
    if (points) {
      svg.setAttribute('width', '' + window.innerWidth)
      svg.setAttribute('height', '' + window.innerHeight)
      path.setAttribute('stroke', '#fff')
      path.setAttribute('stroke-width', '2')
      path.setAttribute('d', Polygon.toSVGPath(points))
      svg.appendChild(path)
      document.body.appendChild(svg)
      document.body.onpointermove = e => {
        if (!followPointer) return
    
        pb = new Point(e.pageX, e.pageY)
        if (pb.withinRect(big)) {
          for (const rect of rects) {
            if (pb.withinRect(rect)) {
              pb.set(pb.touchPoint(rect))
              break
            }
          }
    
          points = solve()
          console.table(points.meta)
          if (points.length > 2) {
            path.setAttribute('d', Polygon.toSVGPath(points))
          }
        }
      }
    }

API

# ShortestPath src/find-shortest-path.ts#L15
# Strategy src/find-shortest-path.ts#L26
# Heuristics  =  ... src/heuristics.ts#L3

    {

    # Chebyshev  =  ...

      # (a, b)

        # a

          Point

        # b

          Point

        (a, b)  =>

          number

    # Euclidean  =  ...

      # (a, b)

        # a

          Point

        # b

          Point

        (a, b)  =>

          number

    # Manhattan  =  ...

      # (a, b)

        # a

          Point

        # b

          Point

        (a, b)  =>

          number

    }

# findShortestPath(FindShortestPathOptions<T>) src/find-shortest-path.ts#L131

    FindShortestPathOptions<T>

    findShortestPath<T>(FindShortestPathOptions<T>)  =>

# findShortestPathBi(FindShortestPathOptions<T>) src/find-shortest-path.ts#L179

    FindShortestPathOptions<T>

    findShortestPathBi<T>(FindShortestPathOptions<T>)  =>

Contributing

Fork or edit and submit a PR.

All contributions are welcome!

License

MIT © 2022 stagas