华为 2023 软件精英挑战赛，通用算法，京津冀东北赛区，初赛第 3 名，复赛第 6 名。

目录

路径	解释
src	c++源代码，上传文件目录
Robot	判题器&播放器&replay 存档&官方示例
build	cmake 缓存&可执行文件目录
doc	文档

运行方式

> cd build
> cmake ../src
> make

程序不需要读/写文件，使用标准输入输出里交互。

判题器使用：

Robot -m <地图> <可执行文件>

代码思路

• src/iointerface.h: 读取地图、每一帧的机器人状态；输出每一帧的机器人指令。机器人的控制指令出存在iointerface.h中的std::vector<io::Instruction *> instructions全局变量中。
• src/model.h: 机器人的和地图的数据结构。这些数据需要全局共享，也设置为了全局变量。
• src/find_path_squre.h: 寻路算法的实现。直接 bfs 遍历地图的正方形块。（改为 A*会更合适，当时比赛时瓶颈不在这里，因此没动）
• src/nav_model.h、src/nav_navigate.h: 导航模型的实现。根据当前机器人的状态，以及地图以及机器人的目标状态，计算机器人的下一步指令。
• src/route_stupid.h: 机器人的调度策略。
• src/const.h: 题目给定的一些常量和测试模拟器得到的常量，主要为一些物理量和地图的大小、起始资金。
• src/args.h: 可以调整的程序参数，例如一下奖励/惩罚系数，移动时的误差修正等。

核心调用

int main()
{
    io::init(std::cin);
    trans_map::init();
    route_stupid::init();
    puts("[info] init OK");
    fflush(stdout);
    // 主循环，15ms 一帧
    while (std::cin.eof() == false)
    {
        io::read_flame(std::cin);
        route_stupid::give_pointing();
        io::print_instructions(io::instructions, std::cout, meta.current_flame);
    }
}

void give_pointing()
{
    // 寻路
    find_path();
    // 解决碰撞问题
    process_anticollision_2();
    // 移动
    mvoe_to();
}

vector<Vertex> find_path(const Vertex &_start, const Vertex &_target, bool _have_good)
{
    const auto &ori_path = get_ori_path();
    const auto &smooth_path = get_smooth_path(ori_path);
    return smooth_path;
}

give_pointing 中，根据机器人的状态（1. 是否空闲； 2. 是否到达目标点（前往买货点/前往卸货点）； 3. 是否持有货物...），计算机器人的下一步目的地。确定目的地后，判断是否存在机器人碰撞问题，并对目的地做临时调整。调整后调用 nav_navigate::move_to 生成机器人的下一步指令。

调度策略

核心在于计算收益率（预期利润/预期花费时间），并根据收益率排序。在给出指令时，根据机器人的状态，选择最高收益率的任务。

由于高级别的货物价值更改，因此为了激励较多地合成高级别货物，在计算预期利润时，对于高级货物缺少的原材料，给予一定的补偿。例如，如果合成货物 4 需要 1、2、3，此时工厂 A 已经具备了 1、2，那么此时运送 3 的收益率会更高。

机器人的预期花费时间使用机器人到买货点、再到卸货点到最短距离之和，叠加一部分固定的误差开销来计算。

寻路策略

在预处理时，使用并查集处理所有存在供应关系的节点之间的最短路径。在寻路时可以直接使用这些最短路径。寻路算法使用 bfs，每次遍历一个正方形区域。在躲避障碍物上，根据地图预先处理出所有会发生碰撞的区域。如果机器人的路径经过了这些 dangerious line ，则判断为不能通过。

最终得到的路径是一个点的序列，再使用一些简单的策略，比如在很长的路径上插入一些点，删去接近直线的点，使得机器人的路径更加平滑。

机器人防碰撞策略

这一部分为比赛时分数的最大瓶颈，做得很不好。

一个简单的策略是预测到机器人将在接下来的几秒内碰撞，则挑选编号较小的机器人使用 find_shelter_path 寻找可以躲避的点。如果在一定距离内找不到躲避点，则顺着编号较大的机器人的路径后退，直到下一帧找到躲避点。

机器人控制

基于物理模型进行计算即可，机器人可以控制的状态包括旋转速度和前进速度。改状态是一个目标值，更改后机器人会最大加速度和最大角加速度达到目标值。这一块只要实现根据距离计算好最有的速度即可。需要注意到是，模拟器的控制是离散的，为了尽量避免碰撞，在接近目标点时需要以较低的速度接近。

其他逻辑

除此以外，还有一些零碎的策略。

1. 如果剩下的时间较少时，为了防止机器人在最后时刻持有未卖出的货物，在调度时对任务花费的时间增加一个惩罚项。
2. 对于无法获得任务的机器人，将其移动到地图的边缘并静止，以减少碰撞的可能性。
3. 对于一些特殊的位置，比如只能以某个特定角度才能通过的狭窄的门，提前预处理出这些门的中心，在路径经过时调整机器人的角度。
4. 机器人控制上，如果到达目标点 a 后下一步的目标点 b 已经确定，可以提前控制机器人的角度，来减少机器人的转向时间。