【C语言+双层BFS算法】自动生成可解地图的推箱子小游戏
新人来论坛有点迷茫(⊙﹏⊙)先发个大一时候做的课程设计混个脸熟（大三了今年，另外如果有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。
#include "map.h"
int player = {H / 2, L / 2};
char map;
int next = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int boxNum = 0, boxes, purs;
/*----------------------------------*/
/* 生成地图(newMap)
/*----------------------------------*/
typedef struct listNode{
int x;
int y;
struct listNode *p;
}list;
int wallCheck(int x, int y){
if(map != 1)
return map;
if(map + map + map + map +
map + map + map + map < 8)
return 1;
return 0;
}
int fullwallCheck(int x, int y){
if(map == 2)
return 2;
if(map == 2 || map == 2 || map == 2 || map == 2 ||
map == 2 || map == 2 || map == 2 || map == 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 = 1;
wallAdd(x + next, y + next, direction, k+1);
}
void mapMake(){
char book, a, b;
int que = {{H / 2, L / 2}}, head = 0, tail = 1;
// 0. 初始化地图
{
for(int i = 0; i < H; i++)
for(int j = 0; j < L; j++)
map = book = 0;
player = H / 2;
player = L / 2;
map = book = 1;
}
// prt();
// 1. 生成wall (use queue)
{
while(head != tail){// bfs + random
a = que;
b = que;
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 >= 0 && a + next <= H - 1 &&
b + next >= 0 && b + next <= L - 1)
if(book]] == 0){
map]] = 1;
book]] = 1;
que = a + next;
que = b + next;
tail++;
}
}
head++;
}
}
// prt();
// 2. 美化墙面
{
for(int i = 0; i < H; i++)// make edges empty
map = map = 0;
for(int j = 0; j < L; j++)// make edges empty
map = map = 0;
for(int i = 0; i < H; i++)// refresh book
for(int j = 0; j < L; j++)
book = map;
}
// prt();
// 3. 查找有效墙面 (与empty接壤)
{
for(int i = 1; i < H - 1; i++)// replace book
for(int j = 1; j < L - 1; j++)
book = wallCheck(i, j);
for(int i = 0; i < H; i++)// refresh map
for(int j = 0; j < L; j++)
map = book;
}
// prt();
// 4. 添加内部障碍墙 (随机替换一部分empty为wall)
{
for(int i = H * L; i > 0; i--){
int pos = rand() % tail;
a = que;
b = que;
wallAdd(a, b, rand() % 2, 0);
}
for(int i = 0; i < H; i++)// refresh book
for(int j = 0; j < L; j++)
book = map;
}
// prt();
// 5. 生成floor (use queue)
{
map = book = 2;
head = 0, tail = 1;// reset queue
while(head != tail){// bfs
a = que;
b = que;
for(int j = 0; j < 4; j++){
if(book]] == 0){
map]] = 2;
book]] = 2;
que = a + next;
que = b + next;
tail++;
}
}
head++;
}
}
// prt();
// 6. 查找有效墙面 (与floor接壤)
{
for(int i = 1; i < H - 1; i++)
for(int j = 1; j < L - 1; j++)
book = fullwallCheck(i, j);
for(int i = 0; i < H; i++)
for(int j = 0; j < L; j++)
map = book;
}
// 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;
tp->y = que;
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 = box->x;
boxes = box->y;
map = 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 = pur->x;
purs = pur->y;
map = 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]] = 6; // set player
}
}
最后再说一句，这个方法水得ep，有任何新的优秀思路欢迎交流~~
感谢楼主分享，学习了。。。 希望以后我也能写出这样的游戏C, 毕竟才开始学C 可以可以 鼓励鼓励 优化可以试试迭代加深 前来学习学习 可以的，{:1_893:} 谢谢分享 请问用VS打开怎么打开呀
页:
[1]