このページは Cloud Translation API によって翻訳されました。

Flutter でワードパズルを作成する

1. 始める前に

世界最大のクロスワードパズルを作成できるかどうかを尋ねられたとします。学校で学んだ AI 手法を思い出し、Flutter を使用してアルゴリズムオプションを調べ、計算量の多い問題の解決策を作成できるかどうかを検討します。

この Codelab では、まさにそれを行います。最終的には、単語グリッドパズルの構築アルゴリズムの分野でプレイするツールを構築します。有効なクロスワードパズルの定義はさまざまですが、これらの手法は、独自の定義に合ったパズルを作成するのに役立ちます。

クロスワードパズルが生成される様子のアニメーション。

このツールをベースに、クロスワードパズルを作成します。クロスワードジェネレータを使用して、ユーザーが解くパズルを構築します。このパズルは、Android、iOS、Windows、macOS、Linux で使用できます。Android の場合は次のようになります。

Google Pixel Fold エミュレータでクロスワードパズルを解いている最中のスクリーンショット。

前提条件

初めての Flutter アプリ Codelab を修了している

学習内容

Flutter の compute 関数と Riverpod の select 再構築フィルタの値キャッシュ機能の組み合わせにより、Flutter のレンダリングループを妨げることなく、計算コストの高い作業を行うために分離を使用する方法。
built_value と built_collection を使用して不変データ構造を活用し、深さ優先探索やバックトラッキングなどの検索ベースの Good Old Fashioned AI（GOFAI）手法を実装する方法。
two_dimensional_scrollables パッケージの機能を使用して、グリッドデータを高速かつ直感的に表示する方法。

必要なもの

Flutter SDK。
Flutter プラグインと Dart プラグインがインストールされた Visual Studio Code（VS Code）。
選択した開発ターゲット用のコンパイラソフトウェア。この Codelab は、すべてのパソコンプラットフォーム、Android、iOS で動作します。Windows をターゲットにするには VS Code、macOS または iOS をターゲットにするには Xcode、Android をターゲットにするには Android Studio が必要です。

2. プロジェクトを作成する

最初の Flutter プロジェクトを作成する

VS Code を起動します。
コマンドパレット（Windows/Linux では Ctrl+Shift+P、macOS では Cmd+Shift+P）を開き、「flutter new」と入力して、メニューから [Flutter: New Project] を選択します。

開いているコマンドパレットに [Flutter: New Project] が表示されている VS Code。

[Empty application] を選択し、プロジェクトを作成するディレクトリを選択します。これは、昇格された権限を必要とせず、パスにスペースが含まれていないディレクトリである必要があります。たとえば、ホームディレクトリや C:\src\ などがあります。

新しいアプリケーションフローの一部として選択されている [Empty Application] が表示された VS Code

プロジェクトに generate_crossword という名前を付けます。この Codelab の残りの部分では、アプリの名前が generate_crossword であると想定しています。

作成中の新しいプロジェクトの名前として generate_crossword が表示されている VS Code

すると、Flutter がプロジェクトフォルダを作成し、VS Code がそのフォルダを開きます。次は、2 つのファイルの内容を、このアプリの基本的なスキャフォールドで上書きします。

初期アプリをコピーして貼り付ける

VS Code の左側のペインで [エクスプローラ] をクリックし、pubspec.yaml ファイルを開きます。

pubspec.yaml ファイルの場所を矢印でハイライト表示している VS Code の部分的なスクリーンショット

このファイルの内容を、クロスワードパズルの生成に必要な次の依存関係に置き換えます。

pubspec.yaml

name: generate_crossword
description: "A new Flutter project."
publish_to: 'none'
version: 0.1.0

environment:
  sdk: ^3.9.0

dependencies:
  flutter:
    sdk: flutter
  built_collection: ^5.1.1
  built_value: ^8.10.1
  characters: ^1.4.0
  flutter_riverpod: ^2.6.1
  intl: ^0.20.2
  riverpod: ^2.6.1
  riverpod_annotation: ^2.6.1
  two_dimensional_scrollables: ^0.3.7

dev_dependencies:
  flutter_test:
    sdk: flutter
  flutter_lints: ^5.0.0
  build_runner: ^2.5.4
  built_value_generator: ^8.10.1
  custom_lint: ^0.7.6
  riverpod_generator: ^2.6.5
  riverpod_lint: ^2.6.5

flutter:
  uses-material-design: true

pubspec.yaml ファイルでは、現在のバージョンや依存関係など、アプリの基本情報を指定します。通常の空の Flutter アプリには含まれていない依存関係のコレクションが表示されます。これらのパッケージは、以降の手順で活用します。

依存関係を理解する

コードに入る前に、これらの特定のパッケージが選択された理由を理解しましょう。

built_value: メモリを効率的に共有する不変オブジェクトを作成します。これはバックトラッキングアルゴリズムにとって重要です。
Riverpod: select() を使用してきめ細かい状態管理を提供し、再ビルドを最小限に抑えます
two_dimensional_scrollables: パフォーマンスの低下なしで大きなグリッドを処理します

lib/ ディレクトリの main.dart ファイルを開きます。

VS Code の一部のスクリーンショット。main.dart ファイルの場所を示す矢印が表示されている

このファイルの内容を次のように置き換えます。

lib/main.dart

import 'package:flutter/material.dart';
import 'package:flutter_riverpod/flutter_riverpod.dart';

void main() {
  runApp(
    ProviderScope(
      child: MaterialApp(
        title: 'Crossword Builder',
        debugShowCheckedModeBanner: false,
        theme: ThemeData(
          colorSchemeSeed: Colors.blueGrey,
          brightness: Brightness.light,
        ),
        home: Scaffold(
          body: Center(
            child: Text('Hello, World!', style: TextStyle(fontSize: 24)),
          ),
        ),
      ),
    ),
  );
}

このコードを実行して、すべてが正常に機能することを確認します。新しいウィンドウが表示され、すべての新しいプロジェクトの必須の開始フレーズが表示されます。このアプリが状態管理に riverpod を使用することを示す ProviderScope があります。

中央に「Hello, World!」と表示されたアプリウィンドウ

チェックポイント: 基本的なアプリの実行

この時点で、「Hello, World!」ウィンドウが表示されます。確認済みではない場合は:

Flutter が正しくインストールされていることを確認する
flutter run でアプリが実行されていることを確認する
ターミナルにコンパイルエラーがないことを確認する

3. 単語を追加する

クロスワードパズルの構成要素

クロスワードパズルは、基本的には単語のリストです。単語はグリッドに配置され、一部は横に、一部は縦に配置され、単語が組み合わされています。1 つの単語を解くと、その単語と交差する単語のヒントが得られます。したがって、最初の構成要素として単語のリストを作成することをおすすめします。

これらの単語の適切なソースは、Peter Norvig の Natural Language Corpus Data ページです。SOWPODS リストは 267,750 語を含む便利な出発点です。

このステップでは、単語のリストをダウンロードし、Flutter アプリのアセットとして追加して、起動時にリストをアプリに読み込むように Riverpod プロバイダを配置します。

まず、次の手順を行います。

プロジェクトの pubspec.yaml ファイルを変更して、選択した単語リストのアセット宣言を追加します。このリストには、アプリの構成の flutter スタンザのみが表示されます。残りの部分は変更されていません。

pubspec.yaml

flutter:
  uses-material-design: true
  assets:                                       # Add this line
    - assets/words.txt                          # And this one.

このファイルはまだ作成されていないため、エディタでこの最後の行が警告付きでハイライト表示される可能性があります。

ブラウザとエディタを使用して、プロジェクトの最上位に assets ディレクトリを作成し、その中に、前にリンクした単語リストのいずれかを含む words.txt ファイルを作成します。

このコードは、前述の SOWPODS リストを念頭に置いて設計されていますが、A ～ Z の文字のみで構成される単語リストであれば、どれでも使用できます。このコードベースを拡張してさまざまな文字セットを扱えるようにすることは、読者の演習として残されています。

単語を読み込む

アプリの起動時に単語リストを読み込むコードを作成する手順は次のとおりです。

lib ディレクトリに providers.dart ファイルを作成します。
ファイルに以下を追加します。

lib/providers.dart

import 'dart:convert';

import 'package:built_collection/built_collection.dart';
import 'package:flutter/services.dart';
import 'package:riverpod/riverpod.dart';
import 'package:riverpod_annotation/riverpod_annotation.dart';

part 'providers.g.dart';

/// A provider for the wordlist to use when generating the crossword.
@riverpod
Future<BuiltSet<String>> wordList(Ref ref) async {
  // This codebase requires that all words consist of lowercase characters
  // in the range 'a'-'z'. Words containing uppercase letters will be
  // lowercased, and words containing runes outside this range will
  // be removed.

  final re = RegExp(r'^[a-z]+$');
  final words = await rootBundle.loadString('assets/words.txt');
  return const LineSplitter()
      .convert(words)
      .toBuiltSet()
      .rebuild(
        (b) => b
          ..map((word) => word.toLowerCase().trim())
          ..where((word) => word.length > 2)
          ..where((word) => re.hasMatch(word)),
      );
}

これは、このコードベースの最初の Riverpod プロバイダです。

このプロバイダの仕組み:

アセットから単語リストを非同期で読み込みます
2 文字より長い a ～ z の文字のみを含むように単語をフィルタします
効率的なランダムアクセスのために変更不可能な BuiltSet を返します

このプロジェクトでは、Riverpod などの複数の依存関係にコード生成を使用しています。

コードの生成を開始するには、次のコマンドを実行します。

$ dart run build_runner watch -d
[INFO] Generating build script completed, took 174ms
[INFO] Setting up file watchers completed, took 5ms
[INFO] Waiting for all file watchers to be ready completed, took 202ms
[INFO] Reading cached asset graph completed, took 65ms
[INFO] Checking for updates since last build completed, took 680ms
[INFO] Running build completed, took 2.3s
[INFO] Caching finalized dependency graph completed, took 42ms
[INFO] Succeeded after 2.3s with 122 outputs (243 actions)

バックグラウンドで実行され続け、プロジェクトに変更を加えると生成されたファイルが更新されます。このコマンドで providers.g.dart にコードが生成されると、エディタは providers.dart に追加されたコードを認識します。

Riverpod では、前に定義した wordList 関数などのプロバイダは通常、遅延インスタンス化されます。ただし、このアプリでは、単語リストをすぐに読み込む必要があります。Riverpod のドキュメントでは、すぐに読み込む必要があるプロバイダを処理する次のアプローチが推奨されています。これを実装します。

lib/widgets ディレクトリに crossword_generator_app.dart ファイルを作成します。
ファイルに以下を追加します。

lib/widgets/crossword_generator_app.dart

import 'package:flutter/material.dart';
import 'package:flutter_riverpod/flutter_riverpod.dart';

import '../providers.dart';

class CrosswordGeneratorApp extends StatelessWidget {
  const CrosswordGeneratorApp({super.key});

  @override
  Widget build(BuildContext context) {
    return _EagerInitialization(
      child: Scaffold(
        appBar: AppBar(
          titleTextStyle: TextStyle(
            color: Theme.of(context).colorScheme.primary,
            fontSize: 16,
            fontWeight: FontWeight.bold,
          ),
          title: Text('Crossword Generator'),
        ),
        body: SafeArea(
          child: Consumer(
            builder: (context, ref, _) {
              final wordListAsync = ref.watch(wordListProvider);
              return wordListAsync.when(
                data: (wordList) => ListView.builder(
                  itemCount: wordList.length,
                  itemBuilder: (context, index) {
                    return ListTile(title: Text(wordList.elementAt(index)));
                  },
                ),
                error: (error, stackTrace) => Center(child: Text('$error')),
                loading: () => Center(child: CircularProgressIndicator()),
              );
            },
          ),
        ),
      ),
    );
  }
}

class _EagerInitialization extends ConsumerWidget {
  const _EagerInitialization({required this.child});
  final Widget child;

  @override
  Widget build(BuildContext context, WidgetRef ref) {
    ref.watch(wordListProvider);
    return child;
  }
}

このファイルは、2 つの異なる方向から興味深いものとなっています。1 つ目は _EagerInitialization ウィジェットです。これは、以前に作成した wordList プロバイダに単語リストの読み込みを要求するという唯一の役割を果たします。このウィジェットは、ref.watch() 呼び出しを使用してプロバイダをリッスンすることで、この目的を達成します。この手法の詳細については、Riverpod ドキュメントのプロバイダの事前初期化をご覧ください。

このファイルで注目すべき 2 つ目の点は、Riverpod が非同期コンテンツを処理する方法です。前述のとおり、ディスクからのコンテンツの読み込みは遅いため、wordList プロバイダは非同期関数として定義されています。このコードで単語リストプロバイダを監視すると、AsyncValue<BuiltSet<String>> が返されます。この型の AsyncValue 部分は、プロバイダの非同期の世界と Widget の build メソッドの同期の世界との間のアダプタです。

AsyncValue の when メソッドは、将来の値が取りうる 3 つの状態を処理します。フューチャーは正常に解決されている場合（data コールバックが呼び出される）、エラー状態の場合（error コールバックが呼び出される）、またはまだ読み込み中の場合があります。呼び出されたコールバックの戻り値は when メソッドによって返されるため、3 つのコールバックの戻り値の型は互換性がある必要があります。この場合、when メソッドの結果は Scaffold ウィジェットの body として表示されます。

ほぼ無限のリストアプリを作成する

CrosswordGeneratorApp ウィジェットをアプリに統合する手順は次のとおりです。

次のコードを追加して lib/main.dart ファイルを更新します。

lib/main.dart

import 'package:flutter/material.dart';
import 'package:flutter_riverpod/flutter_riverpod.dart';

import 'widgets/crossword_generator_app.dart';             // Add this import

void main() {
  runApp(
    ProviderScope(
      child: MaterialApp(
        title: 'Crossword Builder',
        debugShowCheckedModeBanner: false,
        theme: ThemeData(
          colorSchemeSeed: Colors.blueGrey,
          brightness: Brightness.light,
        ),
        home: CrosswordGeneratorApp(),                     // Remove what was here and replace
      ),
    ),
  );
}

アプリを再起動します。辞書内の 267,750 語以上の単語をすべてスクロールするリストが表示されます。

「Crossword Generator」というタイトルのアプリウィンドウと単語のリスト

次のステップ

ここでは、不変オブジェクトを使用してクロスワードパズルのコアデータ構造を作成します。この基盤により、効率的なアルゴリズムとスムーズな UI 更新が可能になります。

4. 単語をグリッドで表示する

このステップでは、built_value パッケージと built_collection パッケージを使用して、クロスワードパズルを作成するためのデータ構造を作成します。これらの 2 つのパッケージを使用すると、データ構造を不変の値として構築できます。これは、Isolate 間でデータを渡す場合と、深さ優先探索とバックトラッキングの実装を大幅に簡素化する場合の両方で役立ちます。

まず、次の手順を行います。

lib ディレクトリに model.dart ファイルを作成し、次の内容を追加します。

lib/model.dart

import 'package:built_collection/built_collection.dart';
import 'package:built_value/built_value.dart';
import 'package:built_value/serializer.dart';
import 'package:characters/characters.dart';

part 'model.g.dart';

/// A location in a crossword.
abstract class Location implements Built<Location, LocationBuilder> {
  static Serializer<Location> get serializer => _$locationSerializer;

  /// The horizontal part of the location. The location is 0 based.
  int get x;

  /// The vertical part of the location. The location is 0 based.
  int get y;

  /// Returns a new location that is one step to the left of this location.
  Location get left => rebuild((b) => b.x = x - 1);

  /// Returns a new location that is one step to the right of this location.
  Location get right => rebuild((b) => b.x = x + 1);

  /// Returns a new location that is one step up from this location.
  Location get up => rebuild((b) => b.y = y - 1);

  /// Returns a new location that is one step down from this location.
  Location get down => rebuild((b) => b.y = y + 1);

  /// Returns a new location that is [offset] steps to the left of this location.
  Location leftOffset(int offset) => rebuild((b) => b.x = x - offset);

  /// Returns a new location that is [offset] steps to the right of this location.
  Location rightOffset(int offset) => rebuild((b) => b.x = x + offset);

  /// Returns a new location that is [offset] steps up from this location.
  Location upOffset(int offset) => rebuild((b) => b.y = y - offset);

