update 2021.07.13
갑자기 너무나 많은 분들이 들어오셔서 일단 급한 마음에 C++로 구현한 코드 올려 봅니다.
https://github.com/ChoiIngon/gamnet/tree/master/example/LobbyServer/Component/Dungeon
코드에 대한 자세한 최대한 빨리 시간내서 랜덤 던전 관련 코드만 정리해서 올리도록 하겠습니다.
https://github.com/ChoiIngon/gamnet/blob/master/example/LobbyServer/Component/Dungeon/Dungeon.cpp 파일의 BuildPath 함수가 핵심입니다.
랜덤 던전의 요구사항은 "모든 방들이 연결 되어있어야 한다" 입니다. 그래서 아래와 같이 만들어 보았습니다.
기본 로직은 :
- 일정한 범위 사이의 랜덤 블록들을 여기 저기 뿌림
- 블록들을 모두 연결하고 각 연결마다 랜덤 가중치를 부여
- 다익스트라 알고리즘에 따라 가중치중 가장 빠른 패스를 선택. 나머지 연결들은 모두 삭제
- AStar 알고리즘을 이용해 연결된 블록들 끼리 적절한 통로를 생성
입니다.
이번 장에서 부터 로그라이크 게임의 꽃이라고 할 수있는 랜덤맵을 만다는 여러가지 알고리즘들을 알아보고 그중 하나를 구현해 보도록 하겠습니다.
방과 미로를 이용한 랜덤 던젼 :
http://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/
http://donjon.bin.sh/code/dungeon/
난쟁이가 땅굴 파듯 만드는 랜덤 던젼 :
그래프 기반 랜덤 던젼 :
https://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/
부록 1. 같이 읽으면 좋은 글