# alpha-blending
下面是一段3dgs的原文

Specifically, the color $C$ is given by volumetric rendering along a ray:

$$
\begin{equation}C=\sum_{i=1}^NT_i(1-\exp(-\sigma_i\delta_i))\mathbf{c}_i\quad\mathrm{with}\quad T_i=\exp\left(-\sum_{j=1}^{i-1}\sigma_j\delta_j\right)
\end{equation}
$$

where samples of density $\sigma$, transmittance $T$, and color $c$ are taken along the ray with intervals $\delta_i$. This can be re-written as

$$
\begin{equation}C=\sum_{i=1}^NT_i\alpha_i\mathbf{c}_i,\end{equation}
$$

with

$$
\alpha_i=(1-\exp(-\sigma_i\delta_i))\mathrm{~and~}T_i=\prod_{j=1}^{i-1}(1-\alpha_i).
$$

这是标准nerf的渲染方程，注意$(2)$式的形式，这里$T$表示为透射率，$\alpha$是一个与采样间隔、体密度有关的值，$c$是点$i$处的颜色。




根据Volume Rendering Digest这篇文章中的推导
<iframe src="https://xuqi.space:7070/api/public/dl/zbjXSmcY?inline=true" width="100%" height="1000px">
  <p>Your browser does not support iframes.</p>
</iframe>

