【C++】生成迷宫的图的深度优先算法和prim算法，还有寻路算法
1、需要安装easyx图形库（官网下载，超级简单）2、代码有详细注释，有些函数命名不规范
3、代码如下
#include<iostream>
#include<stdlib.h>
#include<time.h>
#include <graphics.h>
using namespace std;
/**************************/
/*栈的函数*/
struct Stack
{
int *stack;
int base;
int top;
};
Stack* CreateStack(int Capacity)//创建栈
{
Stack *S = new Stack;
S->stack = new int;
S->base = 0;
S->top = -1;
return S;
}
void DestroyStack(Stack *S) //销毁栈
{
delete S;
S = NULL;
}
bool EmptyStack(Stack *S) //判断栈是否为空
{
if (S->top == -1)
return false;
else
return true;
}
void PushStack(Stack *S, int elem) //出栈
{
S->top++;
S->stack = elem;
}
void PopStack(Stack *S) //入栈
{
if (EmptyStack(S))
S->top--;
}
int TopStack(Stack *S) //返回栈顶元素
{
return S->stack;
}
/************************/
/************************/
/************************/
/****辅助深度优先算法判断是否是死的函数***/
struct BBS
{
int right = 0;
int upside = 1;
int left = 2;
int below = 3;
};
void CCC(BBS *S, int n)
{
if (n == 0)
S->right = -1;
if (n == 1)
S->upside = -1;
if (n == 2)
S->left = -1;
if (n == 3)
S->below = -1;
}
bool AA(BBS *S)
{
if (S->below == -1 && S->left == -1 && S->right == -1 && S->upside == -1)
return 0;
else
return 1;
}
void BB(BBS *S)
{
S->right = 0;
S->upside = 1;
S->left = 2;
S->below = 3;
}
/******************/
/******************/
struct Coordinate//迷宫点类
{
bool Judgment = 1; //判断是否为墙，1为是，0为不是
bool Judgemet_2 = 0;//prim算法用到，深度优先算法没用
};
struct Coordinated//prim算法用到，深度优先算法没用
{
int adress;
};
/*********************/
/********prime算法***********/
void Sequence(Coordinated *Arry, int n, int &sum) //把元素从数组删除
{
int i;
for (i = n; i < sum; i++)
{
Arry = Arry;
}
sum--;
}
void Store(Coordinated *map_1, Coordinate *map_2, int map, int &k, int n) //把元素储存进数组
{
if (((map + 2) % n != 0)&&map_2.Judgemet_2 == 0)
{
map_1.adress = map + 1;
map_2.adress].Judgemet_2 = 1;
k++;
}
if (((map - 1) % n != 0) && map_2.Judgemet_2 == 0)
{
map_1.adress = map - 1;
map_2.adress].Judgemet_2 = 1;
k++;
}
if (((map - n) / n != 0) && map_2.Judgemet_2 == 0)
{
map_1.adress = map - n;
map_2.adress].Judgemet_2 = 1;
k++;
}
if (((map + n) / n != n - 1) && map_2.Judgemet_2 == 0)
{
map_1.adress = map + n;
map_2.adress].Judgemet_2 = 1;
k++;
}
}
void PrimeMap(Coordinate *map, int n)
{
Coordinated *map2 = new Coordinated[(n*n-3*n-2)/2];
srand((unsigned)time(0));
int k = 2;
map2.adress = n + 2;
map2.adress = 2 * n + 1;
map.Judgemet_2 = 1;
map.Judgemet_2 = 1;
int b;
while(k!=0)
{
b = rand() % k;
if ((map2.adress / n) % 2 == 0)
if (map.adress + n].Judgment + map.adress - n].Judgment > 0)
{
map.adress + n].Judgment = 0;
map.adress].Judgment = 0;
map.adress - n].Judgment = 0;
Store(map2, map, map2.adress + n, k, n);
Store(map2, map, map2.adress - n, k, n);
Sequence(map2, b, k);
continue;
}
else
{
Sequence(map2, b, k);
continue;
}
if ((map2.adress / n) % 2 == 1)
if (map.adress + 1].Judgment + map.adress - 1].Judgment > 0)
{
map.adress + 1].Judgment = 0;
map.adress].Judgment = 0;
map.adress - 1].Judgment = 0;
Store(map2, map, map2.adress + 1, k, n);
Store(map2, map, map2.adress - 1, k, n);
Sequence(map2, b, k);
continue;
}
else
{
Sequence(map2, b, k);
continue;
}
}
map.Judgment = 0;
map.Judgment = 0;
delete map2;
}
/*******prim算法**********/
/***********************/
/***********************/
/***图的深度优先算法***/
void CreateMap(Coordinate *map,int n) //生成迷宫数组的函数，map为指向数组的指针，n为迷宫大小
{
/*初始化数据*/
int k = 0;
int b;
int Num = (n - 1) / 2;
enum Direction { right, upside, left, below }; //方向
BBS *Q = new BBS;
Stack *ABS = CreateStack(Num*Num);
srand((unsigned)time(0)); //随机数种子
PushStack(ABS, n+1);
map.Judgment = 0;
//生成一个储存迷宫信息的数组
while (EmptyStack(ABS))
{
//如果栈为空，则退出
if (!AA(Q))
{
PopStack(ABS);
BB(Q);
continue;
}
b = rand() % 4; //随机数
CCC(Q, b);
//生成迷宫算法
switch (b)
{
case right:
if ((TopStack(ABS) + 2) % n != 0)
{
if (map.Judgment == 1)
{
map.Judgment = 0;
map.Judgment = 0;
PushStack(ABS, TopStack(ABS) + 2);
BB(Q);
break;
}
else
break;
}
else
break;
case upside:
if (TopStack(ABS) - 2 * n > 0)
{
if (map.Judgment == 1)
{
map.Judgment = 0;
map.Judgment = 0;
PushStack(ABS, TopStack(ABS) - 2 * n);
BB(Q);
break;
}
else
break;
}
else
break;
case left:
if ((TopStack(ABS) - 1) % n != 0)
{
if (map.Judgment == 1)
{
map.Judgment = 0;
map.Judgment = 0;
PushStack(ABS, TopStack(ABS) - 2);
BB(Q);
break;
}
else
break;
}
else
break;
case below:
if (TopStack(ABS) + 2 * n < n*n-1)
{
if (map.Judgment == 1)
{
map.Judgment = 0;
map.Judgment = 0;
PushStack(ABS, TopStack(ABS) + 2 * n);
BB(Q);
break;
}
else
break;
}
else
break;
}
}
//设置起点和出口
map.Judgment = 0;
map.Judgment = 0;
DestroyStack(ABS);
delete Q;
}
/***********************/
/***图的深度优先算法***/
Stack* Pathfinding(Coordinate *map,int n) //寻找迷宫路径的函数，返回一个储存路径的栈，map为指向迷宫数组的指针，n为迷宫大小
{
int k = 1;
Stack *x = CreateStack(n*n);
Stack *v = CreateStack(n*n);
PushStack(x, 1);
PushStack(x, n + 1);
while (1)
{
map].Judgment = 1;
if (map.Judgment == 0)
{
map].Judgment = 0;
PushStack(x, TopStack(x) + 1);
k++;
continue;
}
else if (map.Judgment == 0 && TopStack(x) + n < (n*n - 1))
{
map].Judgment = 0;
PushStack(x, TopStack(x) + n);
k++;
continue;
}
else if (map.Judgment == 0)
{
map].Judgment = 0;
PushStack(x, TopStack(x) - 1);
k++;
continue;
}
else if (map.Judgment == 0 && TopStack(x) - n > 0)
{
map].Judgment = 0;
PushStack(x, TopStack(x) - n);
k++;
continue;
}
else if (TopStack(x) == n * n - 2)
{
map].Judgment = 0;
while (EmptyStack(x))
{
PushStack(v, TopStack(x));
PopStack(x);
}
DestroyStack(x);
return v;
}
else
{
map.Judgment = 1;
PopStack(x);
map.Judgment = 0;
k--;
}
}
}
void picture_one(Coordinate *map, int n) //画迷宫的函数，map为指向储存迷宫数组的指针，n为迷宫大小
{
// 初始化图形模式
initgraph(n*10, n*10);
//画图，黑色为墙，白色为通路
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
if (map.Judgment == 0) {
setfillcolor(WHITE);
solidrectangle(x * 10, y * 10, x * 10 + 10, y * 10 + 10);
}
else
{
//Sleep(10);
setfillcolor(BLACK);
solidrectangle(x * 10, y * 10, x * 10 + 10, y * 10 + 10);
}
}
}
getchar(); // 按任意键继续
}
void picture_two(Stack *s,int n)//画迷宫路径的函数，s为储存迷宫路径的函数，n为迷宫大小
{
int num;
int x, y;
setfillcolor(RED); //颜色
while (EmptyStack(s))
{
num = TopStack(s);
PopStack(s);
x = num / n;
y = num % n;
solidrectangle(x * 10, y * 10, x * 10 + 10, y * 10 + 10);//画矩阵
Sleep(10);
}
getchar(); //按任意键继续
closegraph(); //关闭幕布
}
int main()
{
int n = 2;
int b;
while (n % 2 == 0)
{
cout << "请输入迷宫大小（大小为奇数）：";
cin >> n;
cout << endl;
}
Coordinate*s = NULL;
while (s == NULL)
s = new Coordinate;
cout << "1:深度遍历" << endl;
cout << "2：prim算法" << endl;
cin >> b;
switch (b)
{
case 1:CreateMap(s, n); break;
case 2:PrimeMap(s, n); break;
}
cin.ignore();
picture_one(s, n);
Stack *Q = Pathfinding(s, n);
picture_two(Q, n);
delete s;
DestroyStack(Q);
return 0;
} 估计要学一个星期 提醒下，我看了作者的代码，作者的在生成地图上下左右那一块是反的，大家注意
我贴出相关代码，因为这一点我都有点看不懂代码了
61行 struct BBS
{
/*int right = 0;
int upside = 1;
int left = 2;
int below = 3;*/
int right = 3;
int upside = 2;
int left = 1;
int below = 0;
};
213行 enum Direction { below,left,upside,right}; //方向
//生成迷宫算法
239行 switch (b)//在设置成挖掘过的路方向b进行挖掘2个方块操作
{
//下方向0
case below:
if ((TopStack(ABS) + 2) % n != 0)
{
if (map.Judgment == 1)
{
map.Judgment = 0;
map.Judgment = 0;
PushStack(ABS, TopStack(ABS) + 2);
BB(Q);
break;
}
else
break;
}
else
break;
//左方向1
case left:
if (TopStack(ABS) - 2 * n > 0)
{
if (map.Judgment == 1)
{
map.Judgment = 0;
map.Judgment = 0;
PushStack(ABS, TopStack(ABS) - 2 * n);
BB(Q);
break;
}
else
break;
}
else
break;
//上方向2
case upside:
if ((TopStack(ABS) - 1) % n != 0)
{
if (map.Judgment == 1)
{
map.Judgment = 0;
map.Judgment = 0;
PushStack(ABS, TopStack(ABS) - 2);
BB(Q);
break;
}
else
break;
}
else
break;
//右方向3
case right:
if (TopStack(ABS) + 2 * n < n * n - 1)
{
if (map.Judgment == 1)
{
map.Judgment = 0;
map.Judgment = 0;
PushStack(ABS, TopStack(ABS) + 2 * n);
BB(Q);
break;
}
else
break;
}
else
break;
} 可以可以学习 以前就有能生成迷宫這個想法，這個值得學習，收下來慢慢研究看看，謝謝樓主的分享。 感谢分享 看到这种技术帖子热血沸腾,就是有点看不懂,保存下来慢慢学习
感谢分享 谢了楼主， 那我分享下easyX
http://t.cn/EiMrAXC
页:
[1]
2