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)

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.

Packed

Nodes are positioned in a dense grid with maximum overlap. This scenario stresses algorithms with many collision pairs.

Separated

Nodes are spaced apart with no overlaps. This tests the best-case scenario where algorithms can early-exit without collision resolution.

Clustered

Nodes form several clusters with overlaps within each cluster. This represents a realistic use case with localized collision groups.

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