尧图网站建设 
游戏开发后端【免费下载链接】OpenFrontIOOnline browser-based RTS game项目地址https://gitcode.com/gh_mirrors/op/OpenFrontIO点击查看免费下载本文是 OpenFrontIO在线浏览器 RTS 游戏寻路算法测试体系的完整实战指南以仓库中 tests/pathfinding/README.md 为核心骨架展开并结合benchmark、playground目录下的真实源码逐一印证。读完本文你将掌握如何用tsx一键运行单场景与全量合成场景的寻路基准如何理解初始化时间、路径距离、寻路耗时三大指标及其在源码中的测量口径如何为任意地图自动生成 200 港口、上千航线的合成测试场景以及如何启动 5555 端口的交互式 Playground通过 HTTP API 与 DebugSpan 调试数据直观对比不同寻路适配器的路径质量与性能。一、背景为什么 OpenFrontIO 需要一套寻路测试体系OpenFrontIO 是一款浏览器实时策略游戏海洋运输、舰队移动都依赖基于 tile 的水上寻路。游戏的src/core/pathfinding目录集中了寻路核心实现包括 AStar.Water.ts水上 A*、AStar.WaterHierarchical.ts分层水上寻路 HPA*、PathFinderBuilder.ts、MiniMapTransformer.ts 等。测试目录 tests/pathfinding 的目的非常明确为这些寻路算法提供可重复的基准benchmark、可自动生成的场景scenario以及可交互的可视化调试playground。正如 README 开篇所述该目录包含 benchmarking 工具、场景生成器和一个用于测试与优化寻路算法的交互式 playground。根据 README 的算法清单当前体系围绕两条寻路路线展开算法代号定位说明NavSatfuture未来实现NavigationSatellite基于 HPA*分层寻路PF.Minicurrent当前实现PathFinder.Mini基于 A*从 utils.ts 的getAdapter实现可以看到当前实际注册的适配器已经细分为五个分别对应不同的寻路策略组合详见下文适配器一节其中hpa/hpa.cached即 README 所说 HPA* 路线的具体形态。二、目录结构与五分钟快速上手README 给出的 TLDR 只有两条命令分别覆盖跑基准与开可视化两条主线npx tsx tests/pathfinding/benchmark/run.ts --synthetic --all npx tsx tests/pathfinding/playground/server.ts第一条对全部已生成合成场景执行全量基准第二条启动交互式 Playground随后在浏览器打开http://localhost:5555。对照仓库实际文件树README 中的结构略旧这里以真实目录为准该测试体系分为三大块tests/pathfinding/ ├── README.md # 本文主体文档 ├── utils.ts # 共享工具适配器注册、场景加载、指标测量、统计 ├── benchmark/ │ ├── run.ts # 基准执行器单场景 / 合成场景 / 全量 │ ├── compare.ts # 多适配器并排对比表 │ ├── generate.ts # 合成场景生成器自动挑选港口与航线 │ └── scenarios/ │ ├── default.ts # 手工挑选的默认场景giantworldmap 真实港口 │ └── synthetic/ # 自动生成的合成场景每地图一个 .ts └── playground/ ├── server.ts # Express 可视化服务端口 5555 ├── README.md # Playground 独立使用说明 ├── api/ │ ├── maps.ts # 地图列表 / 元数据 / 图数据 │ ├── pathfinding.ts # 主路径 对比适配器计算 │ └── spatialQuery.ts # 运输船空间查询closestShoreByWater └── public/ # 前端静态资源index.html / client.js / styles.css其中 run.ts、generate.ts、server.ts 三个入口均可直接通过npx tsx执行。三、基准测试单场景与合成场景的运行方式3.1 运行单个场景run.ts 是基准测试的主入口。它支持的参数组合如下与 README 一致并补充源码中确认的细节# 运行默认场景使用默认适配器 hpa npx tsx tests/pathfinding/benchmark/run.ts # 运行指定场景default 对应 giantworldmap 手工场景 npx tsx tests/pathfinding/benchmark/run.ts default # 运行指定适配器 npx tsx tests/pathfinding/benchmark/run.ts default legacy从源码看run.ts内置了三个默认值const DEFAULT_ADAPTER hpa; const DEFAULT_SCENARIO default; const DEFAULT_ITERATIONS 10;第一个位置参数是场景名缺省为default即 scenarios/default.ts使用 giantworldmap 地图与手工挑选的真实港口共 22 条航线第二个位置参数是适配器名缺省为hpa计时环节对每条航线默认执行 10 次findPath后取平均值DEFAULT_ITERATIONS。这里需要特别说明一个文档与源码的差异README 示例中的适配器名legacy是历史遗留写法。在当前仓库的 utils.tsgetAdapter中实际注册的适配器名为a.baseline、a.generic、a.full、hpa、hpa.cached五个未注册legacy传入会抛出Unknown pathfinding adapter。因此实际可用的命令应写作# 用 A* 全图适配器跑默认场景 npx tsx tests/pathfinding/benchmark/run.ts default a.full3.2 运行合成场景合成场景由生成器从地图自动产出见第四节运行方式# 运行单个合成场景iceland 地图 npx tsx tests/pathfinding/benchmark/run.ts --synthetic iceland # 指定适配器 npx tsx tests/pathfinding/benchmark/run.ts --synthetic iceland legacy # 运行 ALL 合成场景综合基准 npx tsx tests/pathfinding/benchmark/run.ts --synthetic --all # 全量 指定适配器 npx tsx tests/pathfinding/benchmark/run.ts --synthetic --all legacy结合源码补充两个 README 未强调的参数--silent最小化输出每个场景只打印一行摘要格式为✅/⚠️ 场景名 | Init: xx ms | Path: xx ms | Dist: xx tiles | Routes: a/b。--all模式下内部即以此模式逐场景执行--help/-h打印完整用法与可用合成场景说明。--all模式的执行逻辑run.ts 的main函数为扫描benchmark/scenarios/synthetic目录下所有.ts文件作为场景清单逐个以iterations: 1单次计时静默执行最后汇总输出总初始化时间 / 总寻路时间 / 总距离三项累加值。注意--all必须与--synthetic配合且合成场景需要先用generate.ts生成。3.3 三大基准指标README 明确指出基准衡量三个关键指标这里结合 utils.ts 的测量函数给出精确口径指标README 描述源码测量方式初始化时间Initialization Time地图预处理耗时getScenario 中用performance.now()包裹setupFromPath地图加载 游戏创建。对hpa系适配器游戏创建时会启用 NavMesh 构建disableNavMesh: false因此该指标实际包含了分层图构建耗时路径距离Path Distance全部航线的总距离质量指标measurePathLength 调用adapter.findPath(from, to)后返回path.length以 tile 数为单位寻路时间Pathfinding Time计算路径耗时性能指标measureExecutionTime 连续执行findPath指定次数默认 10 次后取平均毫秒数统计由 calculateStats 完成仅对成功找到路径的航线累计距离仅对成功计时的航线累计时间并给出成功航线数 / 总航线数、平均耗时等。失败航线未找到路径会在输出中标记为FAILED不计入距离与时间统计这是判断寻路正确性的重要信号。3.4 示例输出逐段解读README 给出了完整的示例输出其结构对应run.ts的三个 METRIC 分区与 SUMMARY METRIC 1: INITIALIZATION TIME Initialization time: 45.32ms METRIC 2: PATH DISTANCE Route Path Length Miami → Boston 346 tiles Miami → Houston 212 tiles ... Total distance: 52432 tiles Routes completed: 22 / 22 METRIC 3: PATHFINDING TIME Route Time Miami → Boston 2.45ms Miami → Houston 1.82ms ... Total time: 156.34ms Average time: 7.11ms Routes benchmarked: 22 / 22 SUMMARY Adapter: default Scenario: default Scores: Initialization: 45.32ms Pathfinding: 156.34ms Distance: 52432 tiles需要说明上述数值是文档中的示例输出并非当前环境实测结果但在你本机运行时输出格式将与此完全一致行宽 80 字符路由名左对齐 40 列、数值右对齐 12 列。另注意源码在 SUMMARY 中输出的是适配器/场景的实际名称且当successfulRoutes totalRoutes时会打印警告Warning: Only X out of Y routes were completed successfully!这是定位寻路失败航线的直接线索。四、多适配器并排对比compare.ts除了单适配器基准仓库还提供了并排对比工具 compare.ts用一张表格同时呈现多个适配器在同一场景上的表现# 默认场景上对比 hpa 与 a.baseline npx tsx tests/pathfinding/benchmark/compare.ts default hpa,a.baseline # 合成场景上对比三个适配器 npx tsx tests/pathfinding/benchmark/compare.ts --synthetic giantworldmap hpa,hpa.cached,a.full用法要点第一个参数为场景名--synthetic时指向合成场景第二个参数为逗号分隔的适配器列表每个适配器独立加载场景、独立测量输出如下表头的对比表Adapter Init (ms) Path (ms) Distance Routes其中 Routes 列为成功航线数/总航线数可直观看出哪个适配器在某些场景下找不到路径。适配器全解从源码看五种策略适配器是理解整套基准的关键。五个注册名对应的寻路栈来自 utils.tsgetAdapter适配器名实现说明a.baselineAStarWater(miniMap)MiniMapTransformer在迷你地图上跑 A*内联实现作为基线参照a.generic同上与 baseline 相同算法走通用适配器路径a.fullAStarWater(map)在完整地图上直接跑 A*不经过迷你图路径质量最高但开销最大hpaAStarWaterHierarchicalcachePaths: false分层寻路但关闭路径缓存。源码注释特别说明为避免基准对游戏实例产生副作用这里会克隆一份GameImpl并替换其_waterManager._miniWaterHPA再经PathFinding.Water(clonedGame)构建hpa.cachedPathFinding.Water(game)分层寻路且启用路径缓存与游戏内实际使用的寻路一致hpa与hpa.cached的对比因此可以精确回答路径缓存到底带来多少性能收益而a.full与hpa的对比可以量化分层寻路相对全图 A* 的加速比与路径长度损失。此外getScenario 中有一个值得注意的细节const enableNavMesh adapterName.startsWith(hpa)—— 即只有hpa系适配器才启用 NavMesh 构建这也解释了为何初始化时间指标在对比不同系适配器时口径不同a.*系不含分层图构建成本。五、生成合成场景从海岸线到上千航线的流水线5.1 使用方式generate.ts 负责为指定地图或全部地图生成合成场景# 为单个地图生成场景 npx tsx tests/pathfinding/benchmark/generate.ts iceland # 为所有地图生成 npx tsx tests/pathfinding/benchmark/generate.ts --all # 强制覆盖已存在的场景 npx tsx tests/pathfinding/benchmark/generate.ts iceland --force npx tsx tests/pathfinding/benchmark/generate.ts --all --force行为要点若目标场景文件已存在且未加--force会打印⚠️ mapName: File already exists (use --force to overwrite)并跳过--all模式下逐地图遍历并统计Created / Skipped / Errors三类结果地图目录取自源码常量mapsDirectory仓库resources/maps每张地图含map.bin、map4x.bin与manifest.json见 utils.ts 的setupFromPath加载逻辑生成成功后命令行会提示下一步You can now run: npx tsx tests/pathfinding/benchmark/run.ts --synthetic map-name。5.2 生成算法200 港口 × 上千航线README 描述了生成的三步流程源码给出了精确参数generate.tsconst NUM_PORTS 200; const NUM_ROUTES 1000; const ROUTES_PER_PORT 5;具体流程收集海岸线遍历地图全部 tile筛选map.isOcean(tile) map.isShoreline(tile)的水域海岸线 tile若数量不足 10 个shorelinePorts.length 10该地图生成失败并标记为 error随机挑选港口将海岸线 tile 洗牌sort(() Math.random() - 0.5)后取前min(200, shorelinePorts.length)个作为港口命名为Port001…Port200构建航线每个港口与其后 5 个港口ROUTES_PER_PORT逐一建立航线若航线数不足 1000 条目标值再以跳 6~8 个港口的方式追加最多 200 条补足受港口数量上限约束。生成的场景文件遵循统一的纯数据格式见 synthetic/giantworldmap.ts仅包含三个导出export const MAP_NAME giantworldmap; export const PORTS: { [k: string]: [number, number] } { Port001: [2224, 1019], // ... 最多 200 个港口坐标为 [x, y] }; export const ROUTES: Array[keyof typeof PORTS, keyof typeof PORTS] [ [Port001, Port002], // ... 以港口名为端点的航线对 ];run.ts通过动态import()加载这些场景模块配合getScenario将端口坐标转为 TileRef 并实例化全部航线见 utils.ts 的getScenario。合成场景的价值在于以随机化的大规模航线覆盖地图暴露真实游戏中难以手工枚举的长距离、跨岛礁、绕行等寻路边界情况。5.3 手工默认场景真实港口的 22 条航线与合成场景互补的是 scenarios/default.ts它基于 giantworldmap 地图手工挑选了 26 个真实地名港口Miami、Boston、Houston、Barcelona、Tokyo、Anchorage、Honolulu、Venice 等与 22 条有代表性的航线如 Miami → Boston、Luxor → Venice、Kongo River → Guinea River、China Desert River → Australia River。这类小而精的场景便于在引入新算法或新参数时快速验证路径正确性并对照历史结果。六、交互式 Playground可视化调试与算法对比6.1 启动与选项Playground 是一个 Express 驱动的 Web 可视化工具用于可视化寻路结果、对比算法、调试。启动方式playground/README.md# 默认启用路径缓存 npx tsx tests/pathfinding/playground/server.ts # 禁用路径缓存测量无缓存时的性能 npx tsx tests/pathfinding/playground/server.ts --no-cache启动后访问http://localhost:5555。端口可用环境变量覆盖源码中const PORT process.env.PORT ?? 5555server.ts。--no-cache对应 README 所述Disable path caching in NavMesh to measure uncached performance。服务端还启用了 gzip 压缩compression与50mb上限的 JSON body 解析前端静态资源位于playground/public。6.2 HTTP API 一览从 server.ts 的路由定义可完整列出 Playground 后端能力方法与路径功能关键请求/响应字段GET /api/maps列出所有可用地图返回{ maps: [{ name, displayName }] }displayName 优先取manifest.json中的名称否则由目录名格式化下划线转空格、camelCase 分词GET /api/maps/:name获取地图元数据含width、height、mapData1 表示水域、0 表示陆地的一维数组、graphDebug分层图节点/边/簇大小/构建耗时、adapters列表GET /api/maps/:name/thumbnail地图缩略图从resources/maps/name/thumbnail.webp返回图片POST /api/pathfind计算两点间路径请求{ map, from: [x,y], to: [x,y], adapters? }校验起终点必须是水域否则 400is not water返回{ primary, comparisons }详见下节POST /api/spatial-query运输船空间查询请求{ map, ownedTiles: number[], target: [x,y] }用于closestShoreByWater类查询寻找距目标最近的己方水域岸线POST /api/cache/clear清空地图与适配器缓存开发期热重载使用返回{ message: Caches cleared successfully }6.3 调试数据DebugSpan 揭示寻路内部状态Playground 相比纯基准的独特价值在于可观测性。在 api/pathfinding.ts 中主路径计算通过DebugSpan.enable()捕获分层寻路的内部状态返回的primary结构为primary: { path: Array[x,y] | null, // 最终路径全图坐标 length: number, // 路径长度 time: number, // hpa:findPath 耗时 debug: { nodePath: Array[x,y] | null, // 分层图中的节点路径miniMap 坐标 ×2 还原 initialPath: Array[x,y] | null, // 初步路径分层图搜索得到的粗路径 cachedSegmentsUsed: number | null, // 命中的缓存段数量 timings: Recordstring, number // DebugSpan 层级展开的各阶段耗时 } }comparisons数组则对COMPARISON_ADAPTERSapi/maps.ts 中定义为[hpa.cached, hpa, a.baseline, a.generic, a.full]逐个计算路径与耗时。其中hpa.cached特意去掉了调试开销for fair timing comparison。前端public/index.html/client.js据此可同时渲染主路径、分层节点路径、初步路径以及各适配器路径从而直观比较分层粗路径→精化路径的转换过程与缓存命中情况。此外地图元数据中的graphDebug来自DebugSpan的AbstractGraphBuilder:buildspanapi/maps.ts 的extractGraphBuildData可查看分层图每个节点的坐标、边的代价cost与簇大小是理解 HPA* 图结构的绝佳调试窗口。七、指标测量与场景加载的源码级原理7.1 场景加载管线setupFromPath无论是基准还是 Playground场景加载都统一走 utils.ts 的setupFromPath拼接map.bin全图、map4x.bin迷你图、manifest.json三个文件路径任一缺失即抛错用genTerrainFromBin分别构建全图与迷你图以TestConfig构造测试配置默认 FFA、Medium 难度、Singleplayer、无 bot可被调用方覆盖如disableNavMesh通过createGame产出Game实例。基准的初始化时间指标正是在这一整条链路外打点计时getScenario中的performance.now()因此它衡量的是地图 I/O 地形构建 游戏创建含 hpa 系的分层图构建的综合预处理成本。7.2 计时口径平均多次执行measureExecutionTime(adapter, route, executions)会连续执行findPath若干次标准模式默认 10 次、--all模式 1 次返回time / executions的平均值以平滑单次执行的抖动。measurePathLength则只关心路径长度是纯粹的质量指标。二者分开测量避免计时对路径对象形态的干扰。7.3 与游戏内寻路的对应关系hpa.cached直接使用PathFinding.Water(game)与游戏运行时如运输船移动、PathFinder.ts 的调用链采用的寻路栈一致因此基准结果可以直接外推为线上性能预期hpa无缓存克隆实例则用于评估缓存带来的增量收益。而a.full全图 A*提供的是理论最优路径长度上限参照——比较hpa系与a.full的总距离差即可量化分层寻路在路径质量上的折中。八、实践建议与进一步阅读结合 README 与源码推荐以下工作流先确认正确性对新地图或新参数先跑npx tsx tests/pathfinding/benchmark/run.ts default22 条手工航线重点观察Routes completed: x / 22是否全量成功失败即输出FAILED再评估性能用npx tsx tests/pathfinding/benchmark/compare.ts --synthetic giantworldmap hpa,hpa.cached,a.full一次性对比缓存收益与路径质量损失扩展到全量地图npx tsx tests/pathfinding/benchmark/generate.ts --all生成全部合成场景后用npx tsx tests/pathfinding/benchmark/run.ts --synthetic --all跑综合回归--silent下每地图一行的摘要便于快速扫描异常最后可视化定位启动npx tsx tests/pathfinding/playground/server.ts在http://localhost:5555上选中失败航线复现通过debug.nodePath/debug.initialPath/debug.cachedSegmentsUsed与分层图节点边数据定位瓶颈或绕路原因。相关后续资料可继续阅读核心寻路算法 AStar.Water.ts 与 AStar.WaterHierarchical.ts、适配器构建器 PathFinderBuilder.ts、以及仓库 tests/pathfinding/playground/README.md。整个测试体系以数据驱动的方式持续守卫 OpenFrontIO 的寻路质量——从 A* 基线到分层寻路缓存每一次算法演进都可以在这个统一的基准与可视化闭环中得到量化验证。赞分享游戏开发后端【免费下载链接】OpenFrontIOOnline browser-based RTS game项目地址https://gitcode.com/gh_mirrors/op/OpenFrontIO点击查看免费下载相关推荐openage 逆向解析《帝国时代2》寻路机制从 mip-map 高层寻路到流场寻路的工程实践openage 逆向解析《帝国时代2》寻路机制从 mip map 高层寻路到流场寻路的工程实践 openage 作为《帝国时代2》引擎的开源重制实现在其仓库游戏开发图形学openage 寻路子系统深度解析基于 Flow Field 的分层寻路架构与实现openage 寻路子系统深度解析基于 Flow Field 的分层寻路架构与实现 openage 的寻路子系统为游戏世界中的实体导航提供核心支撑它维护地图游戏开发图形学从卡顿到丝滑JavaScript A*寻路算法可视化平台深度解析从卡顿到丝滑JavaScript A 寻路算法可视化平台深度解析 你是否曾为游戏角色绕不开障碍物而抓狂是否在实现路径规划时因算法效率低下而头疼本文将带你深上一篇AI Engineer 必读MCP Client 的角色定位、核心职责与构建路径下一篇智慧教育平台电子课本下载终极指南3分钟学会高效获取教材PDF创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 OpenFrontIO 寻路测试与基准实践指南：从 A* 到分层寻路（HPA*）的 Benchmark、场景生成与可视化调试全解析
游戏开发后端【免费下载链接】OpenFrontIOOnline browser-based RTS game项目地址https://gitcode.com/gh_mirrors/op/OpenFrontIO点击查看免费下载本文是 OpenFrontIO在线浏览器 RTS 游戏寻路算法测试体系的完整实战指南以仓库中 tests/pathfinding/README.md 为核心骨架展开并结合benchmark、playground目录下的真实源码逐一印证。读完本文你将掌握如何用tsx一键运行单场景与全量合成场景的寻路基准如何理解初始化时间、路径距离、寻路耗时三大指标及其在源码中的测量口径如何为任意地图自动生成 200 港口、上千航线的合成测试场景以及如何启动 5555 端口的交互式 Playground通过 HTTP API 与 DebugSpan 调试数据直观对比不同寻路适配器的路径质量与性能。一、背景为什么 OpenFrontIO 需要一套寻路测试体系OpenFrontIO 是一款浏览器实时策略游戏海洋运输、舰队移动都依赖基于 tile 的水上寻路。游戏的src/core/pathfinding目录集中了寻路核心实现包括 AStar.Water.ts水上 A*、AStar.WaterHierarchical.ts分层水上寻路 HPA*、PathFinderBuilder.ts、MiniMapTransformer.ts 等。测试目录 tests/pathfinding 的目的非常明确为这些寻路算法提供可重复的基准benchmark、可自动生成的场景scenario以及可交互的可视化调试playground。正如 README 开篇所述该目录包含 benchmarking 工具、场景生成器和一个用于测试与优化寻路算法的交互式 playground。根据 README 的算法清单当前体系围绕两条寻路路线展开算法代号定位说明NavSatfuture未来实现NavigationSatellite基于 HPA*分层寻路PF.Minicurrent当前实现PathFinder.Mini基于 A*从 utils.ts 的getAdapter实现可以看到当前实际注册的适配器已经细分为五个分别对应不同的寻路策略组合详见下文适配器一节其中hpa/hpa.cached即 README 所说 HPA* 路线的具体形态。二、目录结构与五分钟快速上手README 给出的 TLDR 只有两条命令分别覆盖跑基准与开可视化两条主线npx tsx tests/pathfinding/benchmark/run.ts --synthetic --all npx tsx tests/pathfinding/playground/server.ts第一条对全部已生成合成场景执行全量基准第二条启动交互式 Playground随后在浏览器打开http://localhost:5555。对照仓库实际文件树README 中的结构略旧这里以真实目录为准该测试体系分为三大块tests/pathfinding/ ├── README.md # 本文主体文档 ├── utils.ts # 共享工具适配器注册、场景加载、指标测量、统计 ├── benchmark/ │ ├── run.ts # 基准执行器单场景 / 合成场景 / 全量 │ ├── compare.ts # 多适配器并排对比表 │ ├── generate.ts # 合成场景生成器自动挑选港口与航线 │ └── scenarios/ │ ├── default.ts # 手工挑选的默认场景giantworldmap 真实港口 │ └── synthetic/ # 自动生成的合成场景每地图一个 .ts └── playground/ ├── server.ts # Express 可视化服务端口 5555 ├── README.md # Playground 独立使用说明 ├── api/ │ ├── maps.ts # 地图列表 / 元数据 / 图数据 │ ├── pathfinding.ts # 主路径 对比适配器计算 │ └── spatialQuery.ts # 运输船空间查询closestShoreByWater └── public/ # 前端静态资源index.html / client.js / styles.css其中 run.ts、generate.ts、server.ts 三个入口均可直接通过npx tsx执行。三、基准测试单场景与合成场景的运行方式3.1 运行单个场景run.ts 是基准测试的主入口。它支持的参数组合如下与 README 一致并补充源码中确认的细节# 运行默认场景使用默认适配器 hpa npx tsx tests/pathfinding/benchmark/run.ts # 运行指定场景default 对应 giantworldmap 手工场景 npx tsx tests/pathfinding/benchmark/run.ts default # 运行指定适配器 npx tsx tests/pathfinding/benchmark/run.ts default legacy从源码看run.ts内置了三个默认值const DEFAULT_ADAPTER hpa; const DEFAULT_SCENARIO default; const DEFAULT_ITERATIONS 10;第一个位置参数是场景名缺省为default即 scenarios/default.ts使用 giantworldmap 地图与手工挑选的真实港口共 22 条航线第二个位置参数是适配器名缺省为hpa计时环节对每条航线默认执行 10 次findPath后取平均值DEFAULT_ITERATIONS。这里需要特别说明一个文档与源码的差异README 示例中的适配器名legacy是历史遗留写法。在当前仓库的 utils.tsgetAdapter中实际注册的适配器名为a.baseline、a.generic、a.full、hpa、hpa.cached五个未注册legacy传入会抛出Unknown pathfinding adapter。因此实际可用的命令应写作# 用 A* 全图适配器跑默认场景 npx tsx tests/pathfinding/benchmark/run.ts default a.full3.2 运行合成场景合成场景由生成器从地图自动产出见第四节运行方式# 运行单个合成场景iceland 地图 npx tsx tests/pathfinding/benchmark/run.ts --synthetic iceland # 指定适配器 npx tsx tests/pathfinding/benchmark/run.ts --synthetic iceland legacy # 运行 ALL 合成场景综合基准 npx tsx tests/pathfinding/benchmark/run.ts --synthetic --all # 全量 指定适配器 npx tsx tests/pathfinding/benchmark/run.ts --synthetic --all legacy结合源码补充两个 README 未强调的参数--silent最小化输出每个场景只打印一行摘要格式为✅/⚠️ 场景名 | Init: xx ms | Path: xx ms | Dist: xx tiles | Routes: a/b。--all模式下内部即以此模式逐场景执行--help/-h打印完整用法与可用合成场景说明。--all模式的执行逻辑run.ts 的main函数为扫描benchmark/scenarios/synthetic目录下所有.ts文件作为场景清单逐个以iterations: 1单次计时静默执行最后汇总输出总初始化时间 / 总寻路时间 / 总距离三项累加值。注意--all必须与--synthetic配合且合成场景需要先用generate.ts生成。3.3 三大基准指标README 明确指出基准衡量三个关键指标这里结合 utils.ts 的测量函数给出精确口径指标README 描述源码测量方式初始化时间Initialization Time地图预处理耗时getScenario 中用performance.now()包裹setupFromPath地图加载 游戏创建。对hpa系适配器游戏创建时会启用 NavMesh 构建disableNavMesh: false因此该指标实际包含了分层图构建耗时路径距离Path Distance全部航线的总距离质量指标measurePathLength 调用adapter.findPath(from, to)后返回path.length以 tile 数为单位寻路时间Pathfinding Time计算路径耗时性能指标measureExecutionTime 连续执行findPath指定次数默认 10 次后取平均毫秒数统计由 calculateStats 完成仅对成功找到路径的航线累计距离仅对成功计时的航线累计时间并给出成功航线数 / 总航线数、平均耗时等。失败航线未找到路径会在输出中标记为FAILED不计入距离与时间统计这是判断寻路正确性的重要信号。3.4 示例输出逐段解读README 给出了完整的示例输出其结构对应run.ts的三个 METRIC 分区与 SUMMARY METRIC 1: INITIALIZATION TIME Initialization time: 45.32ms METRIC 2: PATH DISTANCE Route Path Length Miami → Boston 346 tiles Miami → Houston 212 tiles ... Total distance: 52432 tiles Routes completed: 22 / 22 METRIC 3: PATHFINDING TIME Route Time Miami → Boston 2.45ms Miami → Houston 1.82ms ... Total time: 156.34ms Average time: 7.11ms Routes benchmarked: 22 / 22 SUMMARY Adapter: default Scenario: default Scores: Initialization: 45.32ms Pathfinding: 156.34ms Distance: 52432 tiles需要说明上述数值是文档中的示例输出并非当前环境实测结果但在你本机运行时输出格式将与此完全一致行宽 80 字符路由名左对齐 40 列、数值右对齐 12 列。另注意源码在 SUMMARY 中输出的是适配器/场景的实际名称且当successfulRoutes totalRoutes时会打印警告Warning: Only X out of Y routes were completed successfully!这是定位寻路失败航线的直接线索。四、多适配器并排对比compare.ts除了单适配器基准仓库还提供了并排对比工具 compare.ts用一张表格同时呈现多个适配器在同一场景上的表现# 默认场景上对比 hpa 与 a.baseline npx tsx tests/pathfinding/benchmark/compare.ts default hpa,a.baseline # 合成场景上对比三个适配器 npx tsx tests/pathfinding/benchmark/compare.ts --synthetic giantworldmap hpa,hpa.cached,a.full用法要点第一个参数为场景名--synthetic时指向合成场景第二个参数为逗号分隔的适配器列表每个适配器独立加载场景、独立测量输出如下表头的对比表Adapter Init (ms) Path (ms) Distance Routes其中 Routes 列为成功航线数/总航线数可直观看出哪个适配器在某些场景下找不到路径。适配器全解从源码看五种策略适配器是理解整套基准的关键。五个注册名对应的寻路栈来自 utils.tsgetAdapter适配器名实现说明a.baselineAStarWater(miniMap)MiniMapTransformer在迷你地图上跑 A*内联实现作为基线参照a.generic同上与 baseline 相同算法走通用适配器路径a.fullAStarWater(map)在完整地图上直接跑 A*不经过迷你图路径质量最高但开销最大hpaAStarWaterHierarchicalcachePaths: false分层寻路但关闭路径缓存。源码注释特别说明为避免基准对游戏实例产生副作用这里会克隆一份GameImpl并替换其_waterManager._miniWaterHPA再经PathFinding.Water(clonedGame)构建hpa.cachedPathFinding.Water(game)分层寻路且启用路径缓存与游戏内实际使用的寻路一致hpa与hpa.cached的对比因此可以精确回答路径缓存到底带来多少性能收益而a.full与hpa的对比可以量化分层寻路相对全图 A* 的加速比与路径长度损失。此外getScenario 中有一个值得注意的细节const enableNavMesh adapterName.startsWith(hpa)—— 即只有hpa系适配器才启用 NavMesh 构建这也解释了为何初始化时间指标在对比不同系适配器时口径不同a.*系不含分层图构建成本。五、生成合成场景从海岸线到上千航线的流水线5.1 使用方式generate.ts 负责为指定地图或全部地图生成合成场景# 为单个地图生成场景 npx tsx tests/pathfinding/benchmark/generate.ts iceland # 为所有地图生成 npx tsx tests/pathfinding/benchmark/generate.ts --all # 强制覆盖已存在的场景 npx tsx tests/pathfinding/benchmark/generate.ts iceland --force npx tsx tests/pathfinding/benchmark/generate.ts --all --force行为要点若目标场景文件已存在且未加--force会打印⚠️ mapName: File already exists (use --force to overwrite)并跳过--all模式下逐地图遍历并统计Created / Skipped / Errors三类结果地图目录取自源码常量mapsDirectory仓库resources/maps每张地图含map.bin、map4x.bin与manifest.json见 utils.ts 的setupFromPath加载逻辑生成成功后命令行会提示下一步You can now run: npx tsx tests/pathfinding/benchmark/run.ts --synthetic map-name。5.2 生成算法200 港口 × 上千航线README 描述了生成的三步流程源码给出了精确参数generate.tsconst NUM_PORTS 200; const NUM_ROUTES 1000; const ROUTES_PER_PORT 5;具体流程收集海岸线遍历地图全部 tile筛选map.isOcean(tile) map.isShoreline(tile)的水域海岸线 tile若数量不足 10 个shorelinePorts.length 10该地图生成失败并标记为 error随机挑选港口将海岸线 tile 洗牌sort(() Math.random() - 0.5)后取前min(200, shorelinePorts.length)个作为港口命名为Port001…Port200构建航线每个港口与其后 5 个港口ROUTES_PER_PORT逐一建立航线若航线数不足 1000 条目标值再以跳 6~8 个港口的方式追加最多 200 条补足受港口数量上限约束。生成的场景文件遵循统一的纯数据格式见 synthetic/giantworldmap.ts仅包含三个导出export const MAP_NAME giantworldmap; export const PORTS: { [k: string]: [number, number] } { Port001: [2224, 1019], // ... 最多 200 个港口坐标为 [x, y] }; export const ROUTES: Array[keyof typeof PORTS, keyof typeof PORTS] [ [Port001, Port002], // ... 以港口名为端点的航线对 ];run.ts通过动态import()加载这些场景模块配合getScenario将端口坐标转为 TileRef 并实例化全部航线见 utils.ts 的getScenario。合成场景的价值在于以随机化的大规模航线覆盖地图暴露真实游戏中难以手工枚举的长距离、跨岛礁、绕行等寻路边界情况。5.3 手工默认场景真实港口的 22 条航线与合成场景互补的是 scenarios/default.ts它基于 giantworldmap 地图手工挑选了 26 个真实地名港口Miami、Boston、Houston、Barcelona、Tokyo、Anchorage、Honolulu、Venice 等与 22 条有代表性的航线如 Miami → Boston、Luxor → Venice、Kongo River → Guinea River、China Desert River → Australia River。这类小而精的场景便于在引入新算法或新参数时快速验证路径正确性并对照历史结果。六、交互式 Playground可视化调试与算法对比6.1 启动与选项Playground 是一个 Express 驱动的 Web 可视化工具用于可视化寻路结果、对比算法、调试。启动方式playground/README.md# 默认启用路径缓存 npx tsx tests/pathfinding/playground/server.ts # 禁用路径缓存测量无缓存时的性能 npx tsx tests/pathfinding/playground/server.ts --no-cache启动后访问http://localhost:5555。端口可用环境变量覆盖源码中const PORT process.env.PORT ?? 5555server.ts。--no-cache对应 README 所述Disable path caching in NavMesh to measure uncached performance。服务端还启用了 gzip 压缩compression与50mb上限的 JSON body 解析前端静态资源位于playground/public。6.2 HTTP API 一览从 server.ts 的路由定义可完整列出 Playground 后端能力方法与路径功能关键请求/响应字段GET /api/maps列出所有可用地图返回{ maps: [{ name, displayName }] }displayName 优先取manifest.json中的名称否则由目录名格式化下划线转空格、camelCase 分词GET /api/maps/:name获取地图元数据含width、height、mapData1 表示水域、0 表示陆地的一维数组、graphDebug分层图节点/边/簇大小/构建耗时、adapters列表GET /api/maps/:name/thumbnail地图缩略图从resources/maps/name/thumbnail.webp返回图片POST /api/pathfind计算两点间路径请求{ map, from: [x,y], to: [x,y], adapters? }校验起终点必须是水域否则 400is not water返回{ primary, comparisons }详见下节POST /api/spatial-query运输船空间查询请求{ map, ownedTiles: number[], target: [x,y] }用于closestShoreByWater类查询寻找距目标最近的己方水域岸线POST /api/cache/clear清空地图与适配器缓存开发期热重载使用返回{ message: Caches cleared successfully }6.3 调试数据DebugSpan 揭示寻路内部状态Playground 相比纯基准的独特价值在于可观测性。在 api/pathfinding.ts 中主路径计算通过DebugSpan.enable()捕获分层寻路的内部状态返回的primary结构为primary: { path: Array[x,y] | null, // 最终路径全图坐标 length: number, // 路径长度 time: number, // hpa:findPath 耗时 debug: { nodePath: Array[x,y] | null, // 分层图中的节点路径miniMap 坐标 ×2 还原 initialPath: Array[x,y] | null, // 初步路径分层图搜索得到的粗路径 cachedSegmentsUsed: number | null, // 命中的缓存段数量 timings: Recordstring, number // DebugSpan 层级展开的各阶段耗时 } }comparisons数组则对COMPARISON_ADAPTERSapi/maps.ts 中定义为[hpa.cached, hpa, a.baseline, a.generic, a.full]逐个计算路径与耗时。其中hpa.cached特意去掉了调试开销for fair timing comparison。前端public/index.html/client.js据此可同时渲染主路径、分层节点路径、初步路径以及各适配器路径从而直观比较分层粗路径→精化路径的转换过程与缓存命中情况。此外地图元数据中的graphDebug来自DebugSpan的AbstractGraphBuilder:buildspanapi/maps.ts 的extractGraphBuildData可查看分层图每个节点的坐标、边的代价cost与簇大小是理解 HPA* 图结构的绝佳调试窗口。七、指标测量与场景加载的源码级原理7.1 场景加载管线setupFromPath无论是基准还是 Playground场景加载都统一走 utils.ts 的setupFromPath拼接map.bin全图、map4x.bin迷你图、manifest.json三个文件路径任一缺失即抛错用genTerrainFromBin分别构建全图与迷你图以TestConfig构造测试配置默认 FFA、Medium 难度、Singleplayer、无 bot可被调用方覆盖如disableNavMesh通过createGame产出Game实例。基准的初始化时间指标正是在这一整条链路外打点计时getScenario中的performance.now()因此它衡量的是地图 I/O 地形构建 游戏创建含 hpa 系的分层图构建的综合预处理成本。7.2 计时口径平均多次执行measureExecutionTime(adapter, route, executions)会连续执行findPath若干次标准模式默认 10 次、--all模式 1 次返回time / executions的平均值以平滑单次执行的抖动。measurePathLength则只关心路径长度是纯粹的质量指标。二者分开测量避免计时对路径对象形态的干扰。7.3 与游戏内寻路的对应关系hpa.cached直接使用PathFinding.Water(game)与游戏运行时如运输船移动、PathFinder.ts 的调用链采用的寻路栈一致因此基准结果可以直接外推为线上性能预期hpa无缓存克隆实例则用于评估缓存带来的增量收益。而a.full全图 A*提供的是理论最优路径长度上限参照——比较hpa系与a.full的总距离差即可量化分层寻路在路径质量上的折中。八、实践建议与进一步阅读结合 README 与源码推荐以下工作流先确认正确性对新地图或新参数先跑npx tsx tests/pathfinding/benchmark/run.ts default22 条手工航线重点观察Routes completed: x / 22是否全量成功失败即输出FAILED再评估性能用npx tsx tests/pathfinding/benchmark/compare.ts --synthetic giantworldmap hpa,hpa.cached,a.full一次性对比缓存收益与路径质量损失扩展到全量地图npx tsx tests/pathfinding/benchmark/generate.ts --all生成全部合成场景后用npx tsx tests/pathfinding/benchmark/run.ts --synthetic --all跑综合回归--silent下每地图一行的摘要便于快速扫描异常最后可视化定位启动npx tsx tests/pathfinding/playground/server.ts在http://localhost:5555上选中失败航线复现通过debug.nodePath/debug.initialPath/debug.cachedSegmentsUsed与分层图节点边数据定位瓶颈或绕路原因。相关后续资料可继续阅读核心寻路算法 AStar.Water.ts 与 AStar.WaterHierarchical.ts、适配器构建器 PathFinderBuilder.ts、以及仓库 tests/pathfinding/playground/README.md。整个测试体系以数据驱动的方式持续守卫 OpenFrontIO 的寻路质量——从 A* 基线到分层寻路缓存每一次算法演进都可以在这个统一的基准与可视化闭环中得到量化验证。赞分享游戏开发后端【免费下载链接】OpenFrontIOOnline browser-based RTS game项目地址https://gitcode.com/gh_mirrors/op/OpenFrontIO点击查看免费下载相关推荐openage 逆向解析《帝国时代2》寻路机制从 mip-map 高层寻路到流场寻路的工程实践openage 逆向解析《帝国时代2》寻路机制从 mip map 高层寻路到流场寻路的工程实践 openage 作为《帝国时代2》引擎的开源重制实现在其仓库游戏开发图形学openage 寻路子系统深度解析基于 Flow Field 的分层寻路架构与实现openage 寻路子系统深度解析基于 Flow Field 的分层寻路架构与实现 openage 的寻路子系统为游戏世界中的实体导航提供核心支撑它维护地图游戏开发图形学从卡顿到丝滑JavaScript A*寻路算法可视化平台深度解析从卡顿到丝滑JavaScript A 寻路算法可视化平台深度解析 你是否曾为游戏角色绕不开障碍物而抓狂是否在实现路径规划时因算法效率低下而头疼本文将带你深上一篇AI Engineer 必读MCP Client 的角色定位、核心职责与构建路径下一篇智慧教育平台电子课本下载终极指南3分钟学会高效获取教材PDF创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考