8,904 字
45 分钟

PearlCalculatorRS:Minecraft FTL 计算器开发笔记

文章
技术

本文详细记录 PearlCalculatorRS 项目的架构设计、数学物理模拟原理和运算方法。

1. 项目架构

PearlCalculatorRS 是一个用于计算 Minecraft FTL 珍珠炮轨迹的工具。在深入代码细节之前,我们先来了解一下整个项目的结构。

项目采用分层架构,核心计算逻辑用 Rust 编写,可以同时运行在桌面端(通过 Tauri)和网页端(通过 WASM)。接下来我们会依次介绍各层之间的关系、Cargo Workspace 的组织方式,以及每个模块的职责。

1.1 整体结构

下面这张图展示了从用户操作到计算结果返回的完整流程。无论是桌面版还是网页版,最终都会调用同一套 Rust 核心代码:

mermaid
sequenceDiagram
    box 前端层 pearl_calculator_ui
        participant UI as 用户界面
        participant Pages as 页面组件
        participant Services as ICalculatorService
    end

    box 运行时适配层
        participant Tauri as TauriService
        participant WASM as WebService
    end

    box 桥接层 pearl_calculator_bridge
        participant Bridge as Bridge
    end

    box 核心层 pearl_calculator_core
        participant Core as Core Engine
    end

    UI->>Pages: 用户操作
    Pages->>Services: 调用服务

    alt Tauri 桌面模式
        Services->>Tauri: invoke()
        Tauri->>Bridge: IPC 调用
    else WASM 网页模式
        Services->>WASM: wasm 调用
        WASM->>Bridge: wasm-bindgen
    end

    Bridge->>Core: 执行计算
    Core-->>Bridge: 返回结果
    Bridge-->>Services: JSON 序列化
    Services-->>UI: 更新界面

简单来说:

  • 前端层:React + TypeScript 编写的用户界面
  • 运行时适配层:根据运行环境选择 Tauri IPC 或 WASM 调用
  • 桥接层:负责 JSON 和 Rust 结构体之间的转换
  • 核心层:纯 Rust 实现的物理计算引擎

1.2 Cargo Workspace

项目使用 Cargo Workspace 来管理多个 crate:

toml
[workspace]
members = [
    "pearl_calculator_core",      # 核心计算库
    "pearl_calculator_ui/src-tauri", # Tauri 桌面后端
    "pearl_calculator_bridge",    # I/O 桥接层
    "pearl_calculator_wasm"       # WASM 绑定
]
resolver = "3"

构建时有一些优化配置值得注意:

  • Release 模式会启用 LTO(链接时优化)来减小二进制体积
  • 开发模式下依赖包也会开启 opt-level = 3,这样调试时性能也不会太差

1.3 各模块介绍

接下来将逐一介绍每个模块。如果你想快速定位某个功能的代码,这部分会对你有帮助。

1.3.1 pearl_calculator_core

这是整个项目的核心,所有物理计算都在这里完成。它不依赖任何运行时环境,可以独立编译成原生库或 WASM 模块。

plaintext
pearl_calculator_core/src/
├── lib.rs                 # 模块入口
├── calculation/           # 计算逻辑
│   ├── calculation.rs     # TNT 搜索算法
│   ├── simulation.rs      # 轨迹模拟
│   ├── inputs.rs          # 内部输入结构
│   └── results.rs         # 计算结果结构
├── physics/               # 物理引擎
│   ├── entities/          # 实体模型
│   │   ├── entities.rs    # EntityData 基类
│   │   ├── pearl_entities.rs  # 末影珍珠实体
│   │   ├── tnt_entities.rs    # TNT 实体
│   │   └── movement.rs    # 运动系统(版本分化)
│   ├── aabb/              # 碰撞检测
│   │   └── aabb_box.rs    # AABB 包围盒
│   ├── constants/         # 物理常量
│   │   └── constants.rs   # Minecraft 物理参数
│   └── world/             # 世界系统
│       ├── space.rs       # Space3D 向量
│       ├── direction.rs   # 方向枚举
│       └── layout_direction.rs  # 布局方向
├── settings/              # 配置管理
│   ├── types.rs           # 配置类型定义
│   ├── defaults.rs        # 默认值
│   └── io.rs              # 配置读写
└── utils/                 # 工具函数
    └── parallel.rs        # 并行计算封装

依赖关系

依赖版本用途
serde1.0序列化/反序列化
serde_json1.0JSON 处理
rayon1.11并行计算(可选 feature)

Feature Flags

toml
[features]
default = ["enable-rayon"]    # 默认启用多线程
enable-rayon = ["dep:rayon"]  # WASM 构建时禁用

1.3.2 pearl_calculator_bridge

桥接层负责前端 JSON 和 Rust 结构体之间的转换,让 Tauri 和 WASM 两边使用统一的数据格式。

plaintext
pearl_calculator_bridge/src/
├── lib.rs          # 模块入口
├── inputs.rs       # 输入数据转换
└── outputs.rs      # 输出数据转换

核心输入结构

结构体用途
CalculationInputTNT 搜索请求参数
PearlTraceInput珍珠轨迹追踪参数
RawTraceInput自由模拟器参数
Space3DInput三维坐标输入
TntGroupInputTNT 组配置

核心输出结构

结构体用途
TNTResultOutput单条 TNT 配置结果
PearlTraceOutput完整轨迹数据
ClosestApproachOutput最近接近点信息
Space3DOutput三维坐标输出

1.3.3 pearl_calculator_wasm

该模块通过 wasm-bindgen 把核心计算能力暴露给 JavaScript。如果你想知道网页版是怎么调用 Rust 代码的,可以从这里开始看:

rust
// 暴露的 WASM 函数
#[wasm_bindgen]
pub fn calculate_tnt_amount(val: JsValue) -> Result<JsValue, JsError>;

#[wasm_bindgen]
pub fn calculate_pearl_trace(val: JsValue) -> Result<JsValue, JsError>;

#[wasm_bindgen]
pub fn calculate_raw_trace(val: JsValue) -> Result<JsValue, JsError>;

特性

  • 使用 serde_wasm_bindgen 进行 JS ↔ Rust 数据转换
  • 禁用 enable-rayon feature(WASM 环境单线程)
  • 编译目标:wasm32-unknown-unknown

