Maze/DFS 2010.03.31 21:33

Depth-First Search

왜 이런이름인진 모른다..-0-;;

인터넷에서 돌아다니다가...몇몇 알고리즘을 찾았고...생성되는게 적당한 난이도??로 생성되는것 같고..

알고리즘도 상당히 간단해 보여서 이걸로 한번 만들어봐야겠다...

http://www.mazeworks.com/mazegen/mazetut/index.htm

이링크가 내가 찾은 곳인데...

간단하게만 영어를 하면 누구나 다 알수 있게 쉽게 되어있다...

알고리즘 과정은 정말 간단하다..(머리 좋은사람 많네...)

0) 우선 격자모양(바둑판모양)의 셀들로 가득찬 미로판을 준비...(셀들은 상,하,좌,우가 모두 막혀있는 정사각형모양 정도로 생각하면된다..)
1) 이 미로판에서 랜덤으로 아무 셀이나 선택(currentCell).
2) 선택된 셀(currentCell)에서 상,하,좌,우에 인접해있는 셀들중 4방향의 벽이 온전한 벽들을 체크하고 그중 하나를 랜덤으로 선택, 온전한 셀이 없으면 이전에 선택된던셀로 바꿔서 다시 검색.
3) 2에서 선택된 셀과 현재 선택된 셀(currentCell) 사이의 벽을 지운다.
4) 2,3번을 반복

단지 이과정으로미로가 만들어진다...

길이 여러개 있는 미로가 아닌 출구가 하나뿐인 완벽한 미로가....

이글 저장하고...
간단하게 플래시로 만들어보고, 그뒤엔 유니티로 만들어봐야겠다...
신고
posted by andwhy

티스토리 툴바