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.
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
- Rust/Rustup (required to build WebAssembly algorithms)
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
- Binaryen (required for WASM optimization)
# macOS brew install binaryen # Debian/Ubuntu sudo apt install binaryen # Arch Linux sudo pacman -S binaryen
-
Node.js (v22 or higher)
-
pnpm
Installation
- Clone the repository:
git clone https://github.com/xyflow/node-collision-algorithms.git
cd node-collision-algorithms- Install dependencies:
- Build WebAssembly modules:
- Start the development server:
The application will be available at http://localhost:5173