1.3.4 pearl_calculator_ui/src-tauri

Tauri 2.0 桌面后端,负责 IPC 通信和系统能力调用。

plaintext
src-tauri/
├── Cargo.toml           # 依赖配置
├── tauri.conf.json      # Tauri 配置
├── src/
│   ├── main.rs          # 入口
│   ├── lib.rs           # 命令注册
│   └── commands/        # Tauri 命令
│       ├── mod.rs
│       ├── calculation.rs # 计算命令
│       └── config.rs    # 配置命令
└── capabilities/        # 权限配置

注册的 Tauri 命令

命令功能
calculate_tnt_amount_command执行 TNT 搜索
calculate_pearl_trace_command计算珍珠轨迹
calculate_raw_trace_command自由模拟计算
verify_config验证配置文件
load_config加载配置文件
load_config_from_content从内容加载配置

启用的插件

  • tauri-plugin-fs - 文件系统访问
  • tauri-plugin-dialog - 系统对话框
  • tauri-plugin-opener - 打开外部链接

1.3.5 pearl_calculator_ui

前端界面,使用 React + TypeScript 构建。

plaintext
pearl_calculator_ui/src/
├── main.tsx             # 应用入口
├── App.tsx              # 根组件
├── pages/               # 页面组件
│   ├── Calculator.tsx   # 计算器页面
│   ├── Configuration.tsx # 配置页面
│   └── Simulator.tsx    # 模拟器页面
├── components/          # UI 组件库
├── services/            # 服务抽象
│   ├── index.ts         # 服务工厂
│   ├── interface.ts     # 接口定义
│   ├── tauri.ts         # Tauri 实现
│   └── wasm.ts          # WASM 实现
├── context/             # React Context
├── hooks/               # 自定义 Hooks
├── types/               # TypeScript 类型
├── locales/             # i18n 翻译文件
└── lib/                 # 工具库

1.4 运行时适配

由于前端并不知道自己正在运行在桌面端还是网页端。这里通过策略模式屏蔽了这个差异:

typescript
// 接口定义
export interface ICalculatorService {
    calculateTNTAmount(input: CalculationInput): Promise<TNTResult[]>;
    calculatePearlTrace(input: PearlTraceInput): Promise<PearlTraceResult>;
    calculateRawTrace(input: RawTraceInput): Promise<PearlTraceResult>;
}

// 运行时自动检测
const isTauri = '__TAURI_INTERNALS__' in window;
export const calculatorService: ICalculatorService = isTauri
    ? new TauriCalculatorService()  // 桌面应用:IPC 调用
    : new WebCalculatorService();   // 网页应用:WASM 调用

Tauri 实现 通过 invoke() 调用后端命令:

typescript
class TauriCalculatorService implements ICalculatorService {
    async calculateTNTAmount(input: CalculationInput): Promise<TNTResult[]> {
        return invoke<TNTResult[]>("calculate_tnt_amount_command", { input });
    }
}

WASM 实现 直接调用编译好的 WASM 模块:

typescript
class WebCalculatorService implements ICalculatorService {
    async calculateTNTAmount(input: CalculationInput): Promise<TNTResult[]> {
        const wasm = await import("pearl_calculator_wasm");
        return wasm.calculate_tnt_amount(input);
    }
}

1.5 请求处理流程

mermaid
sequenceDiagram
    participant User as 用户
    participant UI as React UI
    participant Service as Service Layer
    participant Backend as Tauri/WASM
    participant Bridge as Bridge Layer
    participant Core as Core Engine

    User->>UI: 输入参数
    UI->>Service: calculatorService.calculateTNTAmount(input)
    
    alt Tauri 桌面模式
        Service->>Backend: invoke("calculate_tnt_amount_command")
        Backend->>Bridge: CalculationInput 反序列化
    else WASM 网页模式
        Service->>Backend: wasm.calculate_tnt_amount(input)
        Backend->>Bridge: serde_wasm_bindgen::from_value
    end
    
    Bridge->>Core: calculate_tnt_amount(&cannon, ...)
    Core->>Core: 并行 TNT 搜索
    Core-->>Bridge: Vec<TNTResult>
    Bridge-->>Backend: TNTResultOutput 序列化
    Backend-->>Service: JSON/JsValue
    Service-->>UI: TNTResult[]
    UI-->>User: 显示结果

2. 物理模拟

要准确计算珍珠轨迹,我们需要精确复现 Minecraft 中的物理规则。这一章会介绍珍珠运动涉及的所有物理系统:重力、空气阻力、TNT 爆炸推进和碰撞检测。

2.1 物理常量

下表列出了模拟中用到的所有常量,它们都是从 Minecraft 反编译代码和 Minecraft Wiki 中获取的:

常量名符号单位说明
重力加速度0.03blocks/tick²末影珍珠重力
空气阻力系数0.99-速度衰减乘数
珍珠半径0.125blocks碰撞箱宽度
珍珠高度0.25blocks碰撞箱高度
TNT 半径0.49blocksTNT 碰撞箱宽度
TNT 高度0.98blocksTNT 碰撞箱高度
爆炸半径8.0blocks爆炸影响范围
TNT Y 偏移0.06125blocksTNT 实体 Y 轴偏移
珍珠爆炸 Y 系数0.85-爆炸力作用点系数
浮点精度阈值1e-10-零值判断阈值

2.2 珍珠运动

2.2.1 状态向量

珍珠在任意时刻的状态由位置 和速度 两个向量描述:

2.2.2 每 Tick 的更新

每个游戏 Tick(1/20 秒),珍珠的位置和速度会按特定顺序更新,但不同 Minecraft 版本的更新顺序不一样:

mermaid
flowchart LR
    subgraph Legacy["Legacy (≤1.20.4)"]
        direction TB
        L1[位置更新] --> L2[阻力衰减] --> L3[重力应用]
    end
    
    subgraph Post1205["Post1205 (1.20.5-1.21.1)"]
        direction TB
        P1[位置更新] --> P2[阻力衰减] --> P3[重力应用]
    end
    
    subgraph Post1212["Post1212 (≥1.21.2)"]
        direction TB
        N1[重力应用] --> N2[阻力衰减] --> N3[位置更新]
    end

    Legacy ~~~ Post1205 ~~~ Post1212

