基于试探回溯策略实现的迷宫寻径算法

/*
 * Created by krislyy on 2018/11/22.
 *
 * 路径规划是人工智能的基本问题之一，要求依照约定的行进规则，在具体
 * 特定的几何空间区域内，找到从起点到终点的一条通路。考虑一个简化版本：
 * 空间区域限定为有n*n个方格组成的迷宫，除了四周的围墙，还有分布在
 * 其间的若干障碍物；只能水平或垂直移动。我们的任务是，在指定的起始
 * 格点与目标格点之间，找出一条通路（如果存在的话）。
 * */

#ifndef ALGORITHM_MAZEROUTE_H
#define ALGORITHM_MAZEROUTE_H

#include <stack>
#include <iostream>
#include <array>
#include <random>

namespace Algorithm {
    //原始可用的、在当前路径上的、所有方向均尝试后失败回溯过的、不可使用的（墙）
    typedef enum {
        AVAILABLE, ROUTE, BACKTRACKED, WALL
    } Status; //迷宫单元状态

    typedef enum {
        UNKOWN, EAST, SOUTH, WEST, NORTH, NO_WAY
    } ESWN; //单元的相对邻接方向


    //数据结构定义如下
    typedef struct Cell {
        int x, y; //坐标
        Status status; //类型
        ESWN incoming, outgoing; //进入 走出方向
        std::vector<ESWN> tryESWN; //已经尝试过的方向

        Cell(int xX, int yY, Status s = AVAILABLE):x(xX), y(yY), status(s),incoming(UNKOWN), outgoing(UNKOWN){
            tryESWN.push_back(EAST);
            tryESWN.push_back(SOUTH);
            tryESWN.push_back(WEST);
            tryESWN.push_back(NORTH);
        }
    } Cell;

    #define LABY_MAX 8 //最大迷宫尺寸
    Cell laby[LABY_MAX][LABY_MAX] = {
            Cell(0,0,WALL), Cell(0,1,WALL), Cell(0,2,WALL), Cell(0,3,WALL), Cell(0,4,WALL), Cell(0,5,WALL), Cell(0,6,WALL), Cell(0,7,WALL),
            Cell(1,0,WALL), Cell(1,1), Cell(1,2), Cell(1,3), Cell(1,4), Cell(1,5), Cell(1,6),                               Cell(1,7,WALL),
            Cell(2,0,WALL), Cell(2,1), Cell(2,2,WALL), Cell(2,3), Cell(2,4), Cell(2,5), Cell(2,6),                          Cell(2,7,WALL),
            Cell(3,0,WALL), Cell(3,1), Cell(3,2), Cell(3,3,WALL), Cell(3,4), Cell(3,5), Cell(3,6),                          Cell(3,7,WALL),
            Cell(4,0,WALL), Cell(4,1), Cell(4,2), Cell(4,3), Cell(4,4,WALL), Cell(4,5), Cell(4,6),                          Cell(4,7,WALL),
            Cell(5,0,WALL), Cell(5,1), Cell(5,2), Cell(5,3), Cell(5,4), Cell(5,5), Cell(5,6),                               Cell(5,7,WALL),
            Cell(6,0,WALL), Cell(6,1), Cell(6,2), Cell(6,3), Cell(6,4), Cell(6,5), Cell(6,6,WALL),                          Cell(6,7,WALL),
            Cell(7,0,WALL), Cell(7,1,WALL), Cell(7,2,WALL), Cell(7,3,WALL), Cell(7,4,WALL), Cell(7,5,WALL), Cell(7,6,WALL), Cell(7,7,WALL),
    }; //迷宫

