아이작 맵 생성

서론이전 시간에 백 트래킹과 BFS를 사용하여 무려 $O(4^M\cdot M\cdot N^2)$ 이 걸리는 맵 생성 알고리즘을 설명하였다. 이번시간에는 이를 대략 $O(M^2\cdot N^2)$ 정도로 획기적으로 단축하는 방법을 설명하고자 한다. 기존 방식은 N(=MapSize)과 M(=EndRoom)이 각각 10이라면 대략 10억의 계산량이 발생하지만 새로 고안한 방법은 고작 10000의 계산량 밖에 발생하지 않는다 단순 수치로 보면 대략 100000배 빨라졌으니 이전 방식이 얼마나 비효율적인지 알 수 있다.Solution 2 : Kruskal + BFS이전에는 EndRoom의 개수만큼 Grid에 랜덤으로 방을 생성하여 해당 점의 방향의 모든 경우의 수를 백트래킹으로 찾아 맵을 생성하였다. 이번에..

절차적 맵 생성아이작과 같은 로그라이크류 게임에서 새로운 맵을 랜덤으로 생성할 때 특정한 알고리즘을 사용하여 자동으로 맵을 생성하는 알고리즘들을 지칭한다. 여러 맵 생성 알고리즘들이 구글에 널려있지만 정확하게 아이작의 구속의 맵 생성 시스템과 비슷한 결과는 없는 것 같아서 본인이 직접 고심하여 알고리즘을 제작해보았다.아이작에서의 맵 생성 방식아이작이 워낙 유명한 게임이다 보니까 모작등을 통해 여러 블로그에서 아이작의 맵 생성 방식을 흉내내는 글이 많았다. 하지만 본인이 원하는 아이작에서 비밀방을 제외한 맵 생성 알고리즘과 정확히 일치하는 알고리즘은 찾지 못하였다. 물론 아이작의 맵생성 알고리즘이 오픈되어 있지 않으니 경험을 토대로 역산할 수 밖에 없는 까닭도 있지만, 최대한 비슷한 결과를 만들기 위해 직..