国际象棋 Demo 实现

数独（Sudoku）是一种数学逻辑游戏。对于 9 阶的标准数独，其搜索状态树节点数量少，简单的回溯法能很快解算出结果，因此不作为并行算法的讨论对象。16 阶与 25 阶数独，其状态树的深度与广度都要比 9 阶数独大，简单的回溯法已经无法快速地完成计算，需要利用并行方法进行加速。




## 算法简介

数独（Sudoku）是一种数学逻辑游戏。如图 1 所示，标准数独由 $9\times 9$ 个格子组成，玩家需要根据格子提供的数字推理出其他格子（cell）的数字。一般情况下设计者会提供最少 17 个数字（known numbers）使得解答谜题只有一个答案。数独要求每一行（row）、每一列（colume）以及每一宫（block）的数字都不缺少也不重复。数独还存在阶数更高的变体，如 $16\times 16$ 和 $25\times 25$ 的高阶数独。

<center>

![图 1](https://cdn.zerolacqua.top/images/blogs/高性能计算课程作业/sudoku.png)

</center>
 
​数独的程序解法一般可用回溯法（Back Tracking）来实现，算法包括以下几步：

- 筛选候选数（cadidate）
- 回溯法暴力求解数独

筛选候选数的目的在于减少每一个未知格里的候选数，从而减少搜索状态树的节点数量，提高搜索速度。有的算法还会采用逻辑解法进一步减少候选数的数量。回溯法则是一种基于深度优先遍历的搜索算法，通常利用递归实现。

## 算法分析

对于 9 阶的标准数独，其搜索状态树节点数量少，简单的回溯法能很快解算出结果，因此不作为并行算法的讨论对象。16 阶与 25 阶数独，其状态树的深度与广度都要比 9 阶数独大，简单的回溯法已经无法快速地完成计算，需要利用并行方法进行加速。

针对一个简单的 25 阶数独，算法的两部分的用时比较如表 1 所示。可以看到，算法最耗时的部分是回溯法求解数独环节，基本决定了总耗时，我们需要对这一部分算法进行基于 MPI 的并行化改进。

| 算法步骤 | 用时（秒） |
| ------------------ | ---------- |
| 筛选候选数（剪枝） | 0.002 |
| 回溯法求解数独 | 448.535 |

针对数独求解的相应串行伪代码如下所示：

```python
# search for result using backtracking with recursion
def backTracking(sudoku: Sudoku)->bool:
 if sudoku.isFinished():
 return True
 cell = sudoku.findNextUnfinishCell()
 for num in cell.cadidate:
 if sudoku.isValidNum(cell, num)
 sudoku.do(cell, num)
 if backTracking(sudoku):
 return True
 sudoku.undo(cell)
	return False
```

## 并行设计

本实验的数独回溯法并行求解基于 MPI 多进程实现，且采用主从模式进行并行，设计过程依照 PCAM 方法。

### 划分

如图 2 所示，回溯法求解数独本质上是一种搜索空间的深度优先遍历，每一个节点都可以看作是一个数据，需要验证其是否矛盾（直到出现完成的节点）。同时由于回溯法的递归特性，数独回溯算法可以拆分成完成度更高的若干个数独（后称“子数独”）进行并行回溯（如图 3 所示）。因此对于数独回溯算法，可以利用域分解进行划分。

![图 2](https://cdn.zerolacqua.top/images/blogs/高性能计算课程作业/图片1.png)

![图 3](https://cdn.zerolacqua.top/images/blogs/高性能计算课程作业/图片2.png)


因为搜索空间是一个树结构，每多一个未填格，树结构就会增加一层，搜索数量会指数级增加。所以应当保证每个并行单元的子数独完成度一致，否则并行单元之间的任务尺寸可能会不同，影响并行效率。利用广度优先遍历，可以保证拆分得到的子数独完成度相同，位于树结构的同一层。

然而，利用广度优先遍历拆分得到的子数独数量（任务数量）不一定与并行单元数相同，任务粒度太粗后分配任务的数量依然会存在差距，需要把任务的粒度划分得更细，以弥补并行单元之间任务分配数量的差距，具体讨论放在组合映射部分。而任务分配涉及的通信问题放在下一节讨论。

### 通信

每个并行单元的子数独都是独立的数独，不存在流依赖、反向依赖或是输出依赖，所以计算时并行单元间不存在通信的问题，很容易并行化。但是在进行任务分配时，则存在并行单元之间的通信。采用主从模式并行时，主节点承担着任务划分和分配的功能，从节点承担主要的计算任务，从节点的计算依赖主节点划分的任务数据。

通信采用点对点阻塞通信，其中涉及的通信包括：

- 主节点向从节点发布任务
- 从节点完成任务向主节点报告是否解决数独
- 主节点通知从节点结束工作

一般来说，主节点存储着一个任务队列，在从节点完成当前任务后，主节点将一直向从节点发布新的任务，直到任务队列清空（如图 4）。这一过程中，会涉及多次主节点与从节点之的通信。

![图 4](https://cdn.zerolacqua.top/images/blogs/高性能计算课程作业/图片4.png)

### 组合与映射

在划分一节中，提到了任务数量与并行单元数量不相同的问题。由于我们采用的是主从并行模式，任务队列里的任务（理论上）会均匀分发给每个子节点，如果任务数除以子节点数存在余数，那么就会有一些子节点多分得一个任务。任务粒度过粗，会使得多出的这一个任务的处理时间要明显超过其他子节点，出现子节点闲置时间过长的现象。细化任务粒度，增加任务数量，能够减少这部分多出的时间，有助于主节点任务队列实现负载均衡。

![图 5](https://cdn.zerolacqua.top/images/blogs/高性能计算课程作业/图片5.png)

而因为主节点任务队列的存在，每个子节点完成任务后都会从任务队列获取新的任务，组合与映射是一个动态的过程，与程序的运行情况有关。

### 并行算法

并行的算法与串行算法差异不大，主要是任务分配需要特别处理，其伪代码如下：

```python
def backTracking(sudoku: Sudoku)->bool:
 // backTracking is similar to the serial one
	pass

// master process
def master()->NoReturn:
 // other initial work
 ...
 // use BSF to find sudokus 
 // that have same unknown cells
 sudokuQue = sudoku.splitSubSudoku() 
 while unfinished:
 if slaveFinishTask(slave):
 if success():
 break
 if sudokuQue.length()>0:
 assignTask(sudokuQue.popFront(),slave)
 sendTerminateMessage(slaves)
 // other work
 ...
 
// slave processes
def slave()->NoReturn:
 // other initial work
 ...
 // always fetch new task until get terminate message
 while not terminate():
 	// if no more sudoku
 	// slave will be blocked until terminate 
 receiveSubSudoku(sudoku)
 if backTracking(sudodu):
 sendSuccessMessage(master)
 else
 sendFailMessage(master)
 
 // other work
 ...
```

需要注意的是，实际代码实现中的阻塞点对点通信函数不是伪代码这样调用的，伪代码屏蔽了 MPI 通信中的具体操作。具体代码实现可参见我的 [github](https://github.com/ZerolAcqua/SudokuMPI) 仓库

## 实验分析

### 实验准备

实验的测试数据使用了[此项目](https://clairewangyuyue.github.io/CS205_G1.github.io/)中的测试数据。但选题、实现与实验均未参考该项目。如图 6 所示，测试数据是一个 25 阶的数独，由于控制测试用时的原因，减少了未填格的数量，盘面有 15 个宫基本填好了数字。

<center>

![图 6](https://cdn.zerolacqua.top/images/blogs/高性能计算课程作业/test_sudoku.png)
 
</center>
 
并行化基于 MPI 实现，使用 Microsoft MPI 在 Windows 平台上开发运行并行应用程序，编程语言为 C++。程序采用主从模式进行并行，由一个主进程负责拆分和分发任务，其他子进程负责计算。

### 实验结果

图 7 红色折线展示了实验进程数与划分任务数的关系，（蓝色折线为另一对比实验，将在下文讨论）。代码中设置的任务数量应为进程数量的 10 倍以上，但是由于数独划分的要求（如前所述，需要保证子数独完成度一致），其数值是受到限制的，所以会呈现出图 7 中红色折线阶跃的现象。

![图 7](https://cdn.zerolacqua.top/images/blogs/高性能计算课程作业/task.png)

并行算法加速比与进程数的关系如图 8 所示。在 1-20 个进程并行时，加速比趋近于线性增长。之后由于并行开销累积，计算资源限制，加速比增长趋于平缓。

![图 8](https://cdn.zerolacqua.top/images/blogs/高性能计算课程作业/speedup.png)

在这里，虽然该折线与 Amdahl 定律给出的折线相近，但个人认为并不是 Amdahl 定律造成的。

其一，算法的串行开销并不大，主进程任务拆分必须在所有子进程运算之前，可以认为是串行开销，这部分用时仅在 0.1 秒以内（2000 个任务时，实际上会更短）。并行化之前，筛选候选数只需要执行一次，并行化之后由于通信时需要将数独类序列化的原因，每个任务都需要重新执行一次，但每次筛选候选数用时仅 0.002 秒，按 1 个进程 50 个任务，用时也不超过 0.1 秒。相比于实验中耗时 25 秒（并行前 450 秒）的结果，基本可以忽略。

其二，由于实验的多进程运行在同一台主机上，其计算资源有限。测试中，当进程数在 28 时（恰好对应图 8 进入平台的折点），电脑的 CPU 利用率就已经到达 100% 了，所以增加更多的进程对算法的加速影响不大了，这一点应该才是折线趋于平缓的原因。

并行算法的并行效率如图 9 所示。由于算法基于主从模式，主进程是不参与主要计算的，所以在进程数设置为 2 时，加速比依然为 1，因而并行效率在这里有一个陡降。后随着并行进程数的增加，这一影响逐渐消失。进程数为 8-16 时，红色折线也出现了一次下降。结合图 7 可以发现可能是由于任务数量的问题（恰好对应任务数为 169），划分不够细导致并行效率下降。当将任务数全固定为 947 时，并行效率如蓝色折线所示，折线 8-16 进程的下降情况消失，可见任务划分粒度对并行效率也有很大影响。

![图 9](https://cdn.zerolacqua.top/images/blogs/高性能计算课程作业/efficiency.png)

实际上，当进程数为 20-64，任务数提升到 2099 甚至 7563 时，加速效果基本没有提升（如表 2）。因此可以认为，20-64 并行进程的任务划分已足够细。 

| 指定任务数 | 160 | 2000 | 4000 |
| ------------------- | ------ | ------ | ------ |
| 实际任务数 | 947 | 2099 | 7563 |
| 20 进程并行实际用时 | 28.469 | 28.453 | 29.574 |
| 64 进程并行实际用时 | 25.463 | 25.404 | 25.765 |

两次实验用时对比如图 10 所示。总体来说，并行实验的加速效果显著，实验取得了成功。

![图 10](https://cdn.zerolacqua.top/images/blogs/高性能计算课程作业/time.png)



## 个人心得

并行算法的编程思维不同于串行算法，通过这次的实验我切切实实地感受到了并行算法编程的难度，也体会到并行算法在高性能计算上的威力。

并行算法需要考虑的东西有很多，光是控制任务尺度一致就花费了我很长的时间，因为任务数与进程数没办法完美平均地进行组合映射，最后才想到了利用任务列表动态进行分配的办法。然而任务队列也没办法解决所有的问题，当我使用串行 50 秒计算完成的数据测试时，加速比与并行效率很快就饱和了，而且计算很低效。计算过程中出现了其他进程跑完了所有任务，而一个进程一直还在计算的情况（即该任务计算量很大）。编程过程中甚至考虑了利用双向队列实现任务窃取算法避免这种情况（太复杂没能实现）。后来换用串行 450 秒计算完成的数据测试时，呈现效果才比较好。可能是由于之前使用的数据状态树较浅，不平稳的情况更严重，而整个并行任务是从树的根结点开始分配的，这就导致分配任务的计算量还是存在差距过大的问题。所以理论与实际情况还是有一定的差别，只有实际实验过才明白其中存在的问题。

在选题过程中我参考了不同的资料，想到了不少的有趣的问题，在选择时也是纠结了很长时间。最后因为出于选题新颖度、呈现效果、PCAM 分析出的题目复杂度和个人编程能力的考量排除了这些选项，但不列出又深感遗憾，遂呈现在这里。

其他候选题目：

- 八皇后问题
 - 对回溯法进行数据并行
 - 不够新颖，而且是书上介绍的题目
 - 基于此问题联想到数独求解问题
- 矩阵乘法的 Cannon 并行算法
 - 是一个针对存储的优化计算，可能并不能进行串并行的比较分析
- 矩阵 LU 分解的并行算法
 - 不够新颖
 - 略复杂
- 离散数学中的稳定匹配问题
 - 存在并行可能，直觉上是适合并行的算法，但并行化算法的有效性并不确定
 - 存在通信同步问题，需要解决读写问题
- 计算机视觉中的切图算法 Seam Carving
 - 边缘检测算子计算能量图
 - 涉及卷积的并行，并行化没有难度

 - 动态规划计算最小的切分路径
 - 可数据并行，但是计算依赖其他单元上一步的计算结果，涉及到通信同步问题
- 计算几何中平面最近点对的分治算法
 - 和 $k$-d 树以及分治构建三角网的算法比较像，可能不够新颖


## 参考文献

- 陈国良. 并行计算系列丛书: 并行算法实践[M]. 高等教育出版社

- GENE H. GOLUB&sbquo; CHARLES F. VAN LOAN. Matrix computations[M]. Fourth edition. Baltimore: The Johns Hopkins University Press&sbquo; 2013.

- [Discrete Mathematics and Probability Theory Course Note: Note 4](https://www.eecs70.org/assets/pdf/notes/n4.pdf)

- [Seam Carving — Interactive Computational Thinking — MIT](https://computationalthinking.mit.edu/Fall22/images_abstractions/seamcarving/)

- [平面最近点对 - OI Wiki](https://oi-wiki.org/geometry/nearest-points/)

高性能计算课程作业

星月湖的华为的软挑大赛总算告一段落了，跌跌撞撞走进复赛已经是出乎意料的结果了（只是可惜了我校内赛的蓝牙耳机，被抢了呜呜）。





## 赛题
这次比赛赛题以“智慧港口”为主题，考查选手在机器人和船只寻路调度的算法。刚开始感觉这个题目和 Screeps 有一点像，但是实际上寻路避障算法都得自己路的，区别还是不少的。


个人认为的若干关键点如下：

- 程序交互

	每帧信息由输入和输出传递，选手程序需要在有限的时间里进行运算，并输出结果。由于跳帧情况的存在，需要尽量保证选手程序每一帧都接收到判题题数据，保证数据同步。
- 计算逻辑：
	
	因为每帧计算限时，可能涉及多线程编程
- 寻路

	寻路算法是这次比赛的关键，寻路用 A* 足够了。船只的寻路是一个比较麻烦的点（船只有体积，且船只的移动不是四方向的），但可以通过一些方式把船只的寻路变为和机器人类似的寻路。
- 避障

	分为机器人之间的避障（初赛），和船只之间的寻路避障（复赛）。机器人的移动是可逆的（即前进可以后退，往右走可以再往左，走回到原位），可以使用一些朴素的避障方法，避障后再原路返回之前的寻路路径上。而船只移动是不可逆的（只有转向和前进的移动），船只避障之后无法简单地回到原位，这就给船避障带来了很大挑战（直至比赛结束我们都没有一个比较满意的方案）。
- 调度策略

	船只和机器人分布在地图的各处，如何把货物尽量多且快得运输到目标点，就是一个非常重要的问题。在复赛阶段，由于增加了机器人（两种）和船只的购买机制，因此怎么搭配各种

可能优化思路有：

- 利用初始化时间

	5000ms 能够做很多事情。比如用洪泛法计算所有点到某个点的路径长度等等（宝贵的打表时间）。
- 优化机器人取货的目标
	
	减少总寻路的长度和总的货物拾取价值。在复赛机器人可以拾取两个货物，对路径优化合并，提出了更高的要求。
- 船只避障

	不再使用那种朴素的避障再返回路径节点的方式，而是尝试进行新的寻路或者局部的寻路，减少船只从避障后恢复的路径长度。
- 炼丹
	
	试各种参数；碰运气，刷随机种子；针对地图进行特化调参。

更多具体的算法讨论，可以参考 [insomniac 的文章](https://xuqi.space/post/15)。

## 学习到了什么东西

这个比赛中我不只收获了赛区二等奖（本来能有一个三等奖就不错了），更重要的是在这个过程中逼着自己学习了新的东西。

- code review
	
 其实平常自己一个人写代码，很少用 PR 功能，也很少去做代码审查。这次比赛算是好好接触了一下这部分流程。（虽然最后代码也没在用 git 管理了，代码也是直接看了x）
- 分支版本控制

 其实是又把 Learn Git Branching 刷了一遍，试了试有源和目标参数的 pull 命令。不过实际上，比赛中版本控制也是做得虎头蛇尾。
- UML 类图
	
 以前听过也看过类图，不过并不是很清楚它具体的规范，这次的初赛索性就试了试，学习了一下绘制的语法，可参考 [mermaid 类图](https://mermaid.js.org/syntax/classDiagram.html)





```mermaid
classDiagram

class Macro_Statics_Method {
 MAP_SIZE = 200
 ROBOT_NUM = 10
 BOAT_NUM = 5
 BERTH_NUM = 10
 TOTAL_FRAME = 15000
 TIME_PER_FRAME = 15
 FRAME_BUFFER_SIZE = 100
 BOAT_CAPACITY
 void output(RobotCommand type, int id=-1, arg=-1)
 void output(BoatCommand type, int id=-1, arg=-1)
 void ok()
 bool checkOk()
}

class World {
+init()
+Map map
+Map origin_map
+Robot robots[ROBOT_NUM]
+Boat boats[BOAT_NUM]
+Berth berths[BERTH_NUM]
+int berth_val[utils::BERTH_NUM]
}

class Map {
+char data[][]
+bool isAccess(int x, int y)
+void modify(int x, int y, TileType type)
}

class Goods {
int x
int y
int deadTime
int val
int come_robot_id
}

class Robot {
int x
int y
int hasGoods
int status
int mbx
int mby
int go_goods_id
}

class Boat {
int capacity
int num
int pos
int status
}

class Berth {
int x
int y
int speed
int time
int come_boat_id = -1
}

class FrameGoods {
int x
int y
int val
}

class FrameRobot {
int hasGoods
int x
int y
int status
}

class FrameBoat {
int status
int targetBerthID
}

class FrameData {
+int frameId
+int frameMoney
+FrameGoods frameGoods[K]
+FrameRobot frameRobots[ROBOT_NUM]
+FrameBoat frameBoats[BOAT_NUM]
}

class FrameBuffer {
+FrameData frameData[]
+int head
+int tail
+bool Read()
+int size() const
+const FrameData &GetLatestFrame()
}

class Controller {
+World &world
+Goods[] &allgoods
+const FrameBuffer frameBuffer
+pathFinder
+Path robotPaths[ROBOT_NUM]
+void UpdateWorld(const FrameData& frameData, vector<Goods>& allGoods)
+void RobotWork()
+void BoatWork(int frame_id)
+void FindBerthAndGo(int id)
+vector<int> CalcBerthPos(int bx, int by, int rx, int ry)
}

class PathFinder {
+World world&
+Path findPath(int sx, int sy, int ex, int ey)
}

World --> Map
World --> Robot
World --> Boat
World --> Berth
FrameData --> FrameGoods
FrameData --> FrameRobot
FrameData --> FrameBoat
Controller --> World
Controller --> Goods
Controller --> PathFinder
PathFinder --> World

```





- 寻路算法

	这次比赛也是把寻路算法稍微系统地过了一遍，对 A* 算法有了更深刻的理解了。当然还有群体寻路、跳点寻路等等。
- 标准错误流

	以前没怎么接触过错误流，这次比赛因为输入输出流被用作传递参数，所以就被迫了解了点这个东西。
- 打日志的重要性

	这个比赛中，代码调试的困难很大，无法实时进行调试（在用判题器的情况下）。通过错误流打印出来的日志对定位错误起到了很大的作用，让我对认真打日志的重要性有了更深刻的认识。

- 协作中不可避免的问题

	在接近一周的比赛中，暴露了很多关于协作的问题：
	
	1. 没有固定的共同工作的时间与场所（除了通宵的那三个晚上我们在一起写代码），缺乏沟通。

	2. 各写各的代码，虽然对赛题有了更深刻的认识，但浪费了不少的时间。同时也出现了工作重复的问题。

	3. 版本管理慢慢荒废。比赛后期基本就是传压缩包。

- 原子变量与锁

	这部分主要是因为队友写的控制代码中需要用到多线程，所以就必须得接触一些。
- wsl 与双系统

	wsl 折腾了没用，在队友的压力和帮助下也是试着在实验室和自己的电脑上装了双系统。比赛结束之后实验室的双系统又折腾了一下卸载掉了，自己电脑上的留着打算用来学习。
- mingw 的计时有问题

	sleep_for 无法准确阻塞主线程，参见：[C/C++中如何稳定地每隔5ms执行某个函数？ - 知乎 (zhihu.com)](https://www.zhihu.com/question/536739862)

- 标准库的使用

	- 容器

		- `std::priority_queue`
		- `std::map`
			
			- 正确地通过索引访问元素
			- 类实例作为 `key` 时正确定义 `operator<`	
		- `std::optional`
		- `std::set`
	- 函数
	
		- `std::greater`
		- `std::less`
	- 算法
		
		- `std::iota`
		- `all_of`
		- `any_of`
		- `none_of`
		- `find_if`

## 有什么感想

比赛强迫自己学了很多新东西，这是平时独立自学所达不到的效果，有时候还是得多逼自己一下。熬夜也是熬出了新的记录。

比赛的队友很给力，被全程带飞哈哈哈哈。一个队友基础特牢，由他负责代码的框架；另一个队友行动力特别强，虽然代码不太规范，但他想到的方法能很快地实现。而我的话，虽然想到一个主意但却又经常拖着写半天写不出来，只好多负责<del>写写</del>改改 bug。这次比赛也让我看到了自身能力实在是有限，再不努把力，真的没有人要了，不希望自己成为一个啥都会一点，但啥都拿不出手的人。

华为软件精英挑战赛感想

记录一下我磕磕绊绊的 Nonebot2 qq 机器人搭建过程。(多半弃坑了，因为 qq 被风控了）



## 使用效果

![图1](https://cdn.zerolacqua.top/images/blogs/QQ机器人搭建体验/1.png)

## 参考链接

### 零基础搭建搭建

- [基于Nonebot2搭建QQ机器人实战篇（一） - 掘金 (juejin.cn)](https://juejin.cn/post/7177022630204014653)
- [Well404的妙妙屋](http://blog.well404.top/categories/NoneBot2%E7%B3%BB%E5%88%97%E6%95%99%E7%A8%8B/)
- [官方文档](https://v2.nonebot.dev/)

## 使用插件

### 商店插件

- [nonebot_plugin_analysis_bilibili](https://github.com/mengshouer/nonebot_plugin_analysis_bilibili)
- [nonebot-plugin-heweather](https://github.com/kexue-z/nonebot-plugin-heweather)
 
 报错解决：[windows平台启动nonebot-plugin-htmlrender 报错 NotImplementedError · Issue #25 · kexue-z/nonebot-plugin-htmlrender (github.com)](https://github.com/kexue-z/nonebot-plugin-htmlrender/issues/25)
- [nonebot-plugin-petpet](https://github.com/noneplugin/nonebot-plugin-petpet)
- [nonebot-plugin-blacklist](https://github.com/tkgs0/nonebot-plugin-blacklist)
- [nonebot-plugin-help](https://github.com/XZhouQD/nonebot-plugin-help)

### 自编插件

- test_derpy_plugin

 获取小马图片。参考了[官方文档](https://v2.nonebot.dev/docs/tutorial/plugin/example)和 [nonebot-plugin-blacklist](https://github.com/tkgs0/nonebot-plugin-blacklist)，使用 requests 和呆站 API 获取图片数据。


## 一些问题

### 常见问题

可在[Well404的妙妙屋](http://blog.well404.top/2022/02/02/nonebot/%E3%80%90NoneBot2%E3%80%91%E7%AC%AC%E4%B8%80%E7%AB%A0%EF%BC%9A%E5%AE%89%E8%A3%85%E5%B9%B6%E9%85%8D%E7%BD%AE%E4%BD%A0%E7%9A%84%E6%9C%BA%E5%99%A8%E4%BA%BA%E5%8F%8A%E5%B8%B8%E8%A7%81%E6%8A%A5%E9%94%99%E7%9A%84%E8%A7%A3%E5%86%B3%E6%96%B9%E6%B3%95/)中找到大部分常见报错，以下是我的一些白痴问题。

### 代码问题

- 机器人搭好了怎么连接 qq？

 还要用 `go-cqhttp` 作为 qq 客户端

- 怎么通过 `url` 发送图片消息？

 - 使用 `MessageSegment`

 - 注意要导入适配器的 `MessageSegment` 

 - 参见：[Discussions · nonebot/discussions (github.com)](https://github.com/nonebot/discussions/discussions/)

 - 例如：

 ``` python
 from nonebot.adapters.onebot.v11 import Message, MessageSegment
 ```

- 实例化 `MessageSegment` 时无法使用图片（版本相关）

 - 参见：[[Bug]: 使用图文时 警告: 图片上传失败: image type error: application/octet-stream · Issue #1660 · Mrs4s/go-cqhttp (github.com)](https://github.com/Mrs4s/go-cqhttp/issues/1660)

 - 代码应为

 ``` python
 MessageSegment(type='image', data={'file':img_url})
 # 本应该是下面这样的写法的
 MessageSegment(type='image', data={'img':img_url})
 ```

 还有其他的方法

 ``` python
 MessageSegment.image(img_url)
 ```

- 怎么接收图片为参数？

 ```python
 # 获取包含图像的消息段列表
 get("image")
 # 获取图像 url 
 messagesegment.data.get("url", "")
 ```

- 获取呆站图像 url （具体应用场景，与 bot 无关）

 - 呆站 API：[API - Derpibooru (trixiebooru.org)API - Derpibooru (trixiebooru.org)](https://trixiebooru.org/pages/api)

 - 注意 `Get` 与 `Post`

- 权限问题示例
 ```python
 from nonebot.adapters.onebot.v11 import (
 Bot,
 Message,
 Event,
 GroupMessageEvent,
 GROUP_ADMIN,
 GROUP_OWNER
 )
 # @xxx.handle()
 async def perssion_test(bot: Bot, event: GroupMessageEvent):
 if await SUPERUSER(bot, event):
 await xxx.send("识别到超级用户权限")
 elif await GROUP_ADMIN(bot, event):
 await xxx.send("识别到管理员权限")
 elif await GROUP_OWNER(bot, event):
 await xxx.send("识别到群主权限")
 else:
 # await xxx.finish("您没有权限（无慈悲）")
 await xxx.send("识别到普通权限")
 ```

 

### 服务器上部署（CentOS 7.6）

- `go-cqhttp` 无法执行

 在 [Releases · Mrs4s/go-cqhttp (github.com)](https://github.com/Mrs4s/go-cqhttp/releases) 中选择合适的程序

- playwright 失败的解决方法

 [[Question] Support for CentOS · Issue #5780 · microsoft/playwright (github.com)](https://github.com/microsoft/playwright/issues/5780#issuecomment-968091413)

- 下载 chrome 与 chromeDriver 

 ```bash
 yum install https://dl.google.com/linux/direct/google-chrome-stable_current_x86_64.rpm
 ```

 [ChromeDriver - WebDriver for Chrome (chromium.org)](https://chromedriver.chromium.org/home)

- Tmux 后台运行机器人

 [Tmux 使用教程 - 阮一峰的网络日志 (ruanyifeng.com)](https://www.ruanyifeng.com/blog/2019/10/tmux.html)

- 查看进程信息

 ```bash
 ps -elf
 ```

- 关闭进程

 ```bash
 killall -u username
 # 或者
 pgrep -u ttlsa | xargs kill -9
 ```

- 安装字体

QQ 机器人搭建体验

啊，我真的懒得写了。明明应该好好学 `Python` 的，怎么学起 `Lua` 了……

其实，我是看到别人用 `Lua` 和 `LÖVE` 框架做了俄罗斯方块，自己也想做一个，才研究了一下 `Lua` （明明 `Python` 也可以做啊）。




## 配置

### Lua

`Lua` 在[官网](https://www.lua.org/)上下载即可，然后配置环境变量，将包含 `Lua` 的文件夹路径加入环境变量中。之后就可以在命令行执行：

```shell
lua54
```

显示相关信息，则说明 `Lua` 配置成功。要注意的是，下载的版本不同，执行的命令可能也不同，我的版本是 `lua-5.4.2` 。这一问题在后面配置 VSCode 时还会遇到。

### LÖVE

`LÖVE` 在[这里](https://love2d.org/)下载，配置环境变量。将包含 `LÖVE` 的文件夹路径加入环境变量中。之后在命令行执行：

```shell
love
```

会启动默认的 `LÖVE` 程序。

### VSCode

没错，我还是想用 VSCode ，所以就需要配置一下了。

VSCode 需要使用相应的拓展。我使用的是 `Code Runner` 和 `Love2D Support` ，在配置拓展时，需要对 `Code Runner` 的默认配置进行修改，并设置 `love.exe` 的路径（我也不知道为什么还要再设一次路径，明明有环境变量了）。

```json
"code-runner.executorMap": {
	"lua": "lua54",
},
"pixelbyte.love2d.path": "xxx\\love-11.4-win64\\love.exe",
```

 `Code Runner` 是用来跑 `Lua` 的， `Love2D Support` 是跑 `LÖVE` 的。在 `Love2D Support` 拓展的设置中，可以设置开启 `LÖVE` 的控制台，这样就能看见 `print()`的输出了（{% del 草 %}）。

### 测试

测试 `Lua` 的情况。

```lua
print("hello world!")
print("你好，世界！")
```

如果中文输出出现乱码，很有可能因为使用的终端是 `cmd` ，有两种方法解决该问题。第一种方法是将使用的终端改为 `powershell`；第二种方法则是将 `cmd` 的编码改为 `UTF-8` 。

```json
"terminal.integrated.defaultProfile.windows": "PowerShell",
"terminal.integrated.shellArgs.windows": ["/K chcp 65001 >nul"],
```

测试 `LÖVE` 的情况。

```lua
-- 初始化矩形的一些默认值
function love.load()
 x, y, w, h = 20, 20, 60, 20
end

-- 每一帧增加矩形的尺寸
function love.update(dt)
 w = w + 1
 h = h + 1
end

-- 绘制有颜色的矩形
function love.draw()
 love.graphics.setColor(0, 100, 100)
 love.graphics.rectangle("fill", x, y, w, h)
end
```

按住 `Alt` + `L`，应当会有 `LÖVE` 程序启动，绘制一个不断变大的青色矩形。当然，拓展的这个快捷键可以在设置中进行修改。

## 编写游戏

### 基础

#### 配置文件

在游戏目录中的 `conf.lua` 文件夹，会在 `LÖVE` 模块加载前运行，可以使用该文件重写 `love.conf` 函数。

 `love.conf` 函数有一个参数，该参数是一个包含所有默认值的 `table` 类型参数。通过 `love.conf` 函数，可以修改默认值，关闭不需要的模块：

```lua
function love.conf(t)
	-- 修改默认值
 t.window.width = 1024
 t.window.height = 768
 
 -- 关闭不需要的模块
 t.modules.joystick = false
 t.modules.physics = false
end
```

以下是 `11.3` 和 `11.4` 的全部默认值：

```lua
function love.conf(t)
 t.identity = nil -- The name of the save directory (string)
 t.appendidentity = false -- Search files in source directory before save directory (boolean)
 t.version = "11.3" -- The LÖVE version this game was made for (string)
 t.console = false -- Attach a console (boolean, Windows only)
 t.accelerometerjoystick = true -- Enable the accelerometer on iOS and Android by exposing it as a Joystick (boolean)
 t.externalstorage = false -- True to save files (and read from the save directory) in external storage on Android (boolean) 
 t.gammacorrect = false -- Enable gamma-correct rendering, when supported by the system (boolean)

 t.audio.mic = false -- Request and use microphone capabilities in Android (boolean)
 t.audio.mixwithsystem = true -- Keep background music playing when opening LOVE (boolean, iOS and Android only)

 t.window.title = "Untitled" -- The window title (string)
 t.window.icon = nil -- Filepath to an image to use as the window's icon (string)
 t.window.width = 800 -- The window width (number)
 t.window.height = 600 -- The window height (number)
 t.window.borderless = false -- Remove all border visuals from the window (boolean)
 t.window.resizable = false -- Let the window be user-resizable (boolean)
 t.window.minwidth = 1 -- Minimum window width if the window is resizable (number)
 t.window.minheight = 1 -- Minimum window height if the window is resizable (number)
 t.window.fullscreen = false -- Enable fullscreen (boolean)
 t.window.fullscreentype = "desktop" -- Choose between "desktop" fullscreen or "exclusive" fullscreen mode (string)
 t.window.vsync = 1 -- Vertical sync mode (number)
 t.window.msaa = 0 -- The number of samples to use with multi-sampled antialiasing (number)
 t.window.depth = nil -- The number of bits per sample in the depth buffer
 t.window.stencil = nil -- The number of bits per sample in the stencil buffer
 t.window.display = 1 -- Index of the monitor to show the window in (number)
 t.window.highdpi = false -- Enable high-dpi mode for the window on a Retina display (boolean)
 t.window.usedpiscale = true -- Enable automatic DPI scaling when highdpi is set to true as well (boolean)
 t.window.x = nil -- The x-coordinate of the window's position in the specified display (number)
 t.window.y = nil -- The y-coordinate of the window's position in the specified display (number)

 t.modules.audio = true -- Enable the audio module (boolean)
 t.modules.data = true -- Enable the data module (boolean)
 t.modules.event = true -- Enable the event module (boolean)
 t.modules.font = true -- Enable the font module (boolean)
 t.modules.graphics = true -- Enable the graphics module (boolean)
 t.modules.image = true -- Enable the image module (boolean)
 t.modules.joystick = true -- Enable the joystick module (boolean)
 t.modules.keyboard = true -- Enable the keyboard module (boolean)
 t.modules.math = true -- Enable the math module (boolean)
 t.modules.mouse = true -- Enable the mouse module (boolean)
 t.modules.physics = true -- Enable the physics module (boolean)
 t.modules.sound = true -- Enable the sound module (boolean)
 t.modules.system = true -- Enable the system module (boolean)
 t.modules.thread = true -- Enable the thread module (boolean)
 t.modules.timer = true -- Enable the timer module (boolean), Disabling it will result 0 delta time in love.update
 t.modules.touch = true -- Enable the touch module (boolean)
 t.modules.video = true -- Enable the video module (boolean)
 t.modules.window = true -- Enable the window module (boolean)
end
```

各配置详细的作用请参考：[Config Files - LOVE (love2d.org)](https://love2d.org/wiki/Config_Files)

#### 运行

`love.run()`是运行的主函数，它包含了运行时的主循环，不同版本的默认值不同。

```lua
-- The default function for 11.0, used if you don't supply your own.
function love.run()
	if love.load then love.load(love.arg.parseGameArguments(arg), arg) end

	-- We don't want the first frame's dt to include time taken by love.load.
	if love.timer then love.timer.step() end

	local dt = 0

	-- Main loop time.
	return function()
		-- Process events.
		if love.event then
			love.event.pump()
			for name, a,b,c,d,e,f in love.event.poll() do
				if name == "quit" then
					if not love.quit or not love.quit() then
						return a or 0
					end
				end
				love.handlers[name](a,b,c,d,e,f)
			end
		end

		-- Update dt, as we'll be passing it to update
		if love.timer then dt = love.timer.step() end

		-- Call update and draw
		if love.update then love.update(dt) end -- will pass 0 if love.timer is disabled

		if love.graphics and love.graphics.isActive() then
			love.graphics.origin()
			love.graphics.clear(love.graphics.getBackgroundColor())

			if love.draw then love.draw() end

			love.graphics.present()
		end

		if love.timer then love.timer.sleep(0.001) end
	end
end
```

可以参见 [love.run - LOVE (love2d.org)](https://love2d.org/wiki/love.run)

### 任务目标

做一款现代俄罗斯方块，具有以下特点：

- 配色：每个方块的颜色有要求
- 延迟锁定：方块接触到地面后，不会立刻锁定
- 旋转系统：根据踢墙表，存在踢墙情况
- 出块系统：使用 `7-Bag` 而不是纯随机的出块方式

在写代码时，学习参考了 MrZ 大佬的代码 [tetris-in-100-lines](https://github.com/MrZ626/tetris-in-100-lines)

### 实现

以下是我的代码，还没写完（小声）：[Tetris](https://github.com/ZerolAcqua/Tetris)

#### 场地参考

场地的话，计划使用 10×40 的场地，其中正常游戏只使用 10×20，剩下 10×20 用于存储顶出显示场地的方块。通过建立一个以场地为参考的坐标描述，我们可以描述方块的位置信息，并将游戏逻辑与绘图的逻辑分开。

实现起来，主要是通过一个二维数组记录 10*40 场地的情况。其中，每格不同的数值代表不同的方块。目前，`0` 代表无方块，`1~7` 代表七种方块。这样，以后既可以拓展格子的类型，又可以绘制彩色的场地。

从数据结构的角度，先消除在线性表靠后数据，再消除在线性表靠前的数据，操作要更方便一些。因此，消行的顺序就很关键。

#### 方块表达

方块，以及方块与其他要素的交互是最麻烦的一部分。

方块表达时，采用以下的方式。

![各方块的边界框](https://tetris.wiki/images/3/3d/SRS-pieces.png)

方块的边界框是包含四个方向形状的外接矩形。除了 `I` 和 `O` 的边界框是 4×4 和 2×2 以外，其他方块的边界框是 3×3 ，若要确定每个 `mino` 的位置，需要知道此刻边界框的位置和方块的朝向。在我们这次的编写中，我们通过边界框左上角的场地坐标，确定方块的位置。此外，在方块新生成的时候， `I` 和 `O` 是居中的，而其他方块是偏左的，它们的边界框左上角坐标也不相同。这些生成时的初始坐标，记录在一个表中。

```lua
-- 方块活动框左上角坐标 (x,y)
local initPos={
	{4,22},		-- I
	{4,22},		-- J
	{4,22},		-- L
	{5,22},		-- O
	{4,22},		-- S
	{4,22},		-- Z
	{4,22}		-- T
}
```

为了表示各个方向下的方块形状，也采用了表结构存储，在已知方块类型和方块朝向后，就能立刻获取其形状。

```lua
-- 记录的各方向的方块形状(从下往上)：1-原位(0) 2-顺时针位(R) 3-180度位(2) 4-逆时针位(L)
local blocks={
	-- I
	{
		{{0,0,0,0},{0,0,0,0},{1,1,1,1},{0,0,0,0}},		--I1
		{{0,0,1,0},{0,0,1,0},{0,0,1,0},{0,0,1,0}},		--I2
		{{0,0,0,0},{1,1,1,1},{0,0,0,0},{0,0,0,0}},		--I3
		{{0,1,0,0},{0,1,0,0},{0,1,0,0},{0,1,0,0}}		--I4
	},	
	-- J
	{
		{{0,0,0},{1,1,1},{1,0,0}},						--J1
		{{0,1,0},{0,1,0},{0,1,1}},						--J2
		{{0,0,1},{1,1,1},{0,0,0}},						--J3
		{{1,1,0},{0,1,0},{0,1,0}}						--J4
	},		
	-- L
	{
		{{0,0,0},{1,1,1},{0,0,1}},						--L1
		{{0,1,1},{0,1,0},{0,1,0}},						--L2
		{{1,0,0},{1,1,1},{0,0,0}},						--L3
		{{0,1,0},{0,1,0},{1,1,0}}						--L4
	},
	-- O	
	{
		{{1,1},{1,1}},									--O1
		{{1,1},{1,1}},									--O2
		{{1,1},{1,1}},									--O3
		{{1,1},{1,1}}									--O4
	},
	-- S
	{
		{{0,0,0},{1,1,0},{0,1,1}},						--S1
		{{0,0,1},{0,1,1},{0,1,0}},						--S2
		{{1,1,0},{0,1,1},{0,0,0}},						--S3
		{{0,1,0},{1,1,0},{1,0,0}}						--S4
	},		
	-- Z
	{
		{{0,0,0},{0,1,1},{1,1,0}},						--Z1
		{{0,1,0},{0,1,1},{0,0,1}},						--Z2
		{{0,1,1},{1,1,0},{0,0,0}},						--Z3
		{{1,0,0},{1,1,0},{0,1,0}}						--Z4
	},
	-- T
	{
		{{0,0,0},{1,1,1},{0,1,0}},						--T1
		{{0,1,0},{0,1,1},{0,1,0}},						--T2
		{{0,1,0},{1,1,1},{0,0,0}},						--T3
		{{0,1,0},{1,1,0},{0,1,0}}						--T4
	}
}
```

在后面的实现中，还使用了不少的表，比如行状态表、列状态表、颜色表、踢墙表等等。

#### 方块碰撞

这点是最复杂的地方，而且牵扯到踢墙的概念。

由于每个方块的边界框{% emp 并不与某一方向时方块的最小外接矩形重合 %}，方块与场地边界的碰撞检测就稍显麻烦。不对边界框中完全没有 `mino` 的行或列进行特殊处理的话，就可能造成（场地下边界或场地左右边界）数组越界或是方块悬空的状况。因此，根据方块的形状表，我计算了对应的行状态与列状态表（遇事不决就打表）。在此基础上，可以实现一个判断方块是否超出场地，与场地内方块重叠的函数。通过该函数，我们可以做到判断方块是否落地（落地了就要计时，准备延迟锁定了）。通过该函数，我们可以判断踢墙的结果是否可行。

踢墙的概念这里不再多说。有踢墙表之后，只需要按顺序进行平移的尝试，成功则采用，不成功则方块不能旋转。

#### 延迟锁定

目前我只做了延迟锁定，其表现为：

- 非落地状态下，不进行延迟锁定计时。
- 落地状态下，移动或旋转后变为非落地状态后，不进行延迟锁定计时。
- 落地状态下不会立即锁定，而是保留一段继续操作的时间。
- 不进行移动或旋转，在设定的时间（锁定延迟）过后，方块锁定。
- 落地状态下无法移动（左右卡住），或无法旋转（踢墙表检测全部失败）时，视作未进行操作。注意 `O` 的旋转虽然看起来没有变化，但它是确确实实成功旋转了的，所以会刷新锁定延迟。

同时，需要注意，为了避免无限刷新锁定延迟的情况，应该增加一个操作次数限制：

- 非落地状态下，不计入操作次数限制。
- 落地状态下，一次移动或旋转后，计一次操作次数。
- 落地状态下无法移动（左右卡住），或无法旋转（踢墙表检测全部失败）时，视作未进行操作，不计入操作次数限制。注意 `O` 的旋转虽然看起来没有变化，但它是确确实实成功旋转了的，所以会计一次操作次数。
- 当操作次数用尽后，移动和旋转将不再刷新锁定延迟。

今天（2022.8.23）我实现操作次数的时候，发现还有一个问题：

- 如果操作次数用尽后，踢墙产生的偏移不能向上。

 这个规定的意义在于，避免玩家通过踢墙将方块“抬高”，然后方块下落，刷新延迟锁定，导致无限操作而不锁定的问题。

#### 出块序列

实际上就是一个队列，当队列短于设定的数量时。按选定的随机生成器，生成一段新序列加到队尾。

如果是 `bag` 出块，则保证要添加的新序列中每种方块各出现一次

#### 暂存

暂存的实现思路很简单，就是记录下暂存的方块 id 和暂存的操作次数限制而已。但是在这个过程中，我意识到关于暂存计数、锁延计数的重置时机问题。

根据游戏逻辑，在暂存之后，更换的方块会重新从场地顶部开始下落，并且方块的锁延计数会重置。暂存计数就是为了避免玩家通过无限的暂存，重置锁延计数的情况。所以暂存之后，锁延计数会重置，暂存计数 `-1`。而暂存计数重置的时机，应当是一个方块成功锁定后，这是毫无疑问的。

可是，锁延计数是什么时候重置呢？在没有暂存功能的情况下，锁延计数在方块成功锁定后，或者新生成方块时重置都是没有问题的。但是引入了暂存功能后，暂存方块会导致方块的锁延计数重置。因此，如果将锁延计数在方块成功锁定后重置，会导致暂存后新方块的锁延计数未重置。所以锁延计数应当在生成方块时更新。

换个角度想想，暂存后的方块，本质就是新生成了一个方块，这和方块锁定后新生成方块的原理应当一致。而锁延计数会在方块锁定后和暂存后重置，因此在生成方块时重置锁延计数能很好地解决这两种情况。

此外，在暂存中无方块和暂存中有方块时，对序列的处理有一定的区别。前者是将当前块暂存，从序列中新取一块作为当前块；后者是将当前块与暂存块交换。

### 发布

#### 创建 .love 文件

将游戏文件变为 `.exe` 文件的步骤比较简单：

- 将游戏文件加入 `.zip` 压缩文件中
- 将后缀更改为`.love`

此文件就可以通过以下方式运行：

```shell
love xxx.love
```

#### 针对 windows 平台构建

- 将 `love.exe` 与 `.zip` 文件合并为一个 `.exe` 文件
- 将 `.dll` 文件、许可 `license.txt` 和 合并得到的 `.exe` 文件放在同一个目录下，即可运行游戏

#### 网页发布

推荐使用 [Davidobot/love.js](https://github.com/Davidobot/love.js)，该作者目前还保持着更新，适用于 `11.4` 版本

通过以下方式安装：

```shell
npm i love.js
```

或

```shell
npm -g i love.js
```

然后构建兼容版本：

```shell
love.js game.love game -c
```

如果命令无法正常执行（比如说，打开了 `love.js` 文件），则可以使用以下命令：

```shell
love.js.cmd game.love game -c
```

即可完成构建。该命令会在当前目录生成一个文件夹：

```shell
Tetris
│ game.data
│ game.js
│ index.html
│ love.js
│ love.wasm
│
└─theme
 bg.png
 love.css
```

其中，`game.data` 和 `game.js` 是游戏的生成文件， `index.html` 就是生成的网页，而 `theme` 目录下的文件是页面的美化相关的文件。`love.js` 和 `love.wasm` 是 `love` 框架对应的文件。

:::info{title="相关信息"}
游戏基本上完成了，剩下的东西主要是美化辅助和提升操作手感的方面（阴影和 DAS ），大概率不会更新了……想体验戳[这里](https://vanblog.zerolacqua.top/c/tetris)
:::

各种发布方式（包括网页发布）具体可以请参考：[Game Distribution - LOVE (love2d.org)](https://love2d.org/wiki/Game_Distribution)