MI—电力系统工作原理

介绍

  现代工业 中包含了很多的公用 API，本篇博文就来详解剖析其中的电力系统的设计思想。

  欢迎正在编写类似功能的小伙伴借鉴我的设计，也欢迎各位大佬指出其中的不足之处。

  电力系统是一个工业模组最为核心的组成之一，在我的设计中，电力系统又以下两个部分组成：

1. 能量传输网络（导线）
2. 发电机和用电器

  看到后面会发现其实用电器也可以不算作电力系统的一部分，因为在我的设计中其可以不负责任何任务。

  本设计基于MC-1.12.2进行开发，设计思想可在任意版本使用，但不保证代码可以百分百兼容所有版本。

基本设计思想

能量

  在开始之前我们先介绍一下 MI 中表示能量的方法：

1
2
3
4
5
6
7
8
9

class EleEnergy(
    val capability: Int,
    val voltage: Int
) {
    
    val current: Int
        get() = if (voltage == 0) 0 else capability / voltage
    
}

  很明显，我们可以发现，一个能量由“电压”、“电流”和“能量”三部分组成（能量写成capability的原因是考虑很多地方会使用energy一词保存该类的对象，如果变量名叫energy的话很容易出现energy.energy的写法，很不美观）。

  其中capability和voltage是需要外部传入的值，current则由两者做除法求值，这也不难看出一个公式：capability ≈ voltage * current。

  我们不保证该式两边恒等，因为整数除法会出现精度损失。至于为什么把current设计成被计算出来的值，是因为在实际使用中，我们更关心一个能量的capability与voltage，current通常仅用来计算传输网络中的电损，所以让前两者永远保持为准确值，而后者为“估读值”。

工作流程

1. 用电器向周围导线请求能量
2. 导线在网络中查找可以提供能量的方块
3. 导线把获取到的能量返回给用电器

发电机与用电器

  首先我们来说最简单的部分：发电机和用电器（下文用发电机同时指代发电机与用电器）。

  为了考虑兼容性，我们让发电机包含一个Capability，不了解Capability的可以参考下面的资料：

• Capability系统与已有实体附加属性
• Forge Capability 系统

  于是一个简易的接口就被设计出来了：

1
2
3
4
5
6
7
8
9
10
11
12

interface IElectricityCap {

    /**
     * 从该方块取出能量
     *
     * @param maxEnergy 需要的能量
     * @param loss 电损计算
     * @return 成功取出的能量，[EleEnergy.capacity] <= [maxEnergy]
     */
    fun extract(maxEnergy: Int, loss: (EleEnergy) -> Int): EleEnergy

}

  看起来设计的非常简单，不过在实际应用的时候我们会遇到一个问题：无法确定到底能够取出来多少能量。

  看到这里读者可能会疑惑，为什么会无法确定呢？这个方法的返回值不就是用来告知调用者取出了多少能量吗？

  我们来看其中的一个很重要的参数：loss: (EleEnergy) -> Int，这是用于计算电力传输网络的电损的一个函数接口。可以发现电损的计算依赖于发电机向外传输的能量信息，这样我们就无法一次性确定能否取出指定数额的能量。

  为了解决这个问题，我们引入了一种计算方法——二分，大体思路为使用二分的方法来查找能够输出的最大能量。

  为了避免每次实现该接口都写一遍二分，我们将接口拓展为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

interface IElectricityCap {

    /**
     * 从该方块取出能量
     *
     * 方法使用二分查找法查找可以输出的最大能量值，在进行二分查找前会先对最大输出进行尝试
     *
     * @param maxEnergy 需要的能量
     * @param loss 电损计算
     * @return 成功取出的能量，[EleEnergy.capacity] <= [maxEnergy]
     */
    fun extract(maxEnergy: Int, loss: (EleEnergy) -> Int): EleEnergy {
        var energy = checkEnergy(maxEnergy, loss)
        if (energy.isNotEmpty()) return energy.copy(voltage = energy.voltage)
        var left = 0
        var right = maxEnergy
        do {
            val mid = (left + right).ceilDiv2()
            energy = checkEnergy(mid, loss)
            if (energy.isEmpty) right = mid - 1
            else left = mid + 1
        } while (left <= right)
        if (left == 0) return EleEnergy.empty
        consumeEnergy(energy.capacity)
        return energy.copy(left - 1)
    }

    /** 消耗指定数额的能量，当方块内部能量不足以消耗时应当抛出异常 */
    fun consumeEnergy(energy: Int)

    /**
     * 检查指定数额的能量是否可以被取出
     * @param energy 需要取出的能量
     * @param loss 电损计算公式
     * @return 不能取出返回 [EleEnergy.empty]，否则返回实际消耗的电能
     */
    fun checkEnergy(energy: Int, loss: (EleEnergy) -> Int): EleEnergy

}

  这样，只需要发电机中包含该capability就可以参与到电力系统的工作之中。

电力传输网络

  电力传输网络是电力系统中最重要也是最复杂的部分，目前 API 仅支持实体方块作为电力传输网络的组成，有支持非实体方块的想法，但开发尚未提上日程。

导线方块

  电力传输在这个设计中要负责的任务很简单，就是在网络中搜索发电机。这个任务看起来非常简单，但是实际开发中我们要考虑很多事情，尤其是性能。

  综合考虑下来，我们肯定需要为每一个网络建立一个缓存，以此避免每次搜索发电机时都将网络全部遍历一遍。

  同时在 MI 中是禁止导线分叉的，即一条线路一定能够拉伸成一条直线且不会形成回路。这样设计有两个优点：

