【C语言+双层BFS算法】自动生成可解地图的推箱子小游戏

RickoNoNo3

新人来论坛有点迷茫(⊙﹏⊙)
先发个大一时候做的课程设计混个脸熟（大三了今年，另外如果有ACMer/OIer的话欢迎交流鸭~）
不造BFS是啥？参考各位大佬的博客或者算法书，这里不做赘述（当年是lrj大哥教会我的）

做这个的时候会的还不是很多，界面是命令行怼上去的，算法也是巨暴力的BFS，因此地图大小会受限制。
程序逻辑由三部分组成，分别是【生成地图】【判断可解】【进行游戏】，总代码量小一千行的亚子~
现在看起来还蛮EASY的，不过敲代码的思路确实没现在成熟……

【生成地图】
生成地图的基本思路是：从地图中点出发，进行一遍带随机参数的BFS来生成可行走的地板（floor），然后在地板周围造墙（Wall），中间还穿插了一点优化，比如在地板中间多铺点障碍墙之类的。
最后在地板上随机放N个箱子，还有N个目标点，具体可以看代码，注释还蛮多的。


【判断可解】
当时想了好几天，终于才把思路理清楚：
        1. 外层负责遍历每一种地图情况，玩家每推动一个箱子即算作不同地图情况。
        2. 内层负责遍历地图各个点的情况，即BFS遍历“玩家可行走区域”，最终得到多种推动箱子的方案。
        3. 内层得到的每种推箱子方案将产生一个新地图置入外层队列中。
        简单来说，外层BFS给内层BFS一个当前需要查询的地图，内层BFS遍历得多种推箱方案，每种推箱方案将交付给外层一个新地图。结束后，外层进行下一个地图查询。
结束条件：
        1. 外层队列已空，即所有地图情况遍历结束，无解。
        2. 超过阈值步数仍未找到解，也跳出遍历，视为无解（减少无用搜索）。
        3. 某种地图情况下所有的箱子落在所有的目标点上，即该地图可解。
        如果无解当然就回到【生成地图】啦~~如果可解当然就到【进行游戏】啦~~

【进行游戏】
这部分没什么好说的了，上下左右走路之前判断能不能走，有没有推到箱子，是不是已经死局了，etc……思路基本是线性的，多考虑点情况，别掉坑里就OK。
值得一提的是我做这个部分的时候学会了用<conio.h>（滑稽



以上只是简单介绍一下程序思路，也还有不少剪枝手段和具体的细节没有提及，需要对照代码来分析。

代码不短（放论坛的话就显得很长了），简单放几行（生成地图部分），有兴趣的话下载附件看吧。工程是用CodeBlocks建的，当然也可以选择手动打开两个.c和一个.h。

[C] 纯文本查看 复制代码

#include "map.h"

int player[2] = {H / 2, L / 2};
char map[H][L];
int next[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int boxNum = 0, boxes[H * L][2], purs[H * L][2];


/*----------------------------------*/
/* 生成地图(newMap)
/*----------------------------------*/
typedef struct listNode{
        int x;
        int y;
        struct listNode *p;
}list;

int wallCheck(int x, int y){
        if(map[x][y] != 1)
                return map[x][y];
        if(map[x + 1][y] + map[x - 1][y] + map[x + 1][y + 1] + map[x - 1][y - 1] +
                map[x][y + 1] + map[x][y - 1] + map[x - 1][y + 1] + map[x + 1][y - 1] < 8)
                return 1;
        return 0;
}
int fullwallCheck(int x, int y){
        if(map[x][y] == 2)
                return 2;
        if(map[x + 1][y] == 2 || map[x - 1][y] == 2 || map[x + 1][y + 1] == 2 || map[x - 1][y - 1] == 2 ||
                map[x][y + 1] == 2 || map[x][y - 1] == 2 || map[x - 1][y + 1] == 2 || map[x + 1][y - 1] == 2)
                return 1;
        return 0;
}
void wallAdd(int x, int y, int direction, int k){
        if(abs(x - H / 2) <= 1 && abs(y - L / 2) <= 1)  // situation 1: spawn point
                return;
        if(x == 0 || x == H - 1 || y == 0 || y == L - 1)  // situation 2: map edges
                return;
        if(k >= 5)  // situation 3: too long
                return;
        if(rand() % 100 < 60)  // situation 4: random
                return;

        map[x][y] = 1;
        wallAdd(x + next[direction][0], y + next[direction][1], direction, k+1);
}
void mapMake(){
        char book[H][L], a, b;
        int que[H * L][2] = {{H / 2, L / 2}}, head = 0, tail = 1;

        // 0. 初始化地图
        {
        for(int i = 0; i < H; i++)
                for(int j = 0; j < L; j++)
                        map[i][j] = book[i][j] = 0;
        player[0] = H / 2;
        player[1] = L / 2;
        map[H / 2][L / 2] = book[H / 2][L / 2] = 1;
        }
//        prt();
        // 1. 生成wall (use queue)
        {
        while(head != tail){  // bfs + random
                a = que[head][0];
                b = que[head][1];
                for(int j = 0; j < 4; j++){
                        if(a <= H / 4 || a > H / 4 * 3 || b <= L / 4 || b > L / 4 * 3)
                                if((rand() % 2)) continue;
                        if(a + next[j][0] >= 0 && a + next[j][0] <= H - 1 &&
                                b + next[j][1] >= 0 && b + next[j][1] <= L - 1)
                        if(book[a + next[j][0]][b + next[j][1]] == 0){
                                map[a + next[j][0]][b + next[j][1]] = 1;
                                book[a + next[j][0]][b + next[j][1]] = 1;
                                que[tail][0] = a + next[j][0];
                                que[tail][1] = b + next[j][1];
                                tail++;
                        }
                }
                head++;
        }
        }
//        prt();
        // 2. 美化墙面
        {
        for(int i = 0; i < H; i++)  // make edges empty
                map[i][0] = map[i][L - 1] = 0;
        for(int j = 0; j < L; j++)  // make edges empty
                map[0][j] = map[H - 1][j] = 0;
        for(int i = 0; i < H; i++)  // refresh book
                for(int j = 0; j < L; j++)
                        book[i][j] = map[i][j];
        }
//        prt();
        // 3. 查找有效墙面 (与empty接壤)
        {
        for(int i = 1; i < H - 1; i++)  // replace book
                for(int j = 1; j < L - 1; j++)
                        book[i][j] = wallCheck(i, j);
        for(int i = 0; i < H; i++)  // refresh map
                for(int j = 0; j < L; j++)
                        map[i][j] = book[i][j];
        }
//        prt();
        // 4. 添加内部障碍墙 (随机替换一部分empty为wall)
        {
        for(int i = H * L; i > 0; i--){
                int pos = rand() % tail;
                a = que[pos][0];
                b = que[pos][1];
                wallAdd(a, b, rand() % 2, 0);
        }
        for(int i = 0; i < H; i++)  // refresh book
                for(int j = 0; j < L; j++)
                        book[i][j] = map[i][j];
        }

//        prt();

        // 5. 生成floor (use queue)
        {
        map[H / 2][L / 2] = book[H / 2][L / 2] = 2;
        head = 0, tail = 1;  // reset queue
        while(head != tail){  // bfs
                a = que[head][0];
                b = que[head][1];
                for(int j = 0; j < 4; j++){
                        if(book[a + next[j][0]][b + next[j][1]] == 0){
                                map[a + next[j][0]][b + next[j][1]] = 2;
                                book[a + next[j][0]][b + next[j][1]] = 2;
                                que[tail][0] = a + next[j][0];
                                que[tail][1] = b + next[j][1];
                                tail++;
                        }
                }
                head++;
        }
        }

//        prt();

        // 6. 查找有效墙面 (与floor接壤)
        {
        for(int i = 1; i < H - 1; i++)
                for(int j = 1; j < L - 1; j++)
                        book[i][j] = fullwallCheck(i, j);
        for(int i = 0; i < H; i++)
                for(int j = 0; j < L; j++)
                        map[i][j] = book[i][j];
        }

//        prt();

        // 7. 放置实体 (box, purpose, player)
        {
        // 队列(que) -> 链表(list)
        int floor_n = tail - 1;
        list floor;
        list *p = &floor, *tp = p;
        for(int i = 0; i < tail; i++){  // init list
                tp->p = (list *)malloc(sizeof(list));
                tp->x = que[i][0];
                tp->y = que[i][1];
                tp = tp->p;
        }
        tp->p = 0;

        // create box, purpose
        tp = p;
        list *box, *pur;
        int place;
        boxNum = floor_n / 5 + 1;
        for(int i = 0; i < boxNum; i++){
                if(p->p == 0) break;
                place = rand() % floor_n + 1;  // find box
                for(int j = 1; j < place; j++)  // tp : box - 1
                        tp = tp->p;
                box = tp->p;
                boxes[i][0] = box->x;
                boxes[i][1] = box->y;
                map[box->x][box->y] = 3;  // set box, del floor
                tp->p = box->p;
                free(box);
                floor_n--;
                tp = p;
        }
        for(int i = 0; i < boxNum; i++){
                if(p->p == 0) break;
                place = rand() % floor_n + 1;  // find purpose
                for(int j = 1; j < place; j++)  // tp : purpose - 1
                        tp = tp->p;
                pur = tp->p;
                purs[i][0] = pur->x;
                purs[i][1] = pur->y;
                map[pur->x][pur->y] = 5;  // set purpose, del floor
                tp->p = pur->p;
                free(pur);
                floor_n--;
                tp = p;
        }

        tp = p->p;  // clear memory
        list *nextp;
        do{
                nextp = tp->p;
                free(tp);
                tp = nextp;
        }while(nextp);

        map[player[0]][player[1]] = 6; // set player
        }
}

最后再说一句，这个方法水得ep，有任何新的优秀思路欢迎交流~~


推箱子.zip (60.53 KB, 下载次数: 58)

2019-7-23 17:46 上传

点击文件名下载附件

dhs347

感谢楼主分享，学习了。。。

flow_one

希望以后我也能写出这样的游戏C, 毕竟才开始学C

KARMA07007

可以可以 鼓励鼓励

MAXtoDEATH

优化可以试试迭代加深

虚灵幻翼

前来学习学习

Aurora.w

可以的，

吾爱Po解啊

谢谢分享

lalala丨

请问用VS打开怎么打开呀