null
距离2023年华为软挑赛落幕已经过去一年有余，本来是没复盘打算的，但是本人即将找工作，得把之前做过的项目回顾一遍，所以就简单写一下吧。
初赛
这次比赛的任务简单来说就是控制场上的4个机器人在工作台之间购买和售卖货物。涉及到两个核心任务：当前机器人去哪一个工作台购买或售卖；确定目的地后如何移动过去。
去哪一个工作台售卖
如果当前机器人持有某个物品，首先遍历所有工作台，如果某个工作台能够买自己的物品并且能够在剩余时间内到达这个工作台，就将这个机器人加入候选名单，最终要根据卖给某个工作台的收益和到达这个工作台的时间综合来计算，此外如果某个工作台只差当前机器人持有的物品就能开工，要给这个工作台较大的价值。另外，有些工作台只吃不生产，这种工作台的权重应该降低。
另外就是如果刚好到达一个工作台的话，这个工作台刚好能买自己的商品，直接售卖。
去哪一个工作台购买
如果当前机器人刚售卖完一个物品，此时需要寻找下一个卖家。买某个物品，首先仍然要考虑买入之后再卖出的时间需要综合考虑这个物品带来的收益、距离和当前场上最缺哪一种物品，以及这个商品的价值。比赛特意给了9号工作台能吃下所有物品，所以不会出现卖不出去的现象。
某一帧确定完买某个工作台的物品，就可以确定要卖给哪一个工作台。
目前的算法是一个工作台一次只能被一个机器人选择，但是有一种情况是，在机器人做选择的时候某个工作台不能选，但是如果机器人去这个不能选的工作台，由于路上耗时到达时候又能选了。我尝试实现过这样的算法，不过机器人到达某个工作台的时间比较难以估算，而且场上的工作台状态经常变化，一个机器人的选择会影响到另一个机器人的选择，实现起来太麻烦了，就没写。
（当时写了一个挺复杂的逻辑，现在我自己都有点看不懂了，不过大致是这个逻辑）
如何移动
机器人有半径，有质量，加速减速需要时间，会发生碰撞，并且碰撞之后物品价值有损失，所以理想的移动方式是避免碰撞且耗时少。碰撞尤其要控制好，因为有可能两个机器人在同一条直线上相向移动，到最后二者谁也不让谁直接停住。初赛的情况下没有任何障碍物，所以机器人直接直线移动就好。
机器人有线速度和角速度两个维度，根据机器人线速度和目标的夹角，分为几种情况：夹角非常小，直接全速移动，角速度为0；夹角比较小，保持较小角速度和较大线速度；夹角很大，角速度最大，线速度置0。如果机器人快要到达目的地或者快要撞墙时，要及时减速。
如何检测和避免碰撞：计算两个机器人的相对速度和相对位移（就是物理中的那两个矢量），理想情况还要考虑角速度，但是奈何本人不会。判断出来两个机器人会发生碰撞，那就确定要旋转的方向。存在二者相向碰撞和相对碰撞两种情况，一定要判断好到底是向左转还是向右转，避免旋转之后二者反而会加速碰撞。判断方向时候还要避免一个机器人避让后撞墙。
避免碰撞只适用于两个机器人，如果2个以上要发生碰撞，只能看运气了。
初赛总结
初赛勉勉强强是进了复赛，给我的感觉是机器人的售卖和购买策略都是次要的，移动策略才是最重要的，别人得分高的算法机器人移动都是又快又能避免碰撞。这方面我一直没找到好的算法。好在复赛已经不看重这个了。
复赛
复赛难度陡升，在场中加入了障碍物，所以此时机器人不能按照直线移动了，需要运用寻路算法找到可行路径。
寻路
首先是复赛的建模，由于机器人的半径在0.5米上下浮动，所以需要对地图以0.5米为单位划分网格（初赛是不需要的）。有一点需要注意，对于一个2×2的网格，机器人在没有携带物品时是可以放下的，但是携带物品的情况下是放不下的，所以有没有携带物品在寻路时寻找出来的路径也不一定一样。
寻路算法我使用了A算法，A\算法找出来的路径是不是直线，是弯弯曲曲的，所以找出来之后还需要对路径做一次优化。例如要找到起点的下一个目标位置，从路径的最后一个节点开始倒序遍历，找到第一个能直接从起点到达的节点，把这个节点当做起点的下一个目标位置，删除起点到这个节点之间的所有节点，用这个节点替换起点按照相同的算法找下一个节点。
可以看到这个寻路算法复杂度还是有点高的，A*本来搜一遍就很慢了，还要对路径进行优化，所以这个寻路算法后期成为我提升性能的瓶颈了，最好情况是每一帧搜一次，但是这个寻路算法一帧根本运行不完，所以只能降而求其次，每次要卖出某个物品或者买入某个物品的时候再确定路径。
一般机器人都是从某个工作台到达另外一个工作台，没意外的情况下路径都是固定的，所以在初始化的时候先一次计算出所有可能的路径。
避障
因为有障碍物的存在，所以之前避障的方法不奏效了。如果一个机器人要避障另外一个机器人，把另一个机器人的路径上的所有点都作为障碍物，找出来一条避障的路径。直接把路径的所有点都作为障碍物可能会找不出来一条可行路径，如果某个点当前机器人比另外一个机器人先到达，那当前机器人是不会阻碍另外一个机器人的行进的，这种情况需要考虑到。如何判断避障完成呢，我的做法是计算当前机器人到达另外一个机器人路径的最小距离，以及对方机器人0.1s后大约走过的距离，如果前者比后者大，说明对方机器人已经走了，避障完成。避障完成之后，就找一条新的路径。另外，快要避障完成时，当前机器人可以向着预定方向先转向。
确定避障方：根据某个机器人是否携带物品，携带的物品价值大小等等判断。
决赛
决赛升级为对抗赛了，两方在同一个场地行进，此时就涉及到策略选择了。判断
复赛的寻路算法写的太复杂了，线上评测的时候经常内存不够程序爆掉，而且也不完善，有些特殊情况还会失效。所以我决赛的时候没想着先写策略，我想着先把寻路、机器人行进方法这些先做好，导致我很长一段时间都没有什么进展。
策略是我临近决赛前一天晚上刚写好的，之前一段时间因为做的改进一直没有什么正反馈，心情不是很好，心情不好就没有什么创造力。策略的话：找出来一个机器人当做干扰机器人，这个干扰机器人去占住对方的重要工作台，让对方卖不出去或买不到；同时这个干扰机器人还可以去撞对方的机器人，干扰对方的正常行进，这个非常依赖己方的行进方法。
……
