reynard-algorithms

Algorithm primitives and data structures for Reynard applications

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.

Features

• 🦊 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

Data Structures

• 🔗 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 Structures

• 🗺️ 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

Geometry Operations

• 📐 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

Collision Detection

• 💥 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

Pathfinding Algorithms

• ⭐ 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

Installation

npm install @entropy-tamer/reynard-algorithms

Quick Start

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

Documentation

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

Key Documentation Sections

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

Performance

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

Examples

See the examples directory for complete usage examples:

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

API Reference

Data Structures

// 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;
}

Geometry

// 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;
}

Pathfinding

// 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;
}

Contributing

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

License

MIT License - see LICENSE for details.

Related Packages

• 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.