构建 PathCraft：Go 语言的开源路由引擎

I’m happy to translate the article for you, but I’ll need the full text of the post (the content you’d like translated). Could you please paste the article’s body here? Once I have that, I’ll provide a Simplified‑Chinese translation while keeping the source line, formatting, markdown, and any code blocks unchanged.

引言

当我开始构建 PathCraft 时，我只有一个简单的目标：创建一个我能够真正理解、扩展并且在没有供应商锁定的情况下部署的路由引擎。最初作为一个实验性的副项目，它已经演变成一个模块化的、多模态路由引擎，能够处理从步行导航到公共交通路线的所有需求。

在本文中，我将分享构建 PathCraft 的历程——包括架构决策、驱动它的算法，以及在此过程中汲取的经验教训。

什么是 PathCraft？

PathCraft 是一个使用 Go 编写的实验性步行和公共交通路径规划引擎。它的设计目标是：

• 可复用的 Go 库（SDK），开发者可以将其嵌入自己的应用
• CLI 应用，用于快速路径查询
• HTTP 服务器，用于生产环境部署
• 可嵌入的引擎，便于集成到更大的系统中

核心理念是什么？先保证正确性，再追求性能。太多路径规划引擎为了微小的性能提升而牺牲可读性和可维护性。PathCraft 采用了不同的做法。

为什么选择 Go？

Source: …

架构

最重要的决策之一是架构选择。我最初考虑了 六边形（端口与适配器） 架构，但最终决定采用 模块化单体（Modular Monolith）方式。

• 对于专注于算法正确性和快速迭代的项目，六边形架构会引入不必要的开销。
• 虽然间接层和抽象边界对大型企业系统很有价值，但在此场景下会减慢开发速度，却没有相应的收益。

模块布局

/internal                → Private core logic
  /graph                → Graph data structures
  /geo                  → Geographic calculations
  /routing              → A*, RAPTOR algorithms
  /osm                  → OpenStreetMap parsing
  /gtfs                 → Transit data parsing

/pkg/pathcraft/engine   → Public API (the only thing users import)
/cmd/pathcraft          → CLI entrypoint
/web                    → Visualization tools

该结构保持 低耦合 与 高内聚，同时让系统易于理解。依赖流严格：核心逻辑永不依赖基础设施（HTTP、CLI、文件 I/O）。

Walking Router – A*

PathCraft 步行路由器的核心是 A* 算法。以下是它的简化工作原理：

• A* 结合了 Dijkstra 算法的优势（保证最短路径）和启发式搜索的优势（更快的探索）。
• 对于每个节点我们计算

[ f(n) = g(n) + h(n) ]

• g(n) – 从起点到节点 n 的实际代价

• h(n) – 从 n 到目标的估计代价（我们的启发式函数）

• 在地理路由中，我们使用 Haversine 公式计算地球上两点之间的大圆距离。这提供了一个 可接受的启发式——它永不高估实际距离，从而保证最优性。

该算法将 open set 维护为优先队列，总是优先探索最有前景的节点。Go 的 container/heap 包提供了基础，实现了一个自定义的 pqItem 结构体，用于跟踪节点 ID 和优先级。

公共交通路由器 – RAPTOR

对于公共交通，我们实现了 RAPTOR（基于轮次的公共交通优化路由器）算法。与传统的基于图的方式不同，RAPTOR 直接在时刻表数据上工作。

• 轮次（Rounds） – 每一轮代表一次额外的乘车段（换乘）
• 线路扫描（Route Scanning） – 对每个已标记的站点，扫描所有经过该站点的线路
• 换乘处理（Transfer Processing） – 在线路扫描之后，处理步行换乘
• Pareto 最优性（Pareto Optimality） – 同时跟踪到达时间和换乘次数

为什么选择 RAPTOR？

公共 API

/pkg/pathcraft/engine 中的 Engine 结构体充当 公共 API——外部用户应仅导入的唯一包。

type Engine struct {
    graph     *graph.Graph
    gtfsIndex *gtfs.StopTimeIndex
}

// Core methods
func (e *Engine) Route(req RouteRequest) (RouteResult, error)
func (e *Engine) LoadOSM(path string) error
func (e *Engine) LoadGTFS(stopTimesPath, tripsPath string) error

引擎负责 编排；它不进行计算。此分离可防止 HTTP/CLI 相关的内容泄漏到算法中。

处理 GTFS 时间格式

一个棘手的挑战是处理超过 24:00:00 的 GTFS 时间，以表示跨午夜的服务。例如，出发时间为 25:30:00 的行程意味着 次日凌晨 1:30。

我们在 /internal/time 中构建了一个自定义的 time 包，能够透明地处理这种边缘情况，使代码库的其余部分保持简洁。

开发原则

1. Pure Functions – Routing algorithms are pure. Given the same graph and query, they always produce the same result (no hidden state, randomness, or side effects).
   纯函数 – 路由算法是纯函数。给定相同的图和查询，它们总是产生相同的结果（没有隐藏状态、随机性或副作用）。

2. Comprehensive Tests – Every routing algorithm has thorough tests, especially for edge cases. Bugs in routing logic can be subtle and hard to detect.
   全面测试 – 每个路由算法都有详尽的测试，尤其是针对边缘情况。路由逻辑中的错误可能很微妙且难以发现。

3. Interface Discipline – Introduce interfaces only when there’s a concrete need, not based on hypothetical future requirements.
   接口规范 – 仅在有具体需求时才引入接口，而不是基于假设的未来需求。

4. Self‑Documenting Code – Code should explain what it does; comments are reserved for why certain decisions were made.
   自解释代码 – 代码应说明它 做了什么；注释仅用于说明 为何 做出某些决定。

OSM 解析与图构建

(原始内容在此被截断；以下是一个简短的占位符，指示下一节。)

OSM 解析将原始的 OpenStreetMap 数据转换为可步行的图，处理节点去重、边的创建以及属性提取（例如，footway 标签、表面类型）。生成的图直接供 A* 路由器使用，实现快速、精确的行人路径规划。

快速开始

• A* 步行路径规划
• CLI 界面
• GeoJSON 导出
• HTTP 服务器模式，提供 /route 和 /health 接口
• GTFS 数据导入
• RAPTOR 算法实现
• 基础地图可视化
• 步行 + 公共交通集成
• 时变路由
• 性能基准测试
• 图收缩以加速查询
• 缓存策略
• WASM/JavaScript 绑定
• gRPC API
• 插件系统

PathCraft 的第一个版本简直太简单了。这是有意为之——先让它能工作，然后再改进。

一个好的 Makefile、一致的格式以及自动化测试会带来回报。每花在工具上的一小时，都能节省后面数天的调试时间。

编写文档迫使你深入思考设计。如果你无法简明地解释它，说明你可能并未真正理解它。