带有记忆功能的迷宫算法分析

图6-8 在迷宫中的竞赛机器人

竞赛机器人有了记忆功能，才能表现出智能。

1.迷宫的状况

设在迷宫中的竞赛机器人如图6-8所示，竞赛机器人具有三个方向的传感器：前方传感器F、左方传感器L、右方传感器R。如果前方有隔栅，则传感器来的信号为“1”，无隔栅则为“0”。竞赛机器人在迷宫中运动时，三个传感器F、L、R会传来迷宫的8种状况，即111、110、101、100、011、010、001、000，如图6-9所示。即死胡同111、右转弯110、左转弯101、直丁字路口100、直路011、右丁字路口010、左丁字路口001、十字路口000。

图6-9 迷宫的8种状况

2.记忆迷宫的状态寄存器

设可位操作的路况寄存器road_flag用来记忆迷宫的路况，每遇到变化的分叉的路况，置road_flag.0=1或0，且左移一位，把路况保存起来。“1”表示可前进，“0”表示可右转（对于十字路口，右转优先），如图6-10所示。

设死胡同寄存器dead_flag用来记忆遇到的死胡同。每遇到一个死胡同，置dead_flag.0=1，且左移一位。

设转向寄存器turn_flag用来记忆竞赛机器人的向左转或向右转的操作状态，如图6-11所示。

图6-10 可位操作的路况寄存器road_flag

图6-11 转向寄存器turn_flag

3.迷宫问题的分析

一般的迷宫有上面的8种状况，当竞赛机器人遇到这8种状况时，做出正确的选择才能走出迷宫。下面具体来研究竞赛机器人遇到这8种状况时应采取的措施。

（1）死胡同111状况 当竞赛机器人遇到死胡同111状况时，应采取的处理方法是：原地180°调头，同时置死胡同标志，如图6-12所示，由state_111（）函数实现。

（2）右转弯110状况 当竞赛机器人遇到右转弯110状况时，应采取的处理方法是：原地右转90°前进，如图6-13所示，由state_110（）函数实现。

图6-12 死胡同111状况

图6-13 右转弯110状况

（3）左转弯101状况 当竞赛机器人遇到左转弯101状况时，应采取的处理方法是：原地左转90°前进，如图6-14所示，由state_101（）函数实现。(www.xing528.com)

（4）直路011状态 当竞赛机器人处于直路011状态时，应采取的处理方法是：继续保持前进，由state_011（）函数实现。

（5）十字路口000状态 当竞赛机器人遇到十字路口000状态时，应采取的处理方法是：向右转90°前进，如图6-15所示，由state_000（）函数实现。

图6-14 左转弯101状况

图6-15 十字路口000状况

（6）直丁字路口100状态 当竞赛机器人遇到直丁字路口100状态时，如图6-16所示。应采取的处理方法的程序框图如图6-17所示，由state_100（）函数实现。

图6-16 遇到直丁字路口100状况

图6-17 遇到直丁字路口100状况时的程序框图

（7）右丁字路口010状态 当竞赛机器人遇到右丁字路口010状态时，如图6-18所示。应采取的处理方法的程序框图如图6-19所示，由state_010（）函数实现。

图6-18 丁字路口状况

图6-19 遇到右丁字路口010状况时的程序框图

（8）左丁字路口001状态 当竞赛机器人遇到左丁字路口001状态时，如图6-18b所示。应采取的处理方法的程序框图如图6-20所示，由state_001（）函数实现。

图6-20 遇到左丁字路口001状况时的程序框图

4.迷宫问题的解决

竞赛机器人在遇到每种分叉口状况时，记忆路况，转向。当遇到死胡同时返回，当返回时遇到刚才的分叉口时，根据上次的转向，决定当前的运动，或前进或左转或右转。其程序框图如图6-21所示。

图6-21 具有记忆功能的迷宫程序框图