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

赛题

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

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

  • 程序交互

    每帧信息由输入和输出传递，选手程序需要在有限的时间里进行运算，并输出结果。由于跳帧情况的存在，需要尽量保证选手程序每一帧都接收到判题题数据，保证数据同步。

  • 计算逻辑：

    因为每帧计算限时，可能涉及多线程编程

  • 寻路

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

  • 避障

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

  • 调度策略

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

可能优化思路有：

  • 利用初始化时间

    5000ms 能够做很多事情。比如用洪泛法计算所有点到某个点的路径长度等等（宝贵的打表时间）。

  • 优化机器人取货的目标

    减少总寻路的长度和总的货物拾取价值。在复赛机器人可以拾取两个货物，对路径优化合并，提出了更高的要求。

  • 船只避障

    不再使用那种朴素的避障再返回路径节点的方式，而是尝试进行新的寻路或者局部的寻路，减少船只从避障后恢复的路径长度。

  • 炼丹

    试各种参数；碰运气，刷随机种子；针对地图进行特化调参。

更多具体的算法讨论，可以参考 insomniac 的文章。

学习到了什么东西

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

  • code review

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

  • 分支版本控制

    其实是又把 Learn Git Branching 刷了一遍，试了试有源和目标参数的 pull 命令。不过实际上，比赛中版本控制也是做得虎头蛇尾。

  • UML 类图

    以前听过也看过类图，不过并不是很清楚它具体的规范，这次的初赛索性就试了试，学习了一下绘制的语法，可参考 PlantUML

  • 寻路算法

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

  • 标准错误流

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

  • 打日志的重要性

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

  • 协作中不可避免的问题

    在接近一周的比赛中，暴露了很多关于协作的问题：

    1. 没有固定的共同工作的时间与场所（除了通宵的那三个晚上我们在一起写代码），缺乏沟通。

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

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

  • 原子变量与锁

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

  • wsl 与双系统

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

  • mingw 的计时有问题

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

  • 标准库的使用

    • 容器

      • 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

有什么感想

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

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