orthogonal-path-finding

v0.0.3

Published

2 months ago

Compute an orthogonal line from start to end with obstacles

Downloads

0High
0Medium
0Low

nicodechal

routing path finding orthogonal line obstacle grid

Orthogonal Path Finding Library

Overview

This is a powerful tool designed to calculate orthogonal (right-angled) paths between two points while avoiding obstacles. This library is particularly useful in applications such as diagramming tools, routing algorithms, and any scenario where clear, non-overlapping paths are required.

Features

Efficient Path Calculation: Quickly computes the shortest orthogonal path between two points.
Obstacle Avoidance: Takes into account rectangular obstacles and finds a path that navigates around them.
Customizable Options: Provides flexibility through optional parameters to fine-tune the path finding behavior.

Demo

To see the library in action, check out our live demo. This demo provides an interactive interface to visualize how the orthogonal path finding algorithm works with various start and end points and obstacles.

Installation

To install the library, use npm or yarn:

npm install orthogonal-path-finding

yarn add orthogonal-path-finding

Usage

Importing the Library

First, import the orthogonalPathFinding function from the library:

import { orthogonalPathFinding } from 'orthogonal-path-finding';

Function Signature

export declare const orthogonalPathFinding: (
  start: Point, 
  end: Point, 
  obstacles: Rectangle[], 
  options?: PathFindingOptions
) => { path: Point[], d: string };

Parameters

start: The starting point of the path. It should be an object with x and y properties.
end: The ending point of the path. It should be an object with x and y properties.
obstacles: An array of rectangular obstacles. Each rectangle should be an object with x, y, width, and height properties.
options (optional): An object containing additional options to customize the path finding behavior.

Return Value

The function returns an object with the following properties:

path: An array of points representing the calculated path.
d: A string representing the path in SVG path data format.

Example

Here is a simple example demonstrating how to use the orthogonalPathFinding function:

import { orthogonalPathFinding } from 'orthogonal-path-finding';

const start = { x: 10, y: 10 };
const end = { x: 200, y: 200 };
const obstacles = [
  { x: 50, y: 50, width: 100, height: 100 },
  { x: 150, y: 150, width: 50, height: 50 }
];

const result = orthogonalPathFinding(start, end, obstacles);

console.log(result.path); // Array of points representing the path
console.log(result.d);    // SVG path data string

Visualization

To visualize the path, you can use the SVG path data string (d) in an SVG element. Here is an example using HTML and JavaScript:

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Orthogonal Path Visualization</title>
</head>
<body>
  <svg width="300" height="300" style="border: 1px solid black;">
    <path id="path" stroke="blue" fill="none" />
  </svg>

  <script type="module">
    import { orthogonalPathFinding } from 'orthogonal-path-finding';

    const start = { x: 10, y: 10 };
    const end = { x: 200, y: 200 };
    const obstacles = [
      { x: 50, y: 50, width: 100, height: 100 },
      { x: 150, y: 150, width: 50, height: 50 }
    ];

    const result = orthogonalPathFinding(start, end, obstacles);

    const pathElement = document.getElementById('path');
    pathElement.setAttribute('d', result.d);
  </script>
</body>
</html>

Use Cases

Diagramming Tools: Automatically generate clear, non-overlapping connections between nodes in flowcharts, UML diagrams, and other visual representations.
Routing Algorithms: Find optimal paths in grid-based games or applications where movement is restricted to orthogonal directions.

Acknowledgements

This library is built upon the excellent work done in the PathFinding.js library by Xueqiao Xu. We have rewritten parts of the code in TypeScript to better suit our needs and to provide a more robust and type-safe implementation. We extend our gratitude for the foundational path finding algorithms provided by PathFinding.js.