[알고리즘 알아보기] Cellular Automata 맵 만들기

Algorithm/알고리즘

Basaeng 2025. 9. 16. 23:05

[알고리즘 알아보기] A* 알고리즘 알아보기

개요A*알고리즘은 최적의 경로를 찾는 알고리즘입니다. 비슷한 알고리즘으로는 다익스트라 알고리즘이 있는데 이를 개선, 확장한 알고리즘입니다.이 포스팅에서는 2차원을 한정해서 알아보겠

basaeng.tistory.com

개요

길을 찾는 다는 것은 맵이 있어야 완성됩니다.

허허벌판에서만 움직인다면 복잡한 길찾기 알고리즘은 필요없겠죠.

따라서 길찾기 알고리즘을 제대로 테스트해보기 위해서는 랜덤한 맵이 필요할 것입니다.

이번에는 맵을 만드는 알고리즘 중에서도 Cellular Automata방식을 알아보도록 하겠습니다.

콘웨이의 생명 게임

Cellular Automata방식은 콘웨이의 생명 게임을 기반으로 만들어진 방식입니다.

콘웨이의 생명게임은 인접한 8칸을 기준으로 규칙에 따라 세포의 생사가 결정됩니다.

생명 게임에 대한 자세한 규칙 설명은 생략하겠습니다.

Cellular Automata

Cellular Automata는 콘웨이의 생명게임과 비슷하게 주변 8방의 현재 상태에 따라 본인의 상태를 결정합니다.

먼저 전체 맵에 대하여 랜덤하게 장애물의 설치여부를 결정합니다.

그렇다면 마치 노이즈가 낀듯한 모양의 맵이 생성됩니다.

이후에 주변 8방향 중 5방향 이상이 장애물이라면 본인의 상태를 장애물로, 아니라면 장애물이 없는 평지 상태로 설정합니다.

그리고 이를 반복합니다.

반복한다면 잡음같은 패턴은 주변에 동화되기 때문에 점점 안정된 상태로 맵이 변합니다.

최종적으로는 위와 같은 결과를 볼 수 있습니다.

이 방법은 간단하면서 테스트하기에는 충분히 효과적인 맵을 만들 수 있는 방법입니다.

물론 실제로 사용하기에는 부족한 부분이 많아 튜닝이 필요할 것입니다.

위와 같이 길을 찾는것도 확인해볼 수 있습니다.

길찾기에 사용된 알고리즘은 JPS로 다음 포스팅에서 다뤄보겠습니다.