由于将$\sigma$视作表示射线击中粒子的微分可能性（即在行驶无穷小距离时击中粒子的概率)。解出微分方程的形式中就会带有$\exp{}$项，排除掉这些数学符号的干扰，其本质是一种alpha-blending或者叫 [alpha compositing](https://en.wikipedia.org/wiki/Alpha_compositing)


那么对于3dgs来说，其alpha-blending的形式，
$$
\begin{equation}C=\sum_{i\in N}c_i\alpha_i\prod_{j=1}^{i-1}(1-\alpha_j),\end{equation}
$$
也就很好理解了。

其中$c_i$是该splatting在渲染方向上的颜色，$\alpha_i$是一个学习到的透明度值。

# computeColorFromSH
其中$c_i$是与方向有关的颜色值，本质上是一组球谐函数的基，在3dgs的cuda源码中可以找到

```cpp
// Forward method for converting the input spherical harmonics
// coefficients of each Gaussian to a simple RGB color.
__device__ glm::vec3 computeColorFromSH(int idx, int deg, int max_coeffs, const glm::vec3* means, glm::vec3 campos, const float* shs, bool* clamped)
{
	// The implementation is loosely based on code for 
	// "Differentiable Point-Based Radiance Fields for 
	// Efficient View Synthesis" by Zhang et al. (2022)
	glm::vec3 pos = means[idx];
	glm::vec3 dir = pos - campos;
	dir = dir / glm::length(dir);

	glm::vec3* sh = ((glm::vec3*)shs) + idx * max_coeffs;
	glm::vec3 result = SH_C0 * sh[0];

	if (deg > 0)
	{
		float x = dir.x;
		float y = dir.y;
		float z = dir.z;
		result = result - SH_C1 * y * sh[1] + SH_C1 * z * sh[2] - SH_C1 * x * sh[3];

		if (deg > 1)
		{
			float xx = x * x, yy = y * y, zz = z * z;
			float xy = x * y, yz = y * z, xz = x * z;
			result = result +
				SH_C2[0] * xy * sh[4] +
				SH_C2[1] * yz * sh[5] +
				SH_C2[2] * (2.0f * zz - xx - yy) * sh[6] +
				SH_C2[3] * xz * sh[7] +
				SH_C2[4] * (xx - yy) * sh[8];

			if (deg > 2)
			{
				result = result +
					SH_C3[0] * y * (3.0f * xx - yy) * sh[9] +
					SH_C3[1] * xy * z * sh[10] +
					SH_C3[2] * y * (4.0f * zz - xx - yy) * sh[11] +
					SH_C3[3] * z * (2.0f * zz - 3.0f * xx - 3.0f * yy) * sh[12] +
					SH_C3[4] * x * (4.0f * zz - xx - yy) * sh[13] +
					SH_C3[5] * z * (xx - yy) * sh[14] +
					SH_C3[6] * x * (xx - 3.0f * yy) * sh[15];
			}
		}
	}
	result += 0.5f;

	// RGB colors are clamped to positive values. If values are
	// clamped, we need to keep track of this for the backward pass.
	clamped[3 * idx + 0] = (result.x < 0);
	clamped[3 * idx + 1] = (result.y < 0);
	clamped[3 * idx + 2] = (result.z < 0);
	return glm::max(result, 0.0f);
}
```
这段代码用gpt解释
```txt
这段代码是一个CUDA内核函数，用于将球谐系数（spherical harmonics coefficients）转换为简单的RGB颜色。这个函数是图形渲染中的一部分，特别是在计算光源对场景中物体颜色的影响时。球谐函数是拉普拉斯方程在球坐标系中的解，它们在描述光的散射和辐射传输中非常有用。

下面是对这段代码的逐行解释：

__device__ 关键字表明这个函数可以在GPU上作为CUDA内核运行。

glm::vec3 computeColorFromSH(...) 定义了一个函数，它接受球谐系数、球面谐波的阶数、最大系数数、高斯分布的均值、相机位置、球谐系数数组和是否被截断的标志数组作为输入，并返回一个glm::vec3类型的RGB颜色。

glm::vec3 pos = means[idx]; 获取当前高斯分布的均值位置。

glm::vec3 dir = pos - campos; 计算从相机位置到当前位置的方向向量。

dir = dir / glm::length(dir); 归一化方向向量。

glm::vec3* sh = ((glm::vec3*)shs) + idx * max_coeffs; 计算指向当前高斯分布球谐系数数组的指针。

glm::vec3 result = SH_C0 * sh[0]; 初始化结果颜色，使用阶数为0的球谐系数。

if (deg > 0) 开始一个条件块，用于计算阶数大于0的球谐系数对颜色的影响。

9-15. 在这个条件块内部，计算更高阶的球谐系数对颜色的贡献。SH_C1, SH_C2, SH_C3 应该是预定义的系数数组，用于计算不同阶数的球谐系数对最终颜色的影响。

result += 0.5f; 将一个小的偏移量加到结果颜色上，以避免颜色太暗。
17-19. clamped 数组用于跟踪RGB颜色分量是否被截断（即是否小于0）。如果某个分量小于0，相应的标志会被设置为true。

return glm::max(result, 0.0f); 确保所有颜色分量都是非负的，返回最终的RGB颜色。
这个函数的目的是将复杂的球谐分析转换为直观的RGB颜色，这在光线追踪和实时渲染算法中很常见。代码中提到的“Differentiable Point-Based Radiance Fields for Efficient View Synthesis”由Zhang等人在2022年提出，这是一种先进的视图合成技术，它允许在保持渲染效率的同时，对场景进行不同的光照和视角变化。
```
3dgs默认使用了3阶的球谐函数。

# semantic from gaussian?
于是我们会思考一个问题，我们可以使用3dgs渲染一个语义图么？

理论上也是可以的，只需要把$(3)$式中的$c$改成$s$，让$s$也是一组球谐函数的基，然后对应也要有另一组学习到的$\alpha$，这样就可以渲染出一张语义图了。但是该如何输入监督信息呢？

我们可以将输入的图像用语义分割网络进行处理，这样每一个view就也带有一张语义图真值了。

思考1：会不会造成语义空间上的不连续？由于仅仅使用2d的监督信息，可能会造成$s$只在有语义真值的渲染方向上表现较好，而在没见过的方向上，语义的表现较差，但是实际上语义随渲染方向的改变应该很小。（同一个物体的语义不随方向改变？）

思考2：如何引入3d信息对语义进行修正？在点云语义分割任务上，有很多可以参考的文章。

# other information from gaussian?

3dgs——rendering

# 摘要
本文简单介绍了如何在内网服务器上自建`overleaf`，使用`overleaf`官方开源的`overleaf toolkit`，并使用`frp`完成内网穿透到公网服务器上，实现公网访问。

# 背景
今天师弟开始写本科毕设论文，但是我给的模板太大了在`overleaf`传不上去，于是记起来利用`IEEE`会员白嫖`overleaf premium`的操作已经被`ban`了，那没办法只好自己建一个`overleaf`咯，以后自己写论文和写作业也方便一点。



# 安装overleaf toolkit
`overleaf toolkit`的官方仓库是https://github.com/overleaf/toolkit

按照指示`clone`下代码后，使用
```bash
sudo ./bin/init
```
生成配置文件，配置文件一共有两个，`overleaf/toolkit/config/overleaf.rc`与`overleaf/toolkit/config/variables.env`

在`overleaf/toolkit/config/overleaf.rc`中修改端口号
```bash
OVERLEAF_PORT=your_port
```
其余的不用修改

在`overleaf/toolkit/config/variables.env`中添加一行
```env
# language
OVERLEAF_SITE_LANGUAGE=zh-CN
```
将语言设置为简体中文
并修改`OVERLEAF_APP_NAME`、`OVERLEAF_NAV_TITLE`等字段

# 启动docker
`overleaf toolkit`在`bin`目录下内置了一系列管理容器的命令
执行
```bash
sudo ./bin/up
```
（其实是执行了docker-compose up）就会生成三个容器，分别是`sharelatex`、`mongo`、`redis`，直到`up`的log逐渐稳定。

之后就可以使用
```bash
sudo ./bin/start
```
以后台运行模式运行容器了

此时就可以访问`http://ip:port/launchpad`网站，设置管理员账号与添加账号了。
# 安装完整版texlive
默认安装的`overleaf toolkit`容器内的`texlive`并不是完整版的，在使用某些宏包时可能会发生一些错误。

使用
```bash
sudo ./bin/shell
```
进入容器内的终端，然后执行以下命令
```bash
cd /usr/local/texlive
# 下载并运行升级脚本
wget http://mirror.ctan.org/systems/texlive/tlnet/update-tlmgr-latest.sh
sh update-tlmgr-latest.sh -- --upgrade
# 更换texlive的下载源
tlmgr option repository https://mirrors.sustech.edu.cn/CTAN/systems/texlive/tlnet/
# 升级tlmgr
tlmgr update --self --all
# 安装完整版texlive（时间比较长，不要让shell断开）
tlmgr install scheme-full
exit
```
最后，重启容器
```bash
sudo ./bin/stop
sudo ./bin/start
```
# 一些注意事项
1. 由于没有配置`nginx`转发与`TLS`，是不能使用`https`访问的。
2. 由于没有配置`SMTP`邮件服务器，因此用户注册的时候是收不到邮件的（事实上我也不想让其他用户随便注册）。但可以让管理员账户在后台添加用户，后台会给出一个注册成功的修改密码的链接，把那个链接发给注册用户就好了。

自建overleaf——没有overleaf premium也能愉快使用

# 摘要
本文主要介绍了如何对卫星影像数据进行处理、构建huggingface diffuser格式的数据集并使用diffuser训练controlnet，从而实现使用全球语义图控制生成全球卫星图。



# 数据介绍
训练数据使用了MODIS数据集的xxxxx卫星图与xxxxx语义图。进行了一定的预处理后裁剪成512x512的小图，在SD1.5版本的controlnet上进行训练。(详细步骤还得等黄子扬同学回忆一下看看能不能加上来）

# 数据集的构建
从已经获取一系列source（控制图像）和target（目标图像）样本对开始记录。
需要的数据集结构如下：
```txt
dataset_name:
├─dataset_name.py
├─prompt.jsonl
├─source
│  ├─0_s.png
│  ├─1_s.png
│  ├─2_s.png
│  ├─3_s.png
│  └─...
└─target
   ├─0_t.png
   ├─1_t.png
   ├─2_t.png
   ├─3_t.png
   └─...
```

其中的prompt.jsonl的具体内容如下,每条记录对应一个样本对。

```
{"source": "数据集文件夹内的控制图像相对路径", "target": "数据集文件夹内的目标图像相对路径", "prompt": "{所需要生成的目标图像的描述提示}"}
{"source": "source/0_s.png", "target": "target/_t.png", "prompt": "a remote sensing image of earth. Containing Closed Shrublands,Open Shrublands,Savannas,Grasslands,Permanent Wetlands,Croplands,Urban and Built-up Lands,Barren,Water Bodies,"}
```

最后一个文件是和dataset文件夹同名的dataset_name.py,其主要作用是重写controlnet内的数据读取接口。

```python
--dataset_name.py:
import pandas as pd
import datasets
import os

_VERSION = datasets.Version("0.0.1")

_DESCRIPTION = "TODO"
_HOMEPAGE = "TODO"
_LICENSE = "TODO"
_CITATION = "TODO"

_FEATURES = datasets.Features(
    {
        "target": datasets.Image(),#!!首先需要改的是这三行，用来指定你的prompt中三个列分别对应的类型
        "source": datasets.Image(),#!!首先需要改的是这三行，用来指定你的prompt中三个列分别对应的类型
        "prompt": datasets.Value("string"),#!!首先需要改的是这三行，用来指定你的prompt中三个列分别对应的类型
    },
)

_DEFAULT_CONFIG = datasets.BuilderConfig(name="default", version=_VERSION)


class MyData(datasets.GeneratorBasedBuilder):
    BUILDER_CONFIGS = [_DEFAULT_CONFIG]
    DEFAULT_CONFIG_NAME = "default"

    def _info(self):
        return datasets.DatasetInfo(
            description=_DESCRIPTION,
            features=_FEATURES,
            supervised_keys=None,
            homepage=_HOMEPAGE,
            license=_LICENSE,
            citation=_CITATION,
        )

    def _split_generators(self, dl_manager):
        #！其次是下面三个路径，分别代表：
        # metadata_path -> prompt.jsonl的路径
        # images_dir -> target目标图像的路径，因为我们在prompt里已经记录了target/0.png， 所以这里只需要写上一级的dataset_name文件夹的路径
        # conditioning_images_dir -> source控制图像的路径，因为我们在prompt里已经记录了source/0.png， 所以这里只需要写上一级的dataset_name文件夹的路径
        metadata_path = "/home/disk/hzy/repos/diffusers/examples/controlnet/gpcvrs_small/small.jsonl"
        images_dir = "/home/disk/hzy/repos/diffusers/examples/controlnet/gpcvrs_small"
        conditioning_images_dir = "/home/disk/hzy/repos/diffusers/examples/controlnet/gpcvrs_small"
        dl_manager.download_and_extract
        return [
            datasets.SplitGenerator(
                name=datasets.Split.TRAIN,
                # These kwargs will be passed to _generate_examples
                gen_kwargs={
                    "metadata_path": metadata_path,
                    "images_dir": images_dir,
                    "conditioning_images_dir": conditioning_images_dir,
                },
            ),
        ]

    def _generate_examples(self, metadata_path, images_dir, conditioning_images_dir):
        metadata = pd.read_json(metadata_path, lines=True)

        for _, row in metadata.iterrows():
            text = row["prompt"]#！这里改为我们的提示词列名称，即"prompt"

            image_path = row["target"]#！这里改为我们的目标图像列名称，即"target"
            image_path = os.path.join(images_dir, image_path)
            image = open(image_path, "rb").read()

            conditioning_image_path = row["source"]#！这里改为我们的控制图像列名称，即"source"
            conditioning_image_path = os.path.join(
                conditioning_images_dir, row["source"]#！这里改为我们的控制图像列名称，即"source"
            )
            conditioning_image = open(conditioning_image_path, "rb").read()

            #最后迭代返回的是两个元素：
            # 1、该样本对目标文件路径（此处即为row["target"]）
            # 2、一个包含下列元素的字典，按照描述修改即可，返回的字典的键名对应开头（line45~47）指定的三个名字： 
            #       "prompt":prompt_str,
            #       "target":{
            #                "path": image_path,（目标图像路径）
            #                "bytes": image,（目标图像路径）
            #                 }
            #       "source":{
            #                "path": conditioning_image_path,（控制图像文件路径）
            #                "bytes": conditioning_image,（控制图像本身）
            #                 }
            yield row["target"], {
                "prompt": text,
                "target": {
                    "path": image_path,
                    "bytes": image,
                },
                "source": {
                    "path": conditioning_image_path,
                    "bytes": conditioning_image,
                },
            }
```

# 训练
在完成dataset_name.py的修改后，只需要修改huggingface 给出的controlnet的训练脚本即可：

```bash
#训练脚本train.sh修改示例：
export MODEL_DIR="runwayml/stable-diffusion-v1-5"
export OUTPUT_DIR="{输出的模型路径}"

accelerate launch --multi_gpu train_controlnet.py \
 --mixed_precision="fp16" \
 --pretrained_model_name_or_path=$MODEL_DIR \
 --output_dir=$OUTPUT_DIR \
 --train_data_dir="{你的dataset文件路径}" \
 --resolution=512 \
 --learning_rate=1e-5 \
 --train_batch_size=4 \
 --num_train_epochs=6 \
 --caption_column="prompt" \ #这里修改caption_column为提示词列名称prompt
 --image_column="target" \ #这里修改image_column为目标图像列名称target
 --conditioning_image_column="source" \ #这里修改conditioning_image_column为目标图像列名称source
```

在diffuser的example/controlnet目录下运行train.sh脚本可以直接开始训练。

ControlNet训练——使用语义图控制生成卫星图

# 摘要
本文简要介绍了如何使用`vue3`和`vue-cesium`实现三维地球表面贴图的可视化


# 背景
之前使用了`controlnet`完成了由语义图到卫星图的2d生成任务，并通过`tilediffusion`插件实现了无缝扩展生成全球的一整块卫星图瓦片。现在试图对这个卫星图进行3d的可视化。

# 创建vue项目
在vue.js中文官网https://cn.vuejs.org/ 上，目前的创建命令是
```bash
npm create vue@latest
```
输入项目名称后有一堆选项选，我只加了`ts`，其他的以后有需要再说。
# 安装vue-cesium组件库
`vue-cesium`是一个新兴的，将`cesium.js`包装成`Vue3`组件库的项目。官网为https://zouyaoji.top/vue-cesium/ 

安装命令目前为
```bash
npm install vue-cesium
```

# 创建SPA并导入vue-cesium相关组件，实现可视化
清理成最小运行单元后，`src`下创建一个`Global.vue`的`SPA`，内容如下：
```jsx
<script setup>
import { reactive } from 'vue'
import { VcConfigProvider, VcViewer, VcLayerImagery, VcImageryProviderSingletile } from 'vue-cesium'

const vcConfig = reactive({
    cesiumPath: 'https://unpkg.com/cesium@latest/Build/Cesium/Cesium.js'
})
const imagePath = './earth_generated_8ds_nearest_no_black.png'
</script>

<template>
    <vc-config-provider :cesium-path="vcConfig.cesiumPath">
        <vc-viewer>
            <vc-layer-imagery>
                <vc-imagery-provider-singletile :url=imagePath>

                </vc-imagery-provider-singletile>
            </vc-layer-imagery>
        </vc-viewer>
    </vc-config-provider>
</template>
```
注意这里的`imagePath`变量，为了访问方便，我把`earth_generated_8ds_nearest_no_black.png`这个卫星图放在了`public`文件夹下，由于打包后`public`文件夹下的内容会被直接放到根目录下，这样就可以使用`./`的相对路径访问，在开发环境与生产环境的`dist`下都可以访问成功。

如果图像放在了`src`下的目录，比如`assets`，实测这里用`@/assets/xxxxx`是不可行的，暂时不清楚是不是组件库的bug还是需要使用更复杂的方式导入图像。

然后修改一下`App.vue`下的内容。
```jsx
<script setup lang="ts">
import Global from './pages/Global.vue'
</script>

<template>
    <Global />
</template>

<style scoped></style>
```
为了打包后访问js文件路径不出错，还需要在`vite.config.ts`中加入
```ts
export default defineConfig({
    base: './',
})
```
# 效果

![CleanShot 2024-04-14 at 19.59.32.jpg](https://xuqi.space/static/img/afe680ad8c7bf4d23c62b0ff0db27161.CleanShot%202024-04-14%20at%2019.59.32.webp)

![CleanShot 2024-04-14 at 20.00.02.jpg](https://xuqi.space/static/img/8767ff30c2cf48231867da1dba5ee985.CleanShot%202024-04-14%20at%2020.00.02.webp)

使用vue+cesium实现三维地球可视化

# 2024华为软件精英挑战赛
首先祝贺蒟蒻小队"星月湖"（话说为啥ikaros每次起名字都是这种风格啊喂!!!），经过了3.7-3.22共计2 weeks 1 day的折磨，凭着亿点点运气获得武长赛区30名的成绩，进入复赛。🥹🎉🥳

下面将记录一下suki whu sakura同学（也就是insomnia本睡不醒啦~！），在这次比赛中遇到了什么奇奇怪怪又还算有意思的经历吧~（其实是不吐不快了，逃~



# 任务书
<iframe src="https://xuqi.space:7070/api/public/dl/B3-ZhIKp?inline=true" width="100%" height="1000px">
  <p>Your browser does not support iframes.</p>
</iframe>

# 对任务书的思考
看完任务书，我们主要思考的方向是
1. 机器人寻路算法
2. 机器人避障算法（为了让机器人之间互相不碰撞）
3. 机器人拾取货物的策略
4. 船选择泊位的策略
5. 船何时开船前往虚拟点的策略
6. 船在泊位之间轮转的策略
7. 针对特定地图优化的策略

# 关于跳帧、碰撞问题
题目中要求每帧必须在`15ms`内处理完成并发送`OK`，否则在没有收到`OK`前，判题器将不会继续输入场面帧信息，若处理超过了`15ms`，那么以判题器接受到`OK`的时刻为准，判题器输入的帧信息的序号就可能发生不连续的情况。

如果发生跳帧，那么就会丢失掉某一帧的场面信息，如果该帧恰好判题器向场地中随机添加了一些货物，那么这部分货物信息就被永远丢失掉了，这对分数影响是巨大的。我们应该**保证，即使在`15ms`内没能处理完所有机器人的计算操作（主要是寻路），也应该在帧耗时接近`15ms`的时候输出`OK`，并接受下一帧的场面信息**，让没能处理完的计算操作在**后台继续执行**，只需要**在使用时检查计算结果是否可用**就好了。

而对于碰撞，发生碰撞后会使得机器人进入长度为20帧的`RECOVERING`状态，这段时间内机器人无法响应任何操作，很显然发生碰撞也是纯亏的操作，所以我们应该**保证不会发生碰撞**。

# 关于寻路算法
寻路算法有单源最短路径和多源最短路径之分，我们一开始的思路就是单源最短路径中的`A*`算法，这个算法在最差情况下会退化到`dijkstra`算法，也就是最差时间复杂度为$O(n\log n)$，因为觉得多源最短路径是要$O(n^3)$时间复杂度，所以可能来不及在初始化的时候搞定，后面使用了泛洪算法求地图上的连通块与到某一点的距离，发现其实dfs遍历一整遍地图也耗时不大，初始化的5s其实大有可为（但截至目前也没有想到什么很好的办法）。

我们的`A*`算法的代码如下：

```cpp
// 启发式函数：曼哈顿距离
int PathFinder::HeuristicCostEstimate(int current_x, int current_y, int goal_x, int goal_y) {
    return abs(current_x - goal_x) + abs(current_y - goal_y);
}

// 判断移动是否合法
bool PathFinder::IsValidMove(int x, int y) { return world.originMap.isAccess(x, y); }

// A*搜索算法
Path PathFinder::FindPath(int sx, int sy, int ex, int ey) {
    //起止点相同，不进入寻路
    if(sx == ex && sy == ey){
        return {};
    }

    //不存在缓存地图，进入寻路
    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> open_set;
    std::vector<std::vector<bool>> closed_set(utils::MAP_SIZE, std::vector<bool>(utils::MAP_SIZE, false));

    open_set.push(Node(sx, sy, 0, HeuristicCostEstimate(sx, sy, ex, ey), {}));

    while (!open_set.empty()) {
        Node current = open_set.top();
        open_set.pop();

        if (current.x == ex && current.y == ey) {
            return current.path;
        }

        if (closed_set[current.x][current.y]) {
            continue;
        }

        closed_set[current.x][current.y] = true;

        for (const auto &dir: directions) {
            int new_x = current.x + dir[0];
            int new_y = current.y + dir[1];

            if (IsValidMove(new_x, new_y)) {
                int new_cost = current.cost + 1;
                int heuristic = HeuristicCostEstimate(new_x, new_y, ex, ey);

                Path new_path = current.path;
                new_path.push_back((dir[0] == 0 && dir[1] == 1)    ? utils::Direction::RIGHT
                                   : (dir[0] == 0 && dir[1] == -1) ? utils::Direction::LEFT
                                   : (dir[0] == -1 && dir[1] == 0) ? utils::Direction::UP
                                                                   : utils::Direction::DOWN);

                open_set.push(Node(new_x, new_y, new_cost, heuristic, new_path));
            }
        }
    }

    return {}; // 未找到路径
}
```
可以看到，这里面还是存在着许多可以优化的地方的，比如`std::vector<bool>`的使用，熟悉`STL`的同学应该知道，`std::vector<bool>`其实并不是`bool`的`vector`，`STL`中对`std::vector<bool>`做了特化，对`bool`类型做了个proxy，使用了一个**代理类**，所以实际上凡是使用`std::vector<bool>`的地方，都应该想想是否可以使用`bool []`作为替代。

其次，这里面存在着大量的**拷贝**操作，每次操作`current.path`的时候，将会产生一次拷贝，而`path`是一个`vector<utils::Direction>`，所以将会产生不必要的性能消耗。事实上，可以记录一个每个节点的parents节点，这样可以通过**对终点的回溯**找到路径，解决发生大量拷贝的问题。

再次，这里对`Path`类型使用了`vector<utils::Direction>`的实现，这里让我们在后面的开发产生了产生了巨大的不便与潜在问题。后来想想，这里就应该使用`vector<Position>`的，每一个节点应该是一个包含`x、y`的位置，而后在输出的时候将两个位置的坐标做比对得到移动方向。如果在寻路的时候直接得到的就是一个`vector<utils::Direction>`的话，那么后续就永远丢**失掉了机器人的坐标位置**了，一旦发生跳帧、移动执行失败等错误，那么整个`Path`就不正确了，那就只能重新寻路了，这样会让整个程序显得不那么优雅。或许这就是“永远不要提早优化”的含义吧。

最后就是**可读性**问题，这次我们的coding习惯感觉还是存在很大的差异的，包括命名方式、对`git`的使用，对`.clangformat`的使用等等。考虑在之后写单独的文章介绍一些在ubuntu下的一些开发标准。

# 关于如何保证不发生碰撞——机器人避障算法
机器人避障是一个复杂的话题，不过总体来说，有两种思路，一种是考虑每个机器人在移动的时候进行试探观察，另一种是考虑对所有机器人的路径做整体调整规划。

## 碰撞的两种可能性

![CleanShot 2024-03-26 at 15.34.17.jpg](https://xuqi.space/static/img/69a1fb2404adf5a2e5036566b45bb478.CleanShot%202024-03-26%20at%2015.34.17.webp)

对于机器人来说，碰撞只会存在两种可能性，第一种是两个机器人在下一帧时将会**移动到同一个位置**，我们可以称为`collision`；第二种是两个机器人在下一帧将会**交换位置互相穿过**，我们称为`cross over`

而对于机器人`2`下一帧将会移动到机器人`3`这一帧的位置，机器人`3`下一帧将会移动到其他方向的位置，这种情况认为是**合法**的，因为实际在移动操作中是**不考虑输出指令的先后顺序**的，判题器会视为所有机器人同时移动。

## 通过试探观察进行避障

![CleanShot 2024-03-26 at 19.13.43.jpg](https://xuqi.space/static/img/c53d575c5858943fb237524f88654a49.CleanShot%202024-03-26%20at%2019.13.43.webp)

如果机器人`0`的路径列表是五个向右走的话（列表里存的节点实现到底是方向还是坐标这点并不要紧），那么在进行第一步行走的时候，`0`号机器人应该要查看右侧蓝色虚线标注的`0`号位置的上下右三个方向是否有机器人，如果有机器人的话，该机器人假设是`1`号机器人，如果正好也要移动到蓝色虚线标注的`0`号位置的话，那么就判断会发生`collision`。解决办法则是让`0`号机器人**呆在原地静止一帧**。


![CleanShot 2024-03-26 at 19.22.50.jpg](https://xuqi.space/static/img/6a4131548983b4acf740872e6ae899f1.CleanShot%202024-03-26%20at%2019.22.50.webp)

这里要思考的点是，**选择呆在原地静止一帧能不能解决问题**，与**选择呆在原地静止一帧会导致什么**。

`0`号机器人在原地静止一帧后，`1`号机器人就会占据蓝色虚线标注的`0`号位置，那么在下一帧，`1`号机器人如果向左走，则会触发`0`号机器人和`1`号机器人的`cross over`，如果往上或者往下走，那么`0`号机器人就可以正常移动了。


![CleanShot 2024-03-26 at 19.57.17.jpg](https://xuqi.space/static/img/53307afeee2f5773145bf2e0dfd3e3a0.CleanShot%202024-03-26%20at%2019.57.17.webp)

如果`0`号机器人要向右走，却发现右侧的位置已经有一个`1`号机器人了，那么如果`1`号机器人下一帧的移动方向是向左，就判断会发生`cross over`。解决办法则是让`0`号机器人**尝试向上、下、右侧避让，并在避让后插入一个相反的方向回到原来的位置**。

这里要注意的点是，**选择向哪个方向避让**与**为什么让`0`号机器人避让而不是`1`号机器人避让**

首先看向哪个方向避让的问题，我们可以进行如下思考：

1. 要选择可以走的方向避让，如果避让的那个方向是墙，则换一个方向
2. 如果`1`号机器人在下一帧要向下移动，那么`0`号机器人本帧就不要向下避让了，因为如果`0`号机器人本帧向下避让，那么在下一帧依然会发生`cross over`，但如果`0`号机器人不向下避让，则之后就不会再次发生`cross over`。总而言之，避让的方向选择不与被避让机器人下一步方向相同的。
3. 假如`0`号机器人排除掉了向下避让，还有向左向上两个方向进行选择，哪一个方向是更好的呢？我们发现`0`号机器人之后的路径中本就有一个向上的行走，如果我们**发现向上避让，并不插入相反的方向让机器人回到避让前的位置，而是接着向右走四步，每一步都可以执行并且也能到达终点的话，那么选择向上避让就会节省两帧的时间**。但如果不能满足这个条件的话，那么在当前已知信息下，向上避让与向左避让是同样优的。

再就是为什么让`0`号机器人避让而不是`1`号机器人避让的问题，这里涉及到了优先级的概念，暂时按下不表（这部分的设计insomnia并不是很清楚，等搞清楚了再补充）。

感谢评论区Zerol Acqua的补充
> 文章里提到的“碰撞的两种可能性”的逻辑，对于试探观察（实时）和整体调整（寻路时）的避障都是适用的。
> 
> 然而，还有一种在目前代码（实现不健全的前提下）会出现的情况
> 
> 一个机器人无法移动在发呆
> 由于寻路、取货、卸货时，机器人有一帧或者多帧无法移动
> 另一个机器人要往静止机器人所在的位置上移动
> 由于存在固定的优先级，优先级高的往优先级停的静止机器人上移动
> 寻路的结果，与避障的结果存到同一个路径队列 robotPaths[i] 中
> 这样就存在一个问题，静止的机器人如果要躲避来袭的高优先级机器人，势必要往自己的路径队列里加入避障移动（一般是一来一回的移动）。
> 假如这个静止的机器人正在寻路，此时发生避障行为就很麻烦，因为寻路随时会结束并往机器人路径里更新移动，
> 那么就可能出现加入的避障移动被寻路结束得到的路径覆盖的问题。
> 
> 同时，因为避障算法是在主线程 RobotWork() 中执行的，寻路则在分离的子线程中执行的。将两者的结果存在同一个路径队列中，会导致每次更新避障也要访问机器人的路径，那就必须扩大上锁的范围了
> 
> 因此，在试探观察避障的实现中，将避障的移动路径与寻路的移动路径分别存在两个队列中。这种分离方式，既能避免路径覆盖的问题，又有助于缩小锁的作用范围。


## 通过整体调整规划进行避障



![CleanShot 2024-03-27 at 17.22.05.jpg](https://xuqi.space/static/img/ea7ddead3abfe03ed6274d8f8e9b5c6c.CleanShot%202024-03-27%20at%2017.22.05.webp)

如图所示，`0`号机器人与`1`号机器人的路径列表中都存放着`xyt`结构，即在`t`帧时刻，机器人将要前往的`xy`位置。根据`xyt`我们可以发现，如果`0`号机器人与`1`号机器人的路径列表中存在`xyt`都相同的节点，则说明会发生`collision`

找到了发生`collision`的位置，就可以通过插入静止帧等办法解决`collision`。


![CleanShot 2024-03-27 at 17.32.35.jpg](https://xuqi.space/static/img/9f583133e0dda1bb809825ffa3c42a8b.CleanShot%202024-03-27%20at%2017.32.35.webp)

如图所示，根据`xyt`我们可以发现，如果`0`号机器人与`1`号机器人的路径列表中存在`t对齐而xy十字交叉相同`的节点，则说明会发生`cross over`

我们可以在机器人的路径列表发生增长的时候对所有机器人的整个路径列表进行检查，查看是否存在`collision`与`cross over`的情况，并尝试解决。

这里要思考一个问题，**尝试解决`cross over`与`collision`的过程中，我们是否会引入新的`cross over`或`collision`呢？**

我个人认为，通过递归结构可以解决该问题。即，一次只尝试解决当前场面中存在的碰撞情况，尝试解决之后，立刻再次检测是否存在碰撞情况，并再次尝试解决，直到不再存在碰撞为止。

那么，感性上这么做是可行的，如何证明不断递归尝试解决碰撞，一定可以停机呢？（也即在经过有限次该过程后，场面总能达到不存在碰撞的情况）

# 关于如何保证不跳帧——Timer与WaitGroup结构
我们希望程序处理每一帧的用时尽量不超过`15ms`，即使超过了`15ms`也不能影响下一帧的信息读入与处理。

在`go`语言中有所谓的`Timer`结构，专门用于处理这种需求。

```go
type Timer struct {
    C <-chan Time
    r runtimeTimer
}

func waitChannel(conn <-chan string) bool {
    timer := time.NewTimer(1 * time.Second) //设置超时时间 1s
    
    select {
    case <- conn:
        timer.stop() // 接收到数据后，要停止计时器
        return true
    case timer.C: //超时判断
        fmt.Println("WaitChannel timeout!")
        return false
    }
}
```
在这段代码中，`Timer`结构体是由一个`channel`与一个`rutimeTimer`构成的，`rutimeTimer`由`go运行时`接管，在到达指定的超时时间后向`C`这个`channel`中放入一个值。

在`waitChannel`函数中，`select`关键字会**阻塞**尝试从`conn`与`timer.C`中取出一个值，哪个`channel`中先有值，`select`就会执行对应的`case`代码，这样就保证了即使`conn`一秒后仍然没有值被放入，`select`也可以从`timer.C`中取出值，从而保证该函数的阻塞时长不会超过`1s`。

回到这次比赛的例子上，我们就是要在`c++`中实现类似的`Timer`结构的功能。

由于我们每个机器人都要开启一个单独的线程执行，所以一共会开很多个线程，这让人想到`go`中的`WaitGroup`结构。

```go
func main() {
    var waitGroup sync.WaitGroup

    start := time.Now()
    waitGroup.Add(5)
    for i := 0; i < 5; i++ {
        go func() {
            defer waitGroup.Done()
            time.Sleep(time.Second)
            fmt.Println("done")
        }()
    }

    waitGroup.Wait()
    fmt.Println(time.Now().Sub(start).Seconds())
}
```
输出为
```txt
done
done
done
done
done
1.000306089
```
在上面的代码中，`waitGroup.Add(5)`指定了要开启协程的数量，在协程内部，调用`waitGroup.Done()`将计数器减一，当`waitGroup`的计数器小于等于`0`时，解除`waitGroup.Wait()`的阻塞。

我们将`waitGroup`与`Timer`结构结合起来。也就是让解除`waitGroup.Wait()`阻塞的条件除了计数器小于等于`0`，还要加上超过了一段时间也解除阻塞。

用`C++`代码实现如下：

```cpp
class WaitGroup {
private:
    std::mutex mtx;
    std::condition_variable cv;
    int count;
    size_t waitUntilOnMs;

public:
    WaitGroup(int initialCount, size_t waitUntil) : count(initialCount), waitUntilOnMs(waitUntil) {
    }

    void Add(int delta) {
        std::thread([this] {
            std::this_thread::sleep_for(std::chrono::milliseconds(waitUntilOnMs));
            unique_lock lock(mtx);
            count = 0;
        }).detach();
        unique_lock lock(mtx);
        count += delta;
    }

    void Done() {
        unique_lock lock(mtx);
        count -= 1;
        if (count <= 0) {
            count = 0;
            cv.notify_all();
        }
    }

    void Wait() {
        unique_lock lock(mtx);
        cv.wait(lock, [this] { return count <= 0; });
    }
};
```
可以看到，在上面的程序中，`WaitGroup`类中有一个计数器与一个计时器，当调用`Add`函数时，会开启一个线程作为计时器，当到达指定的时间时，将计数器重置为`0`，此时视为等同于调用了`Done`函数至计数器归零。

# 事件循环

整理一下整个过程中按照时间顺序的时间循环

1. 世界初始化（读入地图与泊位初始信息）
2. 利用初始化时间对地图做预处理
3. 循环🔄
4. 读入帧信息
5. 根据帧信息更新场面数据
6. 调整机器人的路径（耗时操作）
7. 更新场面统计信息
8. 判断拾取命令
9. 判断卸货命令
10. 移动命令
11. 循环🔄

# 调整机器人路径算法
## 第一次取货
由于第一次取货是从机器人的初始位置出发，去寻找货物，再送到泊位，这部分的全局最优解应该满足，机器人到货物的距离+货物到最近泊位的距离最小（这里不考虑价值是因为第一次取货必定场上货物数量少于机器人数，所以不考虑价值），满足该条件则将机器人与该货物绑定，货物进入机器人的取货列表。
## 非第一次的取货
对于非第一次取货，总是从泊位出发，到距离目标货物最近的泊位结束，因此价值函数可以是
$$
    \forall(r,g)\quad\argmax_{(r,g)}\frac{g.value}{dist(r.xy, g.xy)+closest\_berth\_dist(g)}
$$
其中$r$为机器人，$g$为货物，$g.value$为货物$g$的价值，$dist(r.xy, g.xy)$为机器人$r$到货物$g$的路径长度，$closest\_berth\_dist(g)$为货物到距其最近的泊位的距离
## 对选择 货物-机器人对 这一过程的抽象
我们发现，总是要对所有的$(r,g)$进行遍历，对某一个价值函数进行计算，最后得到使得价值函数最大的$(r,g)$对，因此对该过程抽象为一个函数。