はじめに

ボードゲームドブル (Dobble / Spot it!) を Python 実装した dobble-maker の解説です。

本記事ではカード内でのシンボルのレイアウトについて説明します。

ドブルデッキの構築
- 任意の 2 枚のカードを選んだ時に、必ず共通するシンボルが 1 つだけ存在するような組み合わせを決定する
カード内でのシンボルのレイアウト
- シンボル間の重なり無く、程よくランダムに配置する
生成ツールの紹介
- 画像ファイルから印刷用 PDF まで生成するツールの紹介
- 仕組みはいいから作りたい！ という方はこちらです
2 枚に 2 つのシンボルが共通するデッキ
- 通常ドブルとは異なる特性を持ったデッキを作ります
3 枚に 1 つのシンボルが共通するデッキ
- また別の特性を持つデッキです
派生版のアイデア帖
- デッキの解釈を変えて新しいデッキについて考えてみます

更新履歴

2023/10/22: 方法3 を追記

やりたいこと

ドブルのカードにシンボルを描画するにあたって、やりたいことを整理しました。

カードは任意サイズの円、または長方形
カード内に形が異なる$N$個のシンボルを重ならないように配置する
- 各シンボルのサイズ、形は異なる
各シンボルは程よくランダムに配置

方法 1: 完全ランダムに配置

最初に試したのがこの方法です。とにかくランダムに入れてみる。

結論からいうと、この方法は失敗なので、方法 2まで読み飛ばしていただいてもかまいません。

手順

カード型の空のキャンバスを準備
1 つ目のシンボルをランダムにリサイズ、回転、位置決めして描画
次のシンボルをランダムにリサイズ、回転、位置決めして描画
1. 描画済みのシンボルと重なるなら、再度ランダムに描画
2. 一定回数試しても入らないなら、キャンバスを空にして 1 つ目のシンボルからやり直し

結果

円形のカードに$N=5$個のシンボルを描画してみます。

1 枚目の 1 回目、入らないのでやり直し

1 枚目の 2 回目、入ったので描画

2 枚目の 1 回目、入ったので描画

3 枚目の 1 回目、入らないのでやり直し

・・・

対象とするシンボルがすべて描画できたら、このカードは終わり。

dobble-makerでは、以下を"random"に設定することで、layout_images_randomly_wo_overlap()から_layout_random()が呼び出されます。

dobble_maker.py

def main():
    ...
    layout_method: Literal["random", "voronoi"] = "random"
    ...

方法 1 の問題

さて、この方法はシンプルなんですが、問題がありました。

以下は生成された最初の 6 枚のカードです。
隙間が多くてスカスカで、小さくて見難いシンボルもありますね。
これを嫌ってシンボルのリサイズ率を大きくすると、処理がなかなか終わりません。

方法 2: 重心ボロノイ分割で位置決め

次に試したのは、シンボルの描画位置を重心ボロノイ分割で決める方法です。

手順

カード型の閉領域内を$N$個の母点で重心ボロノイ分割する
各母点の位置を各シンボルの中心位置として、シンボルを回転し、ボロノイ領域に収まったらそこで描画
1. 入らなければシンボルを少し縮小して、再度回転して描画できるか確認、を描画できるまで繰り返す

以下、解説します。

カード型の閉領域で重心ボロノイ分割

重心ボロノイ分割 (CVT)

重心ボロノイ分割 (CVT: Centroidal Voronoi Tessellation) とは、任意の凸領域を、任意の個数の領域（ボロノイ領域）に分割する方法です。

凸領域内にランダムに初期点を配置。この点を母点と呼ぶ。
各母点に基づき、凸領域をボロノイ分割¹する
各母点をボロノイ領域の重心に移動する
移動後の母点で再度ボロノイ分割する
これを指定の回数（または移動量が閾値以下になるまで）繰り返す

この図は、円領域を 12 個の母点で重心ボロノイ分割（20 回反復）した図です。
何度か計算を繰り返すことで、母点が良い感じに均等に散らばる様子がわかります。
各領域の大きさも均一に揃っていますね。

これを使って、カード内におけるシンボルの配置位置とシンボルの描画範囲を決めます。

実装

dobble-makerではvoronoi.pyのcvt()で CVT を実装しています。

まず母点の初期値として、_rand_pts_in_poly()で所定の領域内に点群をランダム配置します。これは以下を参考にしました。

次に、_bounded_voronoi()で閉領域に対するボロノイ分割を行います。こちらは以下のほぼコピペです。

そのあとは母点を重心に移動し、再度ボロノイ分割、を繰り返しです。

各シンボルを母点の位置に描画

あとは母点の位置に、ボロノイ領域に収まる範囲でシンボルがなるべく大きく入るようにくるくる回しながら試していきます。

1 つ目のシンボルを描画します。

2 つ目のシンボルを描画します。

・・・

全部入ったら終わりです。

こちらが方法 2 で作った最初の 6 枚のカード（CVT を 10 回反復）です。