1. 实现简单
2. 拥有更好的性能

  为了实现快速计算电力传输的电损，我们规定两根规格不同（包括类型、材质等）的导线不能直接相连；然后给线路中的每一根导线赋予一个唯一的编号，且相邻两根导线的编号之差的绝对值为1，同时我们保证该编号一定单调递增（或递减）。

  这样，我们就可以通过O(1)的时间复杂度求解两根导线方块之间的距离和电损。

  PS：有些人可能会质疑不同的导线不能直接相连是否会影响游玩体验。在实际游玩中，玩家使用同类导线进行线路铺设是最常见的，所以就算有影响也不会特别大；而且在现实中不同材质、粗细的导线直接连接也很容易出现意外。所以总结下来只要我们后续提供一个接线器就不会很影响游玩体验，同时也切合实际。

缓存

  接下来就是重中之重了——线路缓存。

  首先我们要明确缓存中必须存储的信息是什么，那就是与非导线方块存在连接关系的导线坐标。只有缓存了该信息，我们才能在搜索发电机时避免遍历整条线路。

  接下来再考虑我们是否需要离线存储缓存信息？我们来对比一下实现以及不实现的优劣。

  如果我们不实现离线存储，这时候会有一个很重要的问题：如果一条线路很长，在加载存档的过程中可能会出现只加载了线路的一部分的情况，如果线路的两端被加载而中间却处于未加载的区域，那么这段导线将同时持有两个独立的缓存。当玩家触发中间区域的加载后，我们还需要将两个缓存整合为一个缓存，不然会有空间上的浪费。同时在触发中间区域的加载之前，因为我们无法在一段遍历到另一端，所以两端的机器也是相互独立的，相当于处于两个电力网络中。

  反过来，如果我们实现离线存储，上述问题就可以成功解决，不过会产生一个新的问题：代码会更加复杂，同时更容易产生 bug。

  综合考虑后，我选择实现缓存的离线存储。方案定下来之后就是具体实现了，我们如何实现离线存储呢？

  看了上面对工作流程的介绍我们不难发现，我们需要能够通过线路中的某一个方块获取到这个线路的缓存，所以导线方块的 TE 中应该需要一个变量来存储缓存的引用。

  不过我们也可以不让导线直接存储缓存对象的引用，而是存储一个id，然后通过一个全局静态的表来存储每个id对应哪一个缓存。这样我们在加载存档的时候就可以直接将当前导线添加到对应的缓存中，就算一条线路中间有部分区域未加载，我们也可以绕过这段线路直接让两端的方块进行交互。

  分配 ID 相对来说是一个比较简单的操作，int可以表示 2³² 个值，所以我们完全可以使用int当作缓存的 ID，即使每天分配十万个 ID，也需要一百多年才能轮回一次。

  当然为了避免极端情况，最好用一个全局的表存储正在使用的 ID，分配 ID 的时候检查一下是否冲突，冲突则向后分配。

  接下来我们再考虑如何维护这个缓存，为了维护缓存我们需要以下四种操作：

1. 边缘拓展
2. 随机更新
3. 切分
4. 合并

  边缘拓展和随机更新是缓存维护中最简单的两个操作，前者是在缓存的边界添加新的导线方块，后者是当导线发生变化时更新其在缓存中对应的值。

  切分和合并相对于前两者就复杂多了。这两个操作涉及缓存 ID 和导线编号的更新，为了在更新缓存 ID 和导线编号时避免遍历线路，我们再创建两个全局的表，前者用来存储 ID 更新的相关数据，后者用来存储编号更新的相关数据。

  对于 ID 更新，我们在表中按照如下格式存储数据：

1
2
3
4
5
6

data class Node(
    val count: Int,
    val split: Int,
    val leftNewId: Int,
    val rightNewId: Int
)

  存储时以旧 ID 为 key，其中：

• count用于统计还有多少个导线方块依赖当前项，当count为 0 时就可以将该项从表中移除
• split用于标记当前缓存从哪个地方切分（该值为导线编号）
• leftNewId用于标记位于切分点左侧（编号小于split）的导线的新 ID
• rightNewId用于标记位于切分点及切分点右侧（编号大于等于split）的导线的新 ID

  对于编号更新，我们采用类似的方式：

1
2
3
4
5
6
7

data class Node(
    val map: CableCodeTransformEnum,
    var count: Int,
    val min: Int,
    val max: Int,
    val value: Int
)

  同样，我们存储时以旧 ID 为 key，其中：

• map用于标记编号的更新方式，目前支持两种更新：整体增加或对称翻转后增加
• count用于统计还有多少个导线方块依赖当前项，当该值为 0 时就可以将该项从表中移除
• min用于标记最小的编号
• max用于标记最大的编号
• value用于存储偏移量

  接下来，我们只需要每次访问编号和缓存 ID 之前先更新一次数据即可，同时为了应对对线路的连续编辑操作，更新数据时应当使用链式搜索的方法进行更新，以此获取最新值。

  注意：更新缓存 ID 前必须先更新编号，而更新编号也必须在更新缓存 ID 前进行更新。

  于是，我们成功通过两个全局的表完成了导线编号和缓存 ID 的更新。

  全部算下来，我们一共使用了三个表来实现缓存的控制：

1. IdAllocator - 缓存 ID 分配器
2. InvalidCacheManager - 缓存 ID 更新器
3. InvalidCodeManager - 导线编号更新器

  具体的缓存维护逻辑比较复杂且容易出错，这里不再列出代码，具体代码见github。

  以上就是电力系统的大体设计思路了，具体实现可以到github查看。