为什么使用 A* Odyssey 寻路算法？
寻路算法是在游戏设计中十分基础的算法。然而在 Scratch 中写一个寻路算法却是十分的困难，而且运行效率也十分的低下。 这就让寻路算法在实际游戏开发中变成了障碍。 这就是为什么我们会专门开发 A* 奥德赛插件的原因。 奥德赛在这些方面一定能帮助到你，如果你想…
- 制作一个 RPG 游戏，主角可以通过点击地图上的一个点就自动寻找路径到达目标；
- 制作一个开放世界游戏，地图中会出现一些引导线，帮助用户完成游戏任务；
- 制作一个涉及游戏或者格斗游戏，会有一些跟踪弹会自动跟踪主角。
最重要的是， A* 奥德赛插件的运行效率十分的高，在不降低采样提速的情况下， 奥德赛无论是建图速度还是寻路速度已经是业界极限了（而且还有很大的提升空间）。 它在这些方面是在 Scratch 原生程序中无法实现的：
- 高性能。 无论任何一种寻路算法，不在 TW 或者 Gandi 的运行下，基本是不可用的。 而 奥德赛的性能甚至超过在 TW 中的速度（特别感谢 -6 和 ob 在算法优化方面对我们的帮助）；
- 多地图。 支持多个地图的同时寻路。
- 高并发。 Scratch 程序的算法和 UI 运行在同一个线程中。 当计算资源同时运行时，程序就会卡到爆。 而奥德赛在底层机制中就是为多任务并行而设计的。 这意味着在寻路过程中，程序不会卡顿，而且支持多角色同步寻路也保持高性能（这是在 Scratch 原生中不可能实现的）；
最佳实践
如果你想看一下多角色同时寻路，这个程序演示了多角色同时寻路。它为设计怪物自动跟踪角色提供了简单的演示。
如果你想对比一下 SC 中的原生算法和奥德赛，或者不想用插件进行寻路，可以看这个案例。（注：这是 ob 和 -6 设计和实现的算法）
模块
模块 | 描述 |
🔧 设置 | 创建地图，载入障碍物以及清除障碍物相关 |
🚫 障碍物 | - 测试地图中的某处是否是障碍物
- 以及为地图手动增加障碍物区域 |
🛰 寻路 | 寻路，并且把结果存入到一个列表中 |
📝 工具 | 快速操作列表，以及让当前角色跳到某个坐标 |
💬 调试 | 显示地图和寻路结果，以帮助调试游戏设计 |
在你开始前，可以找到按钮 【显示/隐藏调试窗口】 来打开调试窗口，方便查看代码过程。打开后会看到一个像这样的窗口。 你可以鼠标拖动它。
方法和定义
🔧 设置
把一个障碍物载入到地图中
把一个障碍物载入到地图十分的简单，只需要选择这个地图的对应角色中的对应造型，载入并且设定它的偏移量即可。
当这个造型中不透明的区域将会被标记为障碍物。
参数 | 描述 | 典型数值 |
地图名 | 地图的名字，你可以在一个程序中设置多张地图。 地图名是它们的唯一标识。 | 地图1 |
障碍物角色 | 从哪个角色中载入障碍物 | 角色1 |
造型编号 | 这个角色中的第几编号载入成为障碍物，从 1 开始 | 1 |
x 偏移 | 横坐标的偏移量，通常为 0 | 0 |
y 偏移 | 纵坐标的偏移量，通常为 0 | 0 |
缩放大小 | 是否需要对这个图进行缩放，通常为 100，不缩放 | 100 |
以在 Scratch 中为例，运行这段代码，将会得到这样的地图：
在调试窗口中，
绿色代表的是可以寻路的空地区域；
红色代表的是障碍区；
蓝色的线代表的是找到的最短路径（后面会展示）。
如果你想在一个地图中，载入多个角色，可以这样做：
在这个案例中，我们载入了三次孙小弟到同一个地图中，地图叫做 obstacle ，并且一个向左边偏移了 100 像素， 一个向右边偏移了 150 像素，并且放大 1.5x
清除地图上的障碍物
例如，我们如果想清除上面例子中的上半部分。 只需要把 高 改为 180，运行后看到这样的效果：
🛰 寻路
一旦建立好了地图，现在你可以开始寻路了。
寻路，并且把结果填充到一个列表中
有两种方式可以快速寻路的方法，分别是从给定的两个坐标寻路，或者简化地从两个角色间寻路。
我们以两个坐标为例：
例如，运行下面这句代码后，将会得到这样的结果：
以下是参数详解：
参数 | 描述 | 参考值 |
地图名 | 用于寻路的地图名，这里需要填写在建立地图时的名字 | obstacle |
起点 x | 起点的横坐标（中心点为 0） | -320 |
起点 y | 起点的纵坐标（中心点为 0） | 180 |
终点 x | 终点的横坐标 | 319 |
终点 y | 重点的纵坐标 | -179 |
填充列表 | 寻路结果将会填充进列表中 | 寻路结果 |
结果处理 | 你可以对寻路结果选择两种处理方式：
简化结果: 将会把线段中间的连续点删除，让结果更精简
保持原始结果: 像素到像素的寻路结果 | 简化结果 |
寻路算法选择
你可以选择基础的算法版本（A* 算法或 JPS算法），以及每种算法的策略（更快或者更精确）。
通常情况下，寻路的 JPS 算法的效率要高于 A* 算法。而 “更快”和“更精确” 两个算法策略一般会获得同样的结果。 但更快的算法在一些特定情况下，会得到的结果并非是最优结果（最短路径）。 这是因为更快的算法在遇到障碍物的时候执行一些算法收缩计算范围以帮助更快地寻找到结果。 选择的算法只需要在程序启动后运行一次即可。
在两个角色间寻找路径
它是上面的寻找两个坐标间路径的简化方法。
🚫 障碍物
你不需要创建一个额外的碰撞箱来测试当前的角色是否处于可以行走的区域。
判断某个坐标是否在可行走的区域里
这个比较直观，直接给一个坐标就会返回这个位置是否是障碍区。
如果判断当前角色是否在一个障碍区，可以用简化方法：
在地图中增加一个矩形障碍区
有的时候，我们需要手动向地图中增加障碍区。可以使用下面这个语句：
📝 工具
得到寻路结果中的 x 或者 y
寻路结果存到列表中是以 JSON 的格式展示的，格式为 [x,y]。 很多情况，我们需要直接获取到这个列表中某一项的 x 数值。 使用字符串操作会十分低效。这里，就可以使用简化算法；
这样即刻获得列表中第一项的 x 部分。 对应的，以下代码可以获取 y 部分。
性能提示 在编程中，速度最快的是二进制计算。 例如 a & b, a | b, a >> 1 等等。 对内存中的直接操作其次。 例如 C 语言的数据结构。 比较慢的是字符串操作。 尤其是对字符串的每位进行循环。 所以尽可能在 JSON 操作和数组操作，使用 Gandi 的工具语句，而不是取回去自己计算字符串。
让当前角色出现在某坐标
很多时候我们希望角色出现在某个坐标，格式可能是 x,y (x,y) [x,y]。 过去需要写拆分这个数据结构的代码。 现在只需要这句话即可：
例如，结合列表使用，让角色去到寻路结果的第一个坐标位置：
💬 调试
当调试窗口打开时， 执行下面的语句会把最后一次结果绘制到调试窗口中。
规划和更新日志
规划
目前 A* 奥德赛使用浏览器的 Web Worker 技术以实现不占用 Scratch 的绘制线程。 虽然支持多线程，效率已经很高了，未来我们还是打算把 WASM + GPU 加速 + WebWorker 三个技术混合使用，从而实现更高效率的计算和渲染。
更新日志
版本 | 更新了什么 |
v1.2 | 增加了：
1. 增加 JPS 算法（A* 算法的优化版本）
2. 采用 Rust 编写的 WebAssembly 实现 JPS 算法（感谢 -6，ob 提供算法实现支持）
3. 部分bug修复和性能提升
Cappu 于 2022 年 9 月 21 日 |
v1.1 | 增加了:
1. 在地图上手动添加障碍区
2. 优化了建图效率
Shawn 于 2022 年 8 月 14 日 |
v1.0 | 增加了:
1. 全新的建图方法，直接从角色载入
2. 全新的寻路结果，直接填充列表
3. 调试工具
移除了:
所有在 v0.1 中的低效建图寻路算法
Shawn 于 2022 年 8 月 4 日 |
v0.1 | 初始更新
支持自定义地图和寻路 |
特别鸣谢
排名不分先后
最早想做这样的插件就是因为看了 yk1boy 的纪念碑谷。当我看到里面写一个寻路算法需要在 Scratch 中写如此多的代码，劝退如此多的人时， 我就下决心做一个每个人都能用的寻路算法。 所以感谢 yk1boy 对我的激励。
在整个设计过程中， Arkos 参与了大量的测试工作，帮我找了亿点点 bugs，协助我测试。
-6 和 ob 写了十分优秀的在 SC 中不使用插件下也能寻路的算法。NOdessay，无拓展的情况下实现了寻路算法，以及后续的 JPS NOdessay 优化算法。 在 -6 的督促和帮助下，修改了建图算法，让效率整体有很大提升。