Algorithms, data structures, and computational utilities for spatial computing, collision detection, pathfinding, and procedural generation

A comprehensive collection of reusable algorithmic building blocks with automatic optimization, memory pooling, and performance monitoring. Built with the PAW optimization framework for maximum efficiency.

• 🦊 Optimized Algorithms - Automatic algorithm selection with memory pooling and performance monitoring
• 🔧 PAW Optimization Framework - Intelligent heuristic-based algorithm selection with performance monitoring
• ⚡ Performance Utilities - Comprehensive benchmarking, profiling, and monitoring tools

• 🔗 Union-Find - Efficient set operations, cycle detection, and connected components
• 🌸 Bloom Filter - Space-efficient probabilistic data structure for membership testing
• ⚡ Priority Queue - Binary heap implementation with O(log n) operations
• 🔄 LRU Cache - Least Recently Used cache with O(1) access operations
• 📊 Fenwick Tree - Binary Indexed Tree for efficient range sum queries
• 📅 Interval Tree - Efficient interval overlap queries and range operations
• 🌳 Segment Tree - Range query and update operations in O(log n) time
• 🔤 Trie - Prefix tree for efficient string operations and autocomplete

• 🗺️ Spatial Hashing - Efficient spatial partitioning and nearest neighbor queries
• 🌲 Quadtree - Recursive spatial partitioning for 2D spatial queries
• 🌳 R-Tree - Balanced tree structure for efficient spatial indexing
• 🌲 K-d Tree - Multi-dimensional space partitioning for nearest neighbor searches
• 🧊 Octree - 3D spatial partitioning for efficient 3D queries and ray tracing
• 📦 BVH - Bounding Volume Hierarchy for collision detection and ray tracing

• 📐 Basic Geometry - Complete 2D geometric calculations and transformations (Point, Vector, Line, Rectangle, Circle, Polygon)
• 📏 Bresenham's Line - Efficient line drawing algorithm for pixel-perfect graphics
• 🔺 Delaunay Triangulation - Optimal triangulation using Bowyer-Watson algorithm
• 🛡️ Convex Hull - Multiple algorithms (Graham Scan, Jarvis March, QuickHull)
• 🏔️ Marching Squares - Contour generation from scalar field data
• 🌊 Simplex Noise - High-quality procedural noise generation (2D, 3D, 4D)
• 🎯 Poisson Disk Sampling - High-quality point distribution algorithms
• 🌊 Wave Function Collapse - Constraint-based procedural generation
• 🔷 Voronoi Diagram - Space partitioning for nearest neighbor queries and coverage analysis
• ✂️ Polygon Clipping - Boolean operations on polygons (Sutherland-Hodgman, Weiler-Atherton)
• ⚡ Line Segment Intersection - Efficient intersection detection using Bentley-Ottmann algorithm
• 📐 OBB - Oriented Bounding Box for rotated object collision detection
• 📏 Min Bounding Box - Minimum area rectangle using rotating calipers algorithm

• 💥 AABB Collision Detection - Advanced collision detection with spatial optimization
• 🔀 SAT Collision - Separating Axis Theorem for convex polygon collision detection
• 🔄 Sweep and Prune - Broad-phase collision detection for dynamic scenes

• ⭐ A* Pathfinding - Optimal pathfinding with multiple heuristics and caching
• ⚡ JPS - Jump Point Search for optimized grid-based pathfinding
• 📐 Theta* - Any-angle pathfinding for smooth path generation
• 🌊 Flow Field - Potential field pathfinding for crowd simulation
• 🏗️ HPA* - Hierarchical Pathfinding for large-scale pathfinding

• 🗺️ Isomap - Non-linear dimensionality reduction preserving geodesic distances
• 📊 PCA - Principal Component Analysis for linear dimensionality reduction
• 📉 MDS - Multidimensional Scaling for distance-preserving embeddings

npm install @entropy-tamer/reynard-algorithms

import { UnionFind, PriorityQueue, AABB } from "@entropy-tamer/reynard-algorithms";

// Union-Find for connected components
const uf = new UnionFind(10);
uf.union(0, 1);
console.log(uf.connected(0, 1)); // true

// Priority Queue for efficient ordering
const pq = new PriorityQueue<number>();
pq.push(3, 1);
pq.push(1, 3);
console.log(pq.pop()); // 1 (highest priority)

// AABB collision detection
const box1 = new AABB(0, 0, 10, 10);
const box2 = new AABB(5, 5, 15, 15);
console.log(box1.intersects(box2)); // true

For detailed documentation, mathematical theory, and comprehensive examples, see the Documentation directory.

• Mathematical Theory - Mathematical foundations and proofs
• Algorithm Guides - Detailed implementation guides
• Examples - Usage examples and best practices
• Performance Analysis - Benchmarks and optimization strategies

All algorithms include comprehensive performance monitoring and optimization:

• Memory Pooling - Automatic memory management for high-frequency operations
• Benchmarking - Built-in performance measurement tools
• Optimization - PAW framework for automatic algorithm selection
• Monitoring - Real-time performance tracking and analysis

See the examples directory for complete usage examples:

• Basic Usage - Getting started with core algorithms
• Game Engine Integration - Using algorithms in game development

// Union-Find
class UnionFind {
  constructor(size: number);
  find(x: number): number;
  union(x: number, y: number): boolean;
  connected(x: number, y: number): boolean;
}

// Priority Queue
class PriorityQueue<T> {
  push(item: T, priority: number): void;
  pop(): T | undefined;
  peek(): T | undefined;
  size(): number;
  isEmpty(): boolean;
}

// LRU Cache
class LRUCache<K, V> {
  constructor(capacity: number);
  get(key: K): V | undefined;
  set(key: K, value: V): void;
  has(key: K): boolean;
  delete(key: K): boolean;
}

// Basic shapes
class Point {
  x: number;
  y: number;
}
class Vector {
  x: number;
  y: number;
}
class Rectangle {
  x: number;
  y: number;
  width: number;
  height: number;
}
class Circle {
  x: number;
  y: number;
  radius: number;
}

// Collision detection
class AABB {
  constructor(x: number, y: number, width: number, height: number);
  intersects(other: AABB): boolean;
  contains(point: Point): boolean;
}

// A* Pathfinding
class AStar {
  findPath(start: Point, goal: Point, grid: Grid): Point[];
  setHeuristic(heuristic: HeuristicFunction): void;
}

// Flow Field
class FlowField {
  generate(goal: Point, obstacles: Obstacle[]): void;
  getDirection(position: Point): Vector;
}

Contributions are welcome! Please see our Contributing Guidelines for details.

MIT License - see LICENSE for details.

• reynard-core - Core Reynard framework utilities
• reynard-ui - UI components and primitives
• reynard-testing - Testing utilities and helpers

For more information, visit the Reynard Documentation or check out our examples.