【プロシージャル】Pythonで学ぶ波動関数崩壊アルゴリズム（Wave Function Collapse）

    # 下記論文を参考にした4x4のタイルIDパターン
    # https://graphics.stanford.edu/papers/tile_mapping_gh2004/
    TILE_ID_STR_PATTERN_LIST = [
        "0010", "0110", "0111", "0011",
        "1010", "1110", "1111", "1011",
        "1000", "1100", "1101", "1001",
        "0000", "0100", "0101", "0001",
    ]

    @dataclass
    class TileId:
        """タイルIDデータクラス"""

        top: int
        right: int
        bottom: int
        left: int


    @staticmethod
    def get_tile_id_pattern_list() -> List[WangTilesUtility.TileId]:
        """タイルIDパターンリストを取得する

        Returns:
            List[WangTilesUtility.TileId]: タイルIDパターンリスト
        """
        tile_id_list = []
        for s in WangTilesUtility.TILE_ID_STR_PATTERN_LIST:
            tile_id_list.append(
                WangTilesUtility.TileId(
                    top=int(s[0]), right=int(s[1]), bottom=int(s[2]), left=int(s[3])
                )
            )
        return tile_id_list

    @staticmethod
    def create_random_tile_grids(
        tile_count_x: int,
        tile_count_y: int,
        tile_id_pattern_list: List[TileId],
        random_seed: int = 0,
    ) -> List[List[WangTilesUtility.TileId]]:
        """指定された情報からランダムにタイルIDのGrid情報を生成する

        Args:
            tile_count_x (int): X方向のタイル数
            tile_count_y (int): Y方向のタイル数
            tile_id_pattern_list (List[TileId]): タイルIDパターンリスト
            random_seed (int, optional): 乱数シード値. Defaults to 0.

        Returns:
            List[List[WangTilesUtility.TileId]]: タイルIDのGrid情報
        """
        random.seed(random_seed)

        # grid初期化
        id_tile_list: List[List[WangTilesUtility.TileId]] = [
            [None for _ in range(tile_count_x)] for _ in range(tile_count_y)
        ]

        # タイルを左辺、上辺どちらかが繋がるようにランダムに抽出
        for y in range(tile_count_y):
            for x in range(tile_count_x):
                filter_pattern_id_list = []
                # 最初のタイルはランダムに選択
                if x == 0 and y == 0:
                    id_tile_list[y][x] = random.choice(tile_id_pattern_list)
                    continue
                # 左辺 == 左タイルの右辺
                left_neighbor_tile_id = id_tile_list[x][y - 1]
                if left_neighbor_tile_id:
                    for tile_id in tile_id_pattern_list:
                        if tile_id.left == left_neighbor_tile_id.right:
                            filter_pattern_id_list.append(tile_id)
                # 上辺 == 上タイルの下辺
                top_neighbor_tile_id = id_tile_list[x - 1][y]
                if top_neighbor_tile_id:
                    for tile_id in tile_id_pattern_list:
                        if tile_id.top == top_neighbor_tile_id.bottom:
                            filter_pattern_id_list.append(tile_id)

                id_tile_list[x][y] = random.choice(filter_pattern_id_list)

        return id_tile_list

    def _create_pattern_info_list(
        self, image_grid: ImageGridType, check_pattern_size: int
    ) -> List[TilePatternInfo]:
        """
        入力グリッドからユニークなパターンを抽出し、頻度もカウントする

        Args:
            image_grid (ImageGridType): 画像の2次元リスト
            check_pattern_size (int): チェックするパターンの1辺サイズ

        Returns:
            List[PatternInfo]: パターン情報のリスト
        """
        image_grid_count_x = len(image_grid[0])
        image_grid_count_y = len(image_grid)

        # 画像グリッドからパターンを抽出
        # 抽出範囲のサイズが画像グリッドのサイズを超えないようにする
        pattern_info_dict: Dict[str, WFCSimpleOverlappingModel.TilePatternInfo] = {}
        for y in range(image_grid_count_y - check_pattern_size + 1):
            for x in range(image_grid_count_x - check_pattern_size + 1):
                # 抽出範囲での全てのパターンを追加
                pattern_row_list = []
                for dy in range(check_pattern_size):
                    row = []
                    for dx in range(check_pattern_size):
                        ix = x + dx
                        iy = y + dy
                        row.append(image_grid[iy][ix])
                    pattern_row_list.append(tuple(row))
                # パターンの1次元タプルをキーとして値を設定
                pattern_values = tuple(chain.from_iterable(pattern_row_list))
                if pattern_values not in pattern_info_dict:
                    pattern_info_dict[pattern_values] = self.TilePatternInfo(
                        pattern_values,
                        frequency=1,
                        size=check_pattern_size,
                    )
                else:
                    # 重複していたらfrequencyとしてカウント
                    pattern_info_dict[pattern_values].frequency += 1
        return list(pattern_info_dict.values())

    # 左, 右, 上, 下
    CHECK_DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    class TilePatternInfo:
        """
        タイルのパターン情報をまとめたクラス
        size x size のタイルパターンをvaluesとして1次元タプルで保持する

        例：3x3のパターンなら
        values = ((0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0))
        のようにRGB情報が9つ分入る形になる

        Args:
            patterns: パターン本体（1次元タプル）
            frequency: 出現頻度
            size: パターンの1辺サイズ
        """

        def __init__(
            self,
            patterns: Tuple[int, ...],
            frequency: int = 1,
            size: int = 3,
        ):
            self.values = patterns
            self.frequency = frequency
            self.size = size

        def right_except(self) -> Tuple[int, ...]:
            """右端以外の2列を1次元で返す"""
            return tuple(
                n for i, n in enumerate(self.values) if i % self.size != (self.size - 1)
            )

        def left_except(self) -> Tuple[int, ...]:
            """左端以外の2列を1次元で返す"""
            return tuple(n for i, n in enumerate(self.values) if i % self.size != 0)

        def bottom_except(self) -> Tuple[int, ...]:
            """下端以外の2行を1次元で返す"""
            return self.values[: (self.size * self.size) - self.size]

        def top_except(self) -> Tuple[int, ...]:
            """上端以外の2行を1次元で返す"""
            return self.values[self.size :]