完全にランダムで作った方法 1 に比べて、大きさが揃って、また配置にも偏りがありません。
ゲームなので好みで決めて良いのですが、ある程度大きさが揃っていた方が遊びやすいと思います。

またもっとランダムに配置したい場合には、CVT の反復回数を減らすことで調整ができます。

こちらは反復回数を 2 回にした場合です。シンボルの大きさに差が出てきていますね。

dobble-makerでは、以下を"voronoi"に設定することで、layout_images_randomly_wo_overlap()から_layout_voronoi()が呼び出されます。
反復回数を変更したい場合はcvt()の呼び出し部分にn_iters引数を追加してください。

dobble_maker.py

def main():
    ...
    layout_method: Literal["random", "voronoi"] = "voronoi"
    ...

方法 3: Centroidal Power Diagrams

方法 2 で当初の狙いは達成できますが、「シンボルサイズの調整」を自由に行うことができませんでした（CVT の反復回数での調整は位置も影響を受けてしまう）。

そこで、各母点に重みを与えてボロノイ分割を行う方法の一種である Power Diagram（パワー図）を導入します。

Power Diagram

Power Diagram は、ボロノイ分割を行う際に、各母点の重みとして「円の半径」を付与します。この方法で生成されるボロノイ領域は、簡単にいうと「各円の交点を結ぶ直線を境界とする領域」となります²。

Wikipediaより

全ての母点に同じ重みを与える（＝円の大きさが等しい）と、通常のボロノイ分割と同じ結果になりますが、与える重みを変えることで、ボロノイ領域の大きさをある程度制御することが可能です。

Centroidal Power Diagram

Power Diagram はボロノイ分割の拡張手法であり、CVT の領域生成処理を Power Diagram に置き換えることが可能です。
これはCentroidal Power Diagram (CPD) と呼ばれています。

この図は、円領域に対して 12 個の母点で CPD を適用し、20 回の反復計算をした結果です。
各母点を濃い青の点で、各母点の重みを薄い青の円で示しています。

	1 回目	20 回目
CPD
CVT

こちらは同じ母点の初期配置で CPD と CVT を適用した場合の、 1 回目及び 20 回目の計算結果です（CPD の結果は前述の GIF から抜粋）。

CPD の 1 回目と CVT の 1 回目は、母点の配置は同じながら得られる領域が異なっています。
また 20 回目の結果を比べると、重み（円の半径）が領域のサイズに影響を与えていることがよくわかりますね。

さらに CPD の 1 回目をよく見ると、母点のない領域や複数の母点を含む領域が存在します。このように Power diagram では、必ずしも母点が（自身の）ボロノイ領域内にあるとは限らない、という特徴があります。
そのため CPD の計算時には注意が必要です。

これを使って、カードに描画するシンボルサイズの大きさを制御します。

実装

dobble-makerではlaguerre_voronoi_2d.pyで Power Diagram の処理を実装し、これをvoronoi.pyから呼び出す実装になっています。

laguerre_voronoi_2d.py³はこちらのGitHub Gistで公開されている実装をベースとしています⁴。

ボロノイ分割を Power diagram で置き換えたら、それ以外の処理はすべて方法 2 と同じです。

dobble-makerでは、母点の重みをradius_pで調整する仕様にしています。

dobble_maker.py

def cvt(..., radius_p: float, ...):
    ...
    radius = None
    if radius_p > 0.0:
        poly = Polygon(bounding_points)
        area_per_site = poly.area / n_sites  # 外側の図形の面積を母点で均等に分割した場合の面積を radius の基準とする
        r_basis = np.sqrt(area_per_site / np.pi)  # 基準半径
        radius = r_basis / 2 + radius_p * r_basis / 2 * np.random.random(n_sites)
    ...

def main():
    ...
    # "voronoi"における各母点の半径を決めるパラメータ (0.0なら半径なし, つまり通常のボロノイ分割として処理)
    radius_p: float = 0.5
    ...

外側の図形（カード全体を表す図形）の面積 poly.area を基準に、各母点の基準の面積を求め、それに対する割合をradius_pで調整しています。

パラメータ調整

母点の重みとイテレーション回数を調整しないといけないので、少し調整が難しくなってしまいましたが、重み、及びイテレーション回数の片方を固定しながら、他方を少しずつ変える、というのを何度か試してみると、なかなか良い感じの結果が得られます。

おわり

隣接する 2 つの母点を結ぶ線分の垂直二等分線を境界とする領域（ボロノイ領域）を求める処理のこと ↩
「ある母点の円の中に別の母点の円が内包される」場合や、「母点間の距離が円の距離の和より大きい」場合などはこうはならないので、上記は正確な説明ではありません ↩
Laguerre-Voronoi diagrams は Power diagrams の別名 ↩
前述した CPD の特徴含む諸々の都合で、単純なコピペと関数差し替えでは動かなかったので、少し手を加えています ↩