최근에 나는 종종 반 친구들이 컴퓨터 실에서 미로 게임을하는 것을 본다. 아주 흥미 롭습니다. 또한 Java를 사용하여 임의의 미로 생성을 구현하기 위해 알고리즘을 작성합니다. 실제로, 그것은 그래프의 깊이 우선 트래버스 알고리즘입니다. 기본 아이디어는 미로의 모든 지점에 네 개의 벽이 있다는 것입니다.
1. 모든 지점에서 시작 (내 알고리즘이 지점에서 시작하도록 고정되어) 4 방향 중 하나를 방문하십시오 (접근 가능한 지점에 액세스 할 때마다 해당 지점의 해당 방향으로 벽을 제거 할 때마다 액세스 포인트는 계속 해서이 방향으로 액세스 할 수 있습니다.
2. 방문 된 각 지점은 액세스 된 것으로 식별됩니다. 포인트가 특정 방향에 액세스하면 먼저 액세스 포인트가 액세스되었는지 또는 경계에 닿는 지 결정합니다. 포인트의 네 방향이 모두 액세스되거나 액세스 할 수없는 경우 이전 지점으로 돌아갑니다. 이전 시점은 프로세스를 계속합니다.
이런 식으로 순회 한 후, 각 지점이 방문되었음을 확인할 수 있습니다. 또한, 각 접근의 방향은 무작위이므로, 많은 다른 트래버스 상황이 형성 될 것이다. 동시에, 각각의 두 지점 사이의 경로는 독특하며, 이는 다른 미로를 형성하며 시작점에서 종료점까지의 고유 한 경로 만 있습니다. 이것은 그래프의 깊이 이동 알고리즘의 특성에 의해 결정됩니다. 알고리즘의 구현에서 가장 중요한 것은 스택을 사용하는 것입니다. 처음으로 먼저 첫 번째 지점을 스택으로 누릅니다. 포인트가 액세스 할 때마다 포인트가 스택으로 밀려 나면 스택 상단의 포인트에 4 방향으로 포인트에 액세스 한 다음 새 지점에 액세스 한 다음 새 지점을 누르면이 점의 4 방향이 접근 할 수 없으면 스택에서 포인트를 철회 할 수 있습니다. 스택 출구의 모든 지점이있을 때까지 우리의 횡단이 성공할 것입니다. 이것은 재귀 과정입니다. 이 알고리즘은 자연스럽게 재귀 적 방법으로 구현 될 수 있습니다. 그러나 여기서는이 작업을 수행하지만 스택으로 배열로 수동으로 구현합니다. 하하 ~~ 너무 많이 말한 후, 내가 표현하고 싶은 것이 표현되는지 모르겠습니다. 그러나 내 특정 코드 디자인이 잘 작성되지 않았으며 개선과 최적화가 부족한 곳이 여전히 많습니다. 그것은 단지 알고리즘 운동 일뿐입니다. 다음은 두 주요 클래스의 핵심 코드입니다. 프레젠테이션 계층의 코드는 매우 사소하기 때문에 게시하지 않습니다.
렌더링은 다음과 같습니다.
미로 수업 :
// 저자 : Zhongzw // 이메일 : [email protected] 패키지 cn.zhongzw.model; java.util.arraylist 가져 오기; java.util.random import; 공개 클래스 mazemodel {private int width = 0; 개인 int 높이 = 0; 개인 랜덤 RND = 새로운 랜덤 (); public mazemodel () {this.width = 50; // 미로 너비 this.height = 50; // maze height} public int getWidth () {리턴 너비; } public void setwidth (int width) {this.width = 너비; } public int getheight () {리턴 높이; } public void setheight (int 높이) {this.height = 높이; } public mazemodel (int width, int height) {super (); this.width = 너비; this.height = 높이; } public arraylist <MazePoint> getMaze () {ArrayList <MazePoint> Maze = New ArrayList <MazePoint> (); for (int h = 0; h <height; h ++) {for (int w = 0; w <width; w ++) {mazepoint point = new MazePoint (w, h); maze.add (포인트); }} return createmaze (미로); } private arraylist <MazePoint> Createmaze (ArrayList <MazePoint> Maze) {int top = 0; int x = 0; int y = 0; ArrayList <MazePoint> Team = New ArrayList <MazePoint> (); team.add (maze.get (x + y * width)); while (top> = 0) {int [] val = new int [] {-1, -1, -1, -1}; int times = 0; 부울 플래그 = 거짓; mazepoint pt = (mazepoint) team.get (상단); x = pt.getx (); y = pt.gety (); pt.Visted = true; ro1 : while (times <4) {int dir = rnd.nextint (4); if (val [dir] == dir) 계속; else val [dir] = dir; switch (dir) {case 0 : // 왼쪽 if ((x -1)> = 0 && maze.get (x -1 + y * width) .visted == false) {maze.get (x + y * width) .pepleft (); maze.get (x -1 + y * 너비) .setright (); team.add (maze.get (x -1 + y * 너비)); 상단 ++; flag = true; 브레이크 ro1; } 부서지다; 사례 1 : // 오른쪽 if ((x + 1) <width && maze.get (x + 1 + y * width) .visted == false) {maze.get (x + y * width) .setright (); maze.get (x + 1 + y * 너비) .setleft (); team.add (maze.get (x + 1 + y * 너비)); 상단 ++; flag = true; 브레이크 ro1; } 부서지다; 사례 2 : // if ((y -1)> = 0 && maze.get (x + (y -1) * 너비) .Visted == false) {maze.get (x + y * width) .setup (); maze.get (x + (y -1) * 너비) .setdown (); team.add (maze.get (x + (y -1) * 너비); 상단 ++; flag = true; 브레이크 ro1; } 부서지다; 사례 3 : // 아래 ((y + 1) <height && maze.get (x + (y + 1) * 너비) .Visted == false) {maze.get (x + y * width) .setdown (); maze.get (x + (y + 1) * 너비) .setup (); team.add (maze.get (x + (y + 1) * 너비); 상단 ++; flag = true; 브레이크 ro1; } 부서지다; } times += 1; } if (! flag) {team.remove (상단); 상단 -= 1; }} 리턴 미로; }}
미로
// 저자 : Zhongzw // 이메일 : [email protected] 패키지 cn.zhongzw.model; java.util.*; java.lang.*; 공개 클래스 mazepoint {private int left = 0; 개인 int right = 0; 개인 int up = 0; 개인 int down = 0; 개인 int x; 개인 in y; 공개 부울 목격; public mazepoint (int x, int y) {this.x = x; this.y = y; } public int getleft () {return left; } public void setleft () {this.left = 1; } public int getright () {return right; } public void setright () {this.right = 1; } public int getup () {return Up; } public void setup () {this.up = 1; } public int getDown () {return down; } public void setDown () {this.down = 1; } public int getx () {return x; } public void setx (int x) {this.x = x; } public int gety () {return y; } public void sety (int y) {this.y = y; }}
위는이 기사의 모든 내용입니다. 모든 사람의 학습에 도움이되기를 바랍니다. 모든 사람이 wulin.com을 더 지원하기를 바랍니다.