2.3 版本差异

这里详细介绍每个版本的具体实现。如果你只关心结果,可以跳到 2.4 的对比表格。

2.3.1 Legacy 版本(≤ 1.20.4)

这个版本使用 32 位 float 做速度计算,然后再转回 64 位。更新顺序是:移动 → 阻力 → 重力。

rust
// 1. 位置更新
position += velocity;

// 2. 阻力衰减 (float 精度)
velocity.x = (velocity.x as f32 * 0.99) as f64;
velocity.y = (velocity.y as f32 * 0.99) as f64;
velocity.z = (velocity.z as f32 * 0.99) as f64;

// 3. 重力应用 (float 精度)
velocity.y = (velocity.y as f32 - 0.03) as f64;

数学表达

WARNING

Legacy 版本因 float 精度损失,长距离飞行会出现明显误差累积。


2.3.2 Post1205 版本(1.20.5 - 1.21.1)

这个版本完全使用 64 位 double,更新顺序和 Legacy 一样,但精度更高:

rust
// 1. 位置更新
position += velocity;

// 2. 阻力衰减 (double 精度)
velocity *= 0.99;

// 3. 重力应用
velocity.y -= 0.03;

数学表达


2.3.3 Post1212 版本(≥ 1.21.2)

Mojang 在这个版本重构了实体物理系统,调整了操作顺序:重力 → 阻力 → 移动。

rust
// 1. 重力应用
velocity.y -= 0.03;

// 2. 阻力衰减
velocity *= 0.99;

// 3. 位置更新
position += velocity;

数学表达

Post1212 的顺序变化会导致相同初始条件下轨迹与旧版本产生偏差,远距离飞行尤为明显。


2.4 版本对比总结

特性Legacy (≤1.20.4)Post1205 (1.20.5-1.21.1)Post1212 (≥1.21.2)
浮点精度float (32-bit)double (64-bit)double (64-bit)
Tick 顺序Move→Drag→GravityMove→Drag→GravityGravity→Drag→Move
精度累积误差较大较小较小
轨迹特性相对抛物线偏短标准抛物线阻力先于移动,飞行略短

2.5 TNT 爆炸推进

TNT 爆炸会对范围内的珍珠施加一个推进力。力的计算涉及距离衰减和方向向量。

2.5.1 爆炸力计算

设 TNT 爆炸中心为 ,珍珠位置为

1. 计算 TNT 实际爆炸中心(Y 轴偏移):

其中 (TNT 高度 × 0.0625)

2. 计算距离向量

3. 判断是否在爆炸范围内

4. 计算爆炸方向向量(考虑珍珠高度):

其中 (爆炸作用点在珍珠高度的 85% 处)

5. 归一化方向向量

6. 计算爆炸强度(距离衰减):

7. 最终推进向量

2.5.2 爆炸力可视化

mermaid
graph TD
    subgraph "爆炸力衰减曲线"
        A["距离 d = 0"] -->|"强度 s = 1.0"| B["最大推力"]
        C["距离 d = 4"] -->|"强度 s = 0.5"| D["半衰推力"]
        E["距离 d = 8"] -->|"强度 s = 0"| F["无推力"]
    end

推力强度随距离的衰减公式


2.6 碰撞检测

项目使用 AABB(轴对齐包围盒)算法处理珍珠与世界方块的碰撞。

2.6.1 AABB 包围盒定义

AABB 由最小点和最大点定义:

2.6.2 珍珠包围盒计算

珍珠在位置 的包围盒:

2.6.3 扫掠碰撞检测(Sweep Collision)

实体移动时按 Y → X → Z 顺序依次检测碰撞:

plaintext
原始移动: (xa, ya, za)

    [Y轴碰撞检测] → 修正 ya

    [更新包围盒 Y]

    [X轴碰撞检测] → 修正 xa

    [更新包围盒 X]

    [Z轴碰撞检测] → 修正 za

    [最终位置更新]

2.6.4 单轴碰撞检测算法

以 Y 轴为例(X、Z 轴类似):

rust
fn y_offset(&self, other: &AABBBox, mut offset_y: f64) -> f64 {
    // 1. 检查 X-Z 平面是否重叠
    if other.max_x <= self.min_x || other.min_x >= self.max_x { return offset_y; }
    if other.max_z <= self.min_z || other.min_z >= self.max_z { return offset_y; }
    
    // 2. 向上移动时的碰撞检测
    if offset_y > 0.0 && other.max_y <= self.min_y {
        let d = self.min_y - other.max_y;
        if d < offset_y { offset_y = d; }
    }
    
    // 3. 向下移动时的碰撞检测
    if offset_y < 0.0 && other.min_y >= self.max_y {
        let d = self.max_y - other.min_y;
        if d > offset_y { offset_y = d; }
    }
    
    offset_y
}

2.6.5 碰撞后状态更新

rust
// 发生碰撞时清零对应轴的速度
if original_xa != xa { motion.x = 0.0; }
if original_ya != ya { motion.y = 0.0; }
if original_za != za { motion.z = 0.0; }

// 更新碰撞标志
is_collided_horizontally = (original_xa != xa) || (original_za != za);
is_collided_vertically = original_ya != ya;
on_ground = (original_ya != ya) && (original_ya < 0.0);

2.7 Space3D 向量数学

项目使用 Space3D 结构表示三维向量,支持以下运算:

运算数学表达Rust 实现
向量加法a + b
向量减法a - b
标量乘法a * k
向量长度a.length()
长度平方a.length_sq()
3D 距离a.distance(&b)
2D 距离a.distance_2d(&b)

2.8 模拟精度说明

TIP

本项目的物理模拟与 Minecraft 游戏行为完全一致,采用相同的常量值和计算顺序。唯一差异在于 Legacy 模式的 float 精度模拟使用显式类型转换实现。

为了确保模拟结果可靠,精度上有几个保障:

  • 所有浮点计算都使用 IEEE 754 双精度标准
  • 坐标精度保持到小数点后 10 位以上
  • 判断速度是否为零时,使用 阈值

3. 核心算法

这一章我们会介绍 TNT 数量搜索算法是怎么工作的,以及如何从每秒搜索几十个组合优化到每秒搜索数百万个组合。