  /// Returns a new location that is [offset] steps down from this location.
  Location downOffset(int offset) => rebuild((b) => b.y = y + offset);

  /// Pretty print a location as a (x,y) coordinate.
  String prettyPrint() => '($x,$y)';

  /// Returns a new location built from [updates]. Both [x] and [y] are
  /// required to be non-null.
  factory Location([void Function(LocationBuilder)? updates]) = _$Location;
  Location._();

  /// Returns a location at the given coordinates.
  factory Location.at(int x, int y) {
    return Location((b) {
      b
        ..x = x
        ..y = y;
    });
  }
}

/// The direction of a word in a crossword.
enum Direction {
  across,
  down;

  @override
  String toString() => name;
}

/// A word in a crossword. This is a word at a location in a crossword, in either
/// the across or down direction.
abstract class CrosswordWord
    implements Built<CrosswordWord, CrosswordWordBuilder> {
  static Serializer<CrosswordWord> get serializer => _$crosswordWordSerializer;

  /// The word itself.
  String get word;

  /// The location of this word in the crossword.
  Location get location;

  /// The direction of this word in the crossword.
  Direction get direction;

  /// Compare two CrosswordWord by coordinates, x then y.
  static int locationComparator(CrosswordWord a, CrosswordWord b) {
    final compareRows = a.location.y.compareTo(b.location.y);
    final compareColumns = a.location.x.compareTo(b.location.x);
    return switch (compareColumns) {
      0 => compareRows,
      _ => compareColumns,
    };
  }

  /// Constructor for [CrosswordWord].
  factory CrosswordWord.word({
    required String word,
    required Location location,
    required Direction direction,
  }) {
    return CrosswordWord(
      (b) => b
        ..word = word
        ..direction = direction
        ..location.replace(location),
    );
  }

  /// Constructor for [CrosswordWord].
  /// Use [CrosswordWord.word] instead.
  factory CrosswordWord([void Function(CrosswordWordBuilder)? updates]) =
      _$CrosswordWord;
  CrosswordWord._();
}

/// A character in a crossword. This is a single character at a location in a
/// crossword. It may be part of an across word, a down word, both, but not
/// neither. The neither constraint is enforced elsewhere.
abstract class CrosswordCharacter
    implements Built<CrosswordCharacter, CrosswordCharacterBuilder> {
  static Serializer<CrosswordCharacter> get serializer =>
      _$crosswordCharacterSerializer;

  /// The character at this location.
  String get character;

  /// The across word that this character is a part of.
  CrosswordWord? get acrossWord;

  /// The down word that this character is a part of.
  CrosswordWord? get downWord;

  /// Constructor for [CrosswordCharacter].
  /// [acrossWord] and [downWord] are optional.
  factory CrosswordCharacter.character({
    required String character,
    CrosswordWord? acrossWord,
    CrosswordWord? downWord,
  }) {
    return CrosswordCharacter((b) {
      b.character = character;
      if (acrossWord != null) {
        b.acrossWord.replace(acrossWord);
      }
      if (downWord != null) {
        b.downWord.replace(downWord);
      }
    });
  }

  /// Constructor for [CrosswordCharacter].
  /// Use [CrosswordCharacter.character] instead.
  factory CrosswordCharacter([
    void Function(CrosswordCharacterBuilder)? updates,
  ]) = _$CrosswordCharacter;
  CrosswordCharacter._();
}

/// A crossword puzzle. This is a grid of characters with words placed in it.
/// The puzzle constraint is in the English crossword puzzle tradition.
abstract class Crossword implements Built<Crossword, CrosswordBuilder> {
  /// Serializes and deserializes the [Crossword] class.
  static Serializer<Crossword> get serializer => _$crosswordSerializer;

  /// Width across the [Crossword] puzzle.
  int get width;

  /// Height down the [Crossword] puzzle.
  int get height;

  /// The words in the crossword.
  BuiltList<CrosswordWord> get words;

  /// The characters by location. Useful for displaying the crossword.
  BuiltMap<Location, CrosswordCharacter> get characters;

  /// Add a word to the crossword at the given location and direction.
  Crossword addWord({
    required Location location,
    required String word,
    required Direction direction,
  }) {
    return rebuild(
      (b) => b
        ..words.add(
          CrosswordWord.word(
            word: word,
            direction: direction,
            location: location,
          ),
        ),
    );
  }

  /// As a finalize step, fill in the characters map.
  @BuiltValueHook(finalizeBuilder: true)
  static void _fillCharacters(CrosswordBuilder b) {
    b.characters.clear();

    for (final word in b.words.build()) {
      for (final (idx, character) in word.word.characters.indexed) {
        switch (word.direction) {
          case Direction.across:
            b.characters.updateValue(
              word.location.rightOffset(idx),
              (b) => b.rebuild((bInner) => bInner.acrossWord.replace(word)),
              ifAbsent: () => CrosswordCharacter.character(
                acrossWord: word,
                character: character,
              ),
            );
          case Direction.down:
            b.characters.updateValue(
              word.location.downOffset(idx),
              (b) => b.rebuild((bInner) => bInner.downWord.replace(word)),
              ifAbsent: () => CrosswordCharacter.character(
                downWord: word,
                character: character,
              ),
            );
        }
      }
    }
  }

  /// Pretty print a crossword. Generates the character grid, and lists
  /// the down words and across words sorted by location.
  String prettyPrintCrossword() {
    final buffer = StringBuffer();
    final grid = List.generate(
      height,
      (_) => List.generate(
        width,
        (_) => '░', // https://www.compart.com/en/unicode/U+2591
      ),
    );

    for (final MapEntry(key: Location(:x, :y), value: character)
        in characters.entries) {
      grid[y][x] = character.character;
    }

    for (final row in grid) {
      buffer.writeln(row.join());
    }

    buffer.writeln();
    buffer.writeln('Across:');
    for (final word
        in words.where((word) => word.direction == Direction.across).toList()
          ..sort(CrosswordWord.locationComparator)) {
      buffer.writeln('${word.location.prettyPrint()}: ${word.word}');
    }

    buffer.writeln();
    buffer.writeln('Down:');
    for (final word
        in words.where((word) => word.direction == Direction.down).toList()
          ..sort(CrosswordWord.locationComparator)) {
      buffer.writeln('${word.location.prettyPrint()}: ${word.word}');
    }

    return buffer.toString();
  }

  /// Constructor for [Crossword].
  factory Crossword.crossword({
    required int width,
    required int height,
    Iterable<CrosswordWord>? words,
  }) {
    return Crossword((b) {
      b
        ..width = width
        ..height = height;
      if (words != null) {
        b.words.addAll(words);
      }
    });
  }

  /// Constructor for [Crossword].
  /// Use [Crossword.crossword] instead.
  factory Crossword([void Function(CrosswordBuilder)? updates]) = _$Crossword;
  Crossword._();
}

/// Construct the serialization/deserialization code for the data model.
@SerializersFor([Location, Crossword, CrosswordWord, CrosswordCharacter])
final Serializers serializers = _$serializers;

このファイルには、クロスワードパズルを作成するために使用するデータ構造の開始部分が記述されています。クロスワードパズルは、グリッド内で水平方向と垂直方向の単語が組み合わされたリストです。このデータ構造を使用するには、Crossword.crossword という名前のコンストラクタを使用して適切なサイズの Crossword を構築し、addWord メソッドを使用して単語を追加します。最終的な値を構築する過程で、_fillCharacters メソッドによって CrosswordCharacter のグリッドが作成されます。

このデータ構造を使用する手順は次のとおりです。

lib ディレクトリに utils ファイルを作成し、次の内容を追加します。

lib/utils.dart

import 'dart:math';

import 'package:built_collection/built_collection.dart';

/// A [Random] instance for generating random numbers.
final _random = Random();

/// An extension on [BuiltSet] that adds a method to get a random element.
extension RandomElements<E> on BuiltSet<E> {
  E randomElement() {
    return elementAt(_random.nextInt(length));
  }
}

これは BuiltSet の拡張機能で、セットのランダムな要素を簡単に取得できます。拡張メソッドは、追加機能でクラスを拡張するのに適しています。拡張機能を utils.dart ファイルの外部で使用できるようにするには、拡張機能に名前を付ける必要があります。

lib/providers.dart ファイルに次のインポートを追加します。

lib/providers.dart

import 'dart:convert';
import 'dart:math';                                        // Add this import

import 'package:built_collection/built_collection.dart';
import 'package:flutter/foundation.dart';                  // Add this import
import 'package:flutter/services.dart';
import 'package:riverpod_annotation/riverpod_annotation.dart';

import 'model.dart' as model;                              // And this import
import 'utils.dart';                                       // And this one

part 'providers.g.dart';

