/*
 * Created by krislyy on 2018/11/22.
 *
 * 路徑規(guī)劃是人工智能的基本問題之一，要求依照約定的行進(jìn)規(guī)則，在具體
 * 特定的幾何空間區(qū)域內(nèi)，找到從起點到終點的一條通路。考慮一個簡化版本：
 * 空間區(qū)域限定為有n*n個方格組成的迷宮，除了四周的圍墻，還有分布在
 * 其間的若干障礙物；只能水平或垂直移動。我們的任務(wù)是，在指定的起始
 * 格點與目標(biāo)格點之間，找出一條通路（如果存在的話）。
 * */

#ifndef ALGORITHM_MAZEROUTE_H
#define ALGORITHM_MAZEROUTE_H

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

namespace Algorithm {
    //原始可用的、在當(dāng)前路徑上的、所有方向均嘗試后失敗回溯過的、不可使用的（墻）
    typedef enum {
        AVAILABLE, ROUTE, BACKTRACKED, WALL
    } Status; //迷宮單元狀態(tài)

    typedef enum {
        UNKOWN, EAST, SOUTH, WEST, NORTH, NO_WAY
    } ESWN; //單元的相對鄰接方向


    //數(shù)據(jù)結(jié)構(gòu)定義如下
    typedef struct Cell {
        int x, y; //坐標(biāo)
        Status status; //類型
        ESWN incoming, outgoing; //進(jìn)入 走出方向
        std::vector<ESWN> tryESWN; //已經(jīng)嘗試過的方向

        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; //隨機轉(zhuǎn)入下一個鄰接方向，也可簡單的實現(xiàn)為 ESWN(cell->outgoing + 1)
    }
    /*
     * 除了記錄其位置坐標(biāo)外，格點還需記錄其所處狀態(tài)。共有四種可能得狀態(tài)：原始可用狀態(tài)
     * （AVAILABLE）、在當(dāng)前路徑上的（ROUTE）、所有方向均嘗試失敗后回溯過的（BACKTRACKED）、
     * 不可穿越的（WALL）。屬于當(dāng)前路徑的格點，還需要記錄其前驅(qū)和后記格點的方向。特別的，因尚未
     * 搜索到的而仍處于AVAILABLE狀態(tài)的格點，鄰格得方向都是未知的（UNKNOWN）；經(jīng)過回溯后處于
     * BACKTRACKED狀態(tài)的格點，與鄰格之間的聯(lián)通關(guān)系均已經(jīng)關(guān)閉，故標(biāo)記為NO_WAY。
     */

    //在路徑試探過程中需要反復(fù)確定當(dāng)前位置的相鄰格點
    inline Cell* neighbor(Cell* cell) { //查詢當(dāng)前位置的相鄰格點
        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);
        }
    }

    //在確認(rèn)某一個相鄰格點可用之后，算法將朝對應(yīng)方向向前試探一步，同時路徑延長
    //一個單元格。實現(xiàn)格點轉(zhuǎn)入功能
    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;
    }

    //基于試探回溯策略實現(xiàn)的尋徑算法，在格單元s至t之間規(guī)劃一條通路（如果存在的話）
    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;  //用棧標(biāo)記通路，所謂Theseus手上的線繩
        s->incoming = UNKOWN;
        s->status = ROUTE;
        path.push(s); //起點
        //從起點開始不斷試探、回溯，直到抵達(dá)終點，或者窮盡所有可能
        do {
            Cell* c = path.top();  //檢查當(dāng)前位置，棧頂
            //若已抵達(dá)終點，則找到了一條通路；否則，沿著尚未試探的方向繼續(xù)試探
            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]; //目標(biāo)
labyrinth(laby, s, t);