2023光电大赛

2023光电大赛迷宫图像识别 + 路径规划代码

当时有人找我说可以一起做这个比赛，我也就试着写了一下代码，写出来测试了一下貌似没啥问题，但是因为没有经过实际比赛的测试，所以还是可能存在很多实际测试之后才能发现的潜在问题。

后来因为种种原因没有参赛，想来也是非常非常非常遗憾。一直有一个”从代码到实物”的梦想，从大二的智能车大赛到大三的光电大赛，总因为一些奇怪的原因，做好的东西没有派上任何用场，我甚至一次都没看到过它们在实际的小车上运行是什么样子。现在看起来在大学阶段没办法实现这个梦想了。（或许大四还有可能？？）

今天想起来这个事情，就把代码发出来了，虽然感觉没啥技术含量，而且因为是做思路验证所以代码也比较潦草，但是可能也可以为后面比我更小白的同学提供一些帮助。也欢迎大家交流问题。

因为做的时候才四月份，对赛题的具体明细还不太清楚，所以并没有区分敌我宝藏。

另外宝藏的坐标识别当时也没做，这个应该很好完成，目前宝藏位置是写死在cpp里的：

    maze.treasures[0] = maze.enterPoint;
    maze.treasures[MAX_NUM_OF_TREASURE+1] = maze.exitPoint;
    maze.treasures[1] = make_pair(1, 1);
    maze.treasures[2] = make_pair(7, 2);
    maze.treasures[3] = make_pair(1, 4);
    maze.treasures[4] = make_pair(8, 5);

另外可能还有一些测试阶段的assert在实际使用时可能并不适用，还需要一些进一步修改。

文件说明

read-map

读取map图像的python-opencv实现，会将迷宫进行编码并输出一堆东西（迷宫中所有墙壁的离散化坐标），这堆东西作为get-road的输入。

还没有写图像预处理、宝藏位置识别。

get-road

在获取到read-map的输入后，进行路径规划。这一步没有输出，需要自行补充输出代码。结果会储存在travel-path当中。

输入的最后必须另起一行加上-1 -1 -1 -1并回车才会开始计算。

方案

关键思路

对图像进行预处理（逆透视变换）后，得到一个标准的迷宫（如上图），每个格子都是方方正正的，面积大致一致。

考虑迷宫中每条线段的意义，它表示该竖线两侧的格子中间有挡板，不可直接到达。因此只需读取出图片中所有的挡板（LSD算法），即可把这个迷宫表示出来，用于后续的路径规划。

进行路径规划时，需要先将入口、出口、每个宝藏的位置记录下来，他们都被视作地图上的节点。对每个节点运行bfs，找到每个节点到其他所有节点的最短路径（要记录路径长度与路径），得到一张无向完全图。

然后对这张无向完全图进行暴力搜索（复杂度n!，完全可以满足10个节点以下的任务，比赛中节点数量小于10，无需优化），获得从出口开始，到出口结束，中间经过每个宝藏的最短路径。

图像部分

1. 将图像转换到LAB色彩空间，通过阈值化处理，获得仅有蓝色、红色的图像，在此图像上运行opencv的矩形查找算法，获得地图的左下角、右上角坐标。这为后面读取地图建立了一个相对坐标系。
2. 裁切图片，仅保留迷宫内部线条。
3. 将图片转为灰度图，并进行二值化处理，获得只剩迷宫内部墙壁线条的图片。
4. 运行opencv LSD算法（查了一些资料发现这个LSD最适用，经过测试效果非常好，完全没有必要通过寻找轮廓的方式来进行识别），通过线段的坐标，判断其属于哪些格子之间的墙壁，输出该竖线两侧格子的相对整数坐标（每次输出一对，先输出该直线一端第一个格子的x y坐标，然后输出对应的另一侧格子的x y坐标。如果该直线的长度大于一个格子的长度，则继续读取下一组格子，直到走到直线尽头）。

寻路部分

1. 用一个bool型矩阵maze[M][N]来表示迷宫，a[i][j]表示第i-1行j-1列的格子与i行j列的格子之间是否有墙壁。初始化一个没有任何墙壁（所有元素为false）的迷宫。
2. 通过图像部分的输入，向maze[M][N]对应位置插入墙壁。
3. 从每个宝藏的坐标出发，运行bfs广度优先搜索算法，建立一个带边权的图，记录每个宝藏到其他所有宝藏以及入口、出口的距离和路线（用list头插回溯记录最佳位置）。
4. 在上一步得到的图上进行暴力搜索（复杂度n!，节点数小于10个没有任何问题，不用担心性能问题），找到一条，起点是入口，终点是出口的，遍历每个节点的最佳访问次序。
5. 获得了最佳访问次序后，只需依次读取每个节点到下一个节点的路线，即可输出最佳路线。