/// A provider for the wordlist to use when generating the crossword.
@riverpod
Future<BuiltSet<String>> wordList(WordListRef ref) async {

これらのインポートにより、以前に定義したモデルが、これから作成するプロバイダに公開されます。dart:math インポートは Random 用、flutter/foundation.dart インポートは debugPrint 用、model.dart はモデル用、utils.dart は BuiltSet 拡張機能用です。

同じファイルの末尾に、次のプロバイダを追加します。

lib/providers.dart

/// An enumeration for different sizes of [model.Crossword]s.
enum CrosswordSize {
  small(width: 20, height: 11),
  medium(width: 40, height: 22),
  large(width: 80, height: 44),
  xlarge(width: 160, height: 88),
  xxlarge(width: 500, height: 500);

  const CrosswordSize({required this.width, required this.height});

  final int width;
  final int height;
  String get label => '$width x $height';
}

/// A provider that holds the current size of the crossword to generate.
@Riverpod(keepAlive: true)
class Size extends _$Size {
  var _size = CrosswordSize.medium;

  @override
  CrosswordSize build() => _size;

  void setSize(CrosswordSize size) {
    _size = size;
    ref.invalidateSelf();
  }
}

final _random = Random();

@riverpod
Stream<model.Crossword> crossword(Ref ref) async* {
  final size = ref.watch(sizeProvider);
  final wordListAsync = ref.watch(wordListProvider);

  var crossword = model.Crossword.crossword(
    width: size.width,
    height: size.height,
  );

  yield* wordListAsync.when(
    data: (wordList) async* {
      while (crossword.characters.length < size.width * size.height * 0.8) {
        final word = wordList.randomElement();
        final direction = _random.nextBool()
            ? model.Direction.across
            : model.Direction.down;
        final location = model.Location.at(
          _random.nextInt(size.width),
          _random.nextInt(size.height),
        );

        crossword = crossword.addWord(
          word: word,
          direction: direction,
          location: location,
        );
        yield crossword;
        await Future.delayed(Duration(milliseconds: 100));
      }

      yield crossword;
    },
    error: (error, stackTrace) async* {
      debugPrint('Error loading word list: $error');
      yield crossword;
    },
    loading: () async* {
      yield crossword;
    },
  );
}

これらの変更により、アプリに 2 つのプロバイダが追加されます。1 つ目は Size です。これは、CrosswordSize 列挙型の選択された値を含むグローバル変数です。これにより、UI で作成中のクロスワードのサイズを表示および設定できるようになります。2 つ目のプロバイダ crossword は、より興味深い作成です。これは、一連の Crossword を返す関数です。これは、関数の async* で示されるように、Dart のジェネレータのサポートを使用して構築されています。つまり、return で終了するのではなく、一連の Crossword を生成します。これは、中間結果を返す計算を記述するはるかに簡単な方法です。

crossword プロバイダ関数の先頭に ref.watch 呼び出しのペアがあるため、クロスワードの選択されたサイズが変更されるたび、および単語リストの読み込みが完了するたびに、Crossword のストリームが Riverpod システムによって再開されます。

これで、ランダムな単語ばかりですが、クロスワードを生成するコードができました。ツールを使用するユーザーにクロスワードを表示するとよいでしょう。

lib/widgets ディレクトリに、次の内容の crossword_widget.dart ファイルを作成します。

lib/widgets/crossword_widget.dart

import 'package:flutter/material.dart';
import 'package:flutter_riverpod/flutter_riverpod.dart';
import 'package:two_dimensional_scrollables/two_dimensional_scrollables.dart';

import '../model.dart';
import '../providers.dart';

class CrosswordWidget extends ConsumerWidget {
  const CrosswordWidget({super.key});

  @override
  Widget build(BuildContext context, WidgetRef ref) {
    final size = ref.watch(sizeProvider);
    return TableView.builder(
      diagonalDragBehavior: DiagonalDragBehavior.free,
      cellBuilder: _buildCell,
      columnCount: size.width,
      columnBuilder: (index) => _buildSpan(context, index),
      rowCount: size.height,
      rowBuilder: (index) => _buildSpan(context, index),
    );
  }

  TableViewCell _buildCell(BuildContext context, TableVicinity vicinity) {
    final location = Location.at(vicinity.column, vicinity.row);

    return TableViewCell(
      child: Consumer(
        builder: (context, ref, _) {
          final character = ref.watch(
            crosswordProvider.select(
              (crosswordAsync) => crosswordAsync.when(
                data: (crossword) => crossword.characters[location],
                error: (error, stackTrace) => null,
                loading: () => null,
              ),
            ),
          );

          if (character != null) {
            return Container(
              color: Theme.of(context).colorScheme.onPrimary,
              child: Center(
                child: Text(
                  character.character,
                  style: TextStyle(
                    fontSize: 24,
                    color: Theme.of(context).colorScheme.primary,
                  ),
                ),
              ),
            );
          }

          return ColoredBox(
            color: Theme.of(context).colorScheme.primaryContainer,
          );
        },
      ),
    );
  }

  TableSpan _buildSpan(BuildContext context, int index) {
    return TableSpan(
      extent: FixedTableSpanExtent(32),
      foregroundDecoration: TableSpanDecoration(
        border: TableSpanBorder(
          leading: BorderSide(
            color: Theme.of(context).colorScheme.onPrimaryContainer,
          ),
          trailing: BorderSide(
            color: Theme.of(context).colorScheme.onPrimaryContainer,
          ),
        ),
      ),
    );
  }
}

このウィジェットは ConsumerWidget であるため、Size プロバイダに直接依存して、Crossword の文字を表示するグリッドのサイズを決定できます。このグリッドの表示は、two_dimensional_scrollables パッケージの TableView ウィジェットで行われます。

_buildCell ヘルパー関数によってレンダリングされる個々のセルは、それぞれ返される Widget ツリーに Consumer ウィジェットを含んでいることに注意してください。これは更新境界として機能します。ref.watch の戻り値が変更されると、Consumer ウィジェット内のすべてのものが再作成されます。Crossword が変更されるたびにツリー全体を再作成したくなりますが、この設定を使用すると、多くの計算をスキップできます。

ref.watch のパラメータを見ると、crosswordProvider.select を使用してレイアウトの再計算を回避する別のレイヤがあることがわかります。つまり、ref.watch は、セルがレンダリングを担当する文字が変更された場合にのみ、TableViewCell のコンテンツの再構築をトリガーします。この再レンダリングの削減は、UI のレスポンシブ性を維持するうえで不可欠です。

CrosswordWidget プロバイダと Size プロバイダをユーザーに公開するには、crossword_generator_app.dart ファイルを次のように変更します。

lib/widgets/crossword_generator_app.dart

import 'package:flutter/material.dart';
import 'package:flutter_riverpod/flutter_riverpod.dart';

import '../providers.dart';
import 'crossword_widget.dart';                               // Add this import

class CrosswordGeneratorApp extends StatelessWidget {
  const CrosswordGeneratorApp({super.key});

  @override
  Widget build(BuildContext context) {
    return _EagerInitialization(
      child: Scaffold(
        appBar: AppBar(
          actions: [_CrosswordGeneratorMenu()],               // Add this line
          titleTextStyle: TextStyle(
            color: Theme.of(context).colorScheme.primary,
            fontSize: 16,
            fontWeight: FontWeight.bold,
          ),
          title: Text('Crossword Generator'),
        ),
        body: SafeArea(child: CrosswordWidget()),             // Replace what was here before
      ),
    );
  }
}

class _EagerInitialization extends ConsumerWidget {
  const _EagerInitialization({required this.child});
  final Widget child;

  @override
  Widget build(BuildContext context, WidgetRef ref) {
    ref.watch(wordListProvider);
    return child;
  }
}

class _CrosswordGeneratorMenu extends ConsumerWidget {        // Add from here
  @override
  Widget build(BuildContext context, WidgetRef ref) => MenuAnchor(
    menuChildren: [
      for (final entry in CrosswordSize.values)
        MenuItemButton(
          onPressed: () => ref.read(sizeProvider.notifier).setSize(entry),
          leadingIcon: entry == ref.watch(sizeProvider)
              ? Icon(Icons.radio_button_checked_outlined)
              : Icon(Icons.radio_button_unchecked_outlined),
          child: Text(entry.label),
        ),
    ],
    builder: (context, controller, child) => IconButton(
      onPressed: () => controller.open(),
      icon: Icon(Icons.settings),
    ),
  );                                                          // To here.
}

ここで、いくつかの変更が行われています。まず、wordList を ListView としてレンダリングするコードが、lib/widgets/crossword_widget.dart ファイルで定義された CrosswordWidget の呼び出しに置き換えられました。もう 1 つの大きな変更点は、アプリの動作を変更するためのメニューが追加されたことです。最初はクロスワードのサイズを変更する機能から始まります。今後のステップで MenuItemButton が追加されます。アプリを実行すると、次のように表示されます。

「Crossword Generator」というタイトルのアプリウィンドウと、重なり合う単語として配置された文字のグリッド。韻を踏んだり、理由があったりするわけではない。

グリッドに文字が表示され、ユーザーがグリッドのサイズを変更できるメニューが表示されます。ただし、クロスワードパズルのように単語が配置されているわけではありません。これは、クロスワードに単語を追加する方法に制約を適用していないためです。つまり、めちゃくちゃです。次のステップで制御を開始します。

5. 制約を適用する

変更点とその理由

現在、クロスワードでは単語の重複が許可されており、検証は行われていません。制約チェックを追加して、単語が実際のクロスワードパズルのように適切に組み合わされるようにします。

このステップの目標は、クロスワードパズルの制約を適用するコードをモデルに追加することです。クロスワードパズルにはさまざまな種類がありますが、この Codelab で使用するスタイルは、英語のクロスワードパズルの伝統に沿ったものです。このコードを変更して他のスタイルのクロスワードパズルを生成する作業は、いつものように読者の練習問題として残しておきます。

まず、次の手順を行います。

model.dart ファイルを開き、Crossword モデルのみを次のように置き換えます。

lib/model.dart

/// A crossword puzzle. This is a grid of characters with words placed in it.
/// The puzzle constraint is in the English crossword puzzle tradition.
abstract class Crossword implements Built<Crossword, CrosswordBuilder> {
  /// Serializes and deserializes the [Crossword] class.
  static Serializer<Crossword> get serializer => _$crosswordSerializer;

  /// Width across the [Crossword] puzzle.
  int get width;

  /// Height down the [Crossword] puzzle.
  int get height;

  /// The words in the crossword.
  BuiltList<CrosswordWord> get words;

  /// The characters by location. Useful for displaying the crossword,
  /// or checking the proposed solution.
  BuiltMap<Location, CrosswordCharacter> get characters;

  /// Checks if this crossword is valid.
  bool get valid {
    // Check that there are no duplicate words.
    final wordSet = words.map((word) => word.word).toBuiltSet();
    if (wordSet.length != words.length) {
      return false;
    }

    for (final MapEntry(key: location, value: character)
        in characters.entries) {
      // All characters must be a part of an across or down word.
      if (character.acrossWord == null && character.downWord == null) {
        return false;
      }

      // All characters must be within the crossword puzzle.
      // No drawing outside the lines.
      if (location.x < 0 ||
          location.y < 0 ||
          location.x >= width ||
          location.y >= height) {
        return false;
      }

      // Characters above and below this character must be related
      // by a vertical word
      if (characters[location.up] case final up?) {
        if (character.downWord == null) {
          return false;
        }
        if (up.downWord != character.downWord) {
          return false;
        }
      }

      if (characters[location.down] case final down?) {
        if (character.downWord == null) {
          return false;
        }
        if (down.downWord != character.downWord) {
          return false;
        }
      }

      // Characters to the left and right of this character must be
      // related by a horizontal word
      final left = characters[location.left];
      if (left != null) {
        if (character.acrossWord == null) {
          return false;
        }
        if (left.acrossWord != character.acrossWord) {
          return false;
        }
      }

      final right = characters[location.right];
      if (right != null) {
        if (character.acrossWord == null) {
          return false;
        }
        if (right.acrossWord != character.acrossWord) {
          return false;
        }
      }
    }

    return true;
  }

  /// Add a word to the crossword at the given location and direction.
  Crossword? addWord({
    required Location location,
    required String word,
    required Direction direction,
  }) {
    // Require that the word is not already in the crossword.
    if (words.map((crosswordWord) => crosswordWord.word).contains(word)) {
      return null;
    }

    final wordCharacters = word.characters;
    bool overlap = false;

    // Check that the word fits in the crossword.
    for (final (index, character) in wordCharacters.indexed) {
      final characterLocation = switch (direction) {
        Direction.across => location.rightOffset(index),
        Direction.down => location.downOffset(index),
      };

      final target = characters[characterLocation];
      if (target != null) {
        overlap = true;
        if (target.character != character) {
          return null;
        }
        if (direction == Direction.across && target.acrossWord != null ||
            direction == Direction.down && target.downWord != null) {
          return null;
        }
      }
    }
    if (words.isNotEmpty && !overlap) {
      return null;
    }

    final candidate = rebuild(
      (b) => b
        ..words.add(
          CrosswordWord.word(
            word: word,
            direction: direction,
            location: location,
          ),
        ),
    );

    if (candidate.valid) {
      return candidate;
    } else {
      return null;
    }
  }

  /// As a finalize step, fill in the characters map.
  @BuiltValueHook(finalizeBuilder: true)
  static void _fillCharacters(CrosswordBuilder b) {
    b.characters.clear();

    for (final word in b.words.build()) {
      for (final (idx, character) in word.word.characters.indexed) {
        switch (word.direction) {
          case Direction.across:
            b.characters.updateValue(
              word.location.rightOffset(idx),
              (b) => b.rebuild((bInner) => bInner.acrossWord.replace(word)),
              ifAbsent: () => CrosswordCharacter.character(
                acrossWord: word,
                character: character,
              ),
            );
          case Direction.down:
            b.characters.updateValue(
              word.location.downOffset(idx),
              (b) => b.rebuild((bInner) => bInner.downWord.replace(word)),
              ifAbsent: () => CrosswordCharacter.character(
                downWord: word,
                character: character,
              ),
            );
        }
      }
    }
  }

  /// Pretty print a crossword. Generates the character grid, and lists
  /// the down words and across words sorted by location.
  String prettyPrintCrossword() {
    final buffer = StringBuffer();
    final grid = List.generate(
      height,
      (_) => List.generate(
        width,
        (_) => '░', // https://www.compart.com/en/unicode/U+2591
      ),
    );

    for (final MapEntry(key: Location(:x, :y), value: character)
        in characters.entries) {
      grid[y][x] = character.character;
    }

    for (final row in grid) {
      buffer.writeln(row.join());
    }

    buffer.writeln();
    buffer.writeln('Across:');
    for (final word
        in words.where((word) => word.direction == Direction.across).toList()
          ..sort(CrosswordWord.locationComparator)) {
      buffer.writeln('${word.location.prettyPrint()}: ${word.word}');
    }

    buffer.writeln();
    buffer.writeln('Down:');
    for (final word
        in words.where((word) => word.direction == Direction.down).toList()
          ..sort(CrosswordWord.locationComparator)) {
      buffer.writeln('${word.location.prettyPrint()}: ${word.word}');
    }

    return buffer.toString();
  }

  /// Constructor for [Crossword].
  factory Crossword.crossword({
    required int width,
    required int height,
    Iterable<CrosswordWord>? words,
  }) {
    return Crossword((b) {
      b
        ..width = width
        ..height = height;
      if (words != null) {
        b.words.addAll(words);
      }
    });
  }

  /// Constructor for [Crossword].
  /// Use [Crossword.crossword] instead.
  factory Crossword([void Function(CrosswordBuilder)? updates]) = _$Crossword;
  Crossword._();
}

model.dart ファイルと providers.dart ファイルに対して行う変更では、それぞれの model.g.dart ファイルと providers.g.dart ファイルを更新するために build_runner を実行する必要があります。これらのファイルが自動的に更新されていない場合は、dart run build_runner watch -d を使用して build_runner を再開することをおすすめします。

モデルレイヤのこの新機能を利用するには、プロバイダレイヤを更新して一致させる必要があります。

providers.dart ファイルを次のように編集します。

lib/providers.dart

import 'dart:convert';
import 'dart:math';

import 'package:built_collection/built_collection.dart';
import 'package:flutter/foundation.dart';
import 'package:flutter/services.dart';
import 'package:riverpod_annotation/riverpod_annotation.dart';

import 'model.dart' as model;
import 'utils.dart';

part 'providers.g.dart';

/// A provider for the wordlist to use when generating the crossword.
@riverpod
Future<BuiltSet<String>> wordList(WordListRef ref) async {
  // This codebase requires that all words consist of lowercase characters
  // in the range 'a'-'z'. Words containing uppercase letters will be
  // lowercased, and words containing runes outside this range will
  // be removed.

  final re = RegExp(r'^[a-z]+$');
  final words = await rootBundle.loadString('assets/words.txt');
  return const LineSplitter().convert(words).toBuiltSet().rebuild((b) => b
    ..map((word) => word.toLowerCase().trim())
    ..where((word) => word.length > 2)
    ..where((word) => re.hasMatch(word)));
}

/// An enumeration for different sizes of [model.Crossword]s.
enum CrosswordSize {
  small(width: 20, height: 11),
  medium(width: 40, height: 22),
  large(width: 80, height: 44),
  xlarge(width: 160, height: 88),
  xxlarge(width: 500, height: 500);

  const CrosswordSize({
    required this.width,
    required this.height,
  });

  final int width;
  final int height;
  String get label => '$width x $height';
}

/// A provider that holds the current size of the crossword to generate.
@Riverpod(keepAlive: true)
class Size extends _$Size {
  var _size = CrosswordSize.medium;

  @override
  CrosswordSize build() => _size;

  void setSize(CrosswordSize size) {
    _size = size;
    ref.invalidateSelf();
  }
}

final _random = Random();

@riverpod
Stream<model.Crossword> crossword(CrosswordRef ref) async* {
  final size = ref.watch(sizeProvider);
  final wordListAsync = ref.watch(wordListProvider);

  var crossword =
      model.Crossword.crossword(width: size.width, height: size.height);

  yield* wordListAsync.when(
    data: (wordList) async* {
      while (crossword.characters.length < size.width * size.height * 0.8) {
        final word = wordList.randomElement();
        final direction =
            _random.nextBool() ? model.Direction.across : model.Direction.down;
        final location = model.Location.at(
            _random.nextInt(size.width), _random.nextInt(size.height));

        var candidate = crossword.addWord(                 // Edit from here
            word: word, direction: direction, location: location);
        await Future.delayed(Duration(milliseconds: 10));
        if (candidate != null) {
          debugPrint('Added word: $word');
          crossword = candidate;
          yield crossword;
        } else {
          debugPrint('Failed to add word: $word');
        }                                                  // To here.
      }

      yield crossword;
    },
    error: (error, stackTrace) async* {
      debugPrint('Error loading word list: $error');
      yield crossword;
    },
    loading: () async* {
      yield crossword;
    },
  );
}

アプリを実行します。UI ではあまり変化はありませんが、ログを見ると多くの処理が行われていることがわかります。

クロスワードジェネレータアプリのウィンドウ。単語が縦横に配置され、ランダムなポイントで交差している

ここで何が起こっているかを考えてみましょう。クロスワードパズルがランダムに表示されています。Crossword モデルの addWord メソッドは、現在のクロスワードに当てはまらない単語の候補をすべて拒否しているため、何らかの単語が表示されるのは驚くべきことです。

バックグラウンド処理に移行する理由

クロスワードの生成中に UI が応答しなくなることがあります。これは、クロスワードパズルの生成に数千もの検証チェックが必要になるためです。これらの計算は Flutter の 60 fps レンダリングループをブロックするため、重い計算はバックグラウンドの分離に移動します。この方法には、パズルがバックグラウンドで生成されている間も UI がスムーズに動作するというメリットがあります。

どの単語をどこで試すかをより体系的に選択する準備として、この計算を UI スレッドからバックグラウンド分離に移動すると非常に便利です。Flutter には、作業のチャンクを取得してバックグラウンドの分離で実行するための非常に便利なラッパー（compute 関数）があります。

providers.dart ファイルで、クロスワードプロバイダを次のように変更します。

lib/providers.dart

@riverpod
Stream<model.Crossword> crossword(Ref ref) async* {
  final size = ref.watch(sizeProvider);
  final wordListAsync = ref.watch(wordListProvider);

  var crossword = model.Crossword.crossword(
    width: size.width,
    height: size.height,
  );

  yield* wordListAsync.when(
    data: (wordList) async* {
      while (crossword.characters.length < size.width * size.height * 0.8) {
        final word = wordList.randomElement();
        final direction = _random.nextBool()
            ? model.Direction.across
            : model.Direction.down;
        final location = model.Location.at(
          _random.nextInt(size.width),
          _random.nextInt(size.height),
        );
        try {                                              // Edit from here
          var candidate = await compute((
            (String, model.Direction, model.Location) wordToAdd,
          ) {
            final (word, direction, location) = wordToAdd;
            return crossword.addWord(
              word: word,
              direction: direction,
              location: location,
            );
          }, (word, direction, location));

          if (candidate != null) {
            crossword = candidate;
            yield crossword;
          }
        } catch (e) {
          debugPrint('Error running isolate: $e');
        }                                                  // To here.
      }

      yield crossword;
    },
    error: (error, stackTrace) async* {
      debugPrint('Error loading word list: $error');
      yield crossword;
    },
    loading: () async* {
      yield crossword;
    },
  );
}

分離制限について

このコードは機能しますが、隠れた問題があります。Isolate 間で渡すことができるデータには厳しいルールがあり、クロージャがプロバイダ参照を「キャプチャ」するという問題があります。この参照はシリアル化して別の Isolate に送信することはできません。

シリアル化できないデータを送信しようとすると、次のようなメッセージが表示されます。

flutter: Error running isolate: Invalid argument(s): Illegal argument in isolate message: object is unsendable - Library:'dart:async' Class: _Future@4048458 (see restrictions listed at `SendPort.send()` documentation for more information)
flutter:  <- Instance of 'AutoDisposeStreamProviderElement<Crossword>' (from package:riverpod/src/stream_provider.dart)
flutter:  <- Context num_variables: 2 <- Context num_variables: 1 parent:{ Context num_variables: 2 }
flutter:  <- Context num_variables: 1 parent:{ Context num_variables: 1 parent:{ Context num_variables: 2 } }
flutter:  <- Closure: () => Crossword? (from package:generate_crossword/providers.dart)

これは、compute がバックグラウンド分離に渡すクロージャが、SendPort.send() で送信できないプロバイダを閉じていることが原因です。この問題を解決するには、クロージャがキャプチャするものが送信可能であることを確認します。

最初の手順は、プロバイダを Isolate コードから分離することです。

lib ディレクトリに isolates.dart ファイルを作成し、次の内容を追加します。

lib/isolates.dart

import 'dart:math';

import 'package:built_collection/built_collection.dart';
import 'package:flutter/foundation.dart';

import 'model.dart';
import 'utils.dart';

final _random = Random();

Stream<Crossword> exploreCrosswordSolutions({
  required Crossword crossword,
  required BuiltSet<String> wordList,
}) async* {
  while (crossword.characters.length <
      crossword.width * crossword.height * 0.8) {
    final word = wordList.randomElement();
    final direction = _random.nextBool() ? Direction.across : Direction.down;
    final location = Location.at(
      _random.nextInt(crossword.width),
      _random.nextInt(crossword.height),
    );
    try {
      var candidate = await compute(((String, Direction, Location) wordToAdd) {
        final (word, direction, location) = wordToAdd;
        return crossword.addWord(
          word: word,
          direction: direction,
          location: location,
        );
      }, (word, direction, location));

      if (candidate != null) {
        crossword = candidate;
        yield crossword;
      }
    } catch (e) {
      debugPrint('Error running isolate: $e');
    }
  }
}

このコードは、それほど見慣れないものではないはずです。これは crossword プロバイダにあったもののコアですが、現在はスタンドアロンのジェネレータ関数として存在します。これで、この新しい関数を使用してバックグラウンド分離をインスタンス化するように providers.dart ファイルを更新できます。

lib/providers.dart

// Drop the dart:math import, the _random instance moved to isolates.dart
import 'dart:convert';

import 'package:built_collection/built_collection.dart';
import 'package:flutter/foundation.dart';
import 'package:flutter/services.dart';
import 'package:riverpod/riverpod.dart';
import 'package:riverpod_annotation/riverpod_annotation.dart';

import 'isolates.dart';                                    // Add this import
import 'model.dart' as model;
                                                           // Drop the utils.dart import

part 'providers.g.dart';

/// A provider for the wordlist to use when generating the crossword.
@riverpod
Future<BuiltSet<String>> wordList(Ref ref) async {
  // This codebase requires that all words consist of lowercase characters
  // in the range 'a'-'z'. Words containing uppercase letters will be
  // lowercased, and words containing runes outside this range will
  // be removed.

  final re = RegExp(r'^[a-z]+$');
  final words = await rootBundle.loadString('assets/words.txt');
  return const LineSplitter()
      .convert(words)
      .toBuiltSet()
      .rebuild(
        (b) => b
          ..map((word) => word.toLowerCase().trim())
          ..where((word) => word.length > 2)
          ..where((word) => re.hasMatch(word)),
      );
}

/// An enumeration for different sizes of [model.Crossword]s.
enum CrosswordSize {
  small(width: 20, height: 11),
  medium(width: 40, height: 22),
  large(width: 80, height: 44),
  xlarge(width: 160, height: 88),
  xxlarge(width: 500, height: 500);

  const CrosswordSize({required this.width, required this.height});

  final int width;
  final int height;
  String get label => '$width x $height';
}

/// A provider that holds the current size of the crossword to generate.
@Riverpod(keepAlive: true)
class Size extends _$Size {
  var _size = CrosswordSize.medium;

  @override
  CrosswordSize build() => _size;

  void setSize(CrosswordSize size) {
    _size = size;
    ref.invalidateSelf();
  }
}
                                                           // Drop the _random instance
@riverpod
Stream<model.Crossword> crossword(Ref ref) async* {
  final size = ref.watch(sizeProvider);
  final wordListAsync = ref.watch(wordListProvider);

  final emptyCrossword = model.Crossword.crossword(        // Edit from here
    width: size.width,
    height: size.height,
  );

  yield* wordListAsync.when(
    data: (wordList) => exploreCrosswordSolutions(
      crossword: emptyCrossword,
      wordList: wordList,
    ),
    error: (error, stackTrace) async* {
      debugPrint('Error loading word list: $error');
      yield emptyCrossword;
    },
    loading: () async* {
      yield emptyCrossword;                                // To here.
    },
  );
}

これで、さまざまなサイズのクロスワードパズルを作成するツールが完成しました。パズルの答えを求める処理はバックグラウンドの分離で実行されます。computeクロスワードパズルに追加する単語を決定する際に、コードの効率が向上すればよいのですが。

6. 作業キューを管理する

検索戦略を理解する

クロスワードパズルの生成には、体系的な試行錯誤のアプローチであるバックトラッキングが使用されます。まず、アプリは単語をある場所に配置しようとし、次に、その単語が既存の単語に適合するかどうかを確認します。候補が表示されたら、その候補を保持して次の単語を入力します。使用できない場合は、取り外して別の場所で試してください。

クロスワードパズルでは、各単語の配置によって今後の単語の制約が作成され、無効な配置はすぐに検出されて破棄されるため、バックトラッキングが機能します。不変データ構造により、変更の「取り消し」が効率的になります。

現在のコードの問題の一部は、解決しようとしている問題が事実上検索問題であり、現在の解決策がブラインド検索であることです。コードがグリッドのどこにでも単語をランダムに配置しようとするのではなく、現在の単語に付加される単語を見つけることに集中すれば、システムはより速く解決策を見つけることができます。このアプローチの 1 つは、単語を検索する場所の作業キューを導入することです。

コードは候補ソリューションを構築し、候補ソリューションが有効かどうかを確認します。有効性に応じて、候補を組み込むか破棄します。これは、バックトラッキングアルゴリズムファミリーの実装例です。この実装は、built_value と built_collection によって大幅に簡素化されます。これらを使用すると、導出元の不変の値と共通の状態を導出して共有する新しい不変の値を作成できます。これにより、ディープコピーに必要なメモリ費用をかけずに、候補を安価に活用できます。

まず、次の手順を行います。

model.dart ファイルを開き、次の WorkQueue 定義を追加します。

lib/model.dart

  /// Constructor for [Crossword].
  /// Use [Crossword.crossword] instead.
  factory Crossword([void Function(CrosswordBuilder)? updates]) = _$Crossword;
  Crossword._();
}
                                                           // Add from here
