미로생성 알고리즘, javascript

javascript 를 이용한 미로생성 Class 설명 

MazeClass = function(height,width){     this.height=height;     this.width=width;     this.VisitedCells=1;     this.CurrentCell = {y:1,x:2};     this.CellStack =[];     this.Main();      return this.Maze; }; <code 1>

#설명

생성자 부분 가로세로 값을 인자로 받아서 미로를 생성합니다.

Height와 width를 설정해주고 기본으로 방문한 셀을 1로 만들어 줍니다. (시작위치)

Depth First Search 알고리즘 이용에 스택이 필요하므로 스택으로 사용할 배열설정(CellStack)합니다.

미로 생성 Main()함수로 시작하여 미로를 생성합니다.

미로 생성후 리턴값에 만들어진 미로를 반환합니다. (추후 재사용을 위해)

 

Maze = new MazeClass(15,15);  <- 이 코드는 15x15의 미로를 생성해서 리턴합니다.

 

Main : function (){ //객체 생성시 자동 실행 함수         this.CreateMazeGrid();         this.RandomStartCell();         var TotalCells=this.height*this.width;         while(this.VisitedCells < TotalCells){             var directions = this.FindNeighborCells();             if(directions.length>0) {                 this.selectDir(directions);                 this.VisitedCells++;             }             else this.CurrentCell=this.CellStack.pop();         }     }, <code2>

#설명

MazeClass.prototype에 추가한 Main 메서드로서 미로 생성의 시작입니다.

사용 알고리즘 ( Depth-First Search )
1) Start at a random cell in the grid.  
2) Look for a random neighbor cell you haven't been to yet.  
3) If you find one, move there, knocking down the wall between the cells. If you don't find one, back up to the previous cell.  
4) Repeat steps 2 and 3 until you've been to every cell in the grid.

원문출처 : http://www.mazeworks.com

 

CreateMazeGrid : function(){ //미로 생성함수         this.Maze = new Array(this.height*2+1);         for(var i=0;i<this.Maze.length;i++) this.Maze[i]=new Array(this.width*2+1);         function ImgTypeSelector(y,x){             if(y%2==1 && x%2==1) result='aisle';               else if(y%2==0 && x%2==0) result='dot';             else if(y%2==1 && x%2==0) result='hor';             else if(y%2==0 && x%2==1) result='ver';             return result;         }         function TileTypeSelector(y,x) {             y%2==1 && x%2==1 ? result='tile' : result='wall';             if(y==0||x==0) result='border';                               return result;         }         for(var y=0; y<this.height*2+1; y++){             for(var x=0; x<this.width*2+1; x++){                 var tempCell=new Object();                 tempCell.ImgType=ImgTypeSelector(x,y);                 tempCell.ImgType=='aisle'? tempCell.value='aisle' : tempCell.value='wall';                 tempCell.TileType=TileTypeSelector(x,y);                 tempCell.visited=false;                 this.Maze[y][x]=tempCell;             }         }         return this.Maze;     }, <code3>

#설명

MazeClass.prototype에 추가된 격자생성 메서드입니다.

격자를 생성하고 초기화 합니다.

 

1.     이차원 배열을 생성하고 통로와 점 가로벽 세로벽을 구분하여 생성합니다.

구분은 ImgTypeSelector() 메서드를 사용합니다.

2.     타일 타입을 설정합니다. (벽이 될것인지, 타일이 될것인지 테두리가 될것인지)

TileTypeSelector() 을 이용합니다. ( 자세한내용은 해당 함수 부분에서 설명 )

3.     이중 for문이 돌아가는데 y,x값이 증가되면서

ImgTypeSelector () 와 TileTypeSelector()의 인자로 y,x값이 사용됩니다.

조건2	조건 3	조건2
조건 4	조건 1	조건 4
조건2	조건 3	조건2

a)     ImgTypeSelector()

조건 1. Y,X가 모두 홀수라면 타일

조건 2. Y,X가 모두 짝수라면 점

조건 3. Y가 짝수고 X가 홀수라면 가로벽

조건 4. Y가 홀수고 X가 짝수라면 세로벽

 

 

 

           Ps. 이 함수는 이미지 삽입의 편의를 위해 임의로 집어넣었습니다.

b)     TileTypeSelector()

단순히 격자 무늬를 만들기 위해 타입을 설정합니다.

조건 1. Y,X가 모두 홀수라면 타일

조건 2. Y,X가 모두 짝수라면 벽

조건 3. Y나 X가 하나라도 0이라면 테두리

 

 

