# Optical Neuromorphic Eikonal Solver

[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)
[![Python 3.8+](https://img.shields.io/badge/python-3.8+-blue.svg)](https://www.python.org/downloads/)
[![OpenGL 4.3](https://img.shields.io/badge/OpenGL-4.3-green.svg)](https://www.opengl.org/)

> **Real-time GPU-accelerated pathfinding through neuromorphic wave propagation**

A novel approach to solving the Eikonal equation for shortest path computation, achieving **30-300× speedup** over CPU Dijkstra while maintaining **sub-1% accuracy** and producing **near-optimal paths**.

[**Paper**](PAPER.md) | [**Benchmarks**](BENCHMARK_RESULTS.md) | [**Documentation**](DATASET_PREPARATION.md) | [**Interactive Demo**](#demo)

---

## ✨ Highlights

- 🚀 **Ultra-fast**: 30-300× faster than CPU Dijkstra
- 🎯 **Accurate**: <1% error in travel times
- 📏 **Near-optimal**: 1.02-1.04× optimal path length
- ⚡ **Real-time**: 2-4ms per query on 512×512 grids
- 🧠 **Neuromorphic**: Physical-inspired directional memory evolution
- 🔧 **GPU-accelerated**: Massively parallel fragment shaders
- 📊 **Benchmarked**: Comprehensive evaluation on standard datasets
- 📖 **Open-source**: Full implementation with reproducible results

---

## 🎬 Quick Start

### Installation

```bash
# Clone repository
git clone https://github.com/[username]/optical-neuromorphic-eikonal-solver.git
cd optical-neuromorphic-eikonal-solver

# Install dependencies
pip install -r requirements.txt
```

### Interactive Demo

```bash
# Run the interactive solver
python quantum_eikonal_solver.py
```

**Controls:**
- **Left Click**: Set target
- **Shift + Left Click**: Set source
- **Right Click**: Paint obstacles
- **Space**: Toggle simulation
- **M**: Generate random maze
- **N**: Generate city network
- **R**: Reset travel-time field
- **V**: Toggle CPU validation

### Quick Benchmark

```bash
# Generate synthetic datasets
python -m benchmarks.prepare_datasets synthetic --output cases/synthetic

# Run benchmarks
python benchmarks/generate_results.py --cases cases/synthetic --output results/benchmark.csv

# Generate report
python -m benchmarks.report --results results/benchmark.csv --output reports/summary.md
```

---

## 🧪 How It Works

### The Problem: Eikonal Equation

The Eikonal equation models wavefront propagation for shortest paths:

```
|∇u(x)| = f(x)
```

where `u(x)` is the arrival time and `f(x)` is the slowness (reciprocal of speed).

### Our Solution: Neuromorphic Evolution

We treat the computational grid as a **neuromorphic medium** where:

1. **Each cell** maintains 4 directional memory states (N, E, S, W)
2. **Information flows** through directional coupling between neighbors
3. **Travel times evolve** through parallel relaxation
4. **System converges** to the correct shortest-path solution

```glsl
// GPU Fragment Shader (runs for ALL cells in parallel)
float current_time = texture(time_tex, uv).r;
vec4 directions = texture(state_tex, uv);  // [N, E, S, W]

// Sample neighbor times
float t_N = texture(time_tex, uv + north).r;
float t_E = texture(time_tex, uv + east).r;
float t_S = texture(time_tex, uv + south).r;
float t_W = texture(time_tex, uv + west).r;

// Eikonal update (parallel for all cells)
float new_time = compute_eikonal(t_N, t_E, t_S, t_W, speed);

// Update directional memory (neuromorphic evolution)
vec4 new_directions = update_flow(t_N, t_E, t_S, t_W, new_time);

// Output
out_time = relaxation_mix(current_time, new_time);
out_state = memory_mix(directions, new_directions);
```

### Key Innovation

Unlike traditional methods (Dijkstra, A*, Fast Marching), we:
- ✅ **No priority queue** → Fully parallel
- ✅ **No wavefront management** → Simpler implementation
- ✅ **Directional memory** → Stable convergence
- ✅ **Continuous evolution** → Natural handling of heterogeneous costs

---

## 📊 Performance

### Benchmark Results

| Grid Size | GPU Time | CPU Time | Speedup | Accuracy (MAE) | Path Quality |
|-----------|----------|----------|---------|----------------|--------------|
| 128×128 | **2.3 ms** | 73.9 ms | **32×** | 0.52% | 1.004× |
| 256×256 | **3.1 ms** | 275.5 ms | **89×** | 0.55% | 1.015× |
| 512×512 | **4.1 ms** | 948.9 ms | **231×** | 0.69% | 1.042× |

**Average across all datasets**: **134.9× speedup**, **0.64% error**, **1.025× optimal**

### Scalability

```
Performance scales super-linearly with grid size:
  128 →  256 : 2.7× speedup increase
  256 →  512 : 2.6× speedup increase
  512 → 1024 : 2.0× speedup increase (estimated)
```

### Real-Time Capability

| Grid Size | FPS Capability | Suitable For |
|-----------|----------------|--------------|
| 128×128 | 434 FPS | Mobile robotics, games |
| 256×256 | 323 FPS | Autonomous vehicles |
| 512×512 | 244 FPS | Large-scale simulation |
| 1024×1024 | 122 FPS | High-resolution planning |

---

## 🏗️ Architecture

### System Overview

```
┌──────────────────────────────────────────────────────────┐
│                   GPU Solver (ModernGL)                  │
├──────────────────────────────────────────────────────────┤
│  ┌─────────────────┐  ┌─────────────────┐               │
│  │  Time Texture   │  │  State Texture  │ (Ping-Pong)   │
│  │   (R32F)        │  │   (RGBA32F)     │               │
│  │   [travel       │  │   [N, E, S, W]  │               │
│  │    times]       │  │   [directional  │               │
│  │                 │  │    memory]      │               │
│  └────────┬────────┘  └────────┬────────┘               │
│           │                    │                         │
│           └────────┬───────────┘                         │
│                    ↓                                     │
│         ┌──────────────────────┐                         │
│         │  Fragment Shader     │                         │
│         │  (Parallel Update)   │                         │
│         │  - Eikonal equation  │                         │
│         │  - Neuromorphic flow │                         │
│         │  - Relaxation        │                         │
│         └──────────────────────┘                         │
└──────────────────────────────────────────────────────────┘
```

### Data Flow

1. **Input**: Obstacle field, speed field, source/target positions
2. **Initialization**: Set source to time=0, all others to infinity
3. **Iteration**: Run fragment shader N times (N ≈ 2× grid size)
4. **Convergence**: Travel times stabilize to correct distances
5. **Path Extraction**: Gradient descent on travel-time field

---

## 📚 Documentation

- **[PAPER.md](PAPER.md)**: Full academic paper with theory and analysis
- **[BENCHMARK_RESULTS.md](BENCHMARK_RESULTS.md)**: Detailed benchmark results and analysis
- **[DATASET_PREPARATION.md](DATASET_PREPARATION.md)**: How to prepare datasets
- **[BENCHMARK_GUIDE.md](BENCHMARK_GUIDE.md)**: How to run benchmarks

---

## 🗂️ Repository Structure

```
optical-neuromorphic-eikonal-solver/
├── quantum_eikonal_solver.py      # Main solver implementation
├── benchmarks/                    # Benchmark suite
│   ├── prepare_datasets.py        # Dataset conversion tools
│   ├── generate_results.py        # Benchmark execution
│   ├── run_suite.py               # Batch benchmark runner
│   ├── runner.py                  # GPU/CPU comparison harness
│   ├── synthetic.py               # Synthetic dataset generator
│   ├── movingai.py                # MovingAI dataset loader
│   ├── cmap.py                    # CMAP dataset loader
│   └── io_utils.py                # I/O utilities
├── cases/                         # Benchmark datasets (.npz)
│   └── synthetic/                 # Synthetic test cases
├── results/                       # Benchmark results (.csv)
├── reports/                       # Generated reports (.md)
├── requirements.txt               # Python dependencies
├── LICENSE                        # MIT License
├── PAPER.md                       # Academic paper
├── BENCHMARK_RESULTS.md           # Detailed benchmarks
├── DATASET_PREPARATION.md         # Dataset guide
└── README.md                      # This file
```

---

## 🧬 Technical Details

### Requirements

- **Python**: 3.8 or higher
- **GPU**: OpenGL 4.3 capable (most modern GPUs)
- **Dependencies**: NumPy, ModernGL, GLFW
- **Memory**: ~28 MB per 1024×1024 grid

### Tested Platforms

- ✅ Windows 10/11 (NVIDIA, AMD, Intel GPUs)
- ✅ Linux (Ubuntu 20.04+, NVIDIA, AMD)
- ✅ macOS (Intel, ARM M1/M2 with MoltenVK)

### Algorithm Parameters

| Parameter | Default | Description |
|-----------|---------|-------------|
| Relaxation | 0.95 | Time field convergence rate |
| Memory Mix | 0.08 | Directional memory retention |
| Iterations | 2n - 4n | Grid-size dependent |
| Huge Time | 10⁶ | Obstacle/unreachable marker |

---

## 🎓 Academic Use

### Citation

If you use this work in academic research, please cite:

```bibtex
@article{optical_neuromorphic_eikonal_2025,
  title={Optical Neuromorphic Computing for Real-Time Pathfinding: 
         A GPU-Accelerated Eikonal Solver with Directional Memory},
  author={[Authors]},
  journal={[Journal]},
  year={2025},
  doi={[DOI]}
}
```

### Related Publications

See [PAPER.md](PAPER.md) for full paper with references and detailed analysis.

---

## 🤝 Contributing

Contributions are welcome! Areas of interest:

- **Performance**: Further optimizations, CUDA kernels
- **Features**: 3D extension, dynamic obstacles, multi-agent
- **Benchmarks**: Additional datasets, validation
- **Documentation**: Tutorials, examples
- **Ports**: Other languages/frameworks

See [CONTRIBUTING.md](CONTRIBUTING.md) for guidelines.

---

## 📜 License

This project is licensed under the MIT License - see [LICENSE](LICENSE) file for details.

---

## 🔗 Links

- **Paper**: [PAPER.md](PAPER.md)
- **Zenodo Archive**: [DOI: [to be assigned]]
- **OpenML Dataset**: [Dataset ID: [to be assigned]]
- **Kaggle**: [https://www.kaggle.com/...]
- **Hugging Face Demo**: [https://huggingface.co/spaces/...]
- **ResearchGate**: [Profile/Publication]

---

## 👥 Authors & Acknowledgments

**Authors**: [To be filled]

**Acknowledgments**:
- Fast Marching Method: James Sethian
- GPU Computing: NVIDIA, AMD, Khronos Group
- Benchmark Datasets: MovingAI community, CMAP authors

---

## 📧 Contact

For questions, issues, or collaboration inquiries:

- **Email**: [contact@example.com]
- **Issues**: [GitHub Issues](https://github.com/[username]/[repo]/issues)
- **Discussions**: [GitHub Discussions](https://github.com/[username]/[repo]/discussions)

---

## 🌟 Star History

If you find this project useful, please consider giving it a star! ⭐

---

**Made with ❤️ for real-time pathfinding and GPU parallel computing**