[JAVA] 랜덤 미로 만들기
저번주쯤 만들다가 포기했던 랜덤 미로 생성기..
새로운 방식이 떠올라 제작해보았다..!
결과는
나름 성공적이다.
구상은 다음과 같다.
1. 테두리는 모두 벽으로 감싼다 (출발, 도착지점 제외)
2. 못가는 길 없이 모든 길을 연다
3. 길과 길 사이에는 무조건 벽이 있어야 한다. (갈림길 제외)
이러한 구상에 따라 미로 규모가 원하는 길의 갯수(각 행, 열마다 줄의 수) * 2 + 1 로 표현했다.
저번주 구상에서는 해당 칸은 미리 값을 바꿔두고 근처에 길을 랜덤으로 뚫어 만드는 것이었다.
그 결과
이러한 괴랄한 코드가 나오며 못가는 길도 생기고, 도착할 수 없는 경우도 생기는 코드가 완성되었따..
대략 이런 느낌..?
그 후 내려놓고 있다가 새롭게 깨달은 방식..!
시작은 아래와 같다.
먼저 미로 크기를 입력받고 기존 계산처럼 * 2 한 후 +1을 해주어 미로 사이즈로 사용하였다.
입력 값을 토대로 맵을 만들고, (홀수,홀수)는 무조건 뚫려야하기 때문에 막히지 해당 좌표에 아직 뚫지 못한 곳의 갯수를 측정하기 위해 cntLeft라는 변수를 따로 지정했다. 여기서 -2 는 시작점과 도착점을 미리 뚫어두기 때문.
그 후 맵 출력을 위해 System.out.print 해주면
아래와 같이나온다 (setLoad 안한경우)
그리고 길을 뚫기 위해 시작점의 홀수좌표인 (1,1)부터 상,하,좌,우 방향을 랜덤으로 움직이기위해 move를 만들어주고,
마지막으로 setLoad를 설정해준다.
앞서 말했듯 시작점의 좌표를 y,x(1,1)로 잡아두고, move()에서 나온 랜덤 값을 기반으로
y,x 좌표 py,px에 복사해준다.
여기서 다음칸으로 갈 수 있다면 (좌표 밖이 아니라면) py, px를 2씩 증감시켜주고
y, x는 1씩 증감시켜줬다. (해당 방향으로 진행하는 경로 뚫는 용도)
이후 boolea isMove를 이용해 움직일 수 있다면 맵 좌표 값을 변경해 줄 것이다.
먼저, 나아갈 길이 이미 뚫어놓은 길이 아닐 경우 이동 경로 및 이동 후 좌표 모두 길(1)로 바꿔준다.
이때, 앞서 만들어둔 cntLeft를 1 감소시킨다.
만약, 이미 뚫린 길이라면 기존 자리를 유지하며 cntRs라는 놈을 증가시켜준다
이 cntRs는 무한반복 방지를 위해 랜덤 4가지 방향을 50번정도 돌려도 못가면 더 못간다고 임의 판단하여
뚫어놓은 길 중 출발점, 끝점을 제외한 홀수 좌표를 랜덤으로 받아 해당 좌표에서 다시 길을 뚫는 방식이다.
만약 위에 길이 있는데 50번동안 위가 안나와 덜 뚫고 갔더라도 cntLeft가 감소하지 않았기에 언젠가 다시 시도할 수 있다.
그리하면, cntLeft가 0이되는순간 모든 길은 뚫렸을 것이다.
다만, 도착지점은 뚫지 않았기에 마지막에 도착 좌표 map[size-2][size-2]의 위 또는 왼쪽을 랜덤으로 하나 뚫어준다.
이렇게하면 작은 미로부터
큰 미로까지 모두 생성 가능하다..!
일단 지금까지는 막히는 길 없이 모든 길을 갈 수 있고, 사이즈를 늘리면 생각보다 빡세다..
---- 출력 없이 기능만 돌려본 결과 입력 값 500에선 한 2-3초 걸렸고, 1000은 10초넘길래 무서워서 정지했다..
---- 오류나 피드백 있으시면 말씀해주시면 감사드리겠습니다..!
*** 다 해놓고 느낀거지만 setLoad가 아니고 setRoad였어야 했다는 것.... 미천한 영어실력에 이마를 짚고 간다.^-^