文章目錄

一、前言
二、預備知識
- 1、基礎 c/c++ 語法
- 2、數學基礎排列組合
- 3、深度、廣度優先搜索
- 4、哈希表
三、演算法分析
- 1、資料表示
- 2、演算法設計
- - 1）演算法方向確定
  - 2）狀態表示
  - 3）狀態降維
  - 4）狀態壓縮
  - 5）搜索
  - - 1. 初始狀態生成
    - 2. 狀態擴展
    - 3. 結束狀態判定
四、編碼實作
- 1、類的定義
- 2、輸入合法性判定
- 3、深搜實作格子編號
- - 1）標記格子未訪問
  - 2）深搜訪問所有連通塊
  - 3）對訪問到的塊進行重編號
  - 4）介面封裝
- 4、實作哈希函式
- - 1）設計一個哈希類
  - 2）初始化哈希陣列
  - 3）狀態哈希映射實作
  - 4）狀態編碼實作
- 5、廣搜模擬推箱子程序
- 6、路徑回溯
- 7、效果渲染
五、寫在最后

一、前言

看到這張圖，相信大部分人都不陌生，沒錯，這就是我們那個年代非常流行的益智游戲 —— 推箱子，
圖一-1
今天，我們來研究一下，如何通過計算機的角度，讓這個小人把所有箱子歸位，
先來看下我們最后想要實作的效果：
圖一-2

二、預備知識

需要用到的預備知識有：

1、基礎 c/c++ 語法

本文涉及的代碼語法均為 c/c++，包含但不限于：

1）一些基本的輸入輸出、回圈迭代、遞回語法；
2）一些 STL 佇列 queue 的介面；
3）一些控制臺的顯示介面；

2、數學基礎排列組合

主要是涉及到狀態的計算，需要用到組合數；只需要了解 n n n 個元素中取 m m m 個元素的方案數為：
C n m = n ! m ! ( n ? m ) ! C_n^m = \frac {n!}{m!(n-m)!} Cnm?=m!(n?m)!n!?

3、深度、廣度優先搜索

深度、廣度優先搜索作為最主要的圖論遍歷演算法的，有著廣泛的應用，游戲中的尋路演算法就是基于廣搜的 A*；
可以大致瀏覽一下這篇文章，有一個初步了解：夜深人靜寫演算法（一）搜索入門

4、哈希表

哈希表主要用于廣搜的時候進行狀態標記，避免搜索重復狀態，將原本多維的狀態壓縮到一維后進行哈希；
我之前也有介紹過哈希表，具體可以參見這篇文章：Redis底層詳解（一）哈希表和字典

三、演算法分析

1、資料表示

通過 ASCII 符號來表示不同的游戲塊：

□（空心方塊）代表空地
■（實心方塊）代表障礙物
●（實心圓）代表箱子
◎（同心圓）代表目標位置
♂（男性符號）代表推箱子的人

將圖一-1 中的游戲關卡表示成 ASCII 如圖三-1-1所示：
圖三-1-1
當然，在實際編碼中，每個格子是用列舉來表示的，代碼如下：

enum BlockType {
    BT_EMPTY = 0,    // 空地
    BT_WALL = 1,     // 障礙物、墻
    BT_BOX = 2,      // 箱子
    BT_TARGET = 3,   // 目標位置
    BT_MAN = 4,      // 推箱子的人
    BT_MAX
};

// 這些都是寬字符，占用2個位元組，加上字串末尾 '\0'，總共3個位元組
const char BlockSign[BT_MAX][3] = {
    "□", "■", "●", "◎", "♂"
};

這里的數字代表了游戲中實際每個方塊的含義，屬于資料層，而顯示層進行渲染的時候其實也是通過不同的資料來顯示成不同的畫面，可以是 ASCII 字符，也可以是圖片，甚至還可以是 3D 的，

圖三-1-2
為了將輸入資料轉換成我們可以處理的資料，需要提供轉換介面如下，對于給定的輸入遍歷尋找對應匹配的列舉：

BlockType convertCharToBlockType(char chigh, char clow) {
    BlockType tp = BlockType::BT_EMPTY;
    for (int i = BlockType::BT_EMPTY; i < BlockType::BT_MAX; ++i) {
        if (BlockSign[i][0] == chigh && BlockSign[i][1] == clow) {
            tp = (BlockType)i;
            break;
        }
    }
    return tp;
}

