심시티 4 길찾기 개선하는 법

심시티 4의 길찾기 엔진이 어떻게 작동하는지 잘 정리된 영문 글이 있다. 이 글에서는 엔진의 중요성, 원리, 구성요소의 종류와 그 수치의 최적값 등을 다루고 있어 이 부분에 관심이 많다면 꼭 정독할 것을 강력히 추천한다. 이 글의 대부분의 설명도 저 글의 내용을 참고하여 재구성한 것이라고 볼 수 있다.

1. A* 알고리즘과 최적화
맥시스에서 만든 길찾기 엔진은 A* 알고리즘을 기반으로 길찾기를 위한 경험적 프로그램(Pathfinding Heuristic; PH)을 실시한다. 이 A* 알고리즘에 대한 영문 설명 또한 제공되어 있다. 이 글에서는 대략적인 이해를 위해 핵심만 설명하겠다.
A* 알고리즘에서는 지금 총 비용을 계산하려고 하는 지점의 출발지점으로부터의 이동 비용과 도착점까지의 거리 두 가지 변수를 고려한다.(여기서 도착점까지의 거리는 도착점까지의 경로가 아직 정해져 있지 않으므로 그 본질은 혼잡을 고려하지 않은 비용이다. 또한 여기서 말하는 비용(cost)은 적어도 심시티 4에서는 금전적인 것이 아니라 경로대로 가는 데에 걸리는 시간을 의미한다.)

보통은 f=상수*g+상수*h처럼 1차 함수의 꼴이다. 이 알고리즘은 두 가지 간단한 다른 알고리즘을 섞은 것에 가깝다. 따라서 각각의 극단을 접목해 보다 현실적으로 작동하며, 적용 대상에 따라 두 변수의 반영 비중을 바꿈으로써 유연하게 사용할 수 있다는 특징을 가진다.

▲첫 번째 알고리즘은 출발점으로부터 수면파처럼 퍼져나가며 도착점과 만나는 순간 그 경로를 선택하는 방식이다. 이 알고리즘은 사방의 모든 방향을 고려하므로 도착점을 향하여 움직인다기보다는 도착점을 발견하는 것에 가깝다. 따라서 최소 비용 경로를 반드시 찾아낸다는 장점이 있지만 고려해야 할 경로가 극단적으로 많아 계산이 오래 걸린다.(참고 알고리즘 : Dijkstra's)

수면파가 사방으로 퍼져가는 모습. 출처 : "Ondes compression 2d 20" by Christophe Dang Ngoc Chan (cdang) - Own work. Licensed under CC BY-SA 3.0 via Wikimedia Commons.

▲두 번째 알고리즘은 도착점까지 거리가 가장 가까운 지점을 우선적으로 선택해 길찾기를 진행하는 것이다. 이것은 무작정 도착점을 향해 달려가는 것으로, 경로 비용을 고려하지 않는데다 중간에 장애물을 만나면 빙빙 돌아가기 때문에 복잡한 경로에서는 극단적으로 비용이 늘어난다.(참고 알고리즘 : Best First Search)

두 알고리즘을 섞은 A* 알고리즘은 두 가지 비용의 합을 고려함으로써 도착지에 가까운 경로를 따라 가다가도 비용이 너무 높아지면 짧은 경로를 선택하여 다시 길을 찾게 된다. 따라서 두 번째 알고리즘의 빠른 속도와 첫 번째 알고리즘의 정확성을 모두 가질 수 있으며, 임의로 보정하여 용도에 알맞게 만들 수 있다.

심시티 4의 길찾기는 도착지에 무작정 가까워지려고 직선 거리를 선택하며 이때문에 계산은 덜 걸리는 대신 비용이 통근시간 제한을 초과해 통근이 불가능해져버리는 경우가 많다. 따라서 A* 알고리즘을 보다 신중하게, 즉 도착지까지의 거리인 h를 덜 고려하도록 만들 필요가 있다.

그리고 심시티 4에는 Pathfinding Heuristic 또는 Nearest Destination Attractiveness라고 불리는 값이 있으며 이것이 길찾기를 개선하는 핵심이다. 실제로 C:\Program Files\Maxis\SimCity 4\SimCity_1.dat 파일을 iLive's Reader로 열어 본 결과 확인되었으며, 그 기본값이라고 알려진 0.09도 맞았다.

▲글 맨 위에서 제시한 링크의 영문 튜토리얼에는 심시티 4 오리지널을 위한 플러그인 모드가 제공되어 있는데, 그 파일을 리더로 열어보니 Instance c9133286을 대체하는 것으로 확인됐다. 러시아워는 교통 부분에서 상당한 변화가 이루어졌기 때문에 그 모드는 러시아워에는 적용이 되지 않는다. 그래서 그 인스턴스를 Simcity_1.dat에서 찾아보았다.

▲그랬더니 위와 같이 교통에 관련된 값들이 나왔다. 교통 플러그인으로 유명한 NAM 또한 이 인스턴스를 사용하는 것으로 보인다.

최단 비용의 경로를 찾기 위한 N.D.A.의 최적값은 0.005797이라고 알려져 있다. 이보다 값이 낮으면 정확도는 별 변화가 없는 데에 비해 계산할 경로가 더욱 많아지게 된다.
게임 플레이가 어려워질 정도로 속도가 느려진다면 N.D.A. 값을 기본값 0.09와 최적값 0.005797 사이의 값으로 설정하면 된다.



2. 적용하기
1) 간단하게 Simcity_1.dat을 직접 편집하는 방법
iLive's Reader를 설치한다. 심트로폴리스에서 구할 수 있다.
Simcity_1.dat을 열고, Fill the list 버튼을 눌러 목록을 조회한다.
엔트리 목록을 인스턴스 순으로 정렬한 후 c9133286을 선택한다.
해당 엔트리의 N.D.A. 항목을 원하는 값으로 바꾼다.
오작동할 수 있으니 백업을 해둔 후 저장한다.

2) 플러그인 모드를 만들어서 쓰는 방법
NAM 등 다른 교통 모드와 충돌할 수 있기 때문에 다른 모드들을 전부 삭제해야 한다. 
맨 위의 영문 튜토리얼 링크로 들어가서 Appendix항목을 보면 the7trumpets가 제작한 'Pathfinding Modd' 모드 링크가 있다. 여기서 모드를 다운받는다.
Simcity_1.dat 파일을 열고 위에서 말한 인스턴스를 우클릭해 Copy file(s)한다.
위의 모드에서 BetterPathfinding_Original_Commute_Engine.dat 파일을 연다.
원래 있던 파일은 심시티 4 오리지널 용이고 러시아워에는 쓸 수 없으므로 선택한 후 지운다.(우클릭해서 Remove file)
우클릭해 Paste file(s)해서 복사한 파일을 붙여넣는다.
저장한 후 이 파일을 C:\Program Files\Maxis\SimCity 4\Plugins에 넣어서 사용하면 된다. 이 모드의 readme를 보면 Program Files의 플러그인 폴더에 넣으라고 되어 있기 때문이다. 내문서의 플러그인 폴더에 넣어도 되는지는 모르겠다.

N.D.A. 값 외에도 교통수단의 속도, 수용량, 통근시간 최대값 등도 바꿀 수 있으니 직접 모드를 만들어보는 것도 나쁘지 않다.



0.005797로 바꾼 플러그인 다운로드 : 링크
주의사항 : 다른 교통 모드와 충돌할 수 있음, 러시아워나 디럭스에서만 사용 가능, 혹시 모르니 원래 쓰임새처럼 Program Files 내의 플러그인 폴더에 설치할 것.

그런데 직접 사용해보니 건물이 버려지는 등 그 전보다 오히려 길찾기를 어려워하는 모습을 보여서 다른 조치도 필요해 보인다.