随笔 - 79  文章 - 58  trackbacks - 0
<2011年11月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

常用链接

留言簿(9)

随笔分类

随笔档案

文章档案

相册

搜索

  •  

积分与排名

  • 积分 - 291825
  • 排名 - 87

最新评论

阅读排行榜

评论排行榜

算法是随便想的,如下:

首先迷宫初始化全部为墙

然后随机选择从中间一个点开始,

开始递归,随机选择方向尝试移动,如果是墙,并且不与其他的路相通,就把墙设置成路。

使用深度优先的方法,从新的点继续递归,如果周围全部无法走通,则回退到上次节点,选择其他方向。

如此一直递归,直到所有的点都探索完。最终的效果图如下:

 

后来研究下别人的算法,是先假设地图上有相间隔的点,然后将这些点进行打通,

只要这个点是孤立的,就可以与其他点连通,这样的算法,会好看些,处理上会简单很多,

生成的图形也没有一个个的小块。

照例,共享我的源码咯:

/Files/merlinfang/maze.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<=x*2+1; z2++)
    {
        for(z1=1;z1<=y*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;
}
 

 

posted on 2011-11-17 23:16 merlinfang 阅读(11981) 评论(6)  编辑 收藏 引用 所属分类: v8

FeedBack:
# re: 程序自动生成迷宫 2011-11-18 13:18 阿攀
不错( ^_^ )  回复  更多评论
  
# re: 程序自动生成迷宫[未登录] 2011-11-19 10:16 kkk
那代码风格为何郁闷?  回复  更多评论
  
# re: 程序自动生成迷宫 2011-11-21 17:58 xidiandaily
如果遇到代码风格不适合自己阅读。
可以使用 Astyle 来处理源码。
这样容易阅读得多。

我就是这样做的.
;-)

Astyle链接:http://astyle.sourceforge.net/  回复  更多评论
  
# re: 程序自动生成迷宫 2011-11-21 21:18 merlinfang
不是这个意思,指其他方面,如变量的命名,z1,z2,zx等等,一行语句很复杂等等@xidiandaily
  回复  更多评论
  
# re: 程序自动生成迷宫 2011-11-24 12:36 凤兮归来
哪里是入口,哪里是出口?上面的迷宫你走得通吗?  回复  更多评论
  
# re: 程序自动生成迷宫 2011-11-24 19:18 merlinfang
当然走的通啊,入口出口就左上角和右下角那两个口子。@凤兮归来
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理