2、演算法設計

1）演算法方向確定

首先，一定是用搜索演算法；
其次，盡量肯定是要求最少步數把所有箱子推到目標位置，也就是求最短路問題，那么就是一個很明顯的廣度優先搜索問題（當然，也可以用迭代加深逐步擴大解空間來求解，今天就只介紹廣搜吧），

2）狀態表示

演算法確定后，就需要確定如何進行狀態表示了；
演算法的焦點一定在這個 “小人” 身上，但是光用 “小人” 的位置來表示狀態肯定是不夠的；如圖三-2-1所示，兩個地圖關卡的小人的位置是相同的，但是不能作為同一種情況來考慮，因為箱子的位置不同，所以最終狀態表示也不同，
圖三-2-1
于是，我們發現，狀態和所有能夠動的物件（人、箱子）有關系，那么可以把所有人和箱子的位置聯合起來作為狀態表示的依據，即： ( M a n p o s , B o x [ 1 ] p o s , B o x [ 2 ] p o s , . . . , B o x [ n ] p o s ) (Man_{pos}, Box[1]{pos},Box[2]{pos}, ..., Box[n]{pos}) (Manpos?,Box[1]pos,Box[2]pos,...,Box[n]pos)
這是一個 2 ? n + 2 2*n+2 2?n+2 的向量，不利于哈希映射，所以我們需要把這些向量壓縮到一個數字上，

3）狀態降維

假設一個 R × C R \times C R×C 的地圖上，我們令 “小人” 的位置為 ( m x , m y ) (m_x,m_y) (mx?,my?)， n n n 個箱子的位置分別為 ( b 1 x , b 1 y ) ， ( b 2 x , b 2 y ) ， . . . ， ( b n x , b n y ) (b1_x,b1_y)，(b2_x,b2_y)，...， (bn_x,bn_y) (b1x?,b1y?)，(b2x?,b2y?)，...，(bnx?,bny?) ，并且所有 x x x 坐標都是在 [ 0 , R ) [0, R) [0,R) 范圍內，所有 y y y 坐標都是在 [ 0 , C ) [0, C) [0,C) 范圍內；
為了簡化問題，我們將位置再進行一次轉換，把二維轉換成一維，即：
( m x , m y ) = m p o s = m x ? C + m y ( b 1 x , b 1 y ) = b 1 p o s = b 1 x ? C + b 1 y . . . ( b n x , b n y ) = b n p o s = b n x ? C + b n y (m_x,m_y) = m_{pos} = m_x * C + m_y \\ (b1_x,b1_y) = b1_{pos} = b1_x * C + b1_y \\ ...\\ (bn_x,bn_y) = bn_{pos} = bn_x * C + bn_y (mx?,my?)=mpos?=mx??C+my?(b1x?,b1y?)=b1pos?=b1x??C+b1y?...(bnx?,bny?)=bnpos?=bnx??C+bny?
將這 n + 1 n+1 n+1 個物件的位置看成是 K 進制的每一位，就可以編碼成一個數字 x x x 了(其中 K = R ? C K = R*C K=R?C )；
x = m p o s ? K 0 + b 1 p o s ? K 1 + b 2 p o s ? K 2 + . . . + b n p o s ? K n x = m_{pos} * K^0 + b1_{pos} * K^1 + b2_{pos} * K^2 + ... + bn_{pos} * K^n x=mpos??K0+b1pos??K1+b2pos??K2+...+bnpos??Kn
這就將原本 2 ? ( n + 1 ) 2*(n+1) 2?(n+1) 維的向量降成 1 維的了，

4）狀態壓縮

上面提到的位置中，其實有很多位置是無用位置，也就會有很多無用狀態帶出來，比如：墻的位置、不可達的空地等等；
n n n 個箱子是無差別的，作為 K K K 進制的不同權值的位似乎不太合適，所以這里涉及到一個 最小表示法 的問題，可以將所有箱子的數字進行從小到大排序，再進行狀態降維，如下的三個箱子的位置表示的狀態是一樣的：
( ( 1 , 2 ) , ( 3 , 7 ) , ( 2 , 5 ) ) 和 ( ( 2 , 5 ) , ( 1 , 2 ) , ( 3 , 7 ) ) ((1,2),(3,7),(2,5)) 和 ((2,5),(1,2),(3,7)) ((1,2),(3,7),(2,5))和((2,5),(1,2),(3,7))
綜合以上兩點，我們可以做如下處理，盡量減少狀態：