如果你对性能优化感兴趣,3.9 节记录了完整的优化历程。


3.1 整体流程

先从全局视角看一下算法的执行流程:

mermaid
graph TD
    subgraph Input["输入参数"]
        direction LR
        Cannon[炮台配置] ~~~ Dest[目标坐标] ~~~ MaxTNT[最大 TNT] ~~~ MaxTicks[最大 Tick]
    end
    
    subgraph Core["核心算法流程"]
        A[计算飞行方向] --> B[求解 TNT 向量]
        B --> C[几何方程求解理想 TNT]
        C --> D[Tick 分组优化]
        D --> E[并行轨迹扫描]
        E --> F[结果去重与排序]
    end
    
    subgraph Output["输出结果"]
        Results[TNTResult 列表]
    end
    
    Input --> Core
    Core --> Output

3.2 TNT 搜索算法

这是整个工具的核心问题:给定珍珠的初始位置、速度和目标位置,找到能让珍珠落在目标附近的 TNT 组合。

3.2.1 问题定义

已知:

  • 珍珠初始位置 和初始速度
  • 目标位置
  • 红色/蓝色 TNT 的爆炸向量

求:红色 TNT 数量 和蓝色 TNT 数量 ,使珍珠落点尽可能接近目标。

3.2.2 飞行方向判定

首先根据目标位置计算飞行方向:

方向判定规则:

角度范围方向
East (东)
South (南)
West (西)
其他North (北)

3.2.3 TNT 向量计算

根据飞行方向确定红色和蓝色 TNT 的位置,然后计算爆炸向量:

3.2.4 线性方程组求解(Cramer 法则)

珍珠最终位移可表示为 TNT 推力乘以累积因子:

其中累积因子 随 Tick 变化(见下文)。

将 X-Z 平面投影为二元一次方程组:

使用 Cramer 法则 求解:

行列式计算

解出 TNT 比例

考虑累积因子后的理想整数解

3.2.5 累积因子公式

珍珠每 tick 都在减速(因为空气阻力),所以同样 1 m/s 的初速度,对最终位移的贡献是递减的。累积因子 就是用来描述 个 tick 后速度对位移的总贡献。

因为阻力系数 ,这实际上是个等比数列求和问题:

Legacy / Post1205 版本

Post1212 版本(由于阻力先于移动,公式略有不同):

3.3 Tick 分组优化

3.3.1 优化原理

这个优化思路来自一个简单的观察:由于空气阻力使速度指数衰减,相邻 tick 算出来的理想 TNT 值往往非常接近,四舍五入后甚至完全相同。

做法是把所有 tick 按理想 TNT 组合 分组,相同组合的 tick 共享一次模拟:

rust
// 按理想 TNT 组合分组
let mut groups: HashMap<(i32, i32), Vec<u32>> = HashMap::new();

for tick in 1..=max_ticks {
    let (ideal_red, ideal_blue) = solve_ideal_tnt(tick);
    groups.entry((ideal_red, ideal_blue))
          .or_insert_with(Vec::new)
          .push(tick);
}

3.3.2 搜索邻域扩展

当然,数学求解得到的是浮点数,取整后可能有误差。所以实际搜索时会在理想值附近各扩展 5 个单位:

形成 个候选组合。


3.4 并行计算优化

3.4.1 并行策略

既然各个分组之间互不依赖,自然可以并行处理。这里用 Rayon 库——它把迭代器包装成并行版本,几乎不需要改动原有逻辑:

rust
let raw_results: Vec<TNTResult> = group_list
    .into_par_iter()  // 并行迭代
    .flat_map(|((ideal_red, ideal_blue), valid_ticks)| {
        // 每个分组独立计算
        let mut local_results = Vec::new();
        for r_adjust in -5..=5 {
            for b_adjust in -5..=5 {
                // 模拟并检查命中
            }
        }
        local_results
    })
    .collect();

3.4.2 运行时适配

由于 WASM 环境没法用多线程,所以需要做个兼容处理。通过 feature flag,WASM 构建时会禁用 Rayon,into_par_iter() 将自动降级成普通的顺序迭代:

运行时并行实现线程数
Tauri 桌面RayonCPU 核心数
WASM 网页顺序迭代1(单线程)
rust
#[cfg(not(feature = "enable-rayon"))]
pub mod prelude {
    pub trait IntoParallelIterator {
        type Item;
        type IntoIter: Iterator<Item = Self::Item>;
        fn into_par_iter(self) -> Self::IntoIter;
    }

    impl<I: IntoIterator> IntoParallelIterator for I {
        type Item = I::Item;
        type IntoIter = I::IntoIter;
        fn into_par_iter(self) -> Self::IntoIter {
            self.into_iter()  // 降级为顺序迭代
        }
    }
}

3.5 轨迹模拟算法

3.5.1 scan_trajectory 函数

搜索算法最终要调用的是轨迹模拟。这个函数从初始状态开始,逐 tick 推进珍珠位置,在每个目标 tick 检查是否命中:

rust
pub fn scan_trajectory(
    data: &GeneralData,       // 珍珠初始状态
    destination: Space3D,      // 目标位置
    max_tick: u32,            // 最大模拟 Tick
    valid_ticks: &[bool],     // 有效 Tick 掩码
    world_collisions: &[AABBBox],  // 碰撞体
    offset: Space3D,          // 坐标偏移
    version: PearlVersion,    // MC 版本
    max_distance_sq: f64,     // 最大距离平方
) -> Vec<SimResult>

3.5.2 模拟循环

整个模拟过程可以用下面这张流程图来理解。注意其中有个提前退出条件:珍珠速度趋近于零:

mermaid
graph TD
    A[初始化珍珠实体] --> B[Tick 0]
    B --> C{tick <= max_tick?}
    C -->|是| D[应用 TNT 爆炸力]
    D --> E[执行物理更新]
    E --> F{是有效 Tick?}
    F -->|是| G[计算距离]
    G --> H{距离 <= 阈值?}
    H -->|是| I[记录命中结果]
    H -->|否| J[继续]
    F -->|否| J
    I --> J
    J --> K{速度趋零?}
    K -->|是| L[提前终止]
    K -->|否| M[tick++]
    M --> C
    C -->|否| N[返回结果]
    L --> N