/// A work queue for a worker to process. The work queue contains a crossword
/// and a list of locations to try, along with candidate words to add to the
/// crossword.
abstract class WorkQueue implements Built<WorkQueue, WorkQueueBuilder> {
  static Serializer<WorkQueue> get serializer => _$workQueueSerializer;

  /// The crossword the worker is working on.
  Crossword get crossword;

  /// The outstanding queue of locations to try.
  BuiltMap<Location, Direction> get locationsToTry;

  /// Known bad locations.
  BuiltSet<Location> get badLocations;

  /// The list of unused candidate words that can be added to this crossword.
  BuiltSet<String> get candidateWords;

  /// Returns true if the work queue is complete.
  bool get isCompleted => locationsToTry.isEmpty || candidateWords.isEmpty;

  /// Create a work queue from a crossword.
  static WorkQueue from({
    required Crossword crossword,
    required Iterable<String> candidateWords,
    required Location startLocation,
  }) => WorkQueue((b) {
    if (crossword.words.isEmpty) {
      // Strip candidate words too long to fit in the crossword
      b.candidateWords.addAll(
        candidateWords.where(
          (word) => word.characters.length <= crossword.width,
        ),
      );

      b.crossword.replace(crossword);

      b.locationsToTry.addAll({startLocation: Direction.across});
    } else {
      // Assuming words have already been stripped to length
      b.candidateWords.addAll(
        candidateWords.toBuiltSet().rebuild(
          (b) => b.removeAll(crossword.words.map((word) => word.word)),
        ),
      );
      b.crossword.replace(crossword);
      crossword.characters
          .rebuild(
            (b) => b.removeWhere((location, character) {
              if (character.acrossWord != null && character.downWord != null) {
                return true;
              }
              final left = crossword.characters[location.left];
              if (left != null && left.downWord != null) return true;
              final right = crossword.characters[location.right];
              if (right != null && right.downWord != null) return true;
              final up = crossword.characters[location.up];
              if (up != null && up.acrossWord != null) return true;
              final down = crossword.characters[location.down];
              if (down != null && down.acrossWord != null) return true;
              return false;
            }),
          )
          .forEach((location, character) {
            b.locationsToTry.addAll({
              location: switch ((character.acrossWord, character.downWord)) {
                (null, null) => throw StateError(
                  'Character is not part of a word',
                ),
                (null, _) => Direction.across,
                (_, null) => Direction.down,
                (_, _) => throw StateError('Character is part of two words'),
              },
            });
          });
    }
  });

  WorkQueue remove(Location location) => rebuild(
    (b) => b
      ..locationsToTry.remove(location)
      ..badLocations.add(location),
  );

  /// Update the work queue from a crossword derived from the current crossword
  /// that this work queue is built from.
  WorkQueue updateFrom(final Crossword crossword) =>
      WorkQueue.from(
        crossword: crossword,
        candidateWords: candidateWords,
        startLocation: locationsToTry.isNotEmpty
            ? locationsToTry.keys.first
            : Location.at(0, 0),
      ).rebuild(
        (b) => b
          ..badLocations.addAll(badLocations)
          ..locationsToTry.removeWhere(
            (location, _) => badLocations.contains(location),
          ),
      );

  /// Factory constructor for [WorkQueue]
  factory WorkQueue([void Function(WorkQueueBuilder)? updates]) = _$WorkQueue;

  WorkQueue._();
}                                                          // To here.

/// Construct the serialization/deserialization code for the data model.
@SerializersFor([
  Location,
  Crossword,
  CrosswordWord,
  CrosswordCharacter,
  WorkQueue,                                               // Add this line
])
final Serializers serializers = _$serializers;

この新しいコンテンツを追加してから数秒以上経過しても、このファイルに赤い波線が残っている場合は、build_runner がまだ実行されていることを確認します。そうでない場合は、dart run build_runner watch -d コマンドを実行します。

これから紹介するコードでは、さまざまなサイズのクロスワードパズルを作成するのにかかる時間を示すロギングを追加します。期間が適切にフォーマットされた形式で表示されると便利です。幸いなことに、拡張メソッドを使用すると、必要なメソッドを正確に追加できます。

utils.dart ファイルを次のように編集します。

lib/utils.dart

import 'dart:math';

import 'package:built_collection/built_collection.dart';

/// A [Random] instance for generating random numbers.
final _random = Random();

/// An extension on [BuiltSet] that adds a method to get a random element.
extension RandomElements<E> on BuiltSet<E> {
  E randomElement() {
    return elementAt(_random.nextInt(length));
  }
}
                                                              // Add from here
/// An extension on [Duration] that adds a method to format the duration.
extension DurationFormat on Duration {
  /// A human-readable string representation of the duration.
  /// This format is tuned for durations in the seconds to days range.
  String get formatted {
    final hours = inHours.remainder(24).toString().padLeft(2, '0');
    final minutes = inMinutes.remainder(60).toString().padLeft(2, '0');
    final seconds = inSeconds.remainder(60).toString().padLeft(2, '0');
    return switch ((inDays, inHours, inMinutes, inSeconds)) {
      (0, 0, 0, _) => '${inSeconds}s',
      (0, 0, _, _) => '$inMinutes:$seconds',
      (0, _, _, _) => '$inHours:$minutes:$seconds',
      _ => '$inDays days, $hours:$minutes:$seconds',
    };
  }
}                                                             // To here.

この拡張メソッドでは、レコードに対するスイッチ式とパターンマッチングを利用して、秒から日までのさまざまな期間を表示する適切な方法を選択します。このスタイルのコードの詳細については、Dart のパターンとレコードを詳しく見る Codelab をご覧ください。

この新機能を統合するには、isolates.dart ファイルを置き換えて、exploreCrosswordSolutions 関数の定義方法を次のように再定義します。

lib/isolates.dart

import 'package:built_collection/built_collection.dart';
import 'package:characters/characters.dart';
import 'package:flutter/foundation.dart';

import 'model.dart';
import 'utils.dart';

Stream<Crossword> exploreCrosswordSolutions({
  required Crossword crossword,
  required BuiltSet<String> wordList,
}) async* {
  final start = DateTime.now();
  var workQueue = WorkQueue.from(
    crossword: crossword,
    candidateWords: wordList,
    startLocation: Location.at(0, 0),
  );
  while (!workQueue.isCompleted) {
    final location = workQueue.locationsToTry.keys.toBuiltSet().randomElement();
    try {
      final crossword = await compute(((WorkQueue, Location) workMessage) {
        final (workQueue, location) = workMessage;
        final direction = workQueue.locationsToTry[location]!;
        final target = workQueue.crossword.characters[location];
        if (target == null) {
          return workQueue.crossword.addWord(
            direction: direction,
            location: location,
            word: workQueue.candidateWords.randomElement(),
          );
        }
        var words = workQueue.candidateWords.toBuiltList().rebuild(
          (b) => b
            ..where((b) => b.characters.contains(target.character))
            ..shuffle(),
        );
        int tryCount = 0;
        for (final word in words) {
          tryCount++;
          for (final (index, character) in word.characters.indexed) {
            if (character != target.character) continue;

            final candidate = workQueue.crossword.addWord(
              location: switch (direction) {
                Direction.across => location.leftOffset(index),
                Direction.down => location.upOffset(index),
              },
              word: word,
              direction: direction,
            );
            if (candidate != null) {
              return candidate;
            }
          }
          if (tryCount > 1000) {
            break;
          }
        }
      }, (workQueue, location));
      if (crossword != null) {
        workQueue = workQueue.updateFrom(crossword);
        yield crossword;
      } else {
        workQueue = workQueue.remove(location);
      }
    } catch (e) {
      debugPrint('Error running isolate: $e');
    }
  }
  debugPrint(
    '${crossword.width} x ${crossword.height} Crossword generated in '
    '${DateTime.now().difference(start).formatted}',
  );
}

このコードを実行すると、表面上は同じに見えるアプリが作成されますが、完成したクロスワードパズルを見つけるまでの時間が異なります。以下は、1 分 29 秒で生成された 80 x 44 のクロスワードパズルです。

チェックポイント: 効率的なアルゴリズムの動作

クロスワードパズルの生成が大幅に高速化されました。

インテリジェントな単語配置ターゲティングの交差点
プレースメントが失敗した場合の効率的なバックトラッキング
重複する検索を回避するためのワークキュー管理

多くの単語が交差するクロスワードパズル作成ツール。ズームアウトすると、文字が小さすぎて読めません。

当然の疑問は、さらに高速化できるかどうかです。ああ、そうですね。

7. サーフェスの統計情報

統計情報を追加する理由

高速化するには、何が起こっているかを確認することが重要です。統計情報を使用すると、アルゴリズムのパフォーマンスをリアルタイムで確認し、進捗状況をモニタリングできます。アルゴリズムが時間を費やしている場所を把握することで、ボトルネックを特定できます。これにより、最適化アプローチについて十分な情報に基づいて判断し、パフォーマンスを調整できます。

表示する情報は WorkQueue から抽出して UI に表示する必要があります。まず、表示する情報を含む新しいモデルクラスを定義することをおすすめします。

まず、次の手順を行います。

model.dart ファイルを次のように編集して、DisplayInfo クラスを追加します。

lib/model.dart

import 'package:built_collection/built_collection.dart';
import 'package:built_value/built_value.dart';
import 'package:built_value/serializer.dart';
import 'package:characters/characters.dart';
import 'package:intl/intl.dart';                           // Add this import

part 'model.g.dart';

/// A location in a crossword.
abstract class Location implements Built<Location, LocationBuilder> {

ファイルの末尾で、次の変更を行って DisplayInfo クラスを追加します。

lib/model.dart

  /// Factory constructor for [WorkQueue]
  factory WorkQueue([void Function(WorkQueueBuilder)? updates]) = _$WorkQueue;

  WorkQueue._();
}
                                                           // Add from here.
/// Display information for the current state of the crossword solve.
abstract class DisplayInfo implements Built<DisplayInfo, DisplayInfoBuilder> {
  static Serializer<DisplayInfo> get serializer => _$displayInfoSerializer;

  /// The number of words in the grid.
  String get wordsInGridCount;

  /// The number of candidate words.
  String get candidateWordsCount;

  /// The number of locations to explore.
  String get locationsToExploreCount;

  /// The number of known bad locations.
  String get knownBadLocationsCount;

  /// The percentage of the grid filled.
  String get gridFilledPercentage;

  /// Construct a [DisplayInfo] instance from a [WorkQueue].
  factory DisplayInfo.from({required WorkQueue workQueue}) {
    final gridFilled =
        (workQueue.crossword.characters.length /
        (workQueue.crossword.width * workQueue.crossword.height));
    final fmt = NumberFormat.decimalPattern();

    return DisplayInfo(
      (b) => b
        ..wordsInGridCount = fmt.format(workQueue.crossword.words.length)
        ..candidateWordsCount = fmt.format(workQueue.candidateWords.length)
        ..locationsToExploreCount = fmt.format(workQueue.locationsToTry.length)
        ..knownBadLocationsCount = fmt.format(workQueue.badLocations.length)
        ..gridFilledPercentage = '${(gridFilled * 100).toStringAsFixed(2)}%',
    );
  }

  /// An empty [DisplayInfo] instance.
  static DisplayInfo get empty => DisplayInfo(
    (b) => b
      ..wordsInGridCount = '0'
      ..candidateWordsCount = '0'
      ..locationsToExploreCount = '0'
      ..knownBadLocationsCount = '0'
      ..gridFilledPercentage = '0%',
  );

