前一段时间笔试遇到了好几次组合数的题目（当然也可能其实是用动态规划去做），笔试时看着算法超时有一种深深的无力感。最近有空收集了一点组合数计算的算法，算是以一个非竞赛选手的视角去描述这些算法（公式证明什么的就算了，主要负责用）。




## 递推式预处理

### 原理

- 组合数递推公式：$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$

### 算法复杂度

- 空间复杂度 
 - 打表 $\Omicron(nm)$
- 时间复杂度 
 - 预处理 $\Omicron(nm)$
 - 单次查询 $\Omicron(1)$

### 示例代码

```Java
class CombinationPrecompute {
 static final int N = 1000; // 根据需要设定最大 n
 static long[][] C = new long[N + 1][N + 1];
 static final long MOD = 1_000_000_007; // 如果需要取模，可以加上；否则去掉 MOD 相关代码

 // 预处理组合数表
 static {
 for (int i = 0; i <= N; i++) {
 C[i][0] = 1; // C(i,0) = 1
 for (int j = 1; j <= i; j++) {
 C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
 }
 }
 }

 // 查询组合数 C(n, m)
 public static long comb(int n, int m) {
 if (m < 0 || m > n) return 0;
 return C[n][m];
 }
 
 public static void main(String[] args) {
 System.out.println(comb(5, 2)); // 输出 10
 System.out.println(comb(10, 3)); // 输出 120
 }
}

```

## 预处理阶乘+逆元（模 p 意义下）

### 原理
- 组合数公式：$C_n^m=\frac{n!}{m!(n-m)!}$
- 费马小定理：$a^{p-1} \equiv 1\pmod{p}$ （$p$ 是素数）
 - 两边同除 $a$ 得
 - $a^{p-2} \equiv \frac{1}{a}\pmod p$
 - $\bmod\,p$ 意义下 $\frac{1}{a}$ 就是 $a$ 的逆元， $\operatorname{inv}(a)=a^{p-2}$
 - $a^{p-2}$ 可用快速幂计算求得（时间复杂度 $\log{p}$）

### 算法复杂度

- 空间
 - 打表 $\Omicron(n)$
- 时间
 - 预处理阶乘 $\Omicron(n)$
 - 预处理逆元 $\Omicron(n)$
 - 单次查询 $\Omicron(\log{p})$
 - 若预处理逆元，则单次查询为 $\Omicron(1)$


## Lucas 定理

Lucas 定理是用于处理组合数取模的定理。通常用于解决阶乘无法解决的问题。适用于 $n$ 较大（$n\ge 10^9$），p 较小（$p\le 10^5$）的情况。


### 原理
- Lucas 定理：$C_n^m \bmod p=C_{\lfloor n/p\rfloor}^{\lfloor m/p\rfloor}\cdot C_{n \bmod p}^{m \bmod p} \bmod p$



### 算法复杂度


- 空间
 - 预处理阶乘和阶乘的逆元 $\Omicron(p)$
- 时间
 - 预处理 $\Omicron(p)$
 - 单次查询 $\Omicron(\log{n})$

### 示例代码