3.5.3 距离计算

判断珍珠是否”命中”目标时,只看 X-Z 平面的距离:

只要这个距离在用户设定的阈值内,就算命中:

3.5.4 提前终止条件

当珍珠速度趋近于零时提前终止模拟:

其中


3.6 结果处理算法

3.6.1 去重逻辑

由于一个 TNT 组合可能在多个 tick 都落在目标范围内,需要做去重。对于相同的 组合,只保留最优的那个:

rust
let mut best_results_map: HashMap<(u32, u32), TNTResult> = HashMap::new();

for res in raw_results {
    let key = (res.red, res.blue);
    match best_results_map.entry(key) {
        Vacant(e) => { e.insert(res); }
        Occupied(mut e) => {
            let is_better = if (res.distance - current.distance).abs() < ε {
                res.tick < current.tick  // 距离相同时优先选择更早的 Tick
            } else {
                res.distance < current.distance  // 否则选择距离更近的
            };
            if is_better { e.insert(res); }
        }
    }
}

3.6.2 排序规则

最终结果按距离升序排序:

rust
final_results.sort_by(|a, b| {
    a.distance.partial_cmp(&b.distance)
        .unwrap_or(std::cmp::Ordering::Equal)
});

3.7 轨迹计算

3.7.1 calculate_pearl_trace 函数

给定特定 TNT 配置,计算完整轨迹:

rust
pub fn calculate_pearl_trace(
    cannon: &Cannon,
    red_tnt: u32,
    blue_tnt: u32,
    direction: Direction,
    max_ticks: u32,
    world_collisions: &[AABBBox],
    version: PearlVersion,
) -> Option<CalculationResult>

3.7.2 轨迹数据结构

返回值包含了前端需要的所有信息——落点、轨迹、飞行时间等:

rust
pub struct CalculationResult {
    pub landing_position: Space3D,     // 最终落点
    pub pearl_trace: Vec<Space3D>,     // 位置轨迹
    pub pearl_motion_trace: Vec<Space3D>,  // 速度轨迹
    pub is_successful: bool,           // 是否命中目标
    pub tick: u32,                     // 飞行 Tick 数
    pub final_motion: Space3D,         // 最终速度
    pub distance: f64,                 // 与目标距离
}

3.7.3 轨迹采样

模拟过程中,每个 tick 都会记录一次位置和速度:

去重处理(移除连续重复点):

rust
final_traces.dedup();
final_motion_traces.dedup();

3.8 复杂度分析

最后总结一下算法各阶段的时间和空间复杂度:

算法阶段时间复杂度空间复杂度
几何求解与分组
并行搜索
去重排序