1）從小人的初始位置進行一次深度優先搜索（認為除了墻以外其它點都可達），標記所有遍歷到的點；
2）對以上所有深搜遍歷到的點從 1 開始進行編號，所有這些點編號不重復即可，如圖三-2-2所示：

圖三-2-2

3）小人和箱子到達的位置直接用編碼后的數字表示即可，這樣一來，在壓縮成 K 進制數的時候，K的值從原來的 R x C = 64 變成了 24，大大縮小了狀態空間，狀態編碼的時候，為了讓解碼的時候能夠準確解出有多少個箱子，編碼位從1開始（如果從0開始，那么一旦有個箱子在0的位置會產生二義性），
4）箱子的編碼還是遵從最小表示法，按照遞增順序排完序再壓縮到一維，

由于箱子和人都不能重疊，對于這個關卡來說，23個空位置，選出4個位置放箱子，再從19個位置選擇1個放小人，所以總的狀態數是：
C 23 4 C 19 1 = 4037880 C_{23}^4C_{19}^1 = 4037880 C234?C191?=4037880
然而還有很多狀態其實是非法的，這里說的非法是指：一旦達到這個狀態，就不可能讓 n 個箱子歸位，比如把某個箱子推到一個不是目標位置的角落里面，如圖三-2-3所示，右下角的箱子這么一放，永遠都無法推到目標點了，

在這里插入圖片描述

圖三-2-3

所以排除這些非法狀態后，實際狀態數會更少，
當然，這只是針對這個資料的，狀態數會隨著地圖的增大、箱子的增多而成倍增長，

5）搜索

狀態確定以后，就可以進行廣度優先搜索了，
分成三步走：

1. 初始狀態生成

對初始的人和箱子進行編碼，就生成了初始狀態，初始狀態壓入佇列；

2. 狀態擴展

從當前佇列首部彈出一個元素，然后進行狀態擴展，對于狀態擴展可以這樣描述：

任何情況下，小人都是選擇往四個方向走一格，對于每個方向，都有3種情況：
1）前面沒路（墻或者越界），這種情況無法擴展狀態；
2）前面沒有箱子，直接往前走，擴展狀態（塞入佇列尾部）；
3）前面有個箱子，又分兩種情況：
? 3.1）箱子前面無法放置，這種情況無法擴展狀態；
? 3.2）箱子前面可以放置，人和箱子同時往這個方向前進一格，擴展狀態（塞入佇列尾部）;

3. 結束狀態判定

當彈出的元素，進行解碼后發現，四個箱子都已經到了規定的位置，則搜索結束，

四、編碼實作

1、類的定義

定義一個 PushBoxGame 類，成員變數全部定義成私有；

const int MAXN = 10;

class PushBoxGame {

public:
    // 公有介面
    
private:
    // 私有函式
private:
    // 關卡相關
    int row_, col_;                   // 游戲關卡行和列
    BlockType blocks_[MAXN][MAXN];    // 游戲關卡地圖

    // 深搜相關
    int id_[MAXN][MAXN];              // 關卡格子編號，idCount_為上文提到的 K
    int idrow_[MAXN*MAXN];            // id 行反查
    int idcol_[MAXN*MAXN];            // id 列反查

    // 廣搜相關
    Path path_;                       // 路徑生成器
    Hash hash_;                       // 標記狀態的hash表
    int finalState_;                   // 搜索的最終狀態
};

介面的定義較多，最后會有一個總結，這里為了描述清晰暫且就不列了，只列出必要的成員變數；

2、輸入合法性判定

為了避免狀態過多，短時間搜索不出正確的解，需要對輸入資料進行一個合法性判定，包括以下幾點：

1）地圖大小不超過 10X10
2）箱子最多個數 6
3）目標位置必須和箱子數匹配
4）必須嚴格有一個"小人"

C++ 代碼實作如下：

bool PushBoxGame::isBlockValid() {
    // 1 地圖大小最大 MAXN X MAXN
    if (row_ > MAXN || col_ > MAXN) {
        return false;
    }

    int blockCnt[BlockType::BT_MAX];
    memset(blockCnt, 0, sizeof(blockCnt));

    for (int i = 0; i < row_; ++i) {
        for (int j = 0; j < col_; ++j) {
            ++blockCnt[blocks_[i][j]];
        }
    }
    // 2 箱子最多個數 MAXBOX
    if (blockCnt[BlockType::BT_BOX] > MAXBOX) {
        return false;
    }

    // 3 目標位置必須 和 箱子數匹配
    if (blockCnt[BlockType::BT_TARGET] != blockCnt[BlockType::BT_BOX]) {
        return false;
    }

    // 4 必須嚴格有一個 '小人'
    if (blockCnt[BlockType::BT_MAN] != 1) {
        return false;
    }

    return true;
}

3、深搜實作格子編號

用深度優先搜索來對格子進行編號；

1）初始化所有格子的標記為 VT_UNVISITED(-1)
2）從 “小人” 位置出發，遍歷所有與之相鄰的連通塊，將遍歷到的塊標記位 VT_VISITED(0)；
3）按照從左往右，從上往下的順序對所有已訪問格子進行不重復編號；

1）標記格子未訪問

對格子訪問狀態定義列舉如下：

enum VisitType {
    VT_UNVISITED = -1,
    VT_VISITED = 0,
};

格子訪問狀態存盤在 id_[MAXN][MAXN] 這個成員變數陣列中，然后呼叫 memset 進行統一初始化：

	memset(id_, VisitType::VT_UNVISITED, sizeof(id_));

2）深搜訪問所有連通塊

實作介面 genId_floodfill 尋找小人位置，呼叫 genId_dfs 進行深搜；

void PushBoxGame::genId_floodfill() {
    // 1.初始化所有格子為未訪問
    memset(id_, VisitType::VT_UNVISITED, sizeof(id_));
    // 2.找到 BT_MAN 的格子進行深搜，標記訪問到的格子
    for (int i = 0; i < row_; ++i) {
        for (int j = 0; j < col_; ++j) {
            if (blocks_[i][j] == BT_MAN) {
                genId_dfs(i, j);
            }
        }
    }
}

深搜實作如下：

1）障礙檢測；
2）重復訪問檢測；
3）標記當前格子已訪問；
4）遞回處理相鄰四個格子

C++ 代碼實作如下：

const int dir[4][2] = {
    { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 }
};
  
bool PushBoxGame::isInBound(int r, int c) {
    // 越界檢測
    return r >= 0 && r < row_ && c >= 0 && c < col_;
}

bool PushBoxGame::isInWall(int r, int c) {
    // 墻體障礙檢測
    return blocks_[r][c] == BT_WALL;
}

// 綜合障礙檢測
bool PushBoxGame::isObstacle(int r, int c) {
    return !isInBound(r, c) || isInWall(r, c);
}

void PushBoxGame::genId_dfs(int r, int c) {
    // 1. 障礙檢測
    if (isObstacle(r, c)) {
        return;
    }
    // 2. 重復訪問檢測
    if (id_[r][c] == VisitType::VT_VISITED) {
        return;
    }
    // 3. 標記當前格子已訪問
    id_[r][c] = VisitType::VT_VISITED;

    // 4. 遞回處理相鄰四個格子
    for (int i = 0; i < 4; ++i) {
        genId_dfs(r + dir[i][0], c + dir[i][1]);
    }
}

3）對訪問到的塊進行重編號

按照從左往右，從上往下的順序對所有已訪問格子進行重新編號；
并且，增加一個反查表 idrow_ 和 idcol_，通過編號需要知道它原本的行列；

void PushBoxGame::genId_genTerr() {
    printf("生成地形資料...\n");
    // 1. 按照從左往右，從上往下的順序標記所有已訪問格子
    int idCount = 1;
    for (int i = 0; i < row_; ++i) {
        for (int j = 0; j < col_; ++j) {
            if (id_[i][j] == VisitType::VT_VISITED) {
                // 添加 id 正向映射
                id_[i][j] = idCount++;

                // 添加 id 反向映射
                idrow_[id_[i][j]] = i;
                idcol_[id_[i][j]] = j;
            }
        }
    }
    PushBoxState::setBase(idCount);
}