RandomStartCell : function(){ //미로 생성을 위한 시작위치 무작위 설정         this.CurrentCell.y = parseInt(Math.random()*(this.height))*2+1;         this.CurrentCell.x = parseInt(Math.random()*(this.width))*2+1;         this.Maze[this.CurrentCell.y][this.CurrentCell.x].visited=true;     }, <code 4>

#설명

현재 셀 변수를 무작위로 선정하고 해당 셀을 방문했다고 표기합니다. (visited=true;)

 

FindNeighborCells : function(){ //이동할 주위 셀점검         this.direction=[];         if(this.ImgTypeChecker(-1,0)) this.direction.push('north');         if(this.ImgTypeChecker(0,1)) this.direction.push('east');         if(this.ImgTypeChecker(1,0)) this.direction.push('south');         if(this.ImgTypeChecker(0,-1)) this.direction.push('west');         return this.direction;     }, <code 5>

#설명

이웃 셀 중에서 방문하지 않은 위치를 찾습니다. (이동할 위치)

ImgTypeChecker()를 사용합니다.

북,동,남,서 순서로 검색을 하며 해당 번지가 비었다면 direction배열에 하나씩 push합니다.

검색이 끝났으며 direction배열을 반환하고 이 배열에는 이동할 수 있는 위치들이 삽입 되어 있습니다.

 

ImgTypeChecker : function(ydiff,xdiff){ //이미지 타입에 따라 어떠한 것을 넣을지 선택         var tileType=this.Maze[this.CurrentCell.y+ydiff][this.CurrentCell.x+xdiff].TileType;         var visited=true;         if(this.CurrentCell.y+(ydiff*2)>0 && this.CurrentCell.y+(ydiff*2) <this.height*2)             if(this.CurrentCell.x+(xdiff*2) >0 && this.CurrentCell.x+(xdiff*2) < this.width*2)                 visited=this.Maze[this.CurrentCell.y+ydiff*2][this.CurrentCell.x+xdiff*2].visited;         if(tileType=='wall'&&visited==false) return true;         else return false;     }, <code 6>

#설명

Code6에서 헷갈릴 만한 부분은 CurrentCell의 단위와 이동하는 ydiff에 2를 곱해주는 이유인데

이는 CurrentCell은 이동 할 수 있는 타일만을 나타내기 때문입니다.

<code3>에서 사용한 ImgTypeSelector() 의 표를 이용하자면 조건1에 해당되는 것만 Cell이 되기 때문입니다

 

 

현재 셀에서 북쪽(ydiff = -1 && xdiff =0)이 선택되었을 때 북쪽의 타일 타입 tileType변수로 삽입합니다.

If문 두개는 너무 길어서 나누어 쓴 것으로 두 가지 조건은 간단히 설명하면 미로 격자를 벗어나지 않을 경우를

의미합니다.

미로 격자를 벗어나지 않는 선에서 선택된 위치가 방문한적이 있는지 없는지를 검사해 boolean값으로

visited변수에 삽입합니다.

 

위 과정을 통해 선택된 방향의 셀이 벽이거나(tileType=”wall”) 방문한적이 없다면 (visited==false)

true값을 리턴합니다. 반대의 경우 false값 리턴!!

 

Return 값에 따라서!!

1.     True = 이동 가능한 곳

2.     False = 이동 불가능한 곳

 

 

selectDir : function(directions){ //방향선택함수         var randomNum= parseInt(Math.random()*directions.length), ydiff=0, xdiff=0;         switch(directions[randomNum]){             case 'north' : ydiff--; break;             case 'east' : xdiff++; break;             case 'south' : ydiff++; break;             case 'west' : xdiff--; break;         }         if(this.RangeCheck(this.CurrentCell.y,this.CurrentCell.x,ydiff,xdiff)){             this.Maze[this.CurrentCell.y+ydiff][this.CurrentCell.x+xdiff].value="aisle";                      this.Maze[this.CurrentCell.y+=ydiff*2][this.CurrentCell.x+=xdiff*2].visited=true;              this.CellStack.push({y:this.CurrentCell.y,x:this.CurrentCell.x});                          }     }, <code 7>

#설명

방향 선택 함수로서 FindNeighborCells() 에 의해 선택된 방향들(direction)을 인자로 받아서

그 중 하나를 무작위로 골라주는 함수입니다.

이후 RangeCheck()함수를 통해 미로 격자를 벗어나지 않는 경우에 현재 셀과 선택된 셀 사이를 허물어 통로로 만들어 줍니다. (aisle) 그리고 해당 위치를 방문했다는 표시를 합니다.(visited=true)

 

 

RangeCheck : function(CellY,CellX,ydiff,xdiff){ //범위설정 점검함수         if(CellY+ydiff*2 >= 0 &&CellY+ydiff*2 <= this.height*2+1 )             if(CellX+xdiff*2 >= 0 && CellX+xdiff*2 <= this.width*2+1)                 return true;         else return false;     } } <code 8>

#설명

현재 위치와 이동할 위치를 파악해서 미로 격자를 벗어나는지에 대한 판단을 하는 함수입니다.

 

추가(::WAC::가속도센서::)

 

추가로 가속도 센서와 관련해서 이미지를 이동시키는 부분에 대해서 연구한 부분이 있습니다.

사실 현재 상태값을 주기적으로 받아와서 이미지를 이동시켜야 하지만

KWAC에서는 기울기를 나타내는 가속도 센서를 사용 할 수 밖에 없었습니다.

 

deviceAPI에서 받아오는값의 범위는 -10~+10이 었습니다.

 

이동할 범위를 판단하기 위해선 좌표값에 따라 방향을 선택 해야했습니다.

x,y값의 범위에 따라 (좌표를 선택할 때)

조건 1. Y>0 && X>0 일때 X<Y 일경우 남쪽 Y<X일경우 서쪽을 의미합니다.

조건 2. Y>0 && X<0 일때 X<Y 일경우 남쪽 Y<X일경우 동쪽을 의미합니다.

조건 2. Y<0 && X>0 일때 X<Y 일경우 북쪽 Y<X일경우 서쪽을 의미합니다.

조건 2. Y<0 && X<0 일때 X<Y 일경우 북쪽 Y<X일경우 동쪽을 의미합니다.

 

if(y>=0 && x>=0) this.x < this.y ? returnVal='south' : returnVal='west'                else if(y>=0 && x<0) this.x < this.y ? returnVal='south' : returnVal='east'; else if(y<0 && x>=0) this.x < this.y ? returnVal='north' : returnVal='west' else if(y<0 && x<0) this.x < this.y ? returnVal='north' : returnVal='east'; < code#1 >

 

이 부분을 어떻게 짜느냐에 따라 미로에서 공이 움직이는 방법과 민감도가 차이를 가를 듯 합니다.

-_-많은 연구가 필요한 부분입니다.