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

#ifndef ALGORITHM_MAZEROUTE_H
#define ALGORITHM_MAZEROUTE_H

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

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

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


    //數(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)嘗試過(guò)的方向

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

    //在路徑試探過(guò)程中需要反復(fù)確定當(dāng)前位置的相鄰格點(diǎn)
    inline Cell* neighbor(Cell* cell) { //查詢當(dāng)前位置的相鄰格點(diǎn)
        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)某一個(gè)相鄰格點(diǎn)可用之后灸眼，算法將朝對(duì)應(yīng)方向向前試探一步，同時(shí)路徑延長(zhǎng)
    //一個(gè)單元格墓懂。實(shí)現(xiàn)格點(diǎ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;
    }

    //基于試探回溯策略實(shí)現(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); //起點(diǎn)
        //從起點(diǎn)開(kāi)始不斷試探捕仔、回溯匕积，直到抵達(dá)終點(diǎn)盈罐，或者窮盡所有可能
        do {
            Cell* c = path.top();  //檢查當(dāng)前位置，棧頂
            //若已抵達(dá)終點(diǎn)闪唆，則找到了一條通路盅粪；否則，沿著尚未試探的方向繼續(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) { //若所有方向都嘗試過(guò)票顾，則回溯一步
                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

測(cè)試代碼

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