4）介面封裝

把呼叫關系封裝起來就是：

void PushBoxGame::genId() {
    genId_floodfill();
    genId_genTerr();
}

在外部看來，只需要呼叫 genId()，就可以實作格子重編號了，

4、實作哈希函式

狀態編碼較大的時候，陣列覆寫不到，所以需要進行取模后映射，
取模帶來的問題就是有可能產生哈希沖突，
所以需要實作哈希沖突后重映射的問題，我用的是 二次尋址法，
為了簡化問題，這里采用靜態哈希陣列，如果有興趣的童鞋可以自己實作一下 rehash 和漸進式 rehash，

1）設計一個哈希類

由于哈希陣列比較大，不適合放在成員變數里，所以把它放在堆上；

class Hash {

public:
    Hash();
    virtual ~Hash();

private:
    bool *hashkey_;                   // 狀態hash的key
    StateType *hashval_;              // 狀態hash的val

public:
    // 銷毀呼叫
    void finalize();
    // 初始化呼叫
    void initialize();
    // 獲取給定值的哈希值
    int getKey(StateType val);
    // 查詢是否有這個值在哈希表中
    bool hasKey(StateType val);
    // 獲取給定哈希值的原值
    StateType getValue(int key);
};

2）初始化哈希陣列

注意申請記憶體前先判空，避免記憶體泄漏；
類析構的時候呼叫 finalize 進行堆記憶體釋放；

void Hash::finalize() {
    if (hashkey_) {
        delete[] hashkey_;
        hashkey_ = NULL;
    }
    if (hashval_) {
        delete[] hashval_;
        hashval_ = NULL;
    }
}
void Hash::initialize() {
    // 1. 釋放空間避免記憶體泄漏
    // 2. 初始化哈希的key和val
    if (!hashkey_) {
        hashkey_ = new bool[MAXH + 1];
    }
    if (!hashval_) {
        hashval_ = new StateType[MAXH + 1];
    }
    memset(hashkey_, false, (MAXH + 1) * sizeof(bool));
}

3）狀態哈希映射實作

getKey 這個函式的含義是：根據狀態 val 的值，在陣列 hashkey_ 中找到一個下標與之一一映射；

int Hash::getKey(StateType val) {
    // 1. 采用 位與 代替 取模，位運算加速
    int key = (val & MAXH);
    while (1) {
        if (!hashkey_[key]) {
            // 2. 如果對應的key沒有出現過，則代表沒有沖突過；則key的槽位留給val；
            hashkey_[key] = true;
            hashval_[key] = val;
            return key;
        }
        else {
            if (hashval_[key] == val) {
                // 3. 如果key 的槽位正好和val匹配，則說明找到了，回傳 key；
                return key;
            }
            // 4. 沒有找到合適的 key， 進行二次尋址
            key = (key + 1) & MAXH;
        }
    }
}

1）很多開源代碼中，哈希陣列的長度都是 2 的冪，原因有兩個：

a）方便倍增進行 rehash；
b）位運算的運算效率高于取模，所以可以用位與 2 n ? 1 2^n-1 2n?1 來代替對 2 n 2^n 2n 取模；

2）!hashkey_[key]代表對應的key沒有出現過，即沒有和其他值產生沖突過，則key的槽位留給 val；
3）hashval_[key] == val代表這個key的槽位之前和val的值是一一映射的，則直接范圍 key 的值即可；
4）key = (key + 1) & MAXH;進行二次尋址，繼續尋找合適的 key 槽位；
然后再提供一個反查介面 getValue，即根據 key 查詢 value，如下：

StateType Hash::getValue(int key) {
    if (key < MAXH && hashkey_[key]) {
        return hashval_[key];
    }
    return -1;
}

4）狀態編碼實作

對狀態的編碼三 - 2-4）中提到的狀態壓縮的方法，把所有的數字都壓縮到一個整數上，所以主要對外提供兩個介面：

    StateType Serialize(int man, int boxcnt, int box[MAXBOX]);
    void DeSerialize(StateType state);

