# codecraft2024

**Repository Path**: Holypumpkin/codecraft2024

## Basic Information

- **Project Name**: codecraft2024
- **Description**: codecraft2024
- **Primary Language**: C++
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-06-15
- **Last Updated**: 2024-06-15

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 一、概要设计

## 1. 机器人取物品

地图上随机生成物品，存在时间为1000帧（20s）。

- 机器人优先寻找离自己最近的物品，可以先选取一定松弛范围内的物品，以便提供多种选择。（待优化：考虑物品价值、范围内的障碍、扫描方法）
- 物品筛选。根据物品的坐标粗略判断机器人到达时，物品是否会消失。
- 给物品上锁。当一个物品被一个机器人占有时，其他机器人无法占有。
- 进行取物**路径规划**。
- 出发取物品，需要插入**碰撞处理**。

## 2. 机器人送物品

- 机器人优先寻找离自己最近的泊口，可以先选取一定松弛范围内的泊口，以便提供多种选择。

- 泊口筛选。泊口需要有剩余容量，否则可能白跑一趟。（待优化：泊口装载速度不一样）

  > 可以给每个泊口设计一个消息队列，用于判断泊口的预期容量，方便轮船调度。由于船的容量固定，消息队列的容量大小设为船的容量即可。当机器人选中一个泊口时，将其插入泊口的消息队列。泊口只需按消息队列为机器人提供服务即可。（待优化：消息队列可以时间片轮转防止饥饿）

- 进行送物**路径规划**。

- 出发送物品，需要插入**碰撞处理**。

- 记录路径。机器人有10个，初步记录10条。

## 3. 轮船调度

初赛无需考虑轮船去虚拟点、泊口的路径和碰撞处理。

* 泊口叫船。优先根据泊口的容量大小叫船，当一个泊口预期载货量较大时，优先把船调度到该泊口。
* 调船时，首先轮船不应处于送货状态，且轮船不应被其他泊口占有。在此基础上优先选取到达当前港口时间最短的。
* 船装满就出发。可以设置一定松弛容量。

## 4. 指令生成

* 生成机器人指令
* 生成轮船指令

# 二、关键模块

## 路径规划

初步采用Dijsktra算法进行路径规划。

> 由于泊口点固定，因此在“机器人送物品”的路径规划中，应当加入记录路径判断。

路径规划应当优先解决机器人与墙体的碰撞，机器人之间的碰撞可以交给“碰撞处理”模块解决。

## 碰撞处理

发生碰撞后机器人该帧操作会失效，并且会被惩罚20帧（400ms）。

### 1 碰撞检测

初步只考虑下一帧机器人的移动位置是否会产生碰撞。

由于10个机器人，可能会产生10次移动操作，对应的就可能产生10个目标点。

只需检测产生的10个坐标点是否有重合即可。

### 2 碰撞避免

碰撞避免应该分为”服务竞争“和”路径竞争“

（1）服务竞争：机器人为了**拿到物品**或者为了到泊口**放置物品**产生的碰撞。

* 取物：一个物品可能被多个机器人选中。则按最近最先原则分配给机器人，分配之后，其他机器人无法选中。
* 放物：主要依赖于泊口的等待队列实现。

（2）路径竞争：机器人移动过程中路径产生交叉而产生碰撞。

* 对于可能产生碰撞的目标点，碰撞的机器人个数范围为[2, 4]。
* 对于每个机器人同时顺时针旋转90度，改变其方向，可以形成一个环形，从而避免碰撞。
* 如果道路狭窄无法实现机器人顺时针旋转（例如，有的泊口很长一段路只允许一个机器人进入），分为以下情况：
  * 一个机器人可以转。证明该机器人有一定的自由空间，可以让该机器人旋转；另一个机器人保持不动。
  * 两个都不可以转。可以改变其中一个机器人方向，让两个机器人先同向运行，直至一个机器人出现自由度，从而转化为上述情况。（**TODO:** 如何确定同向运行的方向？）
    * 泊口堵塞
    * 出口堵塞
    * 中途堵塞

# 三、详细设计

## 全局变量

* n
* N
* robot_num
* berth_num
* boat_num
* money
* frame_id

## 结构体

* Point

* Boat
  * capacity
  * pos
  * status

* Berth
  * x,y
  * transport_time
  * loading_time

* Robot
  * x,y
  * is_carry
  * status

* Good
  * x,y
  * ttl
  * val

## 类

* PlanPath
* MakeDecision
* DetectCollision
* IOProcessor
  * void InitData(map, berths, boats)
  * void InputFrameData(frame_id, money, goods, robots, boats)
  * ReadMapFromFile(file_path, map)
  * OutputMap(map)
  * OutputCommand(robot_cmd, boat_cmd)