    inline ESWN nextESWN(Cell* cell) {
        if (cell->tryESWN.empty())
            return NO_WAY;
        static default_random_engine e(time(nullptr));
        static uniform_int_distribution<unsigned > u(0,3);
        int next = u(e) % cell->tryESWN.size();
        ESWN tryEswn = cell->tryESWN.at(next);
        cell->tryESWN.erase(cell->tryESWN.begin() + next);
        return tryEswn; //随机转入下一个邻接方向，也可简单的实现为 ESWN(cell->outgoing + 1)
    }
    /*
     * 除了记录其位置坐标外，格点还需记录其所处状态。共有四种可能得状态：原始可用状态
     * （AVAILABLE）、在当前路径上的（ROUTE）、所有方向均尝试失败后回溯过的（BACKTRACKED）、
     * 不可穿越的（WALL）。属于当前路径的格点，还需要记录其前驱和后记格点的方向。特别的，因尚未
     * 搜索到的而仍处于AVAILABLE状态的格点，邻格得方向都是未知的（UNKNOWN）；经过回溯后处于
     * BACKTRACKED状态的格点，与邻格之间的联通关系均已经关闭，故标记为NO_WAY。
     */

    //在路径试探过程中需要反复确定当前位置的相邻格点
    inline Cell* neighbor(Cell* cell) { //查询当前位置的相邻格点
        switch (cell->outgoing) {
            case EAST:
                return cell + 1; //向东
            case SOUTH:
                return cell + LABY_MAX; //向南
            case WEST:
                return cell - 1; //向西
            case NORTH:
                return cell - LABY_MAX; //向北
            default: exit(-1);
        }
    }

    //在确认某一个相邻格点可用之后，算法将朝对应方向向前试探一步，同时路径延长
    //一个单元格。实现格点转入功能
    inline Cell* advance(Cell* cell) {
        Cell* next;
        switch (cell->outgoing) {
            case EAST:
                next = cell + 1; //向东
                next->incoming = WEST;
                break;
            case SOUTH:
                next = cell + LABY_MAX; //向南
                next->incoming = NORTH;
                break;
            case WEST:
                next = cell - 1; //向西
                next->incoming = EAST;
                break;
            case NORTH:
                next = cell - LABY_MAX; //向北
                next->incoming = SOUTH;
                break;
            default: exit(-1);
        }
        return next;
    }

    inline void printRoute(std::stack<Cell*> &path) {
        while (!path.empty()) {
            Cell* cell = path.top();
            std::cout << "{ x:" << cell->x << " y:"<< cell->y
                      << " out:" << cell->outgoing << " status:" << cell->status
                      << "}";
            path.pop();
            if (!path.empty())
                cout << " <- ";
        }
        cout << endl;
    }

    //基于试探回溯策略实现的寻径算法，在格单元s至t之间规划一条通路（如果存在的话）
    bool labyrinth(Cell Laby[LABY_MAX][LABY_MAX], Cell* s, Cell* t) {
        if (s->status != AVAILABLE || t->status != AVAILABLE)
            return false; //退化情况
        std::stack<Cell*> path;  //用栈标记通路，所谓Theseus手上的线绳
        s->incoming = UNKOWN;
        s->status = ROUTE;
        path.push(s); //起点
        //从起点开始不断试探、回溯，直到抵达终点，或者穷尽所有可能
        do {
            Cell* c = path.top();  //检查当前位置，栈顶
            //若已抵达终点，则找到了一条通路；否则，沿着尚未试探的方向继续试探
            if (c == t) {
                printRoute(path);
                return true;
            }
            //检查所有方向，试图找到未试探的方向
            while ((c->outgoing = nextESWN(c)) < NO_WAY) {
                if (AVAILABLE == neighbor(c)->status)
                    break;
            }
            if (c->outgoing >= NO_WAY) { //若所有方向都尝试过，则回溯一步
                c->status = BACKTRACKED;
                c = path.top();
                path.pop();
            } else { //否则，向前试探一步
                c = advance(c);
                path.push(c);
                c->outgoing = UNKOWN;
                c->status = ROUTE;
            }
        }while (!path.empty());
        return false;
    }
}

#endif //ALGORITHM_MAZEROUTE_H

测试代码

Cell* s = &laby[1][1]; //入口
Cell* t = &laby[6][5]; //目标
labyrinth(laby, s, t);