智能小车走迷宫是一种很有趣的学习编程的方法，我也是通过这种方法初步学习了C语言编程。价位低的小车及传感器组合，会给程序设计带来无尽的烦恼。（因为这个因素，我的小车并没能走出迷宫，更不要提优化路线等后续了。）因为是初学者，对编程不熟悉，所以无从判定是硬件的问题还是程序的问题，非常浪费精力。而质量过硬的硬件，价格自然不便宜，而且学习过后似乎也没有更多的用处。那么有没有其他的方法来学习解迷宫这个智能小车问题呢？我想Scratch图形编程软件是个很好的方法。顺便说两句这个软件是针对青少年和无编程基础的人，正好适合我这样对机器人，编程，编游戏的爱好者。

 

http://s2/small/001nKwlmzy6XpbMcf2pd1&690

画的时候要是这个朝向，前进才能是前进方向。

 

我也是第一次用这个软件，所以也不知道从软件的能力上能不能实现一些想法，所以就从简单的目标开始。然后根据需要不断完善。

和现实世界一样，首先要让小车动起来。在现实世界需要小车的构架，电池，电机驱动，控制这些硬件。还需要编制控制电机转动的程序。在Scratch里，我们就只需要让他前进多少步就好了。当然和现实一样，这样的小车只会一条路走到黑，劣质的小车估计还会严重跑偏。

所以我们就需要第二个道具了，跑道。现实世界你的找很多纸才能拼凑出一块比较像样的场地，在软件里你就可以随意绘制了。当然我们玩的是解谜宫的小车，也必须有一些规范，比如必须是直道，不能有封闭的环路。只要注意这两点就可以了。而小车只需要走直线，转90°和180°方向。

第一步，当然是沿直线行走。假定是一部完美的小车，在现实中我们只需要一个传感器，当它侦测到黑就让电机开始移动，侦测到白就停机。这当然很简单当它走到路的尽头，自然就停止了。软件里更简单，我们用颜色碰撞功能就能实现，当设定的颜色碰到路线的黑色，就开始移动碰白就停止。

 

那么问题来了，碰到路口怎么办？

 

http://s16/bmiddle/001nKwlmzy6XpiFP3I32f&690

分析一下我们会碰到那几种路口呢？

很明显有这么几种，左转，右转，十字路口，T字路口，还有直行+左转，直行+右转，掉头路，终点这八种路口。要想走到终点，在每个路口肯定要有不同的处理方法。这个方法就叫做左手（右手）法则，简单说就是一直摸着一边的墙走，摸那边就叫什么法则，看个人喜好。我喜欢用左手。单纯的左右转不用说了，除了驱动的那个色块碰黑，那侧的另外两个色块也碰黑就往那侧转90°。当然还有一些细节设计才可以转到位，可以边看边改进。终点，十字路口和T字路口色块碰撞的模式是一样的，那么要怎么区分呢！那就是当一排5个传感器都碰到黑以后突进一个距离再次检测，如果中间的碰到黑周围是白那么就是十字路口，左手法则下最左转。如果所有的都碰到白，那么就是T字路口，左转。如果碰到全是黑那么就是终点。直行+左转那就左转，直行+右转在左手法则里就直行。判定方法同上。经过简单的编程（Scratch图形编程很简单多实验几次就能基本搞懂）小车就能顺利找到终点了。要是简单走出迷宫，只要每个路口都转对方向就可以了。但是要想优化路线，那就一定要判断出每个路口的具体类型。

 

这个版本的小车很不稳定，经常有脱离路线的情况，还可以看到我的掉头路用了红色点，因为我程序编制不好，掉头总是做不好，就变通用红点专门来识别。很明显这将给地图绘制带来非常大的麻烦。所以新的需求来了，如何去掉画红点的步骤，如何找路线更稳定？那么通过这种新的需要或者说解决问题，程序就得到了进步。

 

http://s8/small/001nKwlmzy6XpkQc0E7d7&690

和现实中一样，传感器的位置、形状、功能会严重影响程序的实现和完成的精确度。方形接触色块明显比圆形的稳定，单独设置驱动小车的色块还有纠偏的色块。实际中相当于测速码盘，功能就是确保小车走在黑线上并尽量保持在中心位置走直线。和现实中一样，这些色块的设置需要精细调整。通过这些改进，小车可以非常稳定的找到迷宫的终点了。当你的小车99%成功找到终点的时候，你就可以开始进行线路优化的程序设计了。如果这一步不做扎实，那么后续工作将会不胜其烦......

 

进化

 

那么如何才能实现对路线的优化呢？我们知道用左手法则走长的迷宫，那么用右手法则就一定短。那么我定义两个变量A，B，还有里程。将左手和右手的里程分别记录再比较AB的大小，那么不就能优化出一个更短的路线了吗。

http://s11/mw690/001nKwlmzy6XpaTqmimea&690

迷宫全图

 http://s8/mw690/001nKwlmzy6XpuCVsxx27&690

A路线（左手法则）
http://s3/mw690/001nKwlmzy6XpuYDRbs22&690

B（右手法则）重绘。图中粗细不等的部分是纠偏的色块发挥作用的结果。实际上用正常速度是完美重绘，这是用了加速模式（便于调试程序）才会出现的情况。

http://s6/mw690/001nKwlmzy6XpvBuz7Tb5&690


这个B比A短一些，明显小车还是会走冤枉路。如果我用和上次法则不同的法则再次处理一次路线那么一定就可以去掉冤枉路了。道理很简单实现起来就比较难了，反正对我这种门外汉是这样的。为了实现这个新目标就需要记录下每一段里程，和每一个转角。这样才能重绘A路线，并用不同的法则从新走一遍。琢磨了很久都解决不了，直道发现了链表这个东西。

http://s9/mw690/001nKwlmzy6Xpy7FHrG08&690

链表这个东西可以按一定的顺序记录很多数据，并被从新读取出来。那么只需要将A路线的数据以坐标形式记录下来，那就可以重新绘制了。然后在重绘的地图上再次寻找最短路线，那就能得到最优结果了。重走后再将最终路线画到原图上。并显示最佳路线的长度。

http://s13/mw690/001nKwlmzy6Xpno6NDS9c&690

在不断发现问题解决问题的过程中也就慢慢学会软件，了解解决迷宫所需要的知识和放法。完成这些基本目标后，还可以继续玩耍，比如让小车可以自动定位，设置一些操作按钮，加上一些对话，设置关卡等等，让它成为一个完整的游戏。

最终目标

以上的方法，可以找到最佳路线，而且实现比较简单。但是我们是为了模拟真实小车来练习编程的。现实里显然不能让小车找张白纸从新画图再走一遍然后搬家到迷宫再走一遍。能不能直接通过第一次走迷宫得到的数据，直接计算而得出最终结果呢？肯定是行的。但是这种高大上的效果，对我这样的门外汉来说肯定不简单。不简单所以才好玩，就自己琢磨吧。毕竟这是图形编程，相对简单，还是有成功的希望的。折腾之中链表的用法也熟练了，以前每个数据都做一个表，看起来用起来都麻烦。现在相关数据都记录在一个表里，有点像串口数据那个感觉。通过计算优化出路线大概折腾了1,2天，方法就是记录坐标，根据坐标走过的次数再加上坐标的路口类型，判定取舍。路线有了，但是小车是有朝向的，如何让它能在正确的路口，做出正确的动作可真是费了劲了。其实就是一点要考虑到所有可能性，而这些可能性在人的直觉中往往是被忽略的。总之一点点调试吧！中间甚至全盘推翻。几乎用了一周总算是让这个目的达到了！可能我的算法比较笨吧，程序要运行好久才能出结果！不过看着小车完美的画出红色最短路线，各种数据在屏幕上跳动，那种成就感是无可替代的。

http://s8/mw690/001nKwlmzy6XvFa5PdZc7&690
加强娱乐性，增加了迷雾，避免一下看穿迷宫。
http://s4/mw690/001nKwlmzy6XRxVXs0Hf3&690