一、前言

  该文将通过对话的形式，介绍一个童年的回忆 —— 推箱子 游戏。
  这个故事发生在 ❤️学姐教我十道题搞定C语言❤️ 后的三个月，我开始和大部分大学生一样沉迷游戏，这时候学姐为了助我脱坑，竟然要求教我做游戏，也就是因为这么一教，让我入了游戏坑，一做就是十四年！那是我逝去的青春！
  在此也劝诫现在在校打算出来找工作的大学生，千万要选一个你认为能够坚持一辈子做下去的行业，不然中途想转行真的很难！除非你能够接受重新学习和平薪或者降薪切换！

二、预备知识

1、游戏介绍

• 然而，实际最后我们是用控制台实现的，也就是这样……

图二-1-1

2、基础 c/c++ 语法

• 本文涉及的代码语法均为 C/C++，包含但不限于：

1）一些基本的输入输出、循环迭代、递归语法；
2）一些 STL 队列 queue 的接口；
3）一些控制台的显示接口；

• 这里澄清一点，学姐那时候也是半吊子，她一直以为 C 和 C++ 是一个语言，我在这里澄清下，C++ 完美继承了 C语言的语法，但是这的确是两个思想完全不同的语言！ 当然，那时候我的哪知道这么多……

3、数学基础排列组合

• 主要是涉及到状态的计算，需要用到组合数；只需要了解 $n$ 个元素中取 $m$ 个元素的方案数为：
  $$C_n^m=\frac{n!}{m!(n-m)!}$$

4、深度、广度优先搜索

• 深度、广度优先搜索作为最主要的图论遍历算法，有着广泛的应用呢；
• 游戏中的寻路算法就是基于广搜的 A*；
• 可以大致浏览一下以下文章，有一个初步了解：❤️深度优先搜索❤️ 和 ❤️广度优先搜索❤️。

5、哈希表

• 哈希表主要用于广搜的时候进行状态标记，避免搜索重复状态，将原本 多维 的状态压缩到 一维 后进行哈希；
• 我之前也有介绍过哈希表，具体可以参见这篇文章：❤️哈希表底层详解❤️。

三、算法分析

1、数据表示

由于是被迫的，那时候的我，只能说 “好的！”

• 通过 ASCII 符号来表示不同的游戏块：

□（空心方块）代表空地
■（实心方块）代表障碍物
●（实心圆）代表箱子
◎（同心圆）代表目标位置
♂（男性符号）代表推箱子的人

• 将 游戏关卡 表示成 ASCII 如图三-1-1所示：

图三-1-1

• 当然，在实际编码中，每个格子是用 C/C++ 中的枚举来表示的，代码如下：

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所示：
  图三-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

• 于是，我们发现，状态和所有能够动的对象（人、箱子）有关系，那么可以把所有人和箱子的位置联合起来作为状态表示的依据，即：$$(manPos,boxPo{s}_1,boxPo{s}_2,...,boxPo{s}_2)$$

3）状态降维

• 假设一个 $R\times C$ 的地图上，我们令 “小人” 的位置为 $(m_x,m_y)$，$n$ 个箱子的位置分别为 $(b{1}_x,b{1}_y)，(b{2}_x,b{2}_y)，...，(b{n}_x,b{n}_y)$ ，并且所有 $x$ 坐标都是在 $[0,R)$ 范围内，所有 $y$ 坐标都是在$[0,C)$ 范围内；

• 为了简化问题， 我们将位置再进行一次转换，把二维转换成一维，即：
  $$\begin{gathered} (m_x,m_y)=m_{pos}=m_x\times C+m_y \\ (b{1}_x,b{1}_y)=b{1}_{pos}=b{1}_x\times C+b{1}_y \\ ... \\ (b{n}_x,b{n}_y)=b{n}_{pos}=b{n}_x\times C+b{n}_y \end{gathered}$$

• 将这 $n+1$ 个对象的位置看成是 $K$ 进制的每一位，就可以编码成一个数字 $x$ 了(其中 $K=R\times C$ )；
  $$x=m_{pos}\times K^0+b{1}_{pos}\times K^1+b{2}_{pos}\times K^2+...+b{n}_{pos}\times K^n$$

• 这就将原本 $2\ast (n+1)$ 维的向量降成 1 维的了。

4）状态压缩

• 上面提到的位置中，其实有很多位置是无用位置，也就会有很多无用状态带出来，比如：墙的位置、不可达的空地等等；
• $n$ 个箱子是无差别的，作为 $K$ 进制的不同权值的位似乎不太合适，所以这里涉及到一个 最小表示法 的问题，可以将所有箱子的数字进行从小到大排序，再进行状态降维。如下的三个箱子的位置表示的状态是一样的：
  $$((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$$
• 然而还有很多状态其实是非法的，这里说的非法是指：一旦达到这个状态，就不可能让 $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$ 取模；

• 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;
}

6、路径回溯

• 在广搜进行扩展状态的时候，我们通过一个链表把当前状态和前驱状态串联起来，这样，最终就可以通过结束状态回溯到开始状态了。

7、效果渲染

• 效果渲染就是从开始状态到结束状态，遍历所有的状态，然后分别对状态进行解码填充地图即可。
• 以上所有代码均可以在我的 github 上找到：推箱子游戏源码

五、写在最后

• 好了！实用搜索小技巧，你学废了吗？
• 最后来看一波机器人的表演吧！