以[洛谷 P3807](https://www.luogu.org/problemnew/show/P3807) 为例，针对 $p$ 以内的组合数我们打一个表，用阶乘和阶乘逆元 $\Omicron(n)$ 的递推公式去加快 $C_{n \bmod p}^{m \bmod p} \bmod p$ 项的计算。

```Java
import java.io.*;
import java.util.*;
public class Main {
 static final int P = 100003;
 static long[] fact = new long[P];
 static long[] invFact = new long[P];

 static long pow(long a, long b, int p) {
 long res = 1;
 a %= p;
 while (b > 0) {
 if ((b & 1) == 1) res = res * a % p;
 a = a * a % p;
 b >>= 1;
 }
 return res;
 }

 static void init(int p) {
 fact[0] = 1;
 for (int i = 1; i < p; i++) {
 fact[i] = fact[i - 1] * i % p;
 }
 invFact[p - 1] = pow(fact[p - 1], p - 2, p);
 for (int i = p - 2; i >= 0; i--) {
 invFact[i] = invFact[i + 1] * (i + 1) % p;
 }
 }

 static long comb(int n, int m, int p) {
 if (n < m) return 0;
 return fact[n] * invFact[m] % p * invFact[n - m] % p;
 }

 static long lucas(long n, long m, int p) {
 if (m == 0) return 1;
 return comb((int)(n % p), (int)(m % p), p) * lucas(n / p, m / p, p) % p;
 }

 public static void main(String args[]) throws Exception {
 Scanner cin=new Scanner(System.in);
 int T = cin.nextInt();

 for(int i = 0; i < T; i++) {
 int n = cin.nextInt(), m = cin.nextInt(), p = cin.nextInt();
 init(p);
 System.out.println(lucas(n + m, n , p));
 }
 }
}

```


## 参考
- [【算法学习笔记】组合数与 Lucas 定理
](https://www.cnblogs.com/RioTian/p/14659917.html)
- [总结组合数的几种求法（模板)](https://www.cnblogs.com/think-twice/p/11205353.html)
- [大质数表](https://www.cnblogs.com/ljxtt/p/13514346.html)
- [组合数学学习笔记](https://www.luogu.com.cn/article/4vl1ydkc)
- [卢卡斯定理](https://oi-wiki.org/math/number-theory/lucas/)

组合数算法

排序算法经常在笔试和面试中考到，大部分会问平均时间复杂度、空间复杂度、稳定性和是否原地排序的性质，还有少部分会问到最优、最差时间复杂度，神烦无比。而网上的总结又五花八门、莫衷一是，因而自己也收集材料整理一番，虽然无法做到特别全面，但也希望能覆盖大部分的情况。

| 排序算法 | 平时时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度1 | 原地排序 | 稳定性 |
| --- | --- | --- | --- | --- | :---: | :---: |
| 选择排序2 | $\Omicron(n^2)$ | $\Omicron(n^2)$ | $\Omicron(n^2)$ | $\Omicron(1)$ | 原地 | 不稳定 |
| 冒泡排序 | $\Omicron(n^2)$ | $\Omicron(n)$ | $\Omicron(n^2)$ | $\Omicron(1)$ | 原地 | 稳定 |
| 插入排序 | $\Omicron(n^2)$ | $\Omicron(n)$ | $\Omicron(n^2)$ | $\Omicron(1)$ | 原地 | 稳定 |
| 希尔排序3 | - | - | - | $\Omicron(1)$ | 原地 | 不稳定 |
| 快速排序 | $\Omicron(n\log(n))$ | $\Omicron(n\log(n))$ | $\Omicron(n^2)$ | $\Omicron(1)$ | 原地 | 不稳定 |
| 归并排序4 | $\Omicron(n\log(n))$ | $\Omicron(n\log(n))$ | $\Omicron(n\log(n))$ | $\Omicron(n)$ | 非原地 | 稳定 |
| 堆排序5 | $\Omicron(n\log(n))$ | $\Omicron(n\log(n))$ | $\Omicron(n\log(n))$ | $\Omicron(1)$ | 原地 | 不稳定 |
| 计数排序6 | $\Omicron(n+k)$ | $\Omicron(n+k)$ | $\Omicron(n+k)$ | $\Omicron(n+k)$ | 非原地 | 稳定 |
| 桶排序7 | $\Omicron(n+k)$ | $\Omicron(n+k)$ | $\Omicron(n^2)$ | $\Omicron(n+k)$ | 非原地 | 稳定 |
| 基数排序8 | $\Omicron(mn)$ | $\Omicron(mn)$ | $\Omicron(mn)$ | $\Omicron(n)$ | 非原地 | 稳定 |



注释：

1. 这里的空间复杂度并**没有讨论递归的栈空间**，否则快速排序的空间复杂度为 $\Omicron(\log(n))$ 
2. 选择排序由于需要交换数组元素导致不稳定，若是链表排序，则不存在交换问题，因此会是稳定的
3. 希尔排序的复杂度与间距序列的选取有关，由于各处的说法并不统一，因此未列出
4. 归并排序可以用于链表的排序，同时可以递归的排序，也可以从下往上排序。对链表来说，自下而上排序不需要额外的栈空间和辅助空间。表中列出的是最常见的对数组的**递归排序**，$\Omicron(n)$ 的空间复杂度是由于引入了**辅助数组**
5. 堆排序使用数组表达
6. 计数排序中，$n$ 为元素数量，$k$ 为数据范围（或者说是映射后的数据范围），引入了**前缀和计数数组**和**辅助数组**（非原地排序），因此的空间复杂度 $\Omicron(n+k)$
7. 桶排序的时间复杂度为 $\Omicron(n + n^2/k + k)$，当 $k \approx n$ 时有 $\Omicron(n + k)$，当 $k \approx 1$ 时有 $\Omicron(n^2)$
8. 基数排序，$m$ 为数字的位数（关键字数量），$k$为不同数字的个数（关键字值域）。表中数据是 **LSD + 计数排序**对数字排序的场景，则空间复杂度由 $\Omicron(n+k)$ 简化到 $\Omicron(n)$

## 参考材料
- [十大经典排序算法（runoob.com）](https://www.runoob.com/w3cnote/ten-sorting-algorithm.html)
- [十大经典排序算法（sort.hust.cc）](https://sort.hust.cc/)
- [排序简介（oi-wiki）](https://oi-wiki.org/basic/sort-intro/)
- [排序算法（wiki）](https://en.wikipedia.org/wiki/Sorting_algorithm)
- [十大排序算法原理及可视化（labuladong 的算法笔记）](https://labuladong.online/algo/intro/sorting/)

十大排序算法的性能比较

## 前言
前段时间刷到一个牛客题目，问输出的结果。虽苦思冥想蒙对了，但查看解析终不解其意，遂有自己查找资料测试之意。



牛客题目如下，问输出是什么？

```Java
public class Demo {
 public static void main(String[] args) {
 Collection<?>[] collections
 = {new HashSet<String>(), new ArrayList<String>(), new HashMap<String, String>().values()};
 Super subToSuper = new Sub();
 for (Collection<?> collection : collections) {
 System.out.println(subToSuper.getType(collection));
 }
 }

 abstract static class Super {
 public static String getType(Collection<?> collection) {
 return "Super: collection";
 }
 public static String getType(List<?> list) {
 return "Super: list";
 }
 public String getType(ArrayList<?> list) {
 return "Super: arrayList";
 }
 public static String getType(Set<?> set) {
 return "Super: set";
 }
 public String getType(HashSet<?> set) {
 return "Super: hashSet";
 }
 }
 
 static class Sub extends Super {
 public static String getType(Collection<?> collection) {
 return "Sub";
 }
 }
}
```

答案是 `Super:collection Super:collection Super:collection`，所以是为什么呢？

## 静态绑定和动态绑定

由 `private`、`final`、`static` 所修饰的方法和构造器，决定对象调用方法采用的是静态绑定。


## 测试

### static 方法的静态绑定

```Java
import java.util.ArrayList;
import java.util.List;

public class Main {

 public static void main(String[] args) {
 Test test = new SubTest();
 SubTest subTest = new SubTest();
 List<Integer> list = new ArrayList<>();
 ArrayList<Integer> arraylist = new ArrayList<>();
 test.print(list);
 test.print(arraylist);
 subTest.print(list);
 subTest.print(arraylist);
 }

 abstract static class Test {

 public static void print(List<Integer> list) {
 System.out.println("static list");
 }

 public void print(ArrayList<Integer> list) {
 System.out.println("non-static ArrayList");
 }
 }

 static class SubTest extends Test {

 public static void print(List<Integer> list) {
 System.out.println("sub static list");
 }

 public void print(ArrayList<Integer> list) {
 System.out.println("sub non-static ArrayList");
 }
 }
}

```

输出结果：

```txt
static list
sub non-static ArrayList
sub static list
sub non-static ArrayList
```

对以上测试结果的个人理解，调用方法时，先根据方法参数判断使用哪个重载方法。
- 如果使用了静态方法，则由于静态绑定的原因，调用绑定在的类型上的静态方法，而非真实的对象类上的静态方法。
- 如果使用了实例方法，则由于动态绑定的原因，调用真实对象实例的方法，与绑定到什么类型上无关。
- 需要注意的是方法虽然分静态和非静态，但是子类重写方法时相同的参数列表对应的一定是相同的静态/非静态方法。不能父类是静态，而相同的参数列表在子类变为非静态了，这是不行的。

### private 方法的静态绑定

```java
public class Main {

 public static void main(String[] args) {
 Test.print();
 }

 static abstract class Test {
 private void func() {
 System.out.println("test private method");
 }
 public static void print() {
 Test test = new SubTest();
 SubTest subTest = new SubTest();
 test.func();
 subTest.func();
 }
 }
 
 static class SubTest extends Test{
 public void func() {
 System.out.println("sub test method");
 }
 }
}
```
输出结果：

```txt
test private method
sub test method
```

由于 `private` 方法被自动认为 `final` 方法，而且对导出类，也就是子类是屏蔽的，所以在这种情况下，`SubTest` 类中的 `func()` 方法就是一个全行的方法，既然 `Test` 中的 `func()` 方法在 `SubTest` 类中不可见，所以甚至不能进行重写。

### final 方法的静态绑定

由于 `final` 方法无法重写，父类子类方法相同，没有动态绑定的说法。

### 构造器的静态绑定
构造器无法被重写，也就没有动态绑定的说法。

### 动态绑定

```
public class Main {

 public static void main(String[] args) {
 Test test1 = new Test();
 Test test2 = new SubTest();
 SubTest subTest = new SubTest();
 test1.func();
 test2.func();
 subTest.func();
 }

 static class Test {
 public void func() {
 System.out.println("test method");
 }
 }

 static class SubTest extends Test{
 public void func() {
 System.out.println("sub test method");
 }
 }
}
```
输出结果：

```txt
test method
sub test method
sub test method
```

我们使用父类的 `func()` 方法调用了子类的 `func()` 方法。这种绑定是在运行时完成的，因此称为动态绑定。这是多态的一种重要体现。

## 参考
- https://www.cnblogs.com/Hollake/p/9973547.html

Java 的静态绑定与动态绑定

[DDraceNetwork](https://ddnet.org/) 是一款开源免费的多人合作平台跳跃游戏（其前身是 Teeworlds 的一个叫 DDRace 的模组），上限高游戏性强，是一个非常独特的合作游戏。本项目依赖众多好心的程序员进行维护，作为一个基本成熟稳定的 C++ 游戏项目，我们可以从这个项目中学习到很多开发相关的知识，甚至如果你有什么改进，也可以为原代码仓库提出 Issue 贡献 PR。



![image.png](https://vanblog.zerolacqua.top/static/img/681c4541ebc324951c184c717c6f7d0e.image.webp)



## 项目说明

### 项目环境配置

#### 基本配置

Fork 仓库后克隆代码

```bash
git clone --recursive git@github.com:YourUserName/ddnet.git
```

安装依赖

```bash
sudo apt install build-essential cargo cmake git glslang-tools google-mock libavcodec-extra libavdevice-dev libavfilter-dev libavformat-dev libavutil-dev libcurl4-openssl-dev libfreetype6-dev libglew-dev libnotify-dev libogg-dev libopus-dev libopusfile-dev libpng-dev libsdl2-dev libsqlite3-dev libssl-dev libvulkan-dev libwavpack-dev libx264-dev python3 rustc spirv-tools
```

构建项目

```bash
cmake -Bbuild
cmake --build build
```

如果构建的客户端无法连接服务端，有一种可能是你的 TUN 模式没关。


#### 代码格式化脚本

代码格式化检查，运行 `scripts/fix_style.py` 脚本。由于 Ubuntu 24.04 已经找不到 clang-format-10 的安装包，我们需要自行编译或通过其他途径安装：

- 使用 pip 安装（官方推荐）

 > A lot of the style offenses can be fixed automatically by running the fix script ./scripts/fix_style.py
 > 
 > We use clang-format 10. If your package manager no longer provides this version, you can download it from https://pypi.org/project/clang-format/10.0.1.1/.

 由于执行检查脚本使用的是 python，我们可以通过 pip 安装。如果是用 conda 安装的，在执行 python 脚本时指定 python 环境，就可以顺利运行检查。
 
 ```bash
 pip install clang-format==10.0.1.1
 ```

- 直接下载二进制文件

 https://aur.archlinux.org/packages/clang-format-static-bin
 
 下载后将二进制文件移动到 `/usr/local/bin` 目录下并重命令为 `clang-format-10`

 ```bash
 sudo mv /path/to/clang-format-10_linux-amd64 /usr/local/bin/
 cd /usr/local/bin/
 sudo chmod +x clang-format-10_linux-amd64
 sudo mv clang-format-10_linux-amd64 clang-format-10
 ```

- 通过源码编译（未尝试）

 ```bash
 git clone https://github.com/llvm/llvm-project.git
 cd llvm-project
 git checkout llvmorg-10.0.1

 mkdir build
 cd build
 cmake -DCMAKE_BUILD_TYPE=Release -DLLVM_ENABLE_PROJECTS=clang ../llvm
 make -j$(nproc)
 sudo make install
 ```
 
 编译过程中可能出现部分报错：
 - `std:numeric_limits` 不是 `std` 成员。在相关文件中包含 `#include <limits>` 即可
 - `uintptr_t` 未声明，在相关文件中包含 `#include <cstdint>` 即可


#### 运行单元测试

按项目自述文件操作

```bash
sudo apt install libgtest-dev
cd /usr/src/gtest
sudo cmake CMakeLists.txt
sudo make

# copy or symlink libgtest.a and libgtest_main.a to your /usr/lib folder
sudo cp lib/*.a /usr/lib
```

在我运行时，还需要安装 gmock

```bash
sudo apt install libgmock-dev
```

#### 使用 AddressSanitizer + UndefinedBehaviourSanitizer

> 这个博主配了但试不出来有什么东西，估计是没配置好吧

- 安装 Clang

 ```bash
 sudo apt install clang
 ```


- 编译命令

 ```
 CC=clang CXX=clang++ CXXFLAGS="-fsanitize=address,undefined -fsanitize-recover=address,undefined -fno-omit-frame-pointer" CFLAGS="-fsanitize=address,undefined -fsanitize-recover=address,undefined -fno-omit-frame-pointer" cmake -DCMAKE_BUILD_TYPE=Debug .
 make
 ```

- 运行命令

 ```bash
 UBSAN_OPTIONS=suppressions=./ubsan.supp:log_path=./SAN:print_stacktrace=1:halt_on_errors=0 ASAN_OPTIONS=log_path=./SAN:print_stacktrace=1:check_initialization_order=1:detect_leaks=1:halt_on_errors=0 LSAN_OPTIONS=suppressions=./lsan.supp ./DDNet
 ```

- 结果检查

 运行后，检查生成的 `SAN.*` 文件以查看详细的问题报告。ASan + UBSan 能够发现比 Memcheck 更多的问题，尤其是在内存错误和未定义行为方面。


:::info{title="相关信息"}
参见：https://github.com/ddnet/ddnet/tree/master
:::

#### 使用 VSCode 工作区

> 这个工作区配置挺折腾，中间没配好我真的非常沮丧……

在调试过程中，我发现一旦客户端代码命中断点，就会导致鼠标被游戏捕获无法释放的问题。在 dc 中询问后，Jupstar 大佬给我了一个解决方案。


:::warning{title="注意"}
修改桌面环境之后我的系统会经常报错，虽然不影响使用，但修改之前请考虑！
:::

- 按 `other/vscode/README.md` 的说明，下载相应的二进制文件和安装相应的包（其中 `clang-format` 可按前文所述安装）

 ```
 sudo apt install clangd clang-tidy lldb rustup mold ninja-build xdotool
 ```
- 按照自述文件先按 `Ctrl+Shift+P` 输入 `Scan for kits` 扫描工具箱，再按 `Ctrl+Shift+P` 并选择 `Select a kit`,然后选 `[DDNet]` 开头的工具。

- 如果 cmake 生成时出现 rustup 相关报错，请执行命令：
 ```bash
 rustup default stable
 ```
- 查看一下当前显示是什么桌面环境，如果使用的不是 X11 的桌面环境，需要修改设置

 查看桌面环境：
 ```bash
 echo $XDG_SESSION_TYPE
 ```

 修改设置：
 ```bash
 sudo vim /etc/gdm3/custom.conf
 ```

 把该文件中这一行的注释状态解除：
 ```diff
 - # WaylandEnable=false
 + WaylandEnable=false
 ```
 然后重启即可切换。

注意：
- vscode 调试时需要从“运行与调试”（或者 F5）中进入
- **不要**点击 vscode 底部的 Cmake 调试按钮，否则走的不是工作区中定义的调试配置。这样虽然不会卡在 cmake 的 task 上，但因为没走工作区配置，鼠标指针释放的功能无法生效
- 工作区配置项似乎有点旧，当你使用“运行与调试”时，会卡在 cmake 的 task 上，原因不详。建议写一个 `.vscode` 的配置，然后不使用工作区打开。
 > 即不使用工作区配置，而是使用了自己 `.vscode` 文件夹中定义的配置。当然也可以直接修改工作区配置项 `other/vscode/ddnet.code-workspace` 不过这个文件是 git 跟踪过的，这个修改会被提交，所以建议在 `.vscode` 里自己创建一个，或者在分支里修改工作区配置，然后主分支不修改。

 - 使用自己写的 task，`type` 改为 `shell` 的：
 ```json
 {
 "version": "2.0.0",
 "tasks": [
 {
 "type": "shell",
 "label": "CMake: build client (shell)",
 "command": "cmake",
 "args": [
 "--build",
 "${workspaceFolder}/build",
 "--target",
 "DDNet"
 ],
 "group": {
 "kind": "build",
 "isDefault": true
 },
 "problemMatcher": [],
 "detail": "Build client targets (shell)"
 },
 {
 "type": "shell",
 "label": "CMake: build server (shell)",
 "command": "cmake",
 "args": [
 "--build",
 "${workspaceFolder}/build",
 "--target",
 "DDNet-Server"
 ],
 "group": {
 "kind": "build",
 "isDefault": true
 },
 "problemMatcher": [],
 "detail": "Build server targets (shell)"
 }
 ]
 }
 ```
 - 然后运行与调试选择你自己配置的 `launch` 配置：
 ```json
 {
 "version": "0.2.0",
 "configurations": [
 {
 "type": "lldb",
 "request": "launch",
 "name": "Launch client",
 "program": "${workspaceFolder}/build/DDNet",
 "preLaunchTask": "CMake: build client (shell)",
 // use dbg configs like this
 // "args": [ "dbg_gfx 0" ],
 // enable this to start the debugger with TSAN
 // "environment": [ { "name":"TSAN_OPTIONS","value":"ignore_noninstrumented_modules=1" }],
 "cwd": "${workspaceFolder}/build",
 },
 {
 "type": "lldb",
 "request": "launch",
 "name": "Launch server",
 "program": "${workspaceFolder}/build/DDNet-Server",
 "preLaunchTask": "CMake: build server (shell)",
 "cwd": "${workspaceFolder}/build"
 },
 // useful for cross debugging the windows (wine) client
 // for these you need the microsoft cpp extension
 // start the wine executable like this:
 // winedbg --gdb --no-start --port 55555 DDNet.exe
 {
 "type": "cppdbg",
 "request": "launch",
 "name": "Attach to wine gdbserver",
 "program": "${workspaceFolder}/build_win/DDNet.exe",
 "miDebuggerServerAddress": "localhost:55555",
 "cwd": "${workspaceFolder}/build_win/",
 "MIMode": "gdb",
 "setupCommands": [
 {
 "description": "Auto styling for \"gdb\"",
 "text": "-enable-pretty-printing",
 "ignoreFailures": true
 }
 ]
 }
 ]
 }
 ```


:::info{title="相关信息"}
参见：https://github.com/ddnet/ddnet/blob/master/other/vscode/README.md
:::



### 项目结构

- `src/base` 目录

 由于DDNet是一个跨平台游戏，需要一个抽象层来简化开发，因此该目录包含许多有用的函数来处理这一问题。



- `src/engine` 目录

 游戏引擎所在位置，它处理大多数与玩法无关的东西，比如图形、声音、网络等。



- `src/game` 目录

 所有玩法的代码所在位置，分为客户端和服务器。



 - 服务器端
 
 - 这个游戏使用自己的面向对象的实体分级系统，所有其他实体源于主类 `CEntity`，位于 `src/game/server/entity.h` 目录。

 - 游戏世界在 `src/game/server/gameworld.h` 路径下，管理这些实体。

 - 一些重要实体有：

 - `CCharacter`：代表一个活着的 Tee, 当一个 Tee 生成时会被实例化，当它死亡时会被删除。
 - `CPlayer`：包含了其他没有关联 Tee 的信息（昵称、国籍等）。有关玩家在死亡之间的信息，请参阅此项。


 - 客户端
 
 客户端由许多组件构成，都是在 `src/game/client/component.h` 中定义的继承 `CComponent` 的类：这些组件通过实现视觉方法来提供功能，例如 `OnInit`，`OnMessage` 等等。



 - 网络
 
 网络协议几乎由 python 脚本生成并输出 c++ 代码，例如说，`datasrc/network.py` 定义了所有网络包。

:::info{title="相关信息"}
参见：https://wiki.ddnet.org/wiki/Development/zh

文档：https://codedoc.ddnet.org/
:::

### 贡献代码指南

- 贡献前的准备

 在编写代码前，建议先开一个 issue 讨论想法，确保贡献符合 DDNet 项目的理念。常见的被拒绝贡献包括：
 - 影响游戏玩法的 dummy 扩展
 - 破坏向后兼容性的改动（如网络协议、文件格式或游戏玩法）。

- 编程语言

 DDNet 主要使用 C++，少量使用 Rust，Python 用于代码生成和工具，CMake 用于构建。平台特定代码可能使用 Java（Android）或 Objective-C++（macOS），但不接受其他语言的代码。

- 代码风格

 命名规则：变量、方法和类名使用大驼峰命名法（如 `MaxLength`），避免单字母变量名。

 匈牙利命名法：继承自 Teeworlds，使用前缀如 `m_`（类成员）、`g_`（全局变量）、`p`（指针）等。

 现代 C++ 实践：优先使用 `nullptr`、`true`/`false`，避免 `goto`、默认参数和方法重载。

 代码格式化：使用 clang-format 10 自动格式化代码。

- 最佳实践

 避免在 `if` 语句中赋值：明确分离变量赋值和条件判断。

 Getter 方法命名：避免使用 Get 前缀（如 `MyVariable()` 优于 `GetMyVariable()`）。

 类成员初始化：在声明时直接初始化类成员变量。

 文件命名：使用小写字母和下划线分隔（如 `foo_bar.cpp`）。

- 提交消息
 
 提交消息应描述对玩家/用户的影响，而非技术细节，以便直接用于变更日志。

:::info{title="相关信息"}
参见：https://github.com/ddnet/ddnet/blob/master/CONTRIBUTING.md
:::

## 开始贡献

### Good first issue

*goog first issue* 的作用是什么？

- 一般是开源仓库中比较简单的 issue，可能几行代码就能解决，甚至让人有一种捡漏的感觉，一般会由项目维护者选择简单易上手的、无关痛痒的问题，不亲自处理而是留待潜在的贡献者处理，可以吸纳新人参与到项目贡献中。
- 对于没有什么提交经验的人，面对一个复杂的项目，这种简单的 issue 可以帮助参与者建立对流程的基本认识。对贡献者来说，自己提交的 pr 能被合并是非常有成就感的，尤其是首先提交 pr 的贡献者，看到自己的修改被合并还是很高兴的。

比如我找的这个 issue：https://github.com/ddnet/ddnet/issues/9583 是个很简单的工作，只需要把描述文本修改一下就行。


另外，[这个网站](https://goodfirstissue.dev/)可以帮助你查看流行开源项目中可能的 *goog first issue*。

### PR 常用技巧

- 在 PR 中提及要解决的 issue，一般可以用 `fix#xxxx` 或 `close#xxxx`，这样 github 会自动渲染出链接的 issue 并会提示 PR 将关闭这个 issue
- 想要验证其他人还未被合并的 PR？

 在你已经 Fork 了自己的仓库，并且克隆到本地的基础上，先要添加 ddnet 官方的上游仓库：
 
 ```bash
 git remote add upstream git@github.com:ddnet/ddnet.git
 ```
 
 然后，根据你要拉取的 PR 编号进行拉取，比如我想拉取 ＃9786 PR，我就从 `upstream` 拉取 `pull/9786/head`，然后把这个本地分支命名为 `keb-pr`:
 
 ```bash
 git fetch upstream pull/9786/head:keb-pr
 ```
- 在 issue 中插入视频，直接拖入即可 ｀.mp4｀ 最佳，可直接渲染出播放窗口
- 在 issue 中引用特定提交的代码。在 github 某个提交的代码浏览的界面里，点选行号（按住 shift 可以选择范围），点击菜单选择 `Copy permalink` 即可，以下链接会被 github 渲染成相应区域的代码块：

 > https://github.com/ddnet/ddnet/blob/0aff2c75322a99a218fc6a8d659e8e77d62928e4/src/test/editor.cpp#L5-L8

## 其他的话

### 调整心态

参与代码贡献是一件令人振奋的事情，但中间也会遇到一些会让你感到受挫的事情，你需要以平常心看待它们。

- 项目维护者对你的 PR 的 review 可能比较严格

 一般是因为你的提交存在一些问题，或者不规范的地方，如要求你压缩你的提交，修改提交信息等。正视它们，这些直率的建议也能让你进步的更快。
 
- 社区的评价不一定都是中听的

 社区对你的贡献的评价也可能让你不舒服，尽管他们看起来并没有恶意。比如我贡献一个提交，想获取 dev 身份组时，会有人用 “commit: readme typo fix” 来打趣我（而且这种开源贡献笑话还挺常见的，时不时就会出现一次）。
 
 面对这种情况，还是要调整好心态，如果想要做长期的贡献还是从简单的 issue 开始的。跟进时间长了自然会做出有价值的提交。而且即使是简单的拼写修复提交，仓库的维护人员也一直欢迎和接纳，不要太受社区人员的影响。同时也需要自己提升心理承受能力。

- 开源社区终究也是社区，你并不突出

 社区总有光彩夺目的人，你需要降低期待做好无人理睬的准备。在 Manim 幼儿园的时候就已经有这种无力感了，更别说外国社区，英语蹩脚没有熟人更会让你觉得自己是被无视了。DDNet 社区里虽然有几位国人版主和贡献者，但也都根本没有接触过，颇有一种孤军奋战的感觉。
 
### 大胆去问
 
在 github 上找了个几个月前的 issue，里面提到了了一个小 BUG，我的开发就从地图编辑器开始了。

随着慢慢深入源码，我可以发现代码中其实有很多可以改进的地方，不知不觉已经提了五个 PR 了。在这个过程中，可能会有自己的 PR 或者 issue 没有被仓库协作者看到的情况。你可以大胆地在 DC 群里去请求 review。当然遇到了编程相关的问题，也可以去问问 DC 里的人，如果有了解相关的代码的人，是会给予你帮助的。即使他们可能没有负责这部分的代码，他们也可以为你提供一些有价值的建议。

另外，这次有了五个 PR 之后，我也是鼓起勇气去 @ 了管理员，最后也是如愿以偿地得到了开发者的 role，所以还是得要大胆一点，只要你不犯大病礼貌一点，不会有什么惩罚的。

DDNet 项目贡献杂记

其实这已经不是我第一次折腾双系统了。我的笔记本是惠普战 66 六代酷睿版，笔记本上之前装了双系统，但是分的空间太少了，所以这次打算加装一个硬盘，将**双系统装在双硬盘上**。



## 准备工作

### 制作启动盘


启动盘制作工具使用 [Rufus](https://rufus.ie/zh/)
。


| 设置项 | 信息 |
| --- | --- |
| 镜像 | Ubuntu 24.04 |
| 分区类型 | MBR |
| 目标系统类型 | BIOS 或 UEFI|
| 文件系统 | FAT32（默认） |
| 簇大小 | 16K 字节（默认） |

### 添加硬盘

购置了梵想的 1T NVMe SSD M.2 2242 硬盘，用于安装 Ubuntu。

装机时需要注意参照官方装机说明进行，断开电池拼接，去除身上的静电（或使用防静电手套），再安装硬盘。

## 双系统安装

原先的双系统是都安装在 `nvme0` 上的 Ubuntu 版本是 22.04 有部分配置信息，还有密钥什么的是需要迁移的，其他的重装之后再安装吧。

### 安装 Ubuntu 24.04

插入启动盘，在开机时连按 `Esc` 进入 BIOS 设置（不同机型操作可能不同）。把 USB 设置为优先启动项进行安装。

安装中，因为我是新加的一个空盘，所以我选择了清空硬盘安装的选项。安装前一定要注意别清错盘了，清空硬盘的选项只有 `nvme0` 和 `nvme1` 两个，但不清楚硬盘和名称的对应关系。可以先进入手动安装模式，查看自己的 Windows 系统和数据在哪个盘上。

### 卸载 Ubuntu 22.04

旧的 Ubuntu 系统与 Windows 位于同一个硬盘上，通过 Windows 的磁盘管理工具，删除 Ubuntu 所在的分区。然后利用 DiskGenius （或者其他方法如 `diskpart` 命令为 System 分区分配盘符）删除 EFI 目录中的 ubuntu 文件。

当然卸载完 Ubuntu 之后，可能会在 GRUB 中残留它的引导项。

可执行以下命令，生成新的 `grub.cfg` 文件，以更新 GRUB 配置


``` bash
sudo grub-mkconfig -o /boot/grub/grub.cfg
````

这个命令会根据配置文件自动生成 `grub.cfg`，确保所有更改都被应用。

更新后，记得将 `grub.cfg` 文件的权限恢复为只读状态。
``` bash
sudo chmod 444 /boot/grub/grub.cfg
```
重新启动之后，GRUB 将正常显示引导项，原有的无效引导将被清除。


参考：https://developer.aliyun.com/article/1534371



## 新系统的配置


### 配置密钥

其实如果密钥用的地方不多的话，最好还是在新系统上重新生成一个。直接复制到新系统的 `.ssh` 里并不管用，首先需要确保拷贝的密钥具有正确的权限

```bash
chmod 700 ~/.ssh
chmod 600 ~/.ssh/id_rsa
chmod 644 ~/.ssh/id_rsa.pub
```


还可能需要用 `ssh-add` 添加到 `ssh-agent` 中


### 配置输入法

我使用的输入法是五笔的，运行以下命令（其中 `ibus-qt4` 可能已经无法定位到包了）：

```bash
sudo apt-get install ibus ibus-clutter ibus-gtk ibus-gtk3 ibus-qt4
im-config -s ibus
sudo apt-get install ibus-table-wubi
ibus-setup
ibus-daemon -drx
```

然后在键盘设置中，选择中文（极点五笔）即可。

### 安装常用软件

- 代理相关软件

 - 由于 CFW 停止更新和维护，在新版本的 Ubuntu 上可能无法运行，目前还没有找到问题。因此换用了 clash-verge-rev 版本，基本操作都十分类似。
 
- 编程相关软件
 
 - 安装 vscode，用账号同步一些配置和插件

- 生产力相关软件

 - 安装 Chrome，用账号同步插件。
 - 安装大纲笔记软件 Workflowy。由于其安装包是 Appimage 格式的，初次使用可能无法使用（权限问题，或者缺少 `libfuse`）。可以参考文章：https://linux.cn/article-14619-1.html
 
### 配置常用开发环境

- 安装常用的工具（更新中）

 ```bash
 sudo apt-get install git vim build-essential
 ```

- 安装 nvm

- 安装 Docker

 ```bash
 curl -fsSL https://download.docker.com/linux/ubuntu/gpg| sudo gpg --dearmor -o /etc/apt/trusted.gpg.d/docker.gpg
 echo "deb https://download.docker.com/linux/ubuntu noble stable" | sudo tee /etc/apt/sources.list.d/docker.list
 sudo apt install docker-ce docker-ce-cli docker-buildx-plugin docker-compose-plugin containerd.io
 ```