Serialize根據傳入的人和箱子位置，生成一個整數，暫且稱之為序列化；
DeSerialize根據傳入的整數，反算出人和箱子位置，暫且稱之為反序列化；
然后就可以設計出一個狀態類，如下：

// 注意：狀態編碼的時候，為了讓解碼的時候能夠準確解出有多少個箱子，編碼位 為不設定 0
class PushBoxState {
public:
    static void setBase(int b);
    static int getBase();

    PushBoxState();
    virtual ~PushBoxState();

    // 根據傳入的 人和箱子位置，生成一個整數
    StateType Serialize(int man, int boxcnt, int box[MAXBOX]);

    // 根據傳入的整數，反推出 人和箱子位置
    void DeSerialize(StateType state);

    // 對私有成員訪問的封裝
    StateType getBoxState();
    StateType getState();
    void setManCode(int val);
    int getManCode();
    void setBoxCode(int idx, int val);
    int getBoxCode(int idx);
    int getBoxCount();

    // 獲取是否有一個箱子在id上
    // 有的話，回傳箱子下標，否則回傳 -1
    int getMatchBoxIndex(int id);

private:
    void calcState(bool bReCalcBox);
    void calcManCode();
    void calcBoxCode();


private:
    int man_;
    int boxcnt_;
    int box_[MAXBOX];

    StateType boxstate_;
    StateType state_;

    static int base_;
};

實作比較簡單，這里就不貼了，文章結尾會提供整套代碼實作的鏈接；

5、廣搜模擬推箱子程序

廣搜的整個程序寫成偽代碼如下：

bool PushBoxGame::bfs() {
    bfs_initialize();
    bfs_pushInitState();
    while(!queue.empty()) {
        bfs_popFrontState();
        bfs_checkFinalState();
        bfs_extendState();
    }
}

實際C++代碼實作如下：

bool PushBoxGame::bfs() {
    queue <int> Q;
    PushBoxState pbs;

    bfs_initialize();
    // 提前計算出終止狀態
    StateType finalBoxState = getFinalBoxState();
    
    // 將初始狀態壓入佇列
    int startState = hash_.getKey(getInitState());
    Q.push(startState);

    while (!Q.empty()) {
        int nowState = Q.front();
        Q.pop();

        // 將編碼后的資料 反序列化 到 pbs
        pbs.DeSerialize(hash_.getValue(nowState));

        // 找到解，將最終狀態持久化
        if (pbs.getBoxState() == finalBoxState) {
            finalState_ = nowState;
            return true;
        }

        // 人往四個方向走一格，對于每個方向，都有3種情況：
        // 1. 前面沒路，這種情況無法擴展狀態；
        // 2. 前面沒有箱子，直接往前走，擴展狀態；
        // 3. 前面有個箱子，又分兩種情況：
        //   3.1 箱子前面無法放置，這種情況無法擴展狀態；
        //   3.2 箱子前面可以放置，人和箱子同時往這個方向前進一格，擴展狀態;
        
        int man = pbs.getManCode();

        for (int i = 0; i < 4; ++i) {
            
            int manr = idrow_[man] + dir[i][0];
            int manc = idcol_[man] + dir[i][1];

            if (isObstacle(manr, manc)) {
                // 情況1
                continue;
            }

            int nextman = id_[manr][manc];

            // 模擬人走到了這個位置
            pbs.setManCode(nextman);

            int boxIndex = pbs.getMatchBoxIndex(nextman);
            if (boxIndex == -1) {
                // 情況2
                bfs_checkAndExtendState(Q, nowState, pbs);
            }
            else {
                // 情況3 箱子必須往前推進一格
                int boxr = idrow_[nextman] + dir[i][0];
                int boxc = idcol_[nextman] + dir[i][1];

                if (isObstacle(boxr, boxc) || pbs.getMatchBoxIndex(id_[boxr][boxc]) != -1) {
                    // 情況3.1
                    continue;
                }
                // 情況3.2
                // 模擬箱子往前走了一格
                pbs.setBoxCode(boxIndex, id_[boxr][boxc]);
                bfs_checkAndExtendState(Q, nowState, pbs);
                // 回退箱子
                pbs.setBoxCode(boxIndex, nextman);
            }
        }
    }
    return false;
}