用有限状态机实现的迷宫求解.txt

用有限状态机实现的走迷宫演示程序

用有限状态机实现的迷宫求解。


  和大部分的迷宫程序相同，迷宫的解决方法是 递归或者是用堆栈来模拟递归，这个程序也不例外。但是我们知道普通的迷宫求解程序通常是用一种递归的方法来实现的。程序从一开始运行就不断的进行递归，直到找到迷宫的出口。但是这对一个演示程序来说是不行的，我们需要演示一个迷宫行走者在迷宫中的行走过程。
      因此我们用另外的方式来实现，我们首先要需要一个状态机来记录当前行走者的状态，比如说他是处在行走还是寻找一个新的可以到达的地方的状态，因此我使用了一个有限状态机来模拟搜索者的状态的，我们只要记住行走者的状态就可以了。我们在game loop的每一次到来时刻让行走者按照给定的状态行动。根据行动的结果可以转化状态机的状态。同时也可以在任何你喜欢的时候暂停行走者的行动（在game loop里设置一个标记就可以了。）
      关于有限状态机的原理和应用请看《离散数学》。在这个程序里重要有：

      NEXT_DIR：     转动到下一个方向
      MOVE_NEXT：   运动到下一个地方
      TRACE_BACK：   回退：好难实现啊:-(
      NO_PATH：      找不到路，迷宫没有出口
      FIND_EXIT:       找到了出口

      至于本程序用于画图的是OpenGL,强烈推荐OpenGL啊，易学，易用，还附送很多
的特殊扩展哦。


以下是用于有限状态机处理的函数

int CMaze::Action()
{
        //First test the walker is want to search
        switch(_walker.is_rest)
         {
            case true:
            {
                Alert("I think I must have a rest Z...ZZ.....");
                Alert();
                return 0;
            }
        }
       switch(_walker.stauts)
        {
            case NEXT_DIR:
                    NextDir();
            break;
            case MOVE_NEXT:
                    MoveNext();
            break;
            case TRACE_BACK:
                    TraceBack();
            break;
            case NO_PATH:
                    Alert("It's so bad the maze has no exit!!");
            break;
            case FIND_EXIT:
                    Alert("Ha ha! I find the maze's exit!! Yeah!");
            break;
    }
    Alert();
    return 1;
}     

   潘李亮 2003 - 9 - 17 
   Email : [e-mail]
   QQ:     81496744