其中:

  • = 最大 Tick 数
  • = 分组数量(通常
  • = 各分组最大 tick 的平均值
  • = 并行线程数
  • = 原始结果数量
NOTE

几何求解与分组在代码中是同一循环完成的。空间复杂度为 是因为所有 tick 都需要存入对应分组。

总复杂度


3.9 优化过程

初始版本耗时超过 5 分钟,最终版本 0.13 秒,加速约 2300 倍。

3.9.1 初始状态

搜索参数:

  • 搜索范围:10000 tick(约 8.3 分钟飞行时间)
  • 每 tick 搜索 121 种 TNT 组合(理想值 ±5)
  • 总搜索空间: 万次模拟

初始实现性能:

  • 耗时:> 300 秒
  • CPU 占用:6%(8 核 16 线程仅 1 核工作)

初始实现的问题:

问题一:O(N²) 复杂度

检查第 t tick 是否命中,需要从头模拟 t 次物理迭代。总计算量:

问题二:频繁堆分配

simulation::run 返回 LinkedList<Space3D> 记录完整轨迹,每次调用都触发堆内存分配。在热路径上频繁 malloc/free 严重影响性能。

问题三:累积因子重复计算

计算理想 TNT 需要累积因子 ,原实现用循环累加,复杂度 O(t)。对于 tick 10000,需要累加 10000 次。

3.9.2 优化一:减少内存分配

将模拟函数拆分为两个版本:

函数用途内存模式
run前端轨迹绘图返回 Vec<Space3D>
check_landing计算器搜索纯栈内存,仅返回最终位置

check_landing 实现:

rust
pub fn check_landing(...) -> Option<(Space3D, Space3D, u32)> {
    let mut pearl = PearlEntity::new(...);
    
    for tick in 0..max_ticks {
        pearl.tick();
        if pearl.motion.length_sq() < EPSILON { break; }
    }
    
    if pearl.position.distance_2d(&dest) <= max_distance {
        Some((pearl.position, pearl.motion, tick))
    } else {
        None
    }
}

附加微优化:

  • 距离判断使用平方比较,避免 sqrt 运算
  • 速度接近零时提前退出循环

效果:提升约 1.3 倍。但 O(N²) 复杂度未变,瓶颈仍在算法层面。

3.9.3 优化二:并行化

使用 Rayon 将外层 tick 循环并行化:

rust
use rayon::prelude::*;

let results: Vec<_> = (1..=max_ticks)
    .into_par_iter()
    .flat_map(|tick| calculate_for_tick(tick))
    .collect();

效果:

  • CPU 占用:6% → 100%
  • 耗时:300 秒 → 42 秒
  • 加速比:~7x(接近 8 核理论上限)

但 42 秒对于实时工具仍不可接受,且算法复杂度 O(N²/P) 未根本改变。

3.9.4 优化三:等比数列公式

让我们再来看看原实现计算累积因子:

rust
let mut divider = 0.0;
for t in 1..=tick {
    divider += 0.99_f64.powi(t as i32);  // O(N) 循环
}

注意到,这其实就是等比数列求和,可用公式直接计算:

优化后:

rust
let divider = 0.99 * (1.0 - 0.99_f64.powi(tick as i32)) / 0.01;  // O(1)

效果:累积因子计算从 O(N) 降为 O(1)。

3.9.5 优化四:Tick 归组

关键洞察:由于空气阻力使珍珠速度指数衰减,后期 tick 的理想 TNT 值变化极小。

具体表现:

  • tick 100 和 tick 101 的理想 TNT 可能相差 0.5
  • tick 5000 和 tick 5001 的理想 TNT 可能相差 0.0001,四舍五入后完全相同

将 10000 个 tick 按理想 TNT 值分组:

rust
let mut groups: HashMap<(i32, i32), Vec<u32>> = HashMap::new();

for tick in 1..=10000 {
    let ideal_red = (true_red / divider).round() as i32;
    let ideal_blue = (true_blue / divider).round() as i32;
    
    groups.entry((ideal_red, ideal_blue))
          .or_default()
          .push(tick);
}

分组结果:10000 个 tick 仅产生约 50 个不同的组

对每组采用单次遍历扫描:只运行一次模拟到该组最大 tick,在过程中用布尔掩码检查所有目标时间点。

效果:

  • 模拟次数:
  • 计算量减少:99.5%
  • 耗时:42 秒 → 0.13 秒
  • 加速比:~320x

3.9.6 优化五:结果去重

优化后出现新问题:结果大量重复。

原因:

  1. 珍珠落地后静止,从着陆 tick 到 10000 tick 均在目标范围内
  2. 不同理想 TNT 微调后可能得到相同实际 TNT

处理方式:

  1. 组内去重:每次模拟扫描后,使用 min_by 仅保留距离最近的结果
  2. 全局去重:用 HashMap<(u32, u32), TNTResult> 确保每个 (red, blue) 组合只输出最优解

3.9.7 最终对比

阶段耗时加速比主要改进
初始实现> 300 秒1x-
内存优化~230 秒1.3x零分配模拟
并行化42 秒7xRayon 多核
算法优化0.13 秒2300x归组 + 公式

复杂度变化:

主要收益来自算法层面的优化,而非硬件并行。归组策略将有效搜索空间压缩了 200 倍,这是性能跃升的根本原因。

3.9.7 最终结果

版本耗时加速比
初始> 300 秒1x
并行化42 秒~7x
算法优化0.13 秒~2300x

主要收益来自算法优化(复杂度从 降到 ),而非并行化。

4. 数据结构

如果你想了解或修改数据模型,这一章会很有用。我们会介绍项目中最关键的几个结构体:向量、空间、实体、设置等。


4.1 基础类型

4.1.1 Space3D

整个物理系统的基础——三维向量,同时用于表示位置和速度:

rust
#[derive(Debug, Clone, Copy, PartialEq, Default, Serialize, Deserialize)]
pub struct Space3D {
    pub x: f64,
    pub y: f64,
    pub z: f64,
}

方法

方法签名说明
newfn new(x: f64, y: f64, z: f64) -> Self构造函数
distancefn distance(&self, other: &Self) -> f643D 欧几里得距离
distance_sqfn distance_sq(&self, other: &Self) -> f64距离平方(避免 sqrt)
lengthfn length(&self) -> f64向量长度
length_sqfn length_sq(&self) -> f64长度平方
distance_2dfn distance_2d(&self, other: &Self) -> f64XZ 平面距离
angle_to_yawfn angle_to_yaw(&self, other: &Self) -> f64计算朝向角度

运算符重载

运算符操作
+ / +=向量加法
-向量减法
* / *=标量乘法
/ / /=标量除法

4.1.2 AABBBox

轴对齐包围盒(Axis-Aligned Bounding Box),用于碰撞检测。

定义

rust
#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
pub struct AABBBox {
    pub min_x: f64,
    pub min_y: f64,
    pub min_z: f64,
    pub max_x: f64,
    pub max_y: f64,
    pub max_z: f64,
}

方法

方法说明
new(min_x, min_y, min_z, max_x, max_y, max_z)构造函数
offset(x, y, z)返回平移后的新包围盒
x_offset(&self, other, offset_x)X 轴碰撞检测与修正
y_offset(&self, other, offset_y)Y 轴碰撞检测与修正
z_offset(&self, other, offset_z)Z 轴碰撞检测与修正

4.2 物理实体

4.2.1 EntityData

通用实体数据结构,包含位置、速度、碰撞状态等。

定义

rust
#[derive(Debug, Clone, PartialEq)]
pub struct EntityData {
    pub position: Space3D,              // 实体中心位置
    pub motion: Space3D,                // 速度向量
    pub bounding_box: AABBBox,          // 碰撞包围盒
    pub on_ground: bool,                // 是否着地
    pub is_collided_horizontally: bool, // 水平碰撞标志
    pub is_collided_vertically: bool,   // 垂直碰撞标志
    pub is_gravity: bool,               // 是否受重力影响
}

方法

方法说明
new(position, motion, bounding_box)构造函数
move_entity(xa, ya, za, world_collisions)执行移动并处理碰撞

move_entity 碰撞处理流程

  1. 按 Y → X → Z 顺序检测碰撞
  2. 修正移动量以避免穿透
  3. 更新位置和碰撞状态标志
  4. 若发生碰撞,清零对应轴速度

4.2.2 Pearl / PearlEntity

珍珠实体专用结构。

Pearl(轻量配置结构)

rust
#[derive(Debug, Clone, Copy, PartialEq, Default)]
pub struct Pearl {
    pub position: Space3D,  // 初始位置
    pub motion: Space3D,    // 初始速度
    pub offset: Space3D,    // 坐标偏移量
}

PearlEntity(物理模拟实体)

rust
pub struct PearlEntity<M: PearlMovement> {
    pub data: EntityData,       // 实体数据
    _movement: PhantomData<M>,  // 版本特定运动逻辑
}

泛型参数 M 决定使用的运动模型:

  • MovementLegacy:≤ 1.20.4
  • MovementPost1205:1.20.5 - 1.21.1
  • MovementPost1212:≥ 1.21.2

4.3 炮台配置

4.3.1 Cannon

运行时炮台配置,由 CannonSettings 转换而来。

定义

rust
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Cannon {
    pub pearl: Pearl,                           // 珍珠配置
    pub north_west_tnt: Space3D,                // 西北 TNT 位置
    pub north_east_tnt: Space3D,                // 东北 TNT 位置
    pub south_west_tnt: Space3D,                // 西南 TNT 位置
    pub south_east_tnt: Space3D,                // 东南 TNT 位置
    pub default_red_duper: Option<LayoutDirection>,   // 默认红色 Duper 方向
    pub default_blue_duper: Option<LayoutDirection>,  // 默认蓝色 Duper 方向
}

关联方法

rust
impl Cannon {
    pub fn from_settings(settings: &CannonSettings) -> Self;
}

4.3.2 CannonSettings

持久化炮台配置,支持 JSON 序列化。

定义

rust
#[derive(Debug, Clone, PartialEq, Deserialize, Serialize)]
#[serde(rename_all = "PascalCase")]
pub struct CannonSettings {
    #[serde(rename = "MaxTNT")]
    pub max_tnt: u32,                              // 最大 TNT 数量
    pub default_red_direction: Option<LayoutDirection>,
    pub default_blue_direction: Option<LayoutDirection>,
    #[serde(rename = "NorthWestTNT")]
    pub north_west_tnt: Space3D,
    #[serde(rename = "NorthEastTNT")]
    pub north_east_tnt: Space3D,
    #[serde(rename = "SouthWestTNT")]
    pub south_west_tnt: Space3D,
    #[serde(rename = "SouthEastTNT")]
    pub south_east_tnt: Space3D,
    pub offset: Surface2D,                         // 坐标偏移
    pub pearl: PearlInfo,                          // 珍珠信息
}

辅助结构

rust
pub struct PearlInfo {
    pub motion: Space3D,    // 初始速度
    pub position: Space3D,  // 初始位置
}

pub struct Surface2D {
    pub x: f64,
    pub z: f64,
}

4.4 计算输入

4.4.1 GeneralData

通用模拟输入数据。

rust
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct GeneralData {
    pub pearl_position: Space3D,    // 珍珠初始位置
    pub pearl_motion: Space3D,      // 珍珠初始速度(含 TNT 推力)
    pub tnt_charges: Vec<TNT>,      // TNT 列表(用于分时爆炸)
}

4.4.2 TNT

TNT 实体配置。

rust
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct TNT {
    pub position: Space3D,  // 位置
    pub fuse: u32,          // 引信 Tick(0 = 立即爆炸)
}

4.5 计算输出

4.5.1 TNTResult

TNT 搜索结果,单条配置方案。

rust
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct TNTResult {
    pub distance: f64,          // 与目标的 2D 距离
    pub tick: u32,              // 命中 Tick
    pub blue: u32,              // 蓝色 TNT 数量
    pub red: u32,               // 红色 TNT 数量
    pub total: u32,             // 总 TNT 数量
    pub pearl_end_pos: Space3D, // 珍珠最终位置
    pub pearl_end_motion: Space3D,  // 珍珠最终速度
    pub direction: Direction,   // 飞行方向
}

4.5.2 CalculationResult

轨迹追踪结果,包含完整飞行路径。

rust
#[derive(Debug, Clone, PartialEq)]
pub struct CalculationResult {
    pub landing_position: Space3D,       // 最终落点
    pub pearl_trace: Vec<Space3D>,       // 位置轨迹
    pub pearl_motion_trace: Vec<Space3D>,// 速度轨迹
    pub is_successful: bool,             // 是否命中目标
    pub tick: u32,                       // 模拟的最大 Tick 数(即传入的 max_ticks)
    pub final_motion: Space3D,           // 最终速度
    pub distance: f64,                   // 与目标距离
}

4.6 枚举类型

4.6.1 Direction

基本方向枚举,使用位标志表示。

rust
#[repr(u8)]
pub enum Direction {
    North = 1,   // 0b0001
    South = 2,   // 0b0010
    East  = 4,   // 0b0100
    West  = 8,   // 0b1000
}

方法

方法说明
invert()返回相反方向
from_angle(angle: f64)从角度判定方向

4.6.2 LayoutDirection

布局方向枚举,表示象限。

rust
pub enum LayoutDirection {
    NorthWest,  // 西北
    NorthEast,  // 东北
    SouthWest,  // 西南
    SouthEast,  // 东南
    North,      // 北
    South,      // 南
    West,       // 西
    East,       // 东
}

4.6.3 PearlVersion

Minecraft 版本枚举,决定物理计算方式。

rust
pub enum PearlVersion {
    Legacy,     // ≤ 1.20.4(float 精度)
    Post1205,   // 1.20.5 - 1.21.1
    Post1212,   // ≥ 1.21.2(运算顺序变化)
}

4.7 数据结构关系图

mermaid
graph TD
    subgraph Core["核心层"]
        Space3D --> EntityData
        AABBBox --> EntityData
        EntityData --> PearlEntity
        
        Space3D --> GeneralData
        GeneralData --> TNT
        
        Space3D --> TNTResult
        Space3D --> CalculationResult
    end
    
    subgraph Config["配置层"]
        Space3D --> CannonSettings
        Surface2D --> CannonSettings
        PearlInfo --> CannonSettings
        LayoutDirection --> CannonSettings
        
        CannonSettings --> Cannon
        Pearl --> Cannon
    end
    
    subgraph Enum["枚举"]
        Direction
        LayoutDirection
        PearlVersion
    end

5. 接口文档

如果你要调用计算引擎,这里是你需要的全部信息。我们使用了两种接口:Tauri IPC 命令(桌面版)和 WASM 导出函数(网页版)。


5.1 接口总览

运行时接口类型数量
Tauri 桌面IPC 命令6
WASM 网页导出函数3

5.2 Tauri Commands

5.2.1 calculate_tnt_amount_command

功能:搜索能命中目标的 TNT 配置方案。

调用方式

typescript
invoke<TNTResultOutput[]>("calculate_tnt_amount_command", { input: CalculationInput })

输入参数 CalculationInput

字段类型说明
pearlX, pearlY, pearlZf64珍珠初始位置
pearlMotionX, pearlMotionY, pearlMotionZf64珍珠初始速度
offsetX, offsetZf64坐标偏移量
cannonYf64炮台 Y 坐标
northWestTnt, northEastTnt, southWestTnt, southEastTntSpace3DInput四方向 TNT 位置
defaultRedDirection, defaultBlueDirectionstringDuper 方向
destinationX, destinationZf64目标坐标
maxTntu32最大 TNT 数量
maxTicksu32最大搜索 Tick
maxDistancef64最大误差距离
versionstringMC 版本 ("Legacy" / "Post1205" / "Post1212")

输出 TNTResultOutput[]

字段类型说明
distancef64与目标的 2D 距离
ticku32命中 Tick
blue, red, totalu32TNT 数量
pearlEndPosSpace3DOutput珍珠最终位置
pearlEndMotionSpace3DOutput珍珠最终速度
directionstring飞行方向

5.2.2 calculate_pearl_trace_command

功能:计算指定 TNT 配置下的完整珍珠轨迹。

调用方式

typescript
invoke<PearlTraceOutput>("calculate_pearl_trace_command", { input: PearlTraceInput })

输入参数 PearlTraceInput

字段类型说明
redTnt, blueTntu32红/蓝 TNT 数量
pearlX, pearlY, pearlZf64珍珠初始位置
pearlMotionX, pearlMotionY, pearlMotionZf64珍珠初始速度
offsetX, offsetZf64坐标偏移量
cannonYf64炮台 Y 坐标
northWestTnt, northEastTnt, southWestTnt, southEastTntSpace3DInput四方向 TNT 位置
defaultRedDirection, defaultBlueDirectionstringDuper 方向
destinationX, destinationZf64目标坐标
directionstring?飞行方向(可选)
versionstringMC 版本

输出 PearlTraceOutput

字段类型说明
landingPositionSpace3DOutput最终落点
pearlTraceSpace3DOutput[]位置轨迹
pearlMotionTraceSpace3DOutput[]速度轨迹
isSuccessfulbool是否命中目标
ticku32飞行 Tick 数
finalMotionSpace3DOutput最终速度
distancef64与目标距离
closestApproachClosestApproachOutput?最近接近点

5.2.3 calculate_raw_trace_command

功能:自由模拟器,支持自定义 TNT 位置和数量。

调用方式

typescript
invoke<PearlTraceOutput>("calculate_raw_trace_command", { input: RawTraceInput })

输入参数 RawTraceInput

字段类型说明
pearlX, pearlY, pearlZf64珍珠初始位置
pearlMotionX, pearlMotionY, pearlMotionZf64珍珠初始速度
tntGroupsTntGroupInput[]TNT 组列表
versionstringMC 版本

TntGroupInput

字段类型说明
x, y, zf64TNT 位置
amountu32TNT 数量

5.2.4 verify_config

功能:验证配置文件格式是否正确。

调用方式

typescript
invoke<string>("verify_config", { path: string })

输入:配置文件绝对路径

输出:验证结果消息或错误信息


5.2.5 load_config

功能:从文件加载炮台配置。

调用方式

typescript
invoke<CannonSettings>("load_config", { path: string })

输入:配置文件绝对路径

输出:第一个炮台配置的 JSON 对象


5.2.6 load_config_from_content

功能:从 JSON 字符串加载炮台配置。

调用方式

typescript
invoke<CannonSettings>("load_config_from_content", { content: string })

输入:配置文件 JSON 内容

输出:第一个炮台配置的 JSON 对象


5.3 WASM Exports

WASM 模块通过 wasm-bindgen 导出以下函数,可在 JavaScript 环境中直接调用。

5.3.1 calculate_tnt_amount

功能:与 Tauri 版本相同,搜索 TNT 配置方案。

签名

typescript
function calculate_tnt_amount(input: CalculationInput): TNTResultOutput[];

使用示例

typescript
import init, { calculate_tnt_amount } from "pearl_calculator_wasm";

await init();
const results = calculate_tnt_amount({
    pearlX: 0.5,
    pearlY: 64.0,
    pearlZ: 0.5,
    // ... 其他参数
});

5.3.2 calculate_pearl_trace

功能:计算指定 TNT 配置下的完整轨迹。

签名

typescript
function calculate_pearl_trace(input: PearlTraceInput): PearlTraceOutput;

5.3.3 calculate_raw_trace

功能:自由模拟器。

签名

typescript
function calculate_raw_trace(input: RawTraceInput): PearlTraceOutput;

5.4 通用数据类型

5.4.1 Space3DInput(输入)

typescript
interface Space3DInput {
    x: number;
    y: number;
    z: number;
}

5.4.2 Space3DOutput(输出)

typescript
interface Space3DOutput {
    X: number;  // 注意大写
    Y: number;
    Z: number;
}

5.4.3 ClosestApproachOutput

typescript
interface ClosestApproachOutput {
    tick: number;      // 最近接近 Tick
    point: Space3DOutput;  // 最近接近点坐标
    distance: number;  // 最近距离
}

5.5 错误处理

所有 API 调用均返回 Result 类型:

错误类型说明
"Invalid pearl version"版本字符串不合法
"Invalid red direction"红色 Duper 方向不合法
"Pearl trace calculation failed"轨迹计算失败
"Raw trace calculation failed"自由模拟失败
"No cannon configurations found in the file"配置文件无有效炮台
"Failed to parse configuration: ..."配置 JSON 解析失败

5.6 调用流程图

mermaid
sequenceDiagram
    participant JS as JavaScript
    participant Bridge as Bridge Layer
    participant Core as Core Engine

    alt Tauri 桌面模式
        JS->>+Bridge: invoke("calculate_tnt_amount_command", input)
        Note over Bridge: 反序列化 CalculationInput
        Bridge->>+Core: calculate_tnt_amount(&cannon, ...)
        Core-->>-Bridge: Vec<TNTResult>
        Note over Bridge: 序列化为 TNTResultOutput[]
        Bridge-->>-JS: JSON 结果
    else WASM 网页模式
        JS->>+Bridge: calculate_tnt_amount(JsValue)
        Note over Bridge: serde_wasm_bindgen::from_value
        Bridge->>+Core: calculate_tnt_amount(&cannon, ...)
        Core-->>-Bridge: Vec<TNTResult>
        Note over Bridge: serde_wasm_bindgen::to_value
        Bridge-->>-JS: JsValue 结果
    end

6. 附录

6.1 参考资料

6.2

这是モニカ・エヴァレット,没别的意思,她也没走丢,也没生病,也没有被我绑架。就是她实在太可爱了,忍不住想发出来让你们也看看。

モニカ・エヴァレット

PearlCalculatorRS:Minecraft FTL 计算器开发笔记

https://tail.lemonmiaow.xyz/posts/pearlcalculatorrs-design-and-implementation/
作者 Lemon_miaow
发布于 2025-12-11
许可协议 CC BY-NC-ND 4.0