程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 程序自動生成迷宮

程序自動生成迷宮

編輯:關於C

 

算法是隨便想的,如下:

首先迷宮初始化全部為牆

然後隨機選擇從中間一個點開始,

開始遞歸,隨機選擇方向嘗試移動,如果是牆,並且不與其他的路相通,就把牆設置成路。

使用深度優先的方法,從新的點繼續遞歸,如果周圍全部無法走通,則回退到上次節點,選擇其他方向。

如此一直遞歸,直到所有的點都探索完。最終的效果圖如下:

\

 

後來研究下別人的算法,是先假設地圖上有相間隔的點,然後將這些點進行打通,

只要這個點是孤立的,就可以與其他點連通,這樣的算法,會好看些,處理上會簡單很多,

生成的圖形也沒有一個個的小塊。

照例,共享我的源碼咯: http://up.2cto.com/2011/1118/20111118024909417.rar

 

其他人的算法,精煉很多,不過就代碼風格實在是郁悶

// Author: Tanky Woo
// Blog: www.WuTianQi.com
// Brief:  a Maze program
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
#define MAZE_MAX 50
char map[MAZE_MAX+2][MAZE_MAX+2];
const int x = 11, y = 11;
int z1, z2;
 
void printMaze();
void makeMaze();
int searchPath(int, int);
int main()
{
 for(int i=0; i<=x*2+2; ++i)
  for(int j=0; j<=y*2+2; ++j)
   map[i][j] = 1;
 
 makeMaze();
 cout << "Tanky Woo" << endl;
 printMaze();
}
 
void printMaze()
{
    for(z2=1; z2<=y*2+1; z2++)
    {
        for(z1=1;z1<=x*2+1;z1++)
            fputs(map[z2][z1]==0?" ":"█",stdout);
        putchar(10);
    }
 cout << endl;
}
 
void makeMaze()
{
 for(z1=0, z2=2*y+2; z1<=2*x+2; ++z1)
 {
  map[z1][0] = 0;
  map[z1][z2] = 0;
 }
 for(z1=0, z2=2*x+2; z1<=2*y+2; ++z1)
 {
  map[0][z1] = 0;
  map[z2][z1] = 0;
 }
 map[2][1] = 0;
 map[2*x][2*y+1] = 0;
 
 srand((unsigned)time(NULL));
 searchPath(rand()%x+1, rand()%y+1);
}
 
int searchPath(int x, int y)
{
 static int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
 int zx = x*2;
 int zy = y*2;
 int next, turn, i;
 map[zx][zy] = 0;
 turn = rand()%2 ? 1 : 3;
 for(i=0, next=rand()%4; i<4; ++i, next=(next+turn)%4)
  if(map[zx+2*dir[next][0]][zy+2*dir[next][1]] == 1)
  {
   map[zx+dir[next][0]][zy+dir[next][1]] = 0;
   searchPath(x+dir[next][0], y+dir[next][1]);
  }
 return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved