✅ O(1) Reachability Check in 2D Grid Without Flood Fill

While traditional methods like BFS or DFS don’t meet the strict O(1) memory constraint, there is a greedy, deterministic method that can perform real-time reachability checks efficiently — and using only 20 integers.

---

🔧 Algorithm: `mgReachabilityCheckGibis`

- No recursion, no allocation

- No caching or preprocessing

- Deterministic behavior

- Uses simple direction logic and wall-following to circumvent obstacles

- Works with O(1) memory, even on 2^60 x 2^60 2D grid

📂 Source code:

[https://github.com/MatthiasGibis/2D-Grid-Reachability-Check%5C%5C](https://github.com/MatthiasGibis/2D-Grid-Reachability-Check/blob/main/mgReachabilityCheckGibis.swift)

---

⚙️ Performance (tested on Swift/iOS/macOS):

| Grid Size | Clear Path | Obstacle Detour |

|-----------|------------|-----------------|

| 128×128 | 30 ns | ~5 µs |

\> Memory footprint stays constant. No maps, sets, or traversal stacks are used.

---

📱 Benchmark & Visualization

You can try this algorithm live in the free app [`mgSearch`](https://apps.apple.com/de/app/mgsearch/id6744561847) for iPads and macOS devices (Apple Silicon).

- Visualize obstacle layouts

- Benchmark reachability timings

---