・・・略・・・

    def _create_allowed_pattern_adjacencies_dict(
        self,
    ) -> AllowedPattenAdjacenciesType:
        """
        各パターンごとに隣接可能なパターンインデックス辞書を作成する

        Returns:
            AllowedPattenAdjacenciesType: 隣接可能なパターンインデックスリストの辞書
        """
        patten_info_count = len(self._pattern_info_list)
        allowed_pattern_adjacencies_list = {
            i: ([], [], [], []) for i in range(patten_info_count)
        }

        # 各パターンの隣接可能なパターンを上下左右で探索
        for i in range(patten_info_count):
            pattern_i = self._pattern_info_list[i]
            for j in range(patten_info_count):
                pattern_j = self._pattern_info_list[j]
                # 左端以外と右端以外の2列が一致
                if pattern_i.left_except() == pattern_j.right_except():
                    allowed_pattern_adjacencies_list[i][1].append(j) # 右隣接
                    allowed_pattern_adjacencies_list[j][0].append(i) # 左隣接
                # 上端以外と下端以外の2行が一致
                if pattern_i.top_except() == pattern_j.bottom_except():
                    allowed_pattern_adjacencies_list[i][3].append(j) # 下隣接
                    allowed_pattern_adjacencies_list[j][2].append(i) # 上隣接

    def _initialize_entropy_grid(self) -> Dict[int, int]:
        """エントロピー計算用グリッドを初期化する
        初期値は全てのセルでパターン数と同じ値に設定し、開始セルのエントロピーのみ1減らした状態にする

        Returns:
            Dict[int, int]: エントロピー計算用グリッド（key: インデックス value: エントロピー）
        """
        entropy_grid = {}
        for x in range(self._output_grid_size[0] * self._output_grid_size[1]):
            entropy_grid[x] = len(self._pattern_info_list)
        # 開始セルのエントロピーを1減らしておく
        start_index = random.randint(0, len(entropy_grid.keys()) - 1)
        entropy_grid[start_index] = len(self._pattern_info_list) - 1
        return entropy_grid

    def _get_lowest_entropy_cell_index(self) -> int:
        """エントロピーが最小のセルのインデックスを返す

        Returns:
            int: エントロピーが最小のセルのインデックス
        """
        return min(self._entropy_grid, key=self._entropy_grid.get)

    def _assign_random_pattern_to_cell(self, cell_index: int):
        """セルにパターンをランダムに1つ設定して確定する

        Args:
            cell_index (int): 対象セルのインデックス
        """
        # 該当セルで許容されているパターンを取得
        # 出現頻度に基づいてウェイトを設定する
        allowed_patterns = self._output_grid[cell_index]
        weights = [
            self._pattern_info_list[pattern_index].frequency
            for pattern_index in allowed_patterns
        ]
        pattern_index = random.choices(allowed_patterns, weights=weights)[0]
        # セルにパターンを適用してグリッドから削除
        self._output_grid[cell_index] = [pattern_index]
        del self._entropy_grid[cell_index]

    def _propagate_cells(self, cell_index: int) -> bool:
        """セルの確定を周囲に伝播してエントロピーを更新する
        セルの隣接パターン（上下左右）を全てチェックし、隣接セルの許容パターンを更新していく

        Args:
            cell_index (int): 対象セルのインデックス

        Returns:
            bool: 処理が成功したかどうか
        """
        to_update_cell_index_stack = {cell_index}

        while len(to_update_cell_index_stack) != 0:
            cell_index = to_update_cell_index_stack.pop()
            # セルの隣接パターン（上下左右）を全てチェック
            for direction, transform in enumerate(self.CHECK_DIRECTIONS):
                # 隣接セルのインデックスを計算
                neighbor_x = (
                    cell_index % self._output_grid_size[0] + transform[0]
                ) % self._output_grid_size[0]
                neighbor_y = (
                    cell_index // self._output_grid_size[0] + transform[1]
                ) % self._output_grid_size[1]
                neighbor_cell_index = (
                    neighbor_x + neighbor_y * self._output_grid_size[0]
                )
                # 隣接セルが未確定の場合
                if neighbor_cell_index in self._entropy_grid:
                    # セルの許容パターンを全て取得
                    allowed_pattern_indices_in_all_cell = set()
                    for pattern_index in self._output_grid[cell_index]:
                        allowed_pattern_indices: List[int] = (
                            self._allowed_pattern_adjacencies_dict[pattern_index][
                                direction
                            ]
                        )
                        for allowed_patten_index in allowed_pattern_indices:
                            allowed_pattern_indices_in_all_cell.add(allowed_patten_index)
                    # 隣接セルの許容パターンを更新
                    allowed_pattern_indices_in_neighbor_cell = self._output_grid[
                        neighbor_cell_index
                    ]
                    # 隣接セルのパターンがセルの許容パターンに含まれていない場合
                    # (セルの更新が発生して矛盾が発生した場合)
                    if not set(allowed_pattern_indices_in_neighbor_cell).issubset(
                        allowed_pattern_indices_in_all_cell
                    ):
                        # 隣接セルとセルに共通するパターンに絞り込んで設定する
                        shared_pattern_indices = [
                            x
                            for x in allowed_pattern_indices_in_neighbor_cell
                            if x in allowed_pattern_indices_in_all_cell
                        ]
                        if len(shared_pattern_indices) == 0:
                            return False
                        shared_pattern_indices.sort()
                        # 共通パターン数をエントロピーに設定する
                        self._output_grid[neighbor_cell_index] = shared_pattern_indices
                        self._entropy_grid[neighbor_cell_index] = len(
                            shared_pattern_indices
                        )
                        # 更に伝搬する
                        to_update_cell_index_stack.add(neighbor_cell_index)
        return True