リアリティを考慮した都市地区自動配置アルゴリズム

この記事では Procedural City Layout Generation Based on Urban Land Use Models (Groenewegen, et al., EUROGRAPHICS 2009) という論文の都市地区自動配置アルゴリズムを紹介します．
最近、ゲームに関する自動化技術を勉強したり考えたりしているのですが、この論文はそういった話に関連するアルゴリズムを提案したものです．ちなみに EUROGRAPHICS はコンピュータグラフィックスの学会で、この学会も上記の論文もデジタルゲームだけのためのものではありませんが、せっかく勉強したので紹介しようと思います．

論文概要

読んで字の如しですが、この論文は仮想の都市を自動生成するための都市地区の配置を行うアルゴリズムです．
建物を並べて仮想の都市を創る技術はこの論文以前にもあったのですが、大量のデータが必要だったり、あるいは都市計画に関する専門家が操作しないとなんだか意味不明な町並みになったり（病院の横に工場があったりとかでしょうかね）、色々な問題があったそうです．そこでこのアルゴリズムは、「この辺りは住宅地区、この辺りは工業地区、…」という自然な地区の配置を少ないデータと計算量で求めるべく提案されたもののようです．ちなみにこのアルゴリズムはお城や大きな教会やあるいは高層ビルなどといったランドマークを中心に形成されている街並みを創ることを前提としているようです．

このアルゴリズムでは以下の図の手順で都市地区を配置します（上記論文の図 2 からの引用．quoted from Figure 2 in Groenewegen et al.'s paper）．

1. まず地形を入力し
2. 中心地区と街全体の大体の半径を入力し
3. 主要道路の本数を決め（等間隔の自動仮配置．手動入力も可能？）
4. 地区候補点をばらまき
5. 候補点から各地区の中心地の位置を決定し（詳細は後述）
6. ボロノイ図によって地区の範囲を仮決めし
7. ボロノイ図の境界線にノイズを加えて地区を決定し
8. 既存のアルゴリズムで道路を配置して完成です．

各地区の中心地位置の決定については論文中に厳密な記述がなされていないのですが、評価関数の最適化によって一つ一つ順に決定していきます*1．評価関数は、既に配置されている他の地区との関係、地形、河川などに関する５種類の評価値の重み付き和で構成されます．全ての評価値の式やパラメータの値は公開されていませんが、例えば配置済みの他の 個の地区との関係は という式によって決定されるらしいです． は地区 と現在着目している地区との誘因度（-100〜+100）で は地区中心候補点の距離、 は中心点最小距離（これを下回る距離の位置に中心点を配置してはいけない）です．

これを元に西ヨーロッパの都市風のパラメータ設定を行ってアルゴリズムを走らせると以下の図のような配置が生成されるそうです（上記論文の図 3 の 1 からの引用．quoted from Figure 3-1 in Groenewegen et al.'s paper）．

3 種類の青系が住宅地で色が薄い方が高級、海沿いの灰色が重工業で一番薄い色が軽工業、2 種の緑が商業地区（区別不明）、黄色が運送業、赤計二種が政治・教会関連（区別不明）です．地形は左上が海で、右下に行くほど山になっているようです．
特徴を解説すると、まず住宅地は高級になるほど山側に配置されていて（どこの国でも山の手はお金持ちの地域です）、低級住宅地と高級住宅地の分化がきちんとできています．また、重工業地区は海沿いに配置され、それを取り囲むように軽工業地区および低級住宅地が配置されています．商業地区の大部分は高級住宅地の脇に固まっていて、残りは住宅地の隙間にちらほらとあるだけです．おそらく高級住宅地横の商業地区は服飾や宝石、高級食品を取り扱っていて、それ以外は主に食品店や日用品点などを扱う中流〜貧困層のためのお店なんでしょうね．
ただアトランダムに配置されただけではない、人間の生活感を感じさせる自然な配置がうまく生成されています．まぁ、そうなるようにパラメータが設定されているわけですが、パラメータさえ設定すればこれが簡単に創れるというのは面白いことだと思います．

論文は全４ページで、何も考えずに実装さえすれば使えるレベルの詳細な記述が無いためディテールを埋めないければならないのですが、こういうアルゴリズムはそれっぽく作れば詳細が元論文と一致していなくても大体なんとかなるようになっています．

*1:配置のもっともらしさはその順序にも影響されると思うのですが、処理量はかさむものの同時配置の最適化じゃなくてよいのでしょうか？