  factory DisplayInfo([void Function(DisplayInfoBuilder)? updates]) =
      _$DisplayInfo;
  DisplayInfo._();
}                                                          // To here.

/// Construct the serialization/deserialization code for the data model.
@SerializersFor([
  Location,
  Crossword,
  CrosswordWord,
  CrosswordCharacter,
  WorkQueue,
  DisplayInfo,                                             // Add this line.
])
final Serializers serializers = _$serializers;

isolates.dart ファイルを変更して、次のように WorkQueue モデルを公開します。

lib/isolates.dart

import 'package:built_collection/built_collection.dart';
import 'package:characters/characters.dart';
import 'package:flutter/foundation.dart';

import 'model.dart';
import 'utils.dart';

Stream<WorkQueue> exploreCrosswordSolutions({              // Modify this line
  required Crossword crossword,
  required BuiltSet<String> wordList,
}) async* {
  final start = DateTime.now();
  var workQueue = WorkQueue.from(
    crossword: crossword,
    candidateWords: wordList,
    startLocation: Location.at(0, 0),
  );
  while (!workQueue.isCompleted) {
    final location = workQueue.locationsToTry.keys.toBuiltSet().randomElement();
    try {
      final crossword = await compute(((WorkQueue, Location) workMessage) {
        final (workQueue, location) = workMessage;
        final direction = workQueue.locationsToTry[location]!;
        final target = workQueue.crossword.characters[location];
        if (target == null) {
          return workQueue.crossword.addWord(
            direction: direction,
            location: location,
            word: workQueue.candidateWords.randomElement(),
          );
        }
        var words = workQueue.candidateWords.toBuiltList().rebuild(
          (b) => b
            ..where((b) => b.characters.contains(target.character))
            ..shuffle(),
        );
        int tryCount = 0;
        for (final word in words) {
          tryCount++;
          for (final (index, character) in word.characters.indexed) {
            if (character != target.character) continue;

            final candidate = workQueue.crossword.addWord(
              location: switch (direction) {
                Direction.across => location.leftOffset(index),
                Direction.down => location.upOffset(index),
              },
              word: word,
              direction: direction,
            );
            if (candidate != null) {
              return candidate;
            }
          }
          if (tryCount > 1000) {
            break;
          }
        }
      }, (workQueue, location));
      if (crossword != null) {
        workQueue = workQueue.updateFrom(crossword);       // Drop the yield crossword;
      } else {
        workQueue = workQueue.remove(location);
      }
      yield workQueue;                                     // Add this line.
    } catch (e) {
      debugPrint('Error running isolate: $e');
    }
  }
  debugPrint(
    '${crossword.width} x ${crossword.height} Crossword generated in '
    '${DateTime.now().difference(start).formatted}',
  );
}

バックグラウンド分離が作業キューを公開するようになったため、このデータソースから統計情報を取得する方法と場所が問題になります。

古いクロスワードプロバイダをワークキュープロバイダに置き換え、ワークキュープロバイダのストリームから情報を取得するプロバイダを追加します。

lib/providers.dart

import 'dart:convert';
import 'dart:math';                                        // Add this import

import 'package:built_collection/built_collection.dart';
import 'package:flutter/foundation.dart';
import 'package:flutter/services.dart';
import 'package:riverpod/riverpod.dart';
import 'package:riverpod_annotation/riverpod_annotation.dart';

import 'isolates.dart';
import 'model.dart' as model;

part 'providers.g.dart';

/// A provider for the wordlist to use when generating the crossword.
@riverpod
Future<BuiltSet<String>> wordList(Ref ref) async {
  // This codebase requires that all words consist of lowercase characters
  // in the range 'a'-'z'. Words containing uppercase letters will be
  // lowercased, and words containing runes outside this range will
  // be removed.

  final re = RegExp(r'^[a-z]+$');
  final words = await rootBundle.loadString('assets/words.txt');
  return const LineSplitter()
      .convert(words)
      .toBuiltSet()
      .rebuild(
        (b) => b
          ..map((word) => word.toLowerCase().trim())
          ..where((word) => word.length > 2)
          ..where((word) => re.hasMatch(word)),
      );
}

/// An enumeration for different sizes of [model.Crossword]s.
enum CrosswordSize {
  small(width: 20, height: 11),
  medium(width: 40, height: 22),
  large(width: 80, height: 44),
  xlarge(width: 160, height: 88),
  xxlarge(width: 500, height: 500);

  const CrosswordSize({required this.width, required this.height});

  final int width;
  final int height;
  String get label => '$width x $height';
}

/// A provider that holds the current size of the crossword to generate.
@Riverpod(keepAlive: true)
class Size extends _$Size {
  var _size = CrosswordSize.medium;

  @override
  CrosswordSize build() => _size;

  void setSize(CrosswordSize size) {
    _size = size;
    ref.invalidateSelf();
  }
}

@riverpod
Stream<model.WorkQueue> workQueue(Ref ref) async* {        // Modify this provider
  final size = ref.watch(sizeProvider);
  final wordListAsync = ref.watch(wordListProvider);
  final emptyCrossword = model.Crossword.crossword(
    width: size.width,
    height: size.height,
  );
  final emptyWorkQueue = model.WorkQueue.from(
    crossword: emptyCrossword,
    candidateWords: BuiltSet<String>(),
    startLocation: model.Location.at(0, 0),
  );

  ref.read(startTimeProvider.notifier).start();
  ref.read(endTimeProvider.notifier).clear();

  yield* wordListAsync.when(
    data: (wordList) => exploreCrosswordSolutions(
      crossword: emptyCrossword,
      wordList: wordList,
    ),
    error: (error, stackTrace) async* {
      debugPrint('Error loading word list: $error');
      yield emptyWorkQueue;
    },
    loading: () async* {
      yield emptyWorkQueue;
    },
  );

  ref.read(endTimeProvider.notifier).end();
}                                                          // To here.

@Riverpod(keepAlive: true)                                 // Add from here to end of file
class StartTime extends _$StartTime {
  @override
  DateTime? build() => _start;

  DateTime? _start;

  void start() {
    _start = DateTime.now();
    ref.invalidateSelf();
  }
}

@Riverpod(keepAlive: true)
class EndTime extends _$EndTime {
  @override
  DateTime? build() => _end;

  DateTime? _end;

  void clear() {
    _end = null;
    ref.invalidateSelf();
  }

  void end() {
    _end = DateTime.now();
    ref.invalidateSelf();
  }
}

const _estimatedTotalCoverage = 0.54;

@riverpod
Duration expectedRemainingTime(Ref ref) {
  final startTime = ref.watch(startTimeProvider);
  final endTime = ref.watch(endTimeProvider);
  final workQueueAsync = ref.watch(workQueueProvider);

  return workQueueAsync.when(
    data: (workQueue) {
      if (startTime == null || endTime != null || workQueue.isCompleted) {
        return Duration.zero;
      }
      try {
        final soFar = DateTime.now().difference(startTime);
        final completedPercentage = min(
          0.99,
          (workQueue.crossword.characters.length /
              (workQueue.crossword.width * workQueue.crossword.height) /
              _estimatedTotalCoverage),
        );
        final expectedTotal = soFar.inSeconds / completedPercentage;
        final expectedRemaining = expectedTotal - soFar.inSeconds;
        return Duration(seconds: expectedRemaining.toInt());
      } catch (e) {
        return Duration.zero;
      }
    },
    error: (error, stackTrace) => Duration.zero,
    loading: () => Duration.zero,
  );
}

/// A provider that holds whether to display info.
@Riverpod(keepAlive: true)
class ShowDisplayInfo extends _$ShowDisplayInfo {
  var _display = true;

  @override
  bool build() => _display;

  void toggle() {
    _display = !_display;
    ref.invalidateSelf();
  }
}

/// A provider that summarise the DisplayInfo from a [model.WorkQueue].
@riverpod
class DisplayInfo extends _$DisplayInfo {
  @override
  model.DisplayInfo build() => ref
      .watch(workQueueProvider)
      .when(
        data: (workQueue) => model.DisplayInfo.from(workQueue: workQueue),
        error: (error, stackTrace) => model.DisplayInfo.empty,
        loading: () => model.DisplayInfo.empty,
      );
}

新しいプロバイダは、情報表示をクロスワードグリッドの上に重ねるかどうかという形式のグローバル状態と、クロスワード生成の実行時間などの派生データの混合です。この状態の一部のリスナーは一時的なものであるため、この処理は複雑になります。情報表示が非表示の場合、クロスワードパズルの計算の開始時間と終了時間はリスニングされませんが、情報表示が表示されたときに計算が正確に行われるように、メモリに保持する必要があります。この場合、Riverpod 属性の keepAlive パラメータが非常に便利です。

情報表示の際に、わずかなしわができます。経過実行時間を表示したいのですが、経過時間を常に更新するよう強制するものがありません。Flutter で次世代の UI を構築する Codelab に戻ると、この要件にぴったりの便利なウィジェットがあります。

lib/widgets ディレクトリに ticker_builder.dart ファイルを作成し、次の内容を追加します。

lib/widgets/ticker_builder.dart

import 'package:flutter/material.dart';
import 'package:flutter/scheduler.dart';

/// A Builder widget that invokes its [builder] function on every animation frame.
class TickerBuilder extends StatefulWidget {
  const TickerBuilder({super.key, required this.builder});
  final Widget Function(BuildContext context) builder;
  @override
  State<TickerBuilder> createState() => _TickerBuilderState();
}

class _TickerBuilderState extends State<TickerBuilder>
    with SingleTickerProviderStateMixin {
  late final Ticker _ticker;

  @override
  void initState() {
    super.initState();
    _ticker = createTicker(_handleTick)..start();
  }

  @override
  void dispose() {
    _ticker.dispose();
    super.dispose();
  }

  void _handleTick(Duration elapsed) {
    setState(() {
      // Force a rebuild without changing the widget tree.
    });
  }

  @override
  Widget build(BuildContext context) => widget.builder.call(context);
}

このウィジェットはハンマーです。コンテンツはフレームごとに再構築されます。これは一般的には好ましくありませんが、クロスワードパズルを検索する計算負荷と比較すると、経過時間をフレームごとに再描画する計算負荷はノイズに消える可能性があります。この新たに導き出された情報を活用するために、新しいウィジェットを作成します。

lib/widgets ディレクトリに crossword_info_widget.dart ファイルを作成し、次の内容を追加します。

lib/widgets/crossword_info_widget.dart

import 'package:flutter/material.dart';
import 'package:flutter_riverpod/flutter_riverpod.dart';

import '../providers.dart';
import '../utils.dart';
import 'ticker_builder.dart';

class CrosswordInfoWidget extends ConsumerWidget {
  const CrosswordInfoWidget({super.key});

  @override
  Widget build(BuildContext context, WidgetRef ref) {
    final size = ref.watch(sizeProvider);
    final displayInfo = ref.watch(displayInfoProvider);
    final startTime = ref.watch(startTimeProvider);
    final endTime = ref.watch(endTimeProvider);
    final remaining = ref.watch(expectedRemainingTimeProvider);

    return Align(
      alignment: Alignment.bottomRight,
      child: Padding(
        padding: const EdgeInsets.only(right: 32.0, bottom: 32.0),
        child: ClipRRect(
          borderRadius: BorderRadius.circular(8),
          child: ColoredBox(
            color: Theme.of(context).colorScheme.onPrimary.withAlpha(230),
            child: Padding(
              padding: const EdgeInsets.symmetric(horizontal: 12, vertical: 8),
              child: DefaultTextStyle(
                style: TextStyle(
                  fontSize: 16,
                  color: Theme.of(context).colorScheme.primary,
                ),
                child: Column(
                  mainAxisSize: MainAxisSize.min,
                  crossAxisAlignment: CrossAxisAlignment.start,
                  children: [
                    _CrosswordInfoRichText(
                      label: 'Grid Size',
                      value: '${size.width} x ${size.height}',
                    ),
                    _CrosswordInfoRichText(
                      label: 'Words in grid',
                      value: displayInfo.wordsInGridCount,
                    ),
                    _CrosswordInfoRichText(
                      label: 'Candidate words',
                      value: displayInfo.candidateWordsCount,
                    ),
                    _CrosswordInfoRichText(
                      label: 'Locations to explore',
                      value: displayInfo.locationsToExploreCount,
                    ),
                    _CrosswordInfoRichText(
                      label: 'Known bad locations',
                      value: displayInfo.knownBadLocationsCount,
                    ),
                    _CrosswordInfoRichText(
                      label: 'Grid filled',
                      value: displayInfo.gridFilledPercentage,
                    ),
                    switch ((startTime, endTime)) {
                      (null, _) => _CrosswordInfoRichText(
                        label: 'Time elapsed',
                        value: 'Not started yet',
                      ),
                      (DateTime start, null) => TickerBuilder(
                        builder: (context) => _CrosswordInfoRichText(
                          label: 'Time elapsed',
                          value: DateTime.now().difference(start).formatted,
                        ),
                      ),
                      (DateTime start, DateTime end) => _CrosswordInfoRichText(
                        label: 'Completed in',
                        value: end.difference(start).formatted,
                      ),
                    },
                    if (startTime != null && endTime == null)
                      _CrosswordInfoRichText(
                        label: 'Est. remaining',
                        value: remaining.formatted,
                      ),
                  ],
                ),
              ),
            ),
          ),
        ),
      ),
    );
  }
}

class _CrosswordInfoRichText extends StatelessWidget {
  final String label;
  final String value;

  const _CrosswordInfoRichText({required this.label, required this.value});

  @override
  Widget build(BuildContext context) => RichText(
    text: TextSpan(
      children: [
        TextSpan(text: '$label ', style: DefaultTextStyle.of(context).style),
        TextSpan(
          text: value,
          style: DefaultTextStyle.of(
            context,
          ).style.copyWith(fontWeight: FontWeight.bold),
        ),
      ],
    ),
  );
}

このウィジェットは、Riverpod のプロバイダの威力を示す好例です。このウィジェットは、5 つのプロバイダのいずれかが更新されると、再構築の対象としてマークされます。このステップで必要な最後の変更は、この新しいウィジェットを UI に統合することです。

crossword_generator_app.dart ファイルを次のように編集します。

lib/widgets/crossword_generator_app.dart

import 'package:flutter/material.dart';
import 'package:flutter_riverpod/flutter_riverpod.dart';

import '../providers.dart';
import 'crossword_info_widget.dart';                       // Add this import
import 'crossword_widget.dart';

class CrosswordGeneratorApp extends StatelessWidget {
  const CrosswordGeneratorApp({super.key});

  @override
  Widget build(BuildContext context) {
    return _EagerInitialization(
      child: Scaffold(
        appBar: AppBar(
          actions: [_CrosswordGeneratorMenu()],
          titleTextStyle: TextStyle(
            color: Theme.of(context).colorScheme.primary,
            fontSize: 16,
            fontWeight: FontWeight.bold,
          ),
          title: Text('Crossword Generator'),
        ),
        body: SafeArea(
          child: Consumer(                                 // Modify from here
            builder: (context, ref, child) {
              return Stack(
                children: [
                  Positioned.fill(child: CrosswordWidget()),
                  if (ref.watch(showDisplayInfoProvider)) CrosswordInfoWidget(),
                ],
              );
            },
          ),                                               // To here.
        ),
      ),
    );
  }
}

class _EagerInitialization extends ConsumerWidget {
  const _EagerInitialization({required this.child});
  final Widget child;

  @override
  Widget build(BuildContext context, WidgetRef ref) {
    ref.watch(wordListProvider);
    return child;
  }
}

class _CrosswordGeneratorMenu extends ConsumerWidget {
  @override
  Widget build(BuildContext context, WidgetRef ref) => MenuAnchor(
    menuChildren: [
      for (final entry in CrosswordSize.values)
        MenuItemButton(
          onPressed: () => ref.read(sizeProvider.notifier).setSize(entry),
          leadingIcon: entry == ref.watch(sizeProvider)
              ? Icon(Icons.radio_button_checked_outlined)
              : Icon(Icons.radio_button_unchecked_outlined),
          child: Text(entry.label),
        ),
      MenuItemButton(                                      // Add from here
        leadingIcon: ref.watch(showDisplayInfoProvider)
            ? Icon(Icons.check_box_outlined)
            : Icon(Icons.check_box_outline_blank_outlined),
        onPressed: () => ref.read(showDisplayInfoProvider.notifier).toggle(),
        child: Text('Display Info'),
      ),                                                   // To here.
    ],
    builder: (context, controller, child) => IconButton(
      onPressed: () => controller.open(),
      icon: Icon(Icons.settings),
    ),
  );
}

この 2 つの変更は、プロバイダを統合するさまざまなアプローチを示しています。CrosswordGeneratorApp の build メソッドで、情報表示の表示 / 非表示時に再構築を強制する領域を含む新しい Consumer ビルダーを導入しました。一方、ドロップダウンメニュー全体は 1 つの ConsumerWidget であり、クロスワードのサイズ変更や情報表示の表示 / 非表示にかかわらず、再構築されます。どちらのアプローチを採用するかは、常にエンジニアリング上のトレードオフであり、シンプルさと再構築されたウィジェットツリーのレイアウトを再計算するコストとのバランスを考慮する必要があります。

アプリを実行すると、クロスワードパズルの生成の進行状況をユーザーがより詳しく把握できるようになります。しかし、クロスワードパズルの生成の終盤では、数字は変化しているものの、文字のグリッドにはほとんど変化が見られない期間があります。

クロスワードパズル生成アプリのウィンドウ。今回は、認識可能な単語が小さく表示され、右下隅に現在の生成実行に関する統計情報が表示されたフローティングオーバーレイが表示されている

何が起こっているのか、その理由について、さらに詳しい情報を入手するとよいでしょう。

8. スレッドで並列化する

パフォーマンスが低下する理由

クロスワードパズルが完成に近づくにつれて、有効な単語の配置オプションが少なくなるため、アルゴリズムの速度が低下します。アルゴリズムは、機能しない組み合わせを多数試します。シングルスレッド処理では複数のオプションを効率的に探索できない

アルゴリズムの可視化

最後に処理が遅くなる理由を理解するには、アルゴリズムの動作を可視化できると便利です。重要な部分は、WorkQueue の未処理の locationsToTry です。TableView を使用すると、この問題を簡単に調査できます。セルが locationsToTry にあるかどうかに基づいて、セルの色を変更できます。

まず、次の手順を行います。

crossword_widget.dart ファイルを次のように変更します。

lib/widgets/crossword_widget.dart

import 'package:flutter/material.dart';
import 'package:flutter_riverpod/flutter_riverpod.dart';
import 'package:two_dimensional_scrollables/two_dimensional_scrollables.dart';

import '../model.dart';
import '../providers.dart';

class CrosswordWidget extends ConsumerWidget {
  const CrosswordWidget({super.key});

  @override
  Widget build(BuildContext context, WidgetRef ref) {
    final size = ref.watch(sizeProvider);
    return TableView.builder(
      diagonalDragBehavior: DiagonalDragBehavior.free,
      cellBuilder: _buildCell,
      columnCount: size.width,
      columnBuilder: (index) => _buildSpan(context, index),
      rowCount: size.height,
      rowBuilder: (index) => _buildSpan(context, index),
    );
  }

  TableViewCell _buildCell(BuildContext context, TableVicinity vicinity) {
    final location = Location.at(vicinity.column, vicinity.row);

    return TableViewCell(
      child: Consumer(
        builder: (context, ref, _) {
          final character = ref.watch(
            workQueueProvider.select(
              (workQueueAsync) => workQueueAsync.when(
                data: (workQueue) => workQueue.crossword.characters[location],
                error: (error, stackTrace) => null,
                loading: () => null,
              ),
            ),
          );

          final explorationCell = ref.watch(               // Add from here
            workQueueProvider.select(
              (workQueueAsync) => workQueueAsync.when(
                data: (workQueue) =>
                    workQueue.locationsToTry.keys.contains(location),
                error: (error, stackTrace) => false,
                loading: () => false,
              ),
            ),
          );                                               // To here.

          if (character != null) {                         // Modify from here
            return AnimatedContainer(
              duration: Durations.extralong1,
              curve: Curves.easeInOut,
              color: explorationCell
                  ? Theme.of(context).colorScheme.primary
                  : Theme.of(context).colorScheme.onPrimary,
              child: Center(
                child: AnimatedDefaultTextStyle(
                  duration: Durations.extralong1,
                  curve: Curves.easeInOut,
                  style: TextStyle(
                    fontSize: 24,
                    color: explorationCell
                        ? Theme.of(context).colorScheme.onPrimary
                        : Theme.of(context).colorScheme.primary,
                  ),
                  child: Text(character.character),
                ),                                          // To here.
              ),
            );
          }

          return ColoredBox(
            color: Theme.of(context).colorScheme.primaryContainer,
          );
        },
      ),
    );
  }

  TableSpan _buildSpan(BuildContext context, int index) {
    return TableSpan(
      extent: FixedTableSpanExtent(32),
      foregroundDecoration: TableSpanDecoration(
        border: TableSpanBorder(
          leading: BorderSide(
            color: Theme.of(context).colorScheme.onPrimaryContainer,
          ),
          trailing: BorderSide(
            color: Theme.of(context).colorScheme.onPrimaryContainer,
          ),
        ),
      ),
    );
  }
}

このコードを実行すると、アルゴリズムがまだ調査していない未解決の場所の可視化が表示されます。

生成途中のクロスワードパズル生成ツール。一部の文字は濃い青の背景に白のテキストで、他の文字は白の背景に青のテキストです。

クロスワードパズルが完成に近づくにつれて、調査しても役に立たないポイントが多数残っているのが興味深い点です。ここでは、2 つのオプションがあります。1 つは、クロスワードのセルの一定の割合が埋まったら調査を終了すること、もう 1 つは、複数の注目ポイントを同時に調査することです。2 つ目のパスの方が楽しそうなので、それを実行します。

isolates.dart ファイルを編集します。これは、1 つのバックグラウンド分離で計算されていたものを N 個のバックグラウンド分離のプールに分割するために、コードをほぼ完全に書き換えたものです。

lib/isolates.dart

import 'package:built_collection/built_collection.dart';
import 'package:characters/characters.dart';
import 'package:flutter/foundation.dart';

import 'model.dart';
import 'utils.dart';

Stream<WorkQueue> exploreCrosswordSolutions({
  required Crossword crossword,
  required BuiltSet<String> wordList,
  required int maxWorkerCount,
}) async* {
  final start = DateTime.now();
  var workQueue = WorkQueue.from(
    crossword: crossword,
    candidateWords: wordList,
    startLocation: Location.at(0, 0),
  );
  while (!workQueue.isCompleted) {
    try {
      workQueue = await compute(_generate, (workQueue, maxWorkerCount));
      yield workQueue;
    } catch (e) {
      debugPrint('Error running isolate: $e');
    }
  }

  debugPrint(
    'Generated ${workQueue.crossword.width} x '
    '${workQueue.crossword.height} crossword in '
    '${DateTime.now().difference(start).formatted} '
    'with $maxWorkerCount workers.',
  );
}

Future<WorkQueue> _generate((WorkQueue, int) workMessage) async {
  var (workQueue, maxWorkerCount) = workMessage;
  final candidateGeneratorFutures = <Future<(Location, Direction, String?)>>[];
  final locations = workQueue.locationsToTry.keys.toBuiltList().rebuild(
    (b) => b
      ..shuffle()
      ..take(maxWorkerCount),
  );

  for (final location in locations) {
    final direction = workQueue.locationsToTry[location]!;

    candidateGeneratorFutures.add(
      compute(_generateCandidate, (
        workQueue.crossword,
        workQueue.candidateWords,
        location,
        direction,
      )),
    );
  }

  try {
    final results = await candidateGeneratorFutures.wait;
    var crossword = workQueue.crossword;
    for (final (location, direction, word) in results) {
      if (word != null) {
        final candidate = crossword.addWord(
          location: location,
          word: word,
          direction: direction,
        );
        if (candidate != null) {
          crossword = candidate;
        }
      } else {
        workQueue = workQueue.remove(location);
      }
    }

    workQueue = workQueue.updateFrom(crossword);
  } catch (e) {
    debugPrint('$e');
  }

  return workQueue;
}

(Location, Direction, String?) _generateCandidate(
  (Crossword, BuiltSet<String>, Location, Direction) searchDetailMessage,
) {
  final (crossword, candidateWords, location, direction) = searchDetailMessage;

  final target = crossword.characters[location];
  if (target == null) {
    return (location, direction, candidateWords.randomElement());
  }

  // Filter down the candidate word list to those that contain the letter
  // at the current location
  final words = candidateWords.toBuiltList().rebuild(
    (b) => b
      ..where((b) => b.characters.contains(target.character))
      ..shuffle(),
  );
  int tryCount = 0;
  final start = DateTime.now();
  for (final word in words) {
    tryCount++;
    for (final (index, character) in word.characters.indexed) {
      if (character != target.character) continue;

      final candidate = crossword.addWord(
        location: switch (direction) {
          Direction.across => location.leftOffset(index),
          Direction.down => location.upOffset(index),
        },
        word: word,
        direction: direction,
      );
      if (candidate != null) {
        return switch (direction) {
          Direction.across => (location.leftOffset(index), direction, word),
          Direction.down => (location.upOffset(index), direction, word),
        };
      }
      final deltaTime = DateTime.now().difference(start);
      if (tryCount >= 1000 || deltaTime > Duration(seconds: 10)) {
        return (location, direction, null);
      }
    }
  }

  return (location, direction, null);
}

マルチ分離アーキテクチャについて

このコードのほとんどは、コアビジネスロジックが変更されていないため、見慣れたもののはずです。変更点は、compute 呼び出しのレイヤが 2 つになったことです。最初のレイヤは、個々のポジションを検索して N 個のワーカー分離に割り当て、N 個のワーカー分離がすべて完了したら結果を再結合します。第 2 レイヤは N 個のワーカー分離で構成されます。最適なパフォーマンスを得るための N のチューニングは、コンピュータと対象のデータの両方に依存します。グリッドが大きいほど、ワーカーが互いに邪魔することなく連携して作業できます。

興味深いのは、このコードが、クロージャがキャプチャすべきでないものをキャプチャするという問題をどのように処理しているかです。現在、閉鎖はありません。_generate 関数と _generateWorker 関数はトップレベル関数として定義されているため、キャプチャする環境がありません。これらの関数の引数と結果はどちらも Dart レコードの形式です。これは、compute 呼び出しの 1 つの値が入力され、1 つの値が出力されるセマンティクスを回避する方法です。

グリッド内で連動する単語を検索してクロスワードパズルを形成するバックグラウンドワーカーのプールを作成できるようになったので、この機能をクロスワードジェネレータツールの他の部分に公開します。

次のように workQueue プロバイダを編集して、providers.dart ファイルを編集します。

lib/providers.dart

@riverpod
Stream<model.WorkQueue> workQueue(Ref ref) async* {
  final workers = ref.watch(workerCountProvider);          // Add this line
  final size = ref.watch(sizeProvider);
  final wordListAsync = ref.watch(wordListProvider);
  final emptyCrossword = model.Crossword.crossword(
    width: size.width,
    height: size.height,
  );
  final emptyWorkQueue = model.WorkQueue.from(
    crossword: emptyCrossword,
    candidateWords: BuiltSet<String>(),
    startLocation: model.Location.at(0, 0),
  );

  ref.read(startTimeProvider.notifier).start();
  ref.read(endTimeProvider.notifier).clear();

  yield* wordListAsync.when(
    data: (wordList) => exploreCrosswordSolutions(
      crossword: emptyCrossword,
      wordList: wordList,
      maxWorkerCount: workers.count,                       // Add this line
    ),
    error: (error, stackTrace) async* {
      debugPrint('Error loading word list: $error');
      yield emptyWorkQueue;
    },
    loading: () async* {
      yield emptyWorkQueue;
    },
  );

  ref.read(endTimeProvider.notifier).end();
}

次のように、ファイルの末尾に WorkerCount プロバイダを追加します。

lib/providers.dart

/// A provider that summarise the DisplayInfo from a [model.WorkQueue].
@riverpod
class DisplayInfo extends _$DisplayInfo {
  @override
  model.DisplayInfo build() => ref
      .watch(workQueueProvider)
      .when(
        data: (workQueue) => model.DisplayInfo.from(workQueue: workQueue),
        error: (error, stackTrace) => model.DisplayInfo.empty,
        loading: () => model.DisplayInfo.empty,
      );
}

enum BackgroundWorkers {                                   // Add from here
  one(1),
  two(2),
  four(4),
  eight(8),
  sixteen(16),
  thirtyTwo(32),
  sixtyFour(64),
  oneTwentyEight(128);

  const BackgroundWorkers(this.count);

  final int count;
  String get label => count.toString();
}

/// A provider that holds the current number of background workers to use.
@Riverpod(keepAlive: true)
class WorkerCount extends _$WorkerCount {
  var _count = BackgroundWorkers.four;

  @override
  BackgroundWorkers build() => _count;

  void setCount(BackgroundWorkers count) {
    _count = count;
    ref.invalidateSelf();
  }
}                                                          // To here.

この 2 つの変更により、プロバイダレイヤで、分離関数が正しく構成されるようにバックグラウンド分離プールに最大ワーカー数を設定する方法が公開されるようになりました。

CrosswordInfoWidget を次のように変更して、crossword_info_widget.dart ファイルを更新します。

lib/widgets/crossword_info_widget.dart

class CrosswordInfoWidget extends ConsumerWidget {
  const CrosswordInfoWidget({super.key});

  @override
  Widget build(BuildContext context, WidgetRef ref) {
    final size = ref.watch(sizeProvider);
    final displayInfo = ref.watch(displayInfoProvider);
    final workerCount = ref.watch(workerCountProvider).label;  // Add this line
    final startTime = ref.watch(startTimeProvider);
    final endTime = ref.watch(endTimeProvider);
    final remaining = ref.watch(expectedRemainingTimeProvider);

    return Align(
      alignment: Alignment.bottomRight,
      child: Padding(
        padding: const EdgeInsets.only(right: 32.0, bottom: 32.0),
        child: ClipRRect(
          borderRadius: BorderRadius.circular(8),
          child: ColoredBox(
            color: Theme.of(context).colorScheme.onPrimary.withAlpha(230),
            child: Padding(
              padding: const EdgeInsets.symmetric(horizontal: 12, vertical: 8),
              child: DefaultTextStyle(
                style: TextStyle(
                  fontSize: 16,
                  color: Theme.of(context).colorScheme.primary,
                ),
                child: Column(
                  mainAxisSize: MainAxisSize.min,
                  crossAxisAlignment: CrossAxisAlignment.start,
                  children: [
                    _CrosswordInfoRichText(
                      label: 'Grid Size',
                      value: '${size.width} x ${size.height}',
                    ),
                    _CrosswordInfoRichText(
                      label: 'Words in grid',
                      value: displayInfo.wordsInGridCount,
                    ),
                    _CrosswordInfoRichText(
                      label: 'Candidate words',
                      value: displayInfo.candidateWordsCount,
                    ),
                    _CrosswordInfoRichText(
                      label: 'Locations to explore',
                      value: displayInfo.locationsToExploreCount,
                    ),
                    _CrosswordInfoRichText(
                      label: 'Known bad locations',
                      value: displayInfo.knownBadLocationsCount,
                    ),
                    _CrosswordInfoRichText(
                      label: 'Grid filled',
                      value: displayInfo.gridFilledPercentage,
                    ),
                    _CrosswordInfoRichText(               // Add from here
                      label: 'Max worker count',
                      value: workerCount,
                    ),                                    // To here.
                    switch ((startTime, endTime)) {
                      (null, _) => _CrosswordInfoRichText(
                        label: 'Time elapsed',
                        value: 'Not started yet',
                      ),
                      (DateTime start, null) => TickerBuilder(
                        builder: (context) => _CrosswordInfoRichText(
                          label: 'Time elapsed',
                          value: DateTime.now().difference(start).formatted,
                        ),
                      ),
                      (DateTime start, DateTime end) => _CrosswordInfoRichText(
                        label: 'Completed in',
                        value: end.difference(start).formatted,
                      ),
                    },
                    if (startTime != null && endTime == null)
                      _CrosswordInfoRichText(
                        label: 'Est. remaining',
                        value: remaining.formatted,
                      ),
                  ],
                ),
              ),
            ),
          ),
        ),
      ),
    );
  }
}

_CrosswordGeneratorMenu ウィジェットに次のセクションを追加して、crossword_generator_app.dart ファイルを変更します。

lib/widgets/crossword_generator_app.dart

class _CrosswordGeneratorMenu extends ConsumerWidget {
  @override
  Widget build(BuildContext context, WidgetRef ref) => MenuAnchor(
    menuChildren: [
      for (final entry in CrosswordSize.values)
        MenuItemButton(
          onPressed: () => ref.read(sizeProvider.notifier).setSize(entry),
          leadingIcon: entry == ref.watch(sizeProvider)
              ? Icon(Icons.radio_button_checked_outlined)
              : Icon(Icons.radio_button_unchecked_outlined),
          child: Text(entry.label),
        ),
      MenuItemButton(
        leadingIcon: ref.watch(showDisplayInfoProvider)
            ? Icon(Icons.check_box_outlined)
            : Icon(Icons.check_box_outline_blank_outlined),
        onPressed: () => ref.read(showDisplayInfoProvider.notifier).toggle(),
        child: Text('Display Info'),
      ),
      for (final count in BackgroundWorkers.values)        // Add from here
        MenuItemButton(
          leadingIcon: count == ref.watch(workerCountProvider)
              ? Icon(Icons.radio_button_checked_outlined)
              : Icon(Icons.radio_button_unchecked_outlined),
          onPressed: () =>
              ref.read(workerCountProvider.notifier).setCount(count),
          child: Text(count.label),                        // To here.
        ),
    ],
    builder: (context, controller, child) => IconButton(
      onPressed: () => controller.open(),
      icon: Icon(Icons.settings),
    ),
  );
}

アプリを実行すると、クロスワードパズルに当てはまる単語を検索するためにインスタンス化されるバックグラウンド分離の数を変更できるようになります。

歯車アイコンをクリックして、クロスワードのサイズ、生成されたクロスワードに統計情報を表示するかどうか、使用する分離株の数を含むコンテキストメニューを開きます。

単語と統計情報が表示された Crossword Generator ウィンドウ

チェックポイント: マルチスレッドのパフォーマンス

クロスワードジェネレータを実行すると、複数のコアを同時に使用することで、80x44 のクロスワードの計算時間が大幅に短縮されました。次の点に注意してください。

ワーカー数を増やしてクロスワードパズルの生成を高速化
生成中のスムーズな UI レスポンス
生成の進行状況を示すリアルタイムの統計情報
アルゴリズムの探索領域の視覚的なフィードバック

9. ゲームにする

作成するもの: ゲームルームのクロスワードパズル

最後のセクションはボーナスラウンドです。クロスワードパズルジェネレータの作成で学んだすべての手法を使い、ゲームを構築します。次のことを行います。

パズルを生成する: クロスワードパズル生成ツールを使用して、解けるパズルを作成する
単語の選択肢を作成する: 各位置に複数の単語の選択肢を指定します
インタラクションを有効にする: ユーザーが単語を選択して配置できるようにします。
ソリューションを検証する: 完成したクロスワードが正しいかどうかを確認します

クロスワードパズルを作成するには、クロスワードパズルジェネレーターを使用します。コンテキストメニューのイディオムを再利用して、ユーザーが単語を選択または選択解除して、グリッド内のさまざまな単語の形をした穴に入れることができるようにします。すべてはクロスワードパズルを完成させるためです。

このゲームが洗練されているとか完成しているとか言うつもりはありません。実際には、まだまだです。バランスと難易度に関する問題があり、代替語の選択を改善することで解決できます。ユーザーをパズルに導くチュートリアルはありません。「おめでとうございます」というシンプルな画面については、言及するまでもないでしょう。

このトレードオフは、このプロトゲームを完全なゲームに適切に仕上げるには、大幅に多くのコードが必要になることです。1 つの Codelab に含めるべきではないコードが多すぎる。そこで、このステップでは、これまでの Codelab で学習した手法を、その使用場所と使用方法を変更することで強化することを目的としています。この Codelab の前半で学習した内容を再確認していただければ幸いです。また、このコードに基づいて独自の体験を構築することもできます。皆様がどのようなものを構築されるか楽しみにしております。

まず、次の手順を行います。

lib/widgets ディレクトリ内のすべてのファイルを削除します。ゲーム用の新しいウィジェットを作成します。古いウィジェットから多くの要素を借用しているだけです。

model.dart ファイルを編集して、Crossword の addWord メソッドを次のように更新します。

lib/model.dart

  /// Add a word to the crossword at the given location and direction.
  Crossword? addWord({
    required Location location,
    required String word,
    required Direction direction,
    bool requireOverlap = true,                            // Add this parameter
  }) {
    // Require that the word is not already in the crossword.
    if (words.map((crosswordWord) => crosswordWord.word).contains(word)) {
      return null;
    }

    final wordCharacters = word.characters;
    bool overlap = false;

    // Check that the word fits in the crossword.
    for (final (index, character) in wordCharacters.indexed) {
      final characterLocation = switch (direction) {
        Direction.across => location.rightOffset(index),
        Direction.down => location.downOffset(index),
      };

      final target = characters[characterLocation];
      if (target != null) {
        overlap = true;
        if (target.character != character) {
          return null;
        }
        if (direction == Direction.across && target.acrossWord != null ||
            direction == Direction.down && target.downWord != null) {
          return null;
        }
      }
    }
                                                           // Edit from here
    // If overlap is required, make sure that the word overlaps with an existing
    // word. Skip this test if the crossword is empty.
    if (words.isNotEmpty && !overlap && requireOverlap) {  // To here.
      return null;
    }

    final candidate = rebuild(
      (b) => b
        ..words.add(
          CrosswordWord.word(
            word: word,
            direction: direction,
            location: location,
          ),
        ),
    );

    if (candidate.valid) {
      return candidate;
    } else {
      return null;
    }
  }

クロスワードモデルを少し変更することで、重複しない単語を追加できるようになります。プレーヤーが盤面のどこでもプレイできるようにしつつ、Crossword をプレーヤーの動きを保存するためのベースモデルとして使用できるようにすると便利です。特定の場所に特定の方向で配置された単語のリストにすぎません。

model.dart ファイルの末尾に CrosswordPuzzleGame モデルクラスを追加します。

lib/model.dart

/// Creates a puzzle from a crossword and a set of candidate words.
abstract class CrosswordPuzzleGame
    implements Built<CrosswordPuzzleGame, CrosswordPuzzleGameBuilder> {
  static Serializer<CrosswordPuzzleGame> get serializer =>
      _$crosswordPuzzleGameSerializer;

  /// The [Crossword] that this puzzle is based on.
  Crossword get crossword;

  /// The alternate words for each [CrosswordWord] in the crossword.
  BuiltMap<Location, BuiltMap<Direction, BuiltList<String>>> get alternateWords;

  /// The player's selected words.
  BuiltList<CrosswordWord> get selectedWords;

  bool canSelectWord({
    required Location location,
    required String word,
    required Direction direction,
  }) {
    final crosswordWord = CrosswordWord.word(
      word: word,
      location: location,
      direction: direction,
    );

    if (selectedWords.contains(crosswordWord)) {
      return true;
    }

    var puzzle = this;

    if (puzzle.selectedWords
        .where((b) => b.direction == direction && b.location == location)
        .isNotEmpty) {
      puzzle = puzzle.rebuild(
        (b) => b
          ..selectedWords.removeWhere(
            (selectedWord) =>
                selectedWord.location == location &&
                selectedWord.direction == direction,
          ),
      );
    }

    return null !=
        puzzle.crosswordFromSelectedWords.addWord(
          location: location,
          word: word,
          direction: direction,
          requireOverlap: false,
        );
  }

  CrosswordPuzzleGame? selectWord({
    required Location location,
    required String word,
    required Direction direction,
  }) {
    final crosswordWord = CrosswordWord.word(
      word: word,
      location: location,
      direction: direction,
    );

    if (selectedWords.contains(crosswordWord)) {
      return rebuild((b) => b.selectedWords.remove(crosswordWord));
    }

    var puzzle = this;

    if (puzzle.selectedWords
        .where((b) => b.direction == direction && b.location == location)
        .isNotEmpty) {
      puzzle = puzzle.rebuild(
        (b) => b
          ..selectedWords.removeWhere(
            (selectedWord) =>
                selectedWord.location == location &&
                selectedWord.direction == direction,
          ),
      );
    }

    // Check if the selected word meshes with the already selected words.
    // Note this version of the crossword does not enforce overlap to
    // allow the player to select words anywhere on the grid. Enforcing words
    // to be solved in order is a possible alternative.
    final updatedSelectedWordsCrossword = puzzle.crosswordFromSelectedWords
        .addWord(
          location: location,
          word: word,
          direction: direction,
          requireOverlap: false,
        );

    // Make sure the selected word is in the crossword or is an alternate word.
    if (updatedSelectedWordsCrossword != null) {
      if (puzzle.crossword.words.contains(crosswordWord) ||
          puzzle.alternateWords[location]?[direction]?.contains(word) == true) {
        return puzzle.rebuild(
          (b) => b
            ..selectedWords.add(
              CrosswordWord.word(
                word: word,
                location: location,
                direction: direction,
              ),
            ),
        );
      }
    }
    return null;
  }

  /// The crossword from the selected words.
  Crossword get crosswordFromSelectedWords => Crossword.crossword(
    width: crossword.width,
    height: crossword.height,
    words: selectedWords,
  );

  /// Test if the puzzle is solved. Note, this allows for the possibility of
  /// multiple solutions.
  bool get solved =>
      crosswordFromSelectedWords.valid &&
      crosswordFromSelectedWords.words.length == crossword.words.length &&
      crossword.words.isNotEmpty;

  /// Create a crossword puzzle game from a crossword and a set of candidate
  /// words.
  factory CrosswordPuzzleGame.from({
    required Crossword crossword,
    required BuiltSet<String> candidateWords,
  }) {
    // Remove all of the currently used words from the list of candidates
    candidateWords = candidateWords.rebuild(
      (p0) => p0.removeAll(crossword.words.map((p1) => p1.word)),
    );

    // This is the list of alternate words for each word in the crossword
    var alternates =
        BuiltMap<Location, BuiltMap<Direction, BuiltList<String>>>();

    // Build the alternate words for each word in the crossword
    for (final crosswordWord in crossword.words) {
      final alternateWords = candidateWords.toBuiltList().rebuild(
        (b) => b
          ..where((b) => b.length == crosswordWord.word.length)
          ..shuffle()
          ..take(4)
          ..sort(),
      );

      candidateWords = candidateWords.rebuild(
        (b) => b.removeAll(alternateWords),
      );

      alternates = alternates.rebuild(
        (b) => b.updateValue(
          crosswordWord.location,
          (b) => b.rebuild(
            (b) => b.updateValue(
              crosswordWord.direction,
              (b) => b.rebuild((b) => b.replace(alternateWords)),
              ifAbsent: () => alternateWords,
            ),
          ),
          ifAbsent: () => {crosswordWord.direction: alternateWords}.build(),
        ),
      );
    }

    return CrosswordPuzzleGame((b) {
      b
        ..crossword.replace(crossword)
        ..alternateWords.replace(alternates);
    });
  }

  factory CrosswordPuzzleGame([
    void Function(CrosswordPuzzleGameBuilder)? updates,
  ]) = _$CrosswordPuzzleGame;
  CrosswordPuzzleGame._();
}

/// Construct the serialization/deserialization code for the data model.
@SerializersFor([
  Location,
  Crossword,
  CrosswordWord,
  CrosswordCharacter,
  WorkQueue,
  DisplayInfo,
  CrosswordPuzzleGame,                                     // Add this line
])
final Serializers serializers = _$serializers;

providers.dart ファイルの更新は、興味深い変更の詰め合わせです。統計情報の収集をサポートするために存在していたプロバイダのほとんどが削除されました。バックグラウンド分離株の数を変更する機能が削除され、定数に置き換えられました。また、以前に追加した新しい CrosswordPuzzleGame モデルにアクセスできる新しいプロバイダもあります。

lib/providers.dart

import 'dart:convert';
                                                           // Drop the dart:math import

import 'package:built_collection/built_collection.dart';
import 'package:flutter/foundation.dart';
import 'package:flutter/services.dart';
import 'package:riverpod/riverpod.dart';
import 'package:riverpod_annotation/riverpod_annotation.dart';

import 'isolates.dart';
import 'model.dart' as model;

part 'providers.g.dart';

const backgroundWorkerCount = 4;                           // Add this line

/// A provider for the wordlist to use when generating the crossword.
@riverpod
Future<BuiltSet<String>> wordList(Ref ref) async {
  // This codebase requires that all words consist of lowercase characters
  // in the range 'a'-'z'. Words containing uppercase letters will be
  // lowercased, and words containing runes outside this range will
  // be removed.

  final re = RegExp(r'^[a-z]+$');
  final words = await rootBundle.loadString('assets/words.txt');
  return const LineSplitter()
      .convert(words)
      .toBuiltSet()
      .rebuild(
        (b) => b
          ..map((word) => word.toLowerCase().trim())
          ..where((word) => word.length > 2)
          ..where((word) => re.hasMatch(word)),
      );
}

/// An enumeration for different sizes of [model.Crossword]s.
enum CrosswordSize {
  small(width: 20, height: 11),
  medium(width: 40, height: 22),
  large(width: 80, height: 44),
  xlarge(width: 160, height: 88),
  xxlarge(width: 500, height: 500);

  const CrosswordSize({required this.width, required this.height});

  final int width;
  final int height;
  String get label => '$width x $height';
}

/// A provider that holds the current size of the crossword to generate.
@Riverpod(keepAlive: true)
class Size extends _$Size {
  var _size = CrosswordSize.medium;

  @override
  CrosswordSize build() => _size;

  void setSize(CrosswordSize size) {
    _size = size;
    ref.invalidateSelf();
  }
}

@riverpod
Stream<model.WorkQueue> workQueue(Ref ref) async* {
  final size = ref.watch(sizeProvider);                   // Drop the ref.watch(workerCountProvider)
  final wordListAsync = ref.watch(wordListProvider);
  final emptyCrossword = model.Crossword.crossword(
    width: size.width,
    height: size.height,
  );
  final emptyWorkQueue = model.WorkQueue.from(
    crossword: emptyCrossword,
    candidateWords: BuiltSet<String>(),
    startLocation: model.Location.at(0, 0),
  );
                                                          // Drop the startTimeProvider and endTimeProvider refs
  yield* wordListAsync.when(
    data: (wordList) => exploreCrosswordSolutions(
      crossword: emptyCrossword,
      wordList: wordList,
      maxWorkerCount: backgroundWorkerCount,              // Edit this line
    ),
    error: (error, stackTrace) async* {
      debugPrint('Error loading word list: $error');
      yield emptyWorkQueue;
    },
    loading: () async* {
      yield emptyWorkQueue;
    },
  );
}                                                         // Drop the endTimeProvider ref

@riverpod                                                 // Add from here to end of file
class Puzzle extends _$Puzzle {
  model.CrosswordPuzzleGame _puzzle = model.CrosswordPuzzleGame.from(
    crossword: model.Crossword.crossword(width: 0, height: 0),
    candidateWords: BuiltSet<String>(),
  );

  @override
  model.CrosswordPuzzleGame build() {
    final size = ref.watch(sizeProvider);
    final wordList = ref.watch(wordListProvider).value;
    final workQueue = ref.watch(workQueueProvider).value;

    if (wordList != null &&
        workQueue != null &&
        workQueue.isCompleted &&
        (_puzzle.crossword.height != size.height ||
            _puzzle.crossword.width != size.width ||
            _puzzle.crossword != workQueue.crossword)) {
      compute(_puzzleFromCrosswordTrampoline, (
        workQueue.crossword,
        wordList,
      )).then((puzzle) {
        _puzzle = puzzle;
        ref.invalidateSelf();
      });
    }

    return _puzzle;
  }

  Future<void> selectWord({
    required model.Location location,
    required String word,
    required model.Direction direction,
  }) async {
    final candidate = await compute(_puzzleSelectWordTrampoline, (
      _puzzle,
      location,
      word,
      direction,
    ));

    if (candidate != null) {
      _puzzle = candidate;
      ref.invalidateSelf();
    } else {
      debugPrint('Invalid word selection: $word');
    }
  }

  bool canSelectWord({
    required model.Location location,
    required String word,
    required model.Direction direction,
  }) {
    return _puzzle.canSelectWord(
      location: location,
      word: word,
      direction: direction,
    );
  }
}

// Trampoline functions to disentangle these Isolate target calls from the
// unsendable reference to the [Puzzle] provider.

Future<model.CrosswordPuzzleGame> _puzzleFromCrosswordTrampoline(
  (model.Crossword, BuiltSet<String>) args,
) async =>
    model.CrosswordPuzzleGame.from(crossword: args.$1, candidateWords: args.$2);

model.CrosswordPuzzleGame? _puzzleSelectWordTrampoline(
  (model.CrosswordPuzzleGame, model.Location, String, model.Direction) args,
) => args.$1.selectWord(location: args.$2, word: args.$3, direction: args.$4);

Puzzle プロバイダで最も興味深い部分は、Crossword と wordList から CrosswordPuzzleGame を作成する費用と単語を選択する費用を隠すために行われた策略です。これらのアクションは、バックグラウンド Isolate の助けなしに実行されると、UI の操作が遅くなります。最終結果をバックグラウンドで計算しながら、中間結果をプッシュアウトする手品のような手法を使用することで、必要な計算がバックグラウンドで行われている間も、UI の応答性を維持できます。

空になった lib/widgets ディレクトリに、次の内容の crossword_puzzle_app.dart ファイルを作成します。

lib/widgets/crossword_puzzle_app.dart

import 'package:flutter/material.dart';
import 'package:flutter_riverpod/flutter_riverpod.dart';

import '../providers.dart';
import 'crossword_generator_widget.dart';
import 'crossword_puzzle_widget.dart';
import 'puzzle_completed_widget.dart';

class CrosswordPuzzleApp extends StatelessWidget {
  const CrosswordPuzzleApp({super.key});

  @override
  Widget build(BuildContext context) {
    return _EagerInitialization(
      child: Scaffold(
        appBar: AppBar(
          actions: [_CrosswordPuzzleAppMenu()],
          titleTextStyle: TextStyle(
            color: Theme.of(context).colorScheme.primary,
            fontSize: 16,
            fontWeight: FontWeight.bold,
          ),
          title: Text('Crossword Puzzle'),
        ),
        body: SafeArea(
          child: Consumer(
            builder: (context, ref, _) {
              final workQueueAsync = ref.watch(workQueueProvider);
              final puzzleSolved = ref.watch(
                puzzleProvider.select((puzzle) => puzzle.solved),
              );

              return workQueueAsync.when(
                data: (workQueue) {
                  if (puzzleSolved) {
                    return PuzzleCompletedWidget();
                  }
                  if (workQueue.isCompleted &&
                      workQueue.crossword.characters.isNotEmpty) {
                    return CrosswordPuzzleWidget();
                  }
                  return CrosswordGeneratorWidget();
                },
                loading: () => Center(child: CircularProgressIndicator()),
                error: (error, stackTrace) => Center(child: Text('$error')),
              );
            },
          ),
        ),
      ),
    );
  }
}

class _EagerInitialization extends ConsumerWidget {
  const _EagerInitialization({required this.child});
  final Widget child;

  @override
  Widget build(BuildContext context, WidgetRef ref) {
    ref.watch(wordListProvider);
    return child;
  }
}

class _CrosswordPuzzleAppMenu extends ConsumerWidget {
  @override
  Widget build(BuildContext context, WidgetRef ref) => MenuAnchor(
    menuChildren: [
      for (final entry in CrosswordSize.values)
        MenuItemButton(
          onPressed: () => ref.read(sizeProvider.notifier).setSize(entry),
          leadingIcon: entry == ref.watch(sizeProvider)
              ? Icon(Icons.radio_button_checked_outlined)
              : Icon(Icons.radio_button_unchecked_outlined),
          child: Text(entry.label),
        ),
    ],
    builder: (context, controller, child) => IconButton(
      onPressed: () => controller.open(),
      icon: Icon(Icons.settings),
    ),
  );
}

このファイルの大部分は、すでに理解しているはずです。はい、未定義のウィジェットがあります。これから修正を開始します。

crossword_generator_widget.dart ファイルを作成し、次の内容を追加します。

lib/widgets/crossword_generator_widget.dart

import 'package:flutter/material.dart';
import 'package:flutter_riverpod/flutter_riverpod.dart';
import 'package:two_dimensional_scrollables/two_dimensional_scrollables.dart';

import '../model.dart';
import '../providers.dart';

class CrosswordGeneratorWidget extends ConsumerWidget {
  const CrosswordGeneratorWidget({super.key});

  @override
  Widget build(BuildContext context, WidgetRef ref) {
    final size = ref.watch(sizeProvider);
    return TableView.builder(
      diagonalDragBehavior: DiagonalDragBehavior.free,
      cellBuilder: _buildCell,
      columnCount: size.width,
      columnBuilder: (index) => _buildSpan(context, index),
      rowCount: size.height,
      rowBuilder: (index) => _buildSpan(context, index),
    );
  }

  TableViewCell _buildCell(BuildContext context, TableVicinity vicinity) {
    final location = Location.at(vicinity.column, vicinity.row);

    return TableViewCell(
      child: Consumer(
        builder: (context, ref, _) {
          final character = ref.watch(
            workQueueProvider.select(
              (workQueueAsync) => workQueueAsync.when(
                data: (workQueue) => workQueue.crossword.characters[location],
                error: (error, stackTrace) => null,
                loading: () => null,
              ),
            ),
          );

          final explorationCell = ref.watch(
            workQueueProvider.select(
              (workQueueAsync) => workQueueAsync.when(
                data: (workQueue) =>
                    workQueue.locationsToTry.keys.contains(location),
                error: (error, stackTrace) => false,
                loading: () => false,
              ),
            ),
          );

          if (character != null) {
            return AnimatedContainer(
              duration: Durations.extralong1,
              curve: Curves.easeInOut,
              color: explorationCell
                  ? Theme.of(context).colorScheme.primary
                  : Theme.of(context).colorScheme.onPrimary,
              child: Center(
                child: AnimatedDefaultTextStyle(
                  duration: Durations.extralong1,
                  curve: Curves.easeInOut,
                  style: TextStyle(
                    fontSize: 24,
                    color: explorationCell
                        ? Theme.of(context).colorScheme.onPrimary
                        : Theme.of(context).colorScheme.primary,
                  ),
                  child: Text('•'), // https://www.compart.com/en/unicode/U+2022
                ),
              ),
            );
          }

          return ColoredBox(
            color: Theme.of(context).colorScheme.primaryContainer,
          );
        },
      ),
    );
  }

  TableSpan _buildSpan(BuildContext context, int index) {
    return TableSpan(
      extent: FixedTableSpanExtent(32),
      foregroundDecoration: TableSpanDecoration(
        border: TableSpanBorder(
          leading: BorderSide(
            color: Theme.of(context).colorScheme.onPrimaryContainer,
          ),
          trailing: BorderSide(
            color: Theme.of(context).colorScheme.onPrimaryContainer,
          ),
        ),
      ),
    );
  }
}

これも、ある程度は知っておく必要があります。主な違いは、生成される単語の文字を表示する代わりに、不明な文字の存在を示す Unicode 文字を表示するようになったことです。このデザインは、もっと改善の余地がある。

crossword_puzzle_widget.dart ファイルを作成し、次の内容を追加します。

lib/widgets/crossword_puzzle_widget.dart

import 'package:built_collection/built_collection.dart';
import 'package:flutter/material.dart';
import 'package:flutter_riverpod/flutter_riverpod.dart';
import 'package:two_dimensional_scrollables/two_dimensional_scrollables.dart';

import '../model.dart';
import '../providers.dart';

class CrosswordPuzzleWidget extends ConsumerWidget {
  const CrosswordPuzzleWidget({super.key});

  @override
  Widget build(BuildContext context, WidgetRef ref) {
    final size = ref.watch(sizeProvider);
    return TableView.builder(
      diagonalDragBehavior: DiagonalDragBehavior.free,
      cellBuilder: _buildCell,
      columnCount: size.width,
      columnBuilder: (index) => _buildSpan(context, index),
      rowCount: size.height,
      rowBuilder: (index) => _buildSpan(context, index),
    );
  }

  TableViewCell _buildCell(BuildContext context, TableVicinity vicinity) {
    final location = Location.at(vicinity.column, vicinity.row);

    return TableViewCell(
      child: Consumer(
        builder: (context, ref, _) {
          final character = ref.watch(
            puzzleProvider.select(
              (puzzle) => puzzle.crossword.characters[location],
            ),
          );
          final selectedCharacter = ref.watch(
            puzzleProvider.select(
              (puzzle) =>
                  puzzle.crosswordFromSelectedWords.characters[location],
            ),
          );
          final alternateWords = ref.watch(
            puzzleProvider.select((puzzle) => puzzle.alternateWords),
          );

          if (character != null) {
            final acrossWord = character.acrossWord;
            var acrossWords = BuiltList<String>();
            if (acrossWord != null) {
              acrossWords = acrossWords.rebuild(
                (b) => b
                  ..add(acrossWord.word)
                  ..addAll(
                    alternateWords[acrossWord.location]?[acrossWord
                            .direction] ??
                        [],
                  )
                  ..sort(),
              );
            }

            final downWord = character.downWord;
            var downWords = BuiltList<String>();
            if (downWord != null) {
              downWords = downWords.rebuild(
                (b) => b
                  ..add(downWord.word)
                  ..addAll(
                    alternateWords[downWord.location]?[downWord.direction] ??
                        [],
                  )
                  ..sort(),
              );
            }

            return MenuAnchor(
              builder: (context, controller, _) {
                return GestureDetector(
                  onTapDown: (details) =>
                      controller.open(position: details.localPosition),
                  child: AnimatedContainer(
                    duration: Durations.extralong1,
                    curve: Curves.easeInOut,
                    color: Theme.of(context).colorScheme.onPrimary,
                    child: Center(
                      child: AnimatedDefaultTextStyle(
                        duration: Durations.extralong1,
                        curve: Curves.easeInOut,
                        style: TextStyle(
                          fontSize: 24,
                          color: Theme.of(context).colorScheme.primary,
                        ),
                        child: Text(selectedCharacter?.character ?? ''),
                      ),
                    ),
                  ),
                );
              },
              menuChildren: [
                if (acrossWords.isNotEmpty && downWords.isNotEmpty)
                  Padding(
                    padding: const EdgeInsets.all(4),
                    child: Text('Across'),
                  ),
                for (final word in acrossWords)
                  _WordSelectMenuItem(
                    location: acrossWord!.location,
                    word: word,
                    selectedCharacter: selectedCharacter,
                    direction: Direction.across,
                  ),
                if (acrossWords.isNotEmpty && downWords.isNotEmpty)
                  Padding(
                    padding: const EdgeInsets.all(4),
                    child: Text('Down'),
                  ),
                for (final word in downWords)
                  _WordSelectMenuItem(
                    location: downWord!.location,
                    word: word,
                    selectedCharacter: selectedCharacter,
                    direction: Direction.down,
                  ),
              ],
            );
          }

          return ColoredBox(
            color: Theme.of(context).colorScheme.primaryContainer,
          );
        },
      ),
    );
  }

  TableSpan _buildSpan(BuildContext context, int index) {
    return TableSpan(
      extent: FixedTableSpanExtent(32),
      foregroundDecoration: TableSpanDecoration(
        border: TableSpanBorder(
          leading: BorderSide(
            color: Theme.of(context).colorScheme.onPrimaryContainer,
          ),
          trailing: BorderSide(
            color: Theme.of(context).colorScheme.onPrimaryContainer,
          ),
        ),
      ),
    );
  }
}

class _WordSelectMenuItem extends ConsumerWidget {
  const _WordSelectMenuItem({
    required this.location,
    required this.word,
    required this.selectedCharacter,
    required this.direction,
  });

  final Location location;
  final String word;
  final CrosswordCharacter? selectedCharacter;
  final Direction direction;

  @override
  Widget build(BuildContext context, WidgetRef ref) {
    final notifier = ref.read(puzzleProvider.notifier);
    return MenuItemButton(
      onPressed:
          ref.watch(
            puzzleProvider.select(
              (puzzle) => puzzle.canSelectWord(
                location: location,
                word: word,
                direction: direction,
              ),
            ),
          )
          ? () => notifier.selectWord(
              location: location,
              word: word,
              direction: direction,
            )
          : null,
      leadingIcon:
          switch (direction) {
            Direction.across => selectedCharacter?.acrossWord?.word == word,
            Direction.down => selectedCharacter?.downWord?.word == word,
          }
          ? Icon(Icons.radio_button_checked_outlined)
          : Icon(Icons.radio_button_unchecked_outlined),
      child: Text(word),
    );
  }
}

このウィジェットは、過去に他の場所で使用されたパーツから構成されていますが、前のウィジェットよりも少し複雑です。これで、入力された各セルをクリックするとコンテキストメニューが表示され、ユーザーが選択できる単語が一覧表示されます。単語が選択されている場合、競合する単語は選択できません。単語の選択を解除するには、その単語のメニュー項目をタップします。

プレーヤーが単語を選択してクロスワード全体を埋めることができると仮定すると、「おめでとうございます！」という画面が必要です。

puzzle_completed_widget.dart ファイルを作成し、次の内容を追加します。

lib/widgets/puzzle_completed_widget.dart

import 'package:flutter/material.dart';

class PuzzleCompletedWidget extends StatelessWidget {
  const PuzzleCompletedWidget({super.key});

  @override
  Widget build(BuildContext context) {
    return Center(
      child: Text(
        'Puzzle Completed!',
        style: TextStyle(fontSize: 36, fontWeight: FontWeight.bold),
      ),
    );
  }
}

この情報を活用して、さらに興味深いものにできると思います。アニメーションツールについて詳しくは、Flutter で次世代 UI を構築する Codelab をご覧ください。

lib/main.dart ファイルを次のように編集します。

lib/main.dart

import 'package:flutter/material.dart';
import 'package:flutter_riverpod/flutter_riverpod.dart';

import 'widgets/crossword_puzzle_app.dart';                 // Update this line

void main() {
  runApp(
    ProviderScope(
      child: MaterialApp(
        title: 'Crossword Puzzle',                          // Update this line
        debugShowCheckedModeBanner: false,
        theme: ThemeData(
          colorSchemeSeed: Colors.blueGrey,
          brightness: Brightness.light,
        ),
        home: CrosswordPuzzleApp(),                         // Update this line
      ),
    ),
  );
}

このアプリを実行すると、クロスワードパズルジェネレータがパズルを生成するアニメーションが表示されます。次に、空白のパズルが表示されます。パズルを解くと、次のような画面が表示されます。

「パズルが完了しました」というテキストが表示されているクロスワードパズルアプリのウィンドウ

10. 完了

おめでとうございます！Flutter でパズルゲームを作成できました。

クロスワードジェネレータを構築し、パズルゲームにしました。分離プールのバックグラウンド計算の実行を習得しました。不変データ構造を使用して、バックトラッキングアルゴリズムの実装を容易にしました。また、TableView を使用して、表形式のデータを表示する必要がある場合に役立つ時間を過ごしました。

Flutter でワードパズルを作成する コレクションでコンテンツを整理 必要に応じて、コンテンツの保存と分類を行います。

1. 始める前に

前提条件

学習内容

必要なもの

2. プロジェクトを作成する

最初の Flutter プロジェクトを作成する

初期アプリをコピーして貼り付ける

依存関係を理解する

チェックポイント: 基本的なアプリの実行

3. 単語を追加する

クロスワード パズルの構成要素

単語を読み込む

ほぼ無限のリストアプリを作成する

次のステップ

4. 単語をグリッドで表示する

5. 制約を適用する

変更点とその理由

バックグラウンド処理に移行する理由

分離制限について

6. 作業キューを管理する

検索戦略を理解する

チェックポイント: 効率的なアルゴリズムの動作

7. サーフェスの統計情報

統計情報を追加する理由

8. スレッドで並列化する

パフォーマンスが低下する理由

アルゴリズムの可視化

マルチ分離アーキテクチャについて

チェックポイント: マルチスレッドのパフォーマンス

9. ゲームにする

作成するもの: ゲームルームのクロスワード パズル

10. 完了

その他の情報

Flutter でワードパズルを作成する

クロスワードパズルの構成要素

作成するもの: ゲームルームのクロスワードパズル