O(1) 内存，无需预处理的二维网格可达性算法
我正在开发一个用于二维网格的可达性检查器，具有以下特点：
- 使用 *O(1) 内存*
- 不需要 *预处理*
- 处理 *任意障碍物地图*
- 即使在大型网格上（例如，从左下角到右上角的 16,000×16,000），也能在 0.1 毫秒内完成
该检查器不依赖于广度优先搜索（BFS）、深度优先搜索（DFS）、A* 算法或洪水填充。
其核心思想是结合朝目标的贪婪移动和稳健的轮廓跟踪（墙壁追踪），在需要时切换方向并检测循环，以确保正确性。
该算法是完全确定性的，并保证对于任何地图和任何一对可行走的起点/终点的正确性。
我的动机是：
我希望使传统的洪水填充在任何仅用于可达性检查的项目中变得过时。
在许多实时系统（如游戏）中，当你只需要回答：“我能从 A 瓦片到达 B 瓦片吗？”时，完整的 BFS/DFS 或甚至区域预处理都是多余的。
以下是主要逻辑的 Swift 版本：
https://github.com/MatthiasGibis/2D-Grid-Reachability-Check/blob/main/mgReachabilityCheckGibis.swift
还有一个考虑 *高度差异* 的变体：
https://github.com/MatthiasGibis/2D-Grid-Reachability-Check/blob/main/mgReachabilityCheckGibisWithHeight.swift
查看原文
I’ve been working on a reachability checker for 2D grids that:<p>- uses *O(1) memory*
- requires *no preprocessing*
- handles *arbitrary obstacle maps*
- and finishes in under 0.1ms even on large grids (e.g. 16,000×16,000 from bottom-left to top-right)<p>It works without BFS, DFS, A<i>, or flood fill.
The core idea is a hybrid of greedy movement toward the goal and robust outline-following (wall tracing) that switches direction when needed and detects loops to ensure correctness.<p>The algorithm is fully deterministic and guarantees correctness for any map and any pair of walkable start/end points.<p>My motivation:
I want to make traditional flood fill obsolete for any project that uses it purely for reachability checks.
In many real-time systems (like games), a full BFS/DFS or even region-preprocessing is overkill when you just need to answer: </i>“Can I reach tile B from tile A?”*<p>Here’s the Swift version of the main logic<p>https://github.com/MatthiasGibis/2D-Grid-Reachability-Check/blob/main/mgReachabilityCheckGibis.swift<p>A variant that considers *height differences* is also available.<p>https://github.com/MatthiasGibis/2D-Grid-Reachability-Check/blob/main/mgReachabilityCheckGibisWithHeight.swift