기원:
작년 (중학교 첫 학기), 나는 작은 게임을 쓰는 것을 좋아했기 때문에 미로를 쓰고 싶었습니다.
프로그램 효과 :
공간을 누르려면 경로를 표시합니다.
사고 과정 :
미로는 그리드로 구성되며 출구 입구에서 하나의 경로 만 필요합니다.
다양한 데이터 구조에 대해 생각한 후에는 나무가 더 적합한 것으로 보이며 루트 노드에서 각 하위 노드까지의 경로 만있는 것으로 보입니다. 입구가 루트 노드이고 출구가 트리의 하위 노드라고 가정하면 루트 노드에서 하위 노드까지의 경로는 독특합니다.
따라서 모든 그리드를 덮도록 트리를 구성 할 수 있다면 미로를 만들 수 있습니다.
또한 트리의 부모와 자식 노드는 인터페이스에 인접한 그리드 여야합니다.
인터페이스를 표시 할 때, 상위 노드와 하위 노드 사이에 공유되는 모서리가 그려지지 않고 다른 가장자리가 그려지면 미로를 그릴 수 있습니다.
그런 다음 그런 나무를 구현하는 방법에 대해 생각했습니다.
처음 두 질문 :
1. 나무는 어떻게 표현됩니까?
2.이 나무를 구성하는 방법은 무엇입니까?
1. 나무는 어떻게 표현됩니까?
이 트리가 이진 트리를 쓰는 것과 같이 구현된다고 가정하면, 각 트리 노드는 그리드를 나타 내기 위해 좌표 (x, y)를 저장해야하며 4 개의 포인터를 저장해야합니다. 일부 포인터는 비어 있고, 일부는 비어 있고, 일부는 비어 있지 않으며, 자식 노드에 비어 있지 않은 포인터가 없으며, 하위 노드는 이웃 그리드의 좌표를 저장합니다. 이를 수행하는 가장 큰 문제는 모든 그리드가 나무에 있는지 여부를 결정하는 것이 불가능하다는 것입니다. 어쩌면 2 차원 배열도 플래그 어레이로 사용됩니다.
미로의 그리드를 나타 내기 위해 2 차원 배열을 사용한다고 가정 해 봅시다. 각 배열 요소는 상위 노드에 대한 참조를 저장하고 가상 트리를 형성 할 수도 있습니다. 따라서 N*n의 2 차원 배열은 n*n 그리드를 나타내고 각 배열 요소 (격자)는 부모 노드를 참조합니다. 또한 그리드의 좌표를 쉽게 얻으려면 좌표 정보도 저장해야합니다.
2.이 나무를 구성하는 방법은 무엇입니까?
먼저 루트 노드로 그리드를 선택하십시오. 미로의 모양을 충분히 무작위로 만들기 위해, 나는 루트 노드로 좌표를 무작위로 생성하기로 결정했다. 실제로 결정된 좌표를 선택해도 괜찮습니다.
그렇다면이 트리에 노드를 추가하는 방법은 무엇입니까?
나는 여기서 많은 우회를했다. 처음에 나는 지금 역 추적과 유사한 알고리즘을 생각했지만 (당시 역 추적 알고리즘을 몰랐지만) 시간 복잡성은 매우 높습니다. 아마도 미로가 64*64 인 경우 알고리즘은 결과를 얻지 못할 것입니다.
그런 다음 깊이 검색을 스캔하는 방법도 역 추적합니다. 스캔 할 때마다 현재 트리의 노드를 찾아 이웃 그리드가 트리에 있는지 확인합니다. 나무가없는 경우 이웃 그리드를 나무에 추가하십시오. 이미 나무에있는 경우 다음 이웃 그리드를보십시오. 노드의 모든 이웃 그리드가 트리에있는 경우 다음 노드를 찾아 동일한 작업을 계속하십시오. 또한 미로를 무작위로 생성하기 위해 스캔의 시작 위치는 무작위입니다. 그러나이 방법에 의해 생성 된 미로의 경로는 항상 내가 원하는 비난적이고 심도있는 효과를 얻을만큼 깊지 않습니다. 결국, 그것은 폭 검색과 비슷한 방법입니다. 더욱이, 이것을하는 것은 항상 무차별적인 힘에 의존하는 것처럼 보이며 알고리즘은 똑똑하고 간결하지 않습니다.
마침내 마침내 심층적 인 검색을 사용하는 것을 생각했습니다. . 아마도 1 년 동안 데이터 구조를 배웠고 너무 많이 실천하지 않았기 때문에 내가 생각해야 할 첫 번째 방법을 생각한 적이 없습니다. .
루트 노드로 그리드를 무작위로 선택하고, 시작하여 깊이 검색하고, 갈 길이 없을 때까지 길을 열고, 한 단계를 퇴각하고, 다른 방법으로 변경 한 다음, 갈 길을 걸지 않고 한 걸음 뒤로 물러서서 다른 길을 바꾸십시오 ...이 사이클은 갈 길이 없을 때까지 계속됩니다. . . 사실, 그것은 여전히 역 추적입니다.
이 프로그램에서 다음 과정은 (자세한 내용은 코드의 Createmaze () 함수 참조)입니다.
루트 노드로 그리드를 무작위로 선택하고 스택으로 밀어 넣으십시오.
그런 다음 스택이 비어 있지 않으면 다음 루프를 실행하십시오.
그리드를 꺼내어 intree 플래그를 1으로 설정 한 다음 트리에 있지 않은 이웃 그리드를 스택에 (무작위로) 밀어 넣고이 이웃 그리드의 아버지가 그리드를 가리 키게하십시오.
이 두 가지 문제를 해결 한 후, 미로의 나머지 그림, 경로 표시 및 움직이는 공은 비교적 간단합니다.
암호
패키지 Maze; import java.awt.color; import java.awt.graphics; import java.awt.event.keyadapter; import java.awt.event.keyevent; import java.util.random; import java.util.stack; import javax.swing.jframe; javax.swing; joptional. javax.swing.jpanel; 클래스 격자 {static final int intree = 1; 정적 최종 int notintree = 0; 개인 int x = -1; 개인 int y = -1; 개인 int 플래그 = notintree; 사적인 격자 아버지 = null; 공개 격자 (int xx, int yy) {x = xx; y = yy; } public int getx () {return x; } public int gety () {return y; } public int getflag () {반환 플래그; } 공개 격자 getfather () {반환 아버지; } public void setfather (격자 f) {아버지 = f; } public void setflag (int f) {flag = f; } public String toString () {return new String ( "(" + x + "," + y + ")/n"); }} public class 미로 확장 jpanel {private static final long serialversionuid = -83003339045454852626L; 개인 int num, 너비, 패딩; // 너비 각 그리드 개인 격자의 너비와 높이 [] [] 미로; Private Int Ballx, Bally; 개인 부울 드로우트 = 거짓; 미로 (int m, int wi, int p) {num = m; 너비 = wi; 패딩 = P; 미로 = 새로운 격자 [num] [num]; for (int i = 0; i <= num-1; i ++) for (int j = 0; j <= num-1; j ++) 미로 [i] [J] = 새로운 격자 (i, j); Createmaze (); setkeylistener (); this.setfocusable (true); } private void init () {for (int i = 0; i <= num-1; i ++) for (int j = 0; j <= num-1; j ++) {maze [i] [j] .setfather (null); 미로 [i] [j] .setflag (Lattice.notintree); } ballx = 0; 발리 = 0; drawpath = false; Createmaze (); // setKeylistener (); this.setfocusable (true); 리 페인트 (); } public int getCenterx (int x) {리턴 패딩 + x * 너비 + 너비 / 2; } public int getCencery (int y) {리턴 패딩 + y * 너비 + 너비 / 2; } public int getCenterx (Lattice p) {return padding + p.gety () * 너비 + 너비 / 2; } public int getCencery (격자 p) {return padding + p.getx () * 너비 + 너비 / 2; } private void checkiswin () {if (ballx == num-1 && 1 && bally == num-1) {joptionpane.showmessagedialog (null, "당신은 승리!", "당신은 미로에서 나갔습니다.", joptionpane.plain_message); init (); }} 동기화 된 개인 무효 이동 (int c) {int tx = ballx, ty = bally; // system.out.println (c); 스위치 (c) {case keyevent.vk_left : ty-; 부서지다; CASE keyEvent.vk_right : ty ++; 부서지다; case keyEvent.vk_up : tx-; 부서지다; CASE keyEvent.VK_Down : TX ++; 부서지다; case keyEvent.vk_space : if (drawpath == true) {drawpath = false; } else {drawpath = true; } 부서지다; 기본값 :} if (! isoutofborder (tx, ty) && (maze [tx] [ty] .getfather () == 미로 [ballx] [bally] || maze [ballx] [bally] .getfather () == maze [tx] [ty]) {ballx = tx; Bally = ty; }} private void setKeylistener () {this.addkeylistener (new keyadapter () {public void keypressed (keyEvent e) {int c = e.getKeyCode (); move (c); Repaint (); CheckisWin ();}}); } private boolean isoutofborder (Lattice p) {return isoutofborder (p.getx (), p.gety ()); } private boolean isoutofborder (int x, int y) {return (x> num -1 || y> num -1 || x <0 || y <0)? 사실 : 거짓; } private lattice [] getneis (Lattice p) {final int [] adds = {-1, 0, 1, 0, -1}; // 순서는 상단, 오른쪽, 왼쪽, if (isoutofborder (p)) {return null; } 격자 [] ps = 새로운 격자 [4]; // 순서는 상단, 오른쪽, 왼쪽, int xt입니다. int yt; for (int i = 0; i <= 3; i ++) {xt = p.getx ()+adds [i]; yt = p.gety () + 추가 [i + 1]; if (isoutofborder (xt, yt)) 계속; ps [i] = 미로 [xt] [yt]; } 반환 ps; } private void createmaze () {random random = new random (); int rx = math.abs (random.nextint ()) % num; int ry = math.abs (random.nextint ()) % num; 스택 <Lattice> s = 새로운 스택 <격자> (); 격자 p = 미로 [rx] [ry]; 격자 neis [] = null; s.push (p); while (! s.isempty ()) {p = s.pop (); p.setflag (lattice.intree); neis = getneis (p); int ran = math.abs (random.nextint ()) % 4; for (int a = 0; a <= 3; a ++) {ran ++; RAN %= 4; if (neis [ran] == null || neis [ran] .getflag () == lattice.intree) 계속; s.push (neis [Ran]); Neis [RAN] .SETFATHER (P); }} // ChangeFather (미로 [0] [0], NULL); } private void changefather (격자 P, 격자 F) {if (p.getfather () == null) {p.setfather (f); 반품; } else {changefather (p.getfather (), p); }} private void clearfence (int i, int j, int fx, int fy, graphics g) {int sx = padding + ((j> fy? j : fy) * width), sy = padding + ((i> fx? i : fx) * width), dx = (i == fx? sx + width), dy == fx? if (sx! = dx) {sx ++; DX-; } else {sy ++; dy--; } G.DrawLine (SX, SY, DX, DY); } 보호 된 void paintcomponent (그래픽 g) {super.paintcomponent (g); for (int i = 0; i <= num; i ++) {g.drawline (패딩 + i * 너비, 패딩, 패딩 + i * 너비, 패딩 + num * 너비); } for (int j = 0; j <= num; j ++) {g.drawline (패딩, 패딩 + j * 너비, 패딩 + num * 너비, 패딩 + j * 너비); } g.setColor (this.getBackground ()); for (int i = num-1; i> = 0; i-) {for (int j = num-1; j> = 0; if (f! = null) {int fx = f.getx (), fy = f.gety (); Clearfence (I, J, FX, FY, G); }}} G.DrawLine (패딩, 패딩 + 1, 패딩, 패딩 + 너비 -1); int last = padding + num * 너비; G.DrawLine (마지막, 마지막 -1, 마지막, 마지막 - 너비 + 1); g.setcolor (color.red); g.filloval (getCenterx (Bally) - 너비 / 3, getCentery (ballx) - 너비 / 3, 너비 / 2, 너비 / 2); if (drawpath == true) drawpath (g); } private void drawpath (그래픽 g) {color path_color = color.orange, bo_path_color = color.pink; if (drawpath == true) g.setcolor (path_color); else g.setcolor (this.getbackground ()); 격자 P = 미로 [Num -1] [Num -1]; while (p.getfather ()! = null) {p.setflag (2); p = p.getfather (); } g.filloval (getCenterx (p) - 너비 / 3, getCentery (p) - 너비 / 3, 너비 / 2, 너비 / 2); p = 미로 [0] [0]; while (p.getfather ()! = null) {if (p.getflag () == 2) {p.setflag (3); g.setcolor (모두 _path_color); } g.Drawline (getCenterx (p), getCentery (p), getCenterx (p.getfather ()), getCenter (p.getfather ()); p = p.getfather (); } g.setColor (path_color); p = 미로 [num -1] [num -1]; while (p.getfather ()! = null) {if (p.getflag () == 3) break; G.DrawLine (getCenterx (p), getCentery (p), getCenterx (p.getfather ()), getCencer (p.getfather ()); p = p.getfather (); }} public static void main (String [] args) {Final int n = 30, 너비 = 600, 패딩 = 20, lx = 200, ly = 100; JPANEL P = New Maze (N, (폭 - 패딩 - 패딩) / N, 패딩); jframe frame = new Jframe ( "미로 (Show 또는 Hide Paths By Space Bar)"); frame.getContentPane (). add (p); frame.setDefaultCloseOperation (jframe.exit_on_close); frame.setsize (너비 + 패딩, 너비 + 패딩 + 패딩); frame.setLocation (lx, ly); frame.setVisible (true); }}