求一个随机生成迷宫的算法~
就是求一个能自动生成地图的迷宫算法……并且保证要有出口解~这个我一时也实现不了发个贴来看看怎么弄~~~
程序代码:
#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; }