文章介绍本人使用穷举法计算在各种染色玻璃排列下信标光柱的颜色。

相关文章：Minecraft 信标颜色大全

准备工作

首先我们要获取游戏中计算信标光柱颜色的算法。

使用 yarn 反编译Minecraft Java 1.21.1的源码，找到/net/minecraft/block/entity/BeaconBlockEntity.java

核心代码如下：

1
lv2 = new BeamSegment(ColorHelper.Argb.averageArgb(lv2.color, n));
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
public class ColorHelper {

    public static class Rgb {

        public static int getRed(int argb) {
            return argb >> 16 & 0xFF;
        }

        public static int getGreen(int argb) {
            return argb >> 8 & 0xFF;
        }

        public static int getBlue(int argb) {
            return argb & 0xFF;
        }

        public static int getArgb(int red, int green, int blue) {
            return red << 16 | green << 8 | blue;
        }

        public static int mixColor(int first, int second) {
            return Rgb.getArgb(Rgb.getRed(first) * Rgb.getRed(second) / 255, 
                    Rgb.getGreen(first) * Rgb.getGreen(second) / 255, 
                    Rgb.getBlue(first) * Rgb.getBlue(second) / 255);
        }

        public static int averageArgb(int a, int b) {
            return Rgb.getArgb((Rgb.getRed(a) + Rgb.getRed(b)) / 2, 
                    (Rgb.getGreen(a) + Rgb.getGreen(b)) / 2, 
                    (Rgb.getBlue(a) + Rgb.getBlue(b)) / 2);
        }
    }

}

averageArgb()用于计算上一层信标颜色和当前层染色玻璃的平均颜色。

mixColor()用于计算信标颜色和纹理贴图混合后在游戏中渲染出的颜色。

Java

首先定义16种染色玻璃颜色：

1
2
3
public final static int[] colorValue = {
        0xF9FFFE, 0xF9801D, 0xC74EBD, 0x3AB3DA, 0xFED83D, 0x80C71F, 0xF38BAA, 0x474F52,
        0x9D9D97, 0x169C9C, 0x8932B8, 0x3C44AA, 0x835432, 0x5E7C16, 0xB02E26, 0x1D1D21};

由于信标颜色需要和游戏资源中的纹理贴图/assets/minecraft/textures/entity/beacon_beam.png混合后渲染到游戏画面中，还需要计算出纹理贴图的平均颜色，使用mixColor()计算出渲染颜色：

1
2
3
4
5
public final static int beamTextureColor = 0xbed2d0;

public static int getRenderColor(int color) {
    return ColorHelper.Rgb.mixColor(color, beamTextureColor);
}

定义getColorsList()方法，用于输出染色玻璃的排列：

1
2
3
4
5
6
7
public static String getColorsList(int[] colors) {
    StringBuilder sb = new StringBuilder();
    for (int color : colors) {
        sb.append(Integer.toHexString(color).toUpperCase());
    }
    return sb.toString();
}

定义一个HashSet，用于去重：

1
public static HashSet<Integer> set = new HashSet<>();

编写主函数，使用穷举法计算信标颜色，并输出到文件：

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
40
41
42
43
44
45
46
47
for (int i = 0; i < 16; i++) {
    set.add(colorValue[i]);
}
BufferedWriter bw = new BufferedWriter(new FileWriter("资料/4h.csv"));
for (int i = 0; i < 16; i++) {
    for (int j = 0; j < 16; j++) {
        int color = ColorHelper.Rgb.averageArgb(colorValue[i], colorValue[j]);
        if (set.add(color)) {
            bw.write(String.format("%06X,%06X,%s\n",
                    color,
                    getRenderColor(color),
                    getColorsList(new int[]{i, j})));
        }
    }
}
for (int i = 0; i < 16; i++) {
    for (int j = 0; j < 16; j++) {
        int color1 = ColorHelper.Rgb.averageArgb(colorValue[i], colorValue[j]);
        for (int k = 0; k < 16; k++) {
            int color = ColorHelper.Rgb.averageArgb(color1, colorValue[k]);
            if (set.add(color)) {
                bw.write(String.format("%06X,%06X,%s\n",
                        color,
                        getRenderColor(color),
                        getColorsList(new int[]{i, j, k})));
            }
        }
    }
}
for (int i = 0; i < 16; i++) {
    for (int j = 0; j < 16; j++) {
        int color1 = ColorHelper.Rgb.averageArgb(colorValue[i], colorValue[j]);
        for (int k = 0; k < 16; k++) {
            int color2 = ColorHelper.Rgb.averageArgb(color1, colorValue[k]);
            for (int l = 0; l < 16; l++) {
                int color = ColorHelper.Rgb.averageArgb(color2, colorValue[l]);
                if (set.add(color)) {
                    bw.write(String.format("%06X,%06X,%s\n",
                            color,
                            getRenderColor(color),
                            getColorsList(new int[]{i, j, k, l})));
                }
            }
        }
    }
}
bw.close();

Java 多线程

随着染色玻璃层数的增加，计算量大大增加，使用单线程便力不从心，因此需要使用多线程加速计算。

首先需要解决的问题是，随着数据量的增加，使用HashSet去重会大幅增加计算时间，因此将其修改为以下代码：

1
public static volatile boolean[] map = new boolean[0x1000000];

每计算出一个颜色值color，就将map[color]设为true。

编写初始化方法，从之前输出的文件中读取数据：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static void init(int max) throws IOException {
    if (max < 4) {
        throw new IllegalArgumentException("max must be at least 4");
    }
    for (int i = 4; i <= max; i++) {
        File file = new File("资料/" + i + "h.csv");
        if (!file.isFile()) continue;
        BufferedReader br = new BufferedReader(new java.io.FileReader(file));
        String line;
        while ((line = br.readLine()) != null) {
            if (line.isEmpty()) continue;
            String[] parts = line.split(",");
            int color = Integer.parseInt(parts[0], 16);
            map[color] = true;
        }
        br.close();
    }
}

编写线程逻辑：

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
public class ComputeThread extends Thread {
    private final int i, j;
    private final BufferedWriter bw;
    public ComputeThread(int i, int j, BufferedWriter bw) {
        this.i = i;
        this.j = j;
        this.bw = bw;
    }

    @Override
    public void run() {
        int color1 = ColorHelper.Rgb.averageArgb(colorValue[i], colorValue[j]);
        for (int k = 0; k < 16; k++) {
            int color2 = ColorHelper.Rgb.averageArgb(color1, colorValue[k]);
            for (int l = 0; l < 16; l++) {
                int color3 = ColorHelper.Rgb.averageArgb(color2, colorValue[l]);
                for (int m = 0; m < 16; m++) {
                    int finalColor = ColorHelper.Rgb.averageArgb(color3, colorValue[m]);
                    if (!map[finalColor]) {
                        map[finalColor] = true;
                        try {
                            bw.write(String.format("%06X,%06X,%s\n",
                                    finalColor,
                                    getRenderColor(finalColor),
                                    getColorsList(new int[]{i, j, k, l, m})));
                        } catch (IOException e) {
                            throw new RuntimeException(e);
                        }
                    }
                }
            }
        }
    }
}

修改主函数，使用线程池计算：

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
init(4);
System.out.println("初始化完成");
long start = System.currentTimeMillis();
ThreadPoolExecutor executor = new ThreadPoolExecutor(
        32,
        32,
        1,
        TimeUnit.MILLISECONDS,
        new ArrayBlockingQueue<>(256),
        new ThreadPoolExecutor.CallerRunsPolicy()
);
BufferedWriter bw = new BufferedWriter(new FileWriter("资料/5h.csv"));
for (int i = 0; i < 16; i++) {
    for (int j = 0; j < 16; j++) {
        if (i == j) continue;
        ComputeThread thread = new ComputeThread(i, j, bw);
        executor.execute(thread);
    }
}
executor.shutdown();
while (!executor.isTerminated()) {
    Thread.sleep(1);
}
bw.close();
long end = System.currentTimeMillis();
System.out.printf("完成5层计算，耗时: %.2f 秒%n",
        (end - start) / 1000.0);

运行结束后发现，虽对boolean[] map使用了volatile关键字，但还是会出现重复的颜色值。

此时有两个解决方法：

第一种，使用原子类Atomic，可以保证线程安全，不会出现重复值。第二种，在运行结束后再对结果进行去重。

测试后发现，第一种方法确实可以杜绝重复值，但会导致计算时间延长，随着层数的增加，多花费的时间将不可接受。而第二种方法中，重复的数据数量和去除花费的时间都在接受范围内，因此采用方法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void deduplicate(String inputFile, String outputFile) throws IOException {
    BufferedReader br = new BufferedReader(new FileReader(inputFile));
    BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile));
    TreeSet<String> uniqueLines = new TreeSet<>();
    String line;
    while ((line = br.readLine()) != null) {
        if (line.isEmpty()) continue;
        String[] parts = line.split(",");
        if (uniqueLines.add(parts[0])) {
            bw.write(line.concat("\n"));
        }
    }
    br.close();
    bw.close();
}

在层数再度增加后，手动增加for循环层数比较麻烦，且过多的循环嵌套代码不够美观，因此询问AI，做出如下修改：

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class ComputeThread extends Thread {
    private final int[] indices;
    private final int layerCount;
    private final BufferedWriter bw;

    public ComputeThread(int i, int j, int k, int layerCount, BufferedWriter bw) {
        this.indices = new int[layerCount];
        this.indices[0] = i;
        this.indices[1] = j;
        this.indices[2] = k;
        this.layerCount = layerCount;
        this.bw = bw;
    }

    @Override
    public void run() {
        int color = ColorHelper.Rgb.averageArgb(
                ColorHelper.Rgb.averageArgb(
                        colorValue[indices[0]], colorValue[indices[1]]
                ), colorValue[indices[2]]
        );
        processLayer(3, color);
        try {
            bw.flush();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        count.incrementAndGet();
    }

    private void processLayer(int depth, int currentColor) {
        if (depth == layerCount) {
            if (!map[currentColor]) {
                map[currentColor] = true;
                int renderColor = getRenderColor(currentColor);
                try {
                    bw.write(String.format("%06X,%06X,%s\n",
                            currentColor,
                            renderColor,
                            getColorsList(indices)));
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return;
        }
        for (int k = 0; k < 16; k++) {
            indices[depth] = k;
            int nextColor = ColorHelper.Rgb.averageArgb(currentColor, colorValue[k]);
            processLayer(depth + 1, nextColor);
        }
    }
}

最终成功计算完12层。

CUDA

在染色玻璃增加到13层时，即使是将本人的13900HX全部线程利用上，也预计需要半年的时间才能穷举完。

此时就需要使用GPU完成计算任务。

首先需要将工具类转换为C++语言：

ColorHelper.cuh:

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
__device__ int getRed(int argb) {
    return (argb >> 16) & 0xFF;
}

__device__ int getGreen(int argb) {
    return (argb >> 8) & 0xFF;
}

__device__ int getBlue(int argb) {
    return argb & 0xFF;
}

__device__ int getRgb(int red, int green, int blue) {
    return (red << 16) | (green << 8) | blue;
}

__device__ int mixColor(int first, int second) {
    return getRgb(
        (getRed(first) * getRed(second)) / 255,
        (getGreen(first) * getGreen(second)) / 255,
        (getBlue(first) * getBlue(second)) / 255
    );
}

__device__ int averageRgb(int a, int b) {
    return getRgb(
        (getRed(a) + getRed(b)) / 2,
        (getGreen(a) + getGreen(b)) / 2,
        (getBlue(a) + getBlue(b)) / 2
    );
}

Util.cuh:

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
#include <time.h>
#include <Windows.h>

// Windows环境获取时间戳
long long getCurrentTimeMillis()
{
    time_t tt;
    time(&tt);
    SYSTEMTIME t1;
    GetSystemTime(&t1);
    return tt * 1000 + (int)t1.wMilliseconds;
}

// 使用长整型存储染色玻璃排列
__device__ long long getArray(int arr[], int length)
{
    long long total = 0;
    for (int i = 0; i < length; i++)
    {
        total = (total << 4) + arr[i];
    }
    total = total << (4 * (16 - length));
    return total;
}

// 将长整型存储的染色玻璃排列转换为字符串
string getArrayStringHex(long long arr, int length)
{
    stringstream oss;
    for (int i = 0; i < length; i++)
    {
        int part = (arr >> (4 * (15 - i))) & 0xF;
        oss << hex << uppercase << part;
    }
    return oss.str();
}

ColorUtil.cuh:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <string>
#include <sstream>
#include <iomanip>

using namespace std;

string int2hex(int num) {
    stringstream oss;
    oss << setfill('0') << setw(6) << hex << uppercase << num;
    return oss.str();
}

int hex2int(string hex) {
    return stoi(hex, nullptr, 16);
}

编写初始化方法：

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
int init(int max) 
{
    if (max < 4)
    {
        cerr << "Max must be at least 4.\n";
        return 1;
    }
    
    cout << "Initing...\n";
    int icount = 0;
    for (size_t i = 4; i <= max; i++)
    {
        const string readFilePath = "D:\\Java Project\\beacon\\资料\\" + to_string(i) + "h.csv";
        ifstream inputFile(readFilePath);
        if (!inputFile.is_open())
        {
            cerr << "Could not open " << i << "\n";
            continue;
        }
        string line;
        while (getline(inputFile, line))
        {
            if (line.length() == 0) continue;
            int color = hex2int(line.substr(0, 6));
            mapCPU[color] = 1;
            icount++;
        }
        if (inputFile.bad())
        {
            cerr << "Unknown exception while reading the file " << i << "\n";
        }
        
        inputFile.close();
    }
    cout << "Init finish. Read " << icount << " colors.\n";
    return 0;
}

编写Beacon.cu:

1
2
3
4
5
6
7
8
9
10
__device__ int mapGPU[16777216];
__device__ int keys[16777216];
__device__ long long values[16777216];
__device__ unsigned long long tcount = 0;
__device__ int layerCount = 13;

__device__ const int colorValue[] = {
        0xF9FFFE, 0xF9801D, 0xC74EBD, 0x3AB3DA, 0xFED83D, 0x80C71F, 0xF38BAA, 0x474F52,
        0x9D9D97, 0x169C9C, 0x8932B8, 0x3C44AA, 0x835432, 0x5E7C16, 0xB02E26, 0x1D1D21
};

编写核函数：

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
40
41
42
43
44
45
46
47
__global__ void compute(unsigned long long offset) 
{
    int i = blockIdx.x;
    int j = threadIdx.x / 16;

    if (i == j) return;

    int k = threadIdx.x % 16;
    int f4 = (offset >> 0) & 0xF;
    int f5 = (offset >> 4) & 0xF;
    int f6 = (offset >> 8) & 0xF;
    int f7 = (offset >> 12) & 0xF;
    int f8 = (offset >> 16) & 0xF;
    int f9 = (offset >> 20) & 0xF;
    int f10 = (offset >> 24) & 0xF;

    int currentColor = averageRgb(colorValue[i], colorValue[j]);
    currentColor = averageRgb(currentColor, colorValue[k]);
    currentColor = averageRgb(currentColor, colorValue[f4]);
    currentColor = averageRgb(currentColor, colorValue[f5]);
    currentColor = averageRgb(currentColor, colorValue[f6]);
    currentColor = averageRgb(currentColor, colorValue[f7]);
    currentColor = averageRgb(currentColor, colorValue[f8]);
    currentColor = averageRgb(currentColor, colorValue[f9]);
    currentColor = averageRgb(currentColor, colorValue[f10]);

    for (int f11 = 0; f11 < 16; f11++)
    {
        int color11 = averageRgb(currentColor, colorValue[f11]);
        for (int f12 = 0; f12 < 16; f12++)
        {
            int color12 = averageRgb(color11, colorValue[f12]);
            for (int f13 = 0; f13 < 16; f13++)
            {
                int color13 = averageRgb(color12, colorValue[f13]);
                if (mapGPU[color13] == 0)
                {
                    unsigned long long idx = atomicAdd(&tcount, 1);
                    keys[idx] = color13;
                    int is[] = {i, j, k, f4, f5, f6, f7, f8, f9, f10, f11, f12, f13};
                    long long arr = getArray(is, 13);
                    values[idx] = arr;
                }
            }
        }
    }
}

编写主函数：

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
int mapCPU[16777216];
int keysCPU[16777216];
long long valuesCPU[16777216];

int init(int max);
void writeOutputToFile(const string& filename);

int main() 
{
    long long time_0 = getCurrentTimeMillis();
    int code = init(13);
    if (code != 0) return code;
    
    long long time_1 = getCurrentTimeMillis();
    cudaMemcpyToSymbol(mapGPU, mapCPU, sizeof(int) * 16777216, 0, cudaMemcpyHostToDevice);

    long long prevTime = getCurrentTimeMillis();
    long long currentTime = prevTime;
    
    long long currentBatch = 0;
    long long toBatch = 268435456;
    
    for (unsigned long long batch = currentBatch; batch < toBatch; batch ++) {
        if (batch % 30000 == 0) 
        {
            prevTime = currentTime;
            currentTime = getCurrentTimeMillis();
            long long diff = currentTime - prevTime;
            long long tasksLeft = toBatch - batch;
            long long estimatedTime = ((tasksLeft * diff / 30000) + 500) / 1000;
            cout << "\r" << batch << " / " << toBatch << ", estimated " << estimatedTime << " s left.";
        }
        compute<<<16, 256>>>(batch);
        cudaDeviceSynchronize();
    }

    long long time_2 = getCurrentTimeMillis();

    cudaError_t err;
    err = cudaMemcpyFromSymbol(keysCPU, keys, sizeof(int) * 16777216, 0, cudaMemcpyDeviceToHost);
    if (err != cudaSuccess) {
        cerr << "cudaMemcpyFromSymbol keys failed: " << cudaGetErrorString(err) << endl;
        return -1;
    }
    err = cudaMemcpyFromSymbol(valuesCPU, values, sizeof(long long) * 16777216, 0, cudaMemcpyDeviceToHost);
    if (err != cudaSuccess) {
        cerr << "cudaMemcpyFromSymbol values failed: " << cudaGetErrorString(err) << endl;
        return -1;
    }
    writeOutputToFile("D:\\Java Project\\beacon\\资料\\13h1.csv");

    long long time_3 = getCurrentTimeMillis();

    cout << "\n任务完成\n";
    cout << "Init time: " << (time_1 - time_0) << " ms\n";
    cout << "Compute time: " << (time_2 - time_1) << " ms\n";
    cout << "Copy back time: " << (time_3 - time_2) << " ms\n";
    cout << "Total time: " << (time_3 - time_0) << " ms\n";
    cout << "toBatch: " << toBatch << "\n";

    return 0;
}

void writeOutputToFile(const string& filename) 
{
    ofstream outFile(filename);
    if (outFile.is_open()) 
    {
        for (int i = 0; i < 16777216; i++) 
        {
            if (keysCPU[i] != 0) 
            {
                outFile << int2hex(keysCPU[i]) << "," << getArrayStringHex(valuesCPU[i], 13) << "\n";
            }
            else
            {
                continue;
            }
        }
        outFile.close();
        cout << "Output written to " << filename << "\n";
    } 
    else 
    {
        cerr << "Unable to open file " << filename << " for writing.\n";
    }
}

运行后发现报错。经测试发现，keys和values被塞满，里面含有大量（应该说是巨量）相同数据。推测是因为GPU的线程实在是太多，且相邻的排列方式会导致同一时间出现大量相同的混合后颜色。

如果使用原子操作，同样会导致时间大大延长，预计需要4个月。

经过思考，想出了一个好办法：将核函数中的用于遍历的f11顺序打乱，这样同一时间不同线程排列的染色玻璃就会被打乱，混合后的颜色也不尽相同，就可以避免相同颜色扎堆出现。

询问AI，使用Fisher-Yates洗牌算法与线性同余生成器 (LCG)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
__device__ void generateShuffledArray(int* d_output, unsigned int seed) {
    int arr[16] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};

    const unsigned a = 1664525;
    const unsigned c = 1013904223;
    unsigned lcg_state = seed;

    for (int i = 15; i > 0; --i) {
        lcg_state = lcg_state * a + c;
        int j = lcg_state % (i + 1);
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    for (int i = 0; i < 16; ++i) {
        d_output[i] = arr[i];
    }
}

修改核函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
__global__ void compute(unsigned long long offset) 
{
    ......
    int r[16];
    generateShuffledArray(r, (offset ^ ((blockIdx.x << 8) | threadIdx.x)) + clock64());
    for (int r11 = 0; r11 < 16; r11++)
    {
        int f11 = r[r11];
        int color11 = averageRgb(currentColor, colorValue[f11]);
        for (int f12 = 0; f12 < 16; f12++)
        {
    ......
}

最终，成功在不到一周时间内算完13层。