求一个随机生成迷宫的算法~
就是求一个能自动生成地图的迷宫算法……并且保证要有出口解~这个我一时也实现不了发个贴来看看怎么弄
~~~
程序代码:#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 22
void makeline(int a[][N],int x1,int y1,int x2,int y2)
{//产生直线路径
int xs=x2-x1,ys=y2-y1;
double k,w1,w2;
k=(double)ys/((double)xs+0.00001);
xs=xs<0?-1:(xs>0?1:xs);
ys=ys<0?-1:(ys>0?1:ys);
while(x1!=x2||y1!=y2)
{
a[x1][y1]=0;
if(xs&&ys)
{
w1=k-(y2-y1)/((double)(x2-x1-xs)+0.00001);
w2=k-(y2-y1-ys)/((double)(x2-x1)+0.00001);
if(w1<0)w1=-w1;
if(w2<0)w2=-w2;
if(w1<w2)x1+=xs;
else y1+=ys;
}
else
{
if(xs)x1+=xs;
else y1+=ys;
}
}
a[x1][y1]=0;
}
void makepath(int a[][N])
{
//产生随机路径
int i,j,k,x1,x2,y1,y2;
for(i=0; i<N; i++)
{
for(j=0; j<N; j++)
{
k=rand()%1000;
if(k>100&&k<350&&i>0&&i<N-1&&j>0&&j<N-1)a[i][j]=0; //产生随机点
else a[i][j]=1;
}
}
x1=x2=y1=y2=1;
for(i=0;i<12;i++)
{
x2=rand()%(N-2)+1;
y2=rand()%(N-2)+1;
makeline(a,x1,y1,x2,y2); //产生12根随机直线,第一根线起点是入口,最后一根线终点在出口
x1=x2;
y1=y2;
}
x2=y2=N-2;
makeline(a,x1,y1,x2,y2);
a[1][0]='I';
a[N-2][N-1]='O';
}
int main()
{
int a[N][N];
int i,j;
srand((unsigned)time(NULL));
makepath(a);
for(i=0; i<N; i++)
{
for(j=0; j<N; j++)
{
if(a[i][j]>32)printf("%c%c",a[i][j],a[i][j]);
else if(a[i][j])printf("■");
else printf(" ");
}
printf("\n");
}
return 0;
}