用有限状态机实现的迷宫求解-UML软件工程组织-火龙果软件

UML软件工程组织

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

作者：潘李亮来源：gameres

和大部分的迷宫程序相同，迷宫的解决方法是递归或者是用堆栈来模拟递归，这个程序也不例外。但是我们知道普通的迷宫求解程序通常是用一种递归的方法来实现的。程序从一开始运行就不断的进行递归，直到找到迷宫的出口。但是这对一个演示程序来说是不行的，我们需要演示一个迷宫行走者在迷宫中的行走过程。

因此我们用另外的方式来实现，我们首先要需要一个状态机来记录当前行走者的状态，比如说他是处在行走还是寻找一个新的可以到达的地方的状态，因此我使用了一个有限状态机来模拟搜索者的状态的，我们只要记住行走者的状态就可以了。我们在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;
}

下载配套程式