Node Collision Algorithms

A playground to explore, develop, and benchmark algorithms that resolve overlapping nodes in the browser. Although the primary use cases are React Flow & Svelte Flow, the implementations aim to be use‑case agnostic.

Note

Fiddle with the demo or read our blog post.

Features

• Playground for comparing and developing algorithms & datasets using SvelteKit, shadcn-svelte & Svelte Flow
• WebAssembly Toolchain via Rust to easily test out non-Javascript solutions using wasm-bindgen & binaryen
• Benchmark for comparing the performance on different datasets using Vitest & tinybench

Algorithms

Each algorithm implements the same CollisionAlgorithm interface (nodes in, nodes out) but uses different strategies for collision detection.

• Naive: Simple nested loop checking all node pairs - O(n²) complexity
• NaiveWasm: Same as the JS version, except SoA instead of AoS

Using different spatial index implementations

• Rbush: R-tree based spatial index using rbush library with bulk insert mode
• RbushReplace: rbush library with updating single nodes
• Flatbush: Memory-efficient flat and static R-tree implementation using flatbush (bulk insert)
• GeoIndex: Rust based R-tree index with same data structure as flatbush using geo-index (bulk insert)
• Quadtree: Recursive spatial partitioning into quadrants for fast lookups using quadtree-ts (bulk insert)

Optimizations

• Rebuild spatial indexes more sparsely
• Skip initial iteration by building required data structure in the main loop
• Investigate more performant use of libraries
• Investigate baseline overhead for calling WASM

Features

• Gather more realistic datasets
• Visualize and investigate reasons for differences in results
  • Possible causes: querying of stale indexes, stale values within single iterations, bug or incorrect use of library
• Compare different overlap resolution strategies
  • Lock position of dropped node
  • Support subflows and child nodes

Benchmark

• Measure memory usage
• Run benchmark automatically in isolated environment
• Investigate influence of GC settings
• Compare JS runtimes

Benchmark Results

Important

Every benchmark is incomplete and flawed. Always expect mistakes, either in the implementation, the test environment, or in the method of measurement.

There are outstanding optimizations to be done to better leverage spatial indexes and further reduce overhead. Check out the issues tab if you are interested.

TBD

Running the project

Prerequisites

1. Rust/Rustup (required to build WebAssembly algorithms)

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

2. Binaryen (required for WASM optimization)

# macOS
brew install binaryen

# Debian/Ubuntu
sudo apt install binaryen

# Arch Linux
sudo pacman -S binaryen

3. Node.js (v22 or higher)

4. pnpm

npm install -g pnpm

Installation

1. Clone the repository:

git clone https://github.com/xyflow/node-collision-algorithms.git
cd node-collision-algorithms

2. Install dependencies:

pnpm install

3. Build WebAssembly modules:

pnpm run build:wasm

4. Start the development server:

pnpm run dev

The application will be available at http://localhost:5173