Wortpuzzle mit Flutter erstellen

1. Hinweis

Stellen Sie sich vor, Sie werden gefragt, ob es möglich ist, das größte Kreuzworträtsel der Welt zu erstellen. Sie erinnern sich an einige KI-Techniken, die Sie in der Schule gelernt haben, und fragen sich, ob Sie mit Flutter die algorithmischen Optionen nutzen können, um Lösungen für rechenintensive Probleme zu entwickeln.

In diesem Codelab geht es genau darum. Am Ende haben Sie ein Tool entwickelt, mit dem Sie Algorithmen zum Erstellen von Wortgitterrätseln ausprobieren können. Es gibt viele verschiedene Definitionen dafür, was ein gültiges Kreuzworträtsel ist. Mit diesen Techniken können Sie Rätsel erstellen, die Ihrer Definition entsprechen.

Animation eines Kreuzworträtsels, das generiert wird.

Auf dieser Grundlage erstellen Sie dann ein Kreuzworträtsel, das vom Kreuzworträtselgenerator für einen Nutzer generiert wird. Dieses Puzzle kann unter Android, iOS, Windows, macOS und Linux verwendet werden. So gehts auf Android-Geräten:

Screenshot eines Kreuzworträtsels, das auf einem Pixel Fold-Emulator gelöst wird.

Vorbereitung

Lerninhalte

  • So verwenden Sie Isolate für rechenintensive Aufgaben, ohne den Render-Loop von Flutter zu beeinträchtigen, indem Sie die compute-Funktion von Flutter und die Wert-Caching-Funktionen des Riverpod-Filters select rebuild filter's value-caching capabilities kombinieren.
  • Wie Sie unveränderliche Datenstrukturen mit built_value und built_collection nutzen können, um die suchbasierten GOFAI-Techniken (Good Old Fashioned AI) wie die Tiefensuche und Backtracking zu implementieren.
  • Wie Sie mit den Funktionen des two_dimensional_scrollables-Pakets Rasterdaten schnell und intuitiv darstellen.

Voraussetzungen

  • Das Flutter SDK
  • Visual Studio Code (VS Code) mit den Flutter- und Dart-Plug-ins.
  • Compiler-Software für das ausgewählte Entwicklungsziel. Dieses Codelab funktioniert auf allen Desktop-Plattformen, Android und iOS. Für Windows benötigen Sie VS Code, für macOS oder iOS Xcode und für Android Android Studio.

2. Projekt erstellen

Erstes Flutter-Projekt erstellen

  1. Starten Sie VS Code.
  2. Öffnen Sie die Befehlspalette (Strg + Umschalt + P unter Windows/Linux, Cmd + Umschalt + P unter macOS), geben Sie „flutter new“ ein und wählen Sie dann im Menü Flutter: New Project (Flutter: Neues Projekt) aus.

VS Code mit Flutter: „Neues Projekt“ wird in der geöffneten Befehlspalette angezeigt.

  1. Wählen Sie Leere Anwendung aus und wählen Sie dann ein Verzeichnis aus, in dem Sie Ihr Projekt erstellen möchten. Das sollte ein beliebiges Verzeichnis sein, für das keine erhöhten Berechtigungen erforderlich sind und dessen Pfad keine Leerzeichen enthält. Beispiele sind Ihr Basisverzeichnis oder C:\src\.

VS Code mit der Option „Leere Anwendung“ als Teil des Ablaufs für neue Anwendungen

  1. Benennen Sie Ihr Projekt mit generate_crossword. Im weiteren Verlauf dieses Codelabs wird davon ausgegangen, dass Sie Ihre App generate_crossword genannt haben.

VS Code mit „generate_crossword“ als Name für das neue Projekt

Flutter erstellt nun den Projektordner und VS Code öffnet ihn. Sie überschreiben jetzt den Inhalt von zwei Dateien mit einem einfachen Gerüst der App.

Ursprüngliche App kopieren und einfügen

  1. Klicken Sie im linken Bereich von VS Code auf Explorer und öffnen Sie die Datei pubspec.yaml.

Teilweiser Screenshot von VS Code mit Pfeilen, die die Position der Datei „pubspec.yaml“ hervorheben

  1. Ersetzen Sie den Inhalt dieser Datei durch die folgenden Abhängigkeiten, die für die Erstellung von Kreuzworträtseln erforderlich sind:

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

In der Datei pubspec.yaml werden grundlegende Informationen zu Ihrer App angegeben, z. B. die aktuelle Version und die Abhängigkeiten. Sie sehen eine Sammlung von Abhängigkeiten, die nicht Teil einer normalen leeren Flutter-App sind. Sie profitieren in den folgenden Schritten von all diesen Paketen.

Abhängigkeiten

Bevor wir uns den Code ansehen, wollen wir uns ansehen, warum diese Pakete ausgewählt wurden:

  • built_value: Erstellt unveränderliche Objekte, die Arbeitsspeicher effizient nutzen. Das ist entscheidend für unseren Backtracking-Algorithmus.
  • Riverpod: Bietet eine detaillierte Statusverwaltung mit select(), um das Neuerstellen zu minimieren.
  • two_dimensional_scrollables: Ermöglicht die Verarbeitung großer Tabellen ohne Leistungseinbußen
  1. Öffnen Sie die Datei main.dart im Verzeichnis lib/.

Teilweiser Screenshot von VS Code mit einem Pfeil, der die Position der Datei „main.dart“ zeigt

  1. Ersetzen Sie den Inhalt dieser Datei durch Folgendes:

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)),
          ),
        ),
      ),
    ),
  );
}
  1. Führen Sie diesen Code aus, um zu prüfen, ob alles funktioniert. Es sollte überall ein neues Fenster mit dem obligatorischen Startsatz jedes neuen Projekts angezeigt werden. Es gibt ein ProviderScope, das angibt, dass diese App riverpod für die Statusverwaltung verwendet.

Ein App-Fenster mit dem Text „Hello, World!“ in der Mitte

Prüfpunkt: Grundlegende App-Ausführung

Jetzt sollte ein Fenster mit der Meldung „Hello, World!“ angezeigt werden. Falls nicht:

  • Prüfen Sie, ob Flutter richtig installiert ist.
  • Prüfen, ob die App mit flutter run ausgeführt wird
  • Achten Sie darauf, dass im Terminal keine Kompilierungsfehler angezeigt werden.

3. Wörter hinzufügen

Bausteine für ein Kreuzworträtsel

Ein Kreuzworträtsel ist im Grunde eine Liste von Wörtern. Die Wörter sind in einem Raster angeordnet, einige waagerecht, einige senkrecht, sodass sie ineinandergreifen. Wenn Sie ein Wort lösen, erhalten Sie Hinweise auf die Wörter, die dieses Wort kreuzen. Ein guter erster Baustein ist also eine Liste von Wörtern.

Eine gute Quelle für diese Wörter ist die Seite Natural Language Corpus Data von Peter Norvig. Die SOWPODS-Liste mit 267.750 Wörtern ist ein guter Ausgangspunkt.

In diesem Schritt laden Sie eine Liste mit Wörtern herunter, fügen sie als Asset zu Ihrer Flutter-App hinzu und richten einen Riverpod-Provider ein, um die Liste beim Start in die App zu laden.

Führen Sie zunächst die folgenden Schritte aus:

  1. Ändern Sie die Datei pubspec.yaml Ihres Projekts, um die folgende Asset-Deklaration für die ausgewählte Wortliste hinzuzufügen. In diesem Eintrag wird nur der Flutter-Abschnitt der Konfiguration Ihrer App angezeigt, da der Rest unverändert geblieben ist.

pubspec.yaml

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

Ihr Editor wird diese letzte Zeile wahrscheinlich mit einer Warnung hervorheben, da Sie diese Datei noch nicht erstellt haben.

  1. Erstellen Sie mit Ihrem Browser und Ihrem Editor ein assets-Verzeichnis auf der obersten Ebene Ihres Projekts und darin eine words.txt-Datei mit einer der zuvor verlinkten Wortlisten.

Dieser Code wurde für die oben erwähnte SOWPODS-Liste entwickelt, sollte aber mit jeder Wortliste funktionieren, die nur Zeichen von A bis Z enthält. Die Erweiterung dieser Codebasis für die Arbeit mit verschiedenen Zeichensätzen bleibt dem Leser überlassen.

Wörter laden

So schreiben Sie den Code, der für das Laden der Wortliste beim Start der App verantwortlich ist:

  1. Erstellen Sie im Verzeichnis lib eine Datei providers.dart.
  2. Fügen Sie der Datei Folgendes hinzu.

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)),
      );
}

Dies ist Ihr erster Riverpod-Provider für diese Codebasis.

So funktioniert dieser Anbieter:

  1. Lädt die Wortliste asynchron aus Assets
  2. Filtert Wörter, sodass nur a–z-Zeichen mit mehr als zwei Buchstaben enthalten sind
  3. Gibt ein unveränderliches BuiltSet für effizienten Direktzugriff zurück.

In diesem Projekt wird die Codegenerierung für mehrere Abhängigkeiten verwendet, einschließlich Riverpod.

  1. Führen Sie den folgenden Befehl aus, um mit der Generierung von Code zu beginnen:
$ 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)

Es wird weiterhin im Hintergrund ausgeführt und aktualisiert generierte Dateien, wenn Sie Änderungen am Projekt vornehmen. Nachdem mit diesem Befehl der Code in providers.g.dart generiert wurde, sollte der Editor mit dem Code, den Sie in providers.dart hinzugefügt haben, zufrieden sein.

In Riverpod werden Provider wie die zuvor definierte wordList-Funktion in der Regel verzögert instanziiert. Für diese App muss die Wortliste jedoch sofort geladen werden. In der Riverpod-Dokumentation wird der folgende Ansatz für die Verarbeitung von Providern vorgeschlagen, die sofort geladen werden müssen. Das werden Sie jetzt umsetzen.

  1. Erstellen Sie im Verzeichnis lib/widgets eine Datei crossword_generator_app.dart.
  2. Fügen Sie der Datei Folgendes hinzu.

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;
  }
}

Diese Datei ist aus zwei verschiedenen Gründen interessant. Das erste ist das _EagerInitialization-Widget, das nur dazu dient, den zuvor erstellten wordList-Anbieter zum Laden der Wortliste zu zwingen. Dieses Widget erreicht dieses Ziel, indem es mit dem ref.watch()-Aufruf auf den Anbieter wartet. Weitere Informationen zu dieser Technik finden Sie in der Riverpod-Dokumentation unter Eager initialization of providers (Eifrige Initialisierung von Providern).

Der zweite interessante Punkt in dieser Datei ist, wie Riverpod asynchrone Inhalte verarbeitet. Wie Sie sich vielleicht erinnern, ist der wordList-Anbieter als asynchrone Funktion definiert, da das Laden von Inhalten von der Festplatte langsam ist. Wenn Sie sich den Anbieter der Wortliste in diesem Code ansehen, erhalten Sie AsyncValue<BuiltSet<String>>. Der AsyncValue-Teil dieses Typs ist ein Adapter zwischen der asynchronen Welt der Anbieter und der synchronen Welt der build-Methode des Widgets.

Die when-Methode von AsyncValue verarbeitet die drei möglichen Status, in denen sich der zukünftige Wert befinden kann. Das Future wurde möglicherweise erfolgreich aufgelöst. In diesem Fall wird der data-Callback aufgerufen. Es kann sich auch in einem Fehlerstatus befinden. In diesem Fall wird der error-Callback aufgerufen. Schließlich kann es auch noch geladen werden. Die Rückgabetypen der drei Callbacks müssen kompatibel sein, da die Rückgabe des aufgerufenen Callbacks von der Methode when zurückgegeben wird. In diesem Fall wird das Ergebnis der „when“-Methode als body des Scaffold-Widgets angezeigt.

App für eine nahezu unendliche Liste erstellen

So binden Sie das CrosswordGeneratorApp-Widget in Ihre App ein:

  1. Aktualisieren Sie die Datei lib/main.dart, indem Sie den folgenden Code hinzufügen:

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
      ),
    ),
  );
}
  1. Starten Sie die App neu. Es sollte eine scrollende Liste mit allen über 267.750 Wörtern im Wörterbuch angezeigt werden.

Ein App-Fenster mit dem Titel „Crossword Generator“ und einer Liste von Wörtern

Was Sie als Nächstes erstellen

Jetzt erstellen Sie die wichtigsten Datenstrukturen für Ihr Kreuzworträtsel mit unveränderlichen Objekten. Diese Grundlage ermöglicht effiziente Algorithmen und reibungslose UI-Updates.

4. Wörter in einem Raster anzeigen

In diesem Schritt erstellen Sie eine Datenstruktur zum Erstellen eines Kreuzworträtsels mit den Paketen built_value und built_collection. Mit diesen beiden Paketen können Datenstrukturen als unveränderliche Werte erstellt werden. Das ist sowohl für die Übergabe von Daten zwischen Isolates als auch für die Implementierung von Tiefensuche und Backtracking sehr nützlich.

Führen Sie zunächst die folgenden Schritte aus:

  1. Erstellen Sie im Verzeichnis lib eine Datei model.dart und fügen Sie ihr folgenden Inhalt hinzu:

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;

In dieser Datei wird der Beginn der Datenstruktur beschrieben, die Sie zum Erstellen von Kreuzworträtseln verwenden. Ein Kreuzworträtsel besteht aus einer Liste von horizontalen und vertikalen Wörtern, die in einem Raster ineinandergreifen. Um diese Datenstruktur zu verwenden, erstellen Sie mit dem benannten Konstruktor Crossword.crossword ein Crossword der entsprechenden Größe und fügen dann mit der Methode addWord Wörter hinzu. Beim Erstellen des endgültigen Werts wird mit der Methode _fillCharacters ein Raster mit CrosswordCharacter erstellt.

So verwenden Sie diese Datenstruktur:

  1. Erstellen Sie im Verzeichnis lib eine Datei utils und fügen Sie ihr folgenden Inhalt hinzu:

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));
  }
}

Dies ist eine Erweiterung von BuiltSet, mit der sich ganz einfach ein zufälliges Element aus der Menge abrufen lässt. Erweiterungsmethoden sind eine gute Möglichkeit, Klassen mit zusätzlichen Funktionen zu erweitern. Die Erweiterung muss benannt werden, damit sie außerhalb der utils.dart-Datei verfügbar ist.

  1. Fügen Sie in der Datei lib/providers.dart die folgenden Importe hinzu:

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 {

Durch diese Importe wird das zuvor definierte Modell für die Anbieter verfügbar gemacht, die Sie gleich erstellen. Der dart:math-Import ist für Random, der flutter/foundation.dart-Import für debugPrint, model.dart für das Modell und utils.dart für die BuiltSet-Erweiterung enthalten.

  1. Fügen Sie am Ende derselben Datei die folgenden Anbieter hinzu:

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;
    },
  );
}

Durch diese Änderungen werden Ihrer App zwei Anbieter hinzugefügt. Der erste ist Size. Das ist im Grunde eine globale Variable, die den ausgewählten Wert der CrosswordSize-Enumeration enthält. So kann die Größe des Kreuzworträtsels in der Benutzeroberfläche sowohl angezeigt als auch festgelegt werden. Der zweite Anbieter, crossword, ist eine interessantere Kreation. Es ist eine Funktion, die eine Reihe von Crosswords zurückgibt. Sie wird mit der Unterstützung von Dart für Generatoren erstellt, was durch das async* in der Funktion gekennzeichnet ist. Das bedeutet, dass die Funktion nicht mit einem Zeilenumbruch endet, sondern eine Reihe von Crosswords zurückgibt. So lässt sich eine Berechnung, die Zwischenergebnisse zurückgibt, viel einfacher schreiben.

Da am Anfang der crossword-Anbieterfunktion ein Paar ref.watch-Aufrufe vorhanden ist, wird der Stream von Crosswords jedes Mal vom Riverpod-System neu gestartet, wenn sich die ausgewählte Größe des Kreuzworträtsels ändert und wenn die Wortliste geladen wird.

Jetzt haben Sie Code zum Generieren von Kreuzworträtseln, wenn auch voller zufälliger Wörter. Es wäre schön, sie dem Nutzer des Tools zu zeigen.

  1. Erstellen Sie im Verzeichnis lib/widgets eine Datei crossword_widget.dart mit folgendem Inhalt:

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,
          ),
        ),
      ),
    );
  }
}

Dieses Widget ist ein ConsumerWidget und kann sich direkt auf den Size-Anbieter verlassen, um die Größe des Rasters zu bestimmen, in dem die Zeichen des Crossword angezeigt werden. Die Darstellung dieses Rasters erfolgt mit dem TableView-Widget aus dem Paket two_dimensional_scrollables.

Die einzelnen Zellen, die von den _buildCell-Hilfsfunktionen gerendert werden, enthalten jeweils ein Consumer-Widget in ihrem zurückgegebenen Widget-Baum. Dies dient als Aktualisierungsgrenze. Alles im Consumer-Widget wird neu erstellt, wenn sich der zurückgegebene Wert von ref.watch ändert. Es ist verlockend, den gesamten Baum jedes Mal neu zu erstellen, wenn sich Crossword ändert. Dies führt jedoch zu vielen Berechnungen, die mit dieser Einrichtung vermieden werden können.

Wenn Sie sich den Parameter von ref.watch ansehen, sehen Sie, dass durch die Verwendung von crosswordProvider.select eine weitere Ebene der Vermeidung von Neuberechnungen von Layouts vorhanden ist. Das bedeutet, dass ref.watch nur dann einen Neuaufbau des Inhalts von TableViewCell auslöst, wenn sich das Zeichen ändert, für das die Zelle verantwortlich ist. Diese Reduzierung des erneuten Renderns ist ein wesentlicher Bestandteil, um die Reaktionsfähigkeit der Benutzeroberfläche zu gewährleisten.

Wenn Sie den Nutzer auf die Anbieter CrosswordWidget und Size aufmerksam machen möchten, ändern Sie die Datei crossword_generator_app.dart so:

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.
}

Hier hat sich einiges geändert. Zuerst wurde der Code, der für das Rendern von wordList als ListView verantwortlich ist, durch einen Aufruf von CrosswordWidget ersetzt, das in der Datei lib/widgets/crossword_widget.dart definiert wurde. Die andere wichtige Änderung ist der Beginn eines Menüs zum Ändern des Verhaltens der App, beginnend mit der Änderung der Größe des Kreuzworträtsels. In den nächsten Schritten werden weitere MenuItemButton hinzugefügt. Führen Sie Ihre App aus. Sie sehen dann etwa Folgendes:

Ein App-Fenster mit dem Titel „Crossword Generator“ und einem Raster aus Zeichen, die als sich überlappende Wörter ohne erkennbaren Sinn angeordnet sind

Es werden Zeichen in einem Raster angezeigt und ein Menü, mit dem der Nutzer die Größe des Rasters ändern kann. Die Wörter sind aber nicht wie in einem Kreuzworträtsel angeordnet. Das liegt daran, dass keine Einschränkungen für das Hinzufügen von Wörtern zum Kreuzworträtsel erzwungen werden. Kurz gesagt: Es ist ein Chaos. Das werden Sie im nächsten Schritt in den Griff bekommen.

5. Einschränkungen erzwingen

Was wir ändern und warum

Derzeit sind in Ihrem Kreuzworträtsel überlappende Wörter ohne Validierung zulässig. Sie fügen die Überprüfung von Einschränkungen hinzu, um sicherzustellen, dass die Wörter wie in einem echten Kreuzworträtsel ineinandergreifen.

In diesem Schritt fügen Sie dem Modell Code hinzu, um die Kreuzworträtsel-Einschränkungen zu erzwingen. Es gibt viele verschiedene Arten von Kreuzworträtseln. Der Stil, der in diesem Codelab verwendet wird, orientiert sich an englischen Kreuzworträtseln. Die Anpassung dieses Codes zur Generierung anderer Kreuzworträtselstile bleibt wie immer dem Leser überlassen.

Führen Sie zunächst die folgenden Schritte aus:

  1. Öffnen Sie die Datei model.dart und ersetzen Sie nur das Crossword-Modell durch Folgendes:

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._();
}

Zur Erinnerung: Die Änderungen, die Sie an den Dateien model.dart und providers.dart vornehmen, erfordern, dass build_runner ausgeführt wird, um die entsprechenden Dateien model.g.dart und providers.g.dart zu aktualisieren. Wenn diese Dateien nicht automatisch aktualisiert wurden, ist jetzt ein guter Zeitpunkt, um build_runner mit dart run build_runner watch -d noch einmal zu starten.

Damit Sie diese neue Funktion in der Modellebene nutzen können, müssen Sie die Provider-Ebene entsprechend aktualisieren.

  1. Bearbeiten Sie die Datei providers.dart so:

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;
    },
  );
}
  1. Führen Sie die App aus. Auf der Benutzeroberfläche passiert nicht viel, aber in den Logs ist viel los.

App-Fenster für den Kreuzworträtsel-Generator mit horizontal und vertikal angeordneten Wörtern, die sich an zufälligen Stellen kreuzen

Wenn Sie darüber nachdenken, was hier passiert, sehen Sie, dass ein Kreuzworträtsel zufällig angezeigt wird. Die Methode addWord im Modell Crossword lehnt jedes vorgeschlagene Wort ab, das nicht in das aktuelle Kreuzworträtsel passt. Es ist also erstaunlich, dass überhaupt etwas angezeigt wird.

Warum zur Hintergrundverarbeitung wechseln?

Während der Erstellung von Kreuzworträtseln kann es vorkommen, dass die Benutzeroberfläche nicht reagiert. Das liegt daran, dass bei der Erstellung von Kreuzworträtseln Tausende von Validierungsprüfungen durchgeführt werden. Diese Berechnungen blockieren die 60‑fps-Rendering-Schleife von Flutter. Daher sollten Sie rechenintensive Vorgänge in Hintergrundisolaten ausführen. Das hat den Vorteil, dass die Benutzeroberfläche flüssig bleibt, während das Puzzle im Hintergrund generiert wird.

Um methodischer vorzugehen und besser zu entscheiden, welche Wörter wo ausprobiert werden sollen, wäre es sehr hilfreich, diese Berechnung vom UI-Thread in einen Hintergrund-Isolate zu verlagern. Flutter bietet einen sehr nützlichen Wrapper, mit dem sich ein Arbeitsabschnitt in einem Hintergrund-Isolat ausführen lässt: die Funktion compute.

  1. Ändern Sie in der Datei providers.dart den Kreuzworträtselanbieter so:

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;
    },
  );
}

Einschränkungen bei der Isolierung

Dieser Code funktioniert, hat aber ein verborgenes Problem. Für Isolates gelten strenge Regeln dafür, welche Daten zwischen ihnen übergeben werden dürfen. Das Problem besteht darin, dass der Abschluss die Anbieterreferenz „erfasst“, die nicht serialisiert und an ein anderes Isolate gesendet werden kann.

Diese Meldung wird angezeigt, wenn das System versucht, nicht serialisierbare Daten zu senden:

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)

Das ist das Ergebnis des Schließens, das compute an das Schließen des Hintergrundisolats über einen Anbieter übergibt, das nicht über SendPort.send() gesendet werden kann. Eine Lösung für dieses Problem besteht darin, dafür zu sorgen, dass sich der Verschluss nicht über etwas schließt, das nicht versendet werden kann.

Ein erster Schritt besteht darin, die Anbieter vom Isolate-Code zu trennen.

  1. Erstellen Sie eine isolates.dart-Datei in Ihrem lib-Verzeichnis und fügen Sie ihr folgenden Inhalt hinzu:

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');
    }
  }
}

Dieser Code sollte Ihnen bekannt vorkommen. Sie ist der Kern des crossword-Anbieters, aber jetzt als eigenständige Generatorfunktion. Jetzt können Sie die providers.dart-Datei aktualisieren, um diese neue Funktion zum Instanziieren des Hintergrundisolats zu verwenden.

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.
    },
  );
}

Sie haben jetzt ein Tool, mit dem Kreuzworträtsel unterschiedlicher Größe erstellt werden. Das Lösen des Rätsels erfolgt in einem Hintergrund-Isolat.compute Jetzt müsste nur noch der Code effizienter sein, wenn es darum geht, welche Wörter dem Kreuzworträtsel hinzugefügt werden sollen.

6. Arbeitsliste verwalten

Suchstrategie verstehen

Bei der Erstellung des Kreuzworträtsels wird Backtracking verwendet, ein systematischer Ansatz, bei dem verschiedene Möglichkeiten ausprobiert werden. Zuerst versucht die App, ein Wort an einer bestimmten Stelle zu platzieren. Dann wird geprüft, ob es zu den vorhandenen Wörtern passt. Wenn ja, behalten Sie es bei und versuchen Sie es mit dem nächsten Wort. Wenn nicht, entfernen Sie es und versuchen Sie es an einem anderen Ort.

Backtracking funktioniert bei Kreuzworträtseln, weil jede Wortplatzierung Einschränkungen für zukünftige Wörter schafft, wobei ungültige Platzierungen schnell erkannt und verworfen werden. Unveränderliche Datenstrukturen ermöglichen ein effizientes „Rückgängigmachen“ von Änderungen.

Ein Teil des Problems mit dem Code besteht darin, dass das zu lösende Problem im Grunde ein Suchproblem ist und die aktuelle Lösung blind sucht. Wenn sich der Code darauf konzentriert, Wörter zu finden, die an die aktuellen Wörter angehängt werden können, anstatt zufällig zu versuchen, Wörter irgendwo im Raster zu platzieren, würde das System schneller Lösungen finden. Eine Möglichkeit, dies zu erreichen, besteht darin, eine Arbeitswarteschlange mit Orten einzuführen, für die Wörter gesucht werden sollen.

Der Code erstellt mögliche Lösungen, prüft, ob die Lösung gültig ist, und übernimmt oder verwirft sie je nach Gültigkeit. Dies ist eine Beispielimplementierung aus der Familie der Backtracking-Algorithmen. Die Implementierung wird durch built_value und built_collection erheblich vereinfacht. Damit lassen sich neue unveränderliche Werte erstellen, die einen gemeinsamen Status mit dem unveränderlichen Wert haben, von dem sie abgeleitet wurden. So können potenzielle Kandidaten kostengünstig genutzt werden, ohne dass die für das tiefe Kopieren erforderlichen Arbeitsspeicherkosten anfallen.

Führen Sie zunächst die folgenden Schritte aus:

  1. Öffnen Sie die Datei model.dart und fügen Sie ihr die folgende WorkQueue-Definition hinzu:

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;
  1. Wenn in dieser Datei nach dem Hinzufügen der neuen Inhalte länger als einige Sekunden rote Schlangenlinien zu sehen sind, prüfen Sie, ob build_runner noch ausgeführt wird. Falls nicht, führen Sie den Befehl dart run build_runner watch -d aus.

Im Code fügen Sie jetzt Logging hinzu, um zu sehen, wie lange es dauert, Kreuzworträtsel in verschiedenen Größen zu erstellen. Es wäre schön, wenn Zeiträume in irgendeiner Form ansprechend formatiert angezeigt würden. Glücklicherweise können wir mit Erweiterungsmethoden genau die Methode hinzufügen, die wir benötigen.

  1. Bearbeiten Sie die Datei utils.dartso:

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.

Bei dieser Erweiterungsmethode werden Switch-Ausdrücke und Mustervergleich für Datensätze verwendet, um die geeignete Methode zur Anzeige verschiedener Zeiträume von Sekunden bis Tagen auszuwählen. Weitere Informationen zu diesem Codestil finden Sie im Codelab Dive into Dart's patterns and records.

  1. Um diese neue Funktion zu integrieren, ersetzen Sie die Datei isolates.dart, um die Definition der Funktion exploreCrosswordSolutions wie folgt neu zu definieren:

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}',
  );
}

Wenn Sie diesen Code ausführen, erhalten Sie eine App, die oberflächlich identisch aussieht. Der Unterschied besteht jedoch darin, wie lange es dauert, bis ein fertiges Kreuzworträtsel gefunden wird. Hier sehen Sie ein 80 × 44-Kreuzworträtsel, das in 1 Minute und 29 Sekunden generiert wurde.

Prüfpunkt: Effiziente Funktionsweise des Algorithmus

Die Kreuzworträtselgenerierung sollte jetzt deutlich schneller sein. Das liegt an folgenden Faktoren:

  • Schnittpunkte für das intelligente Targeting auf Wortgruppen
  • Effizientes Backtracking bei fehlgeschlagenen Placements
  • Verwaltung der Arbeitswarteschlange, um redundante Suchvorgänge zu vermeiden

Kreuzworträtsel-Generator mit vielen sich überschneidenden Wörtern Wenn die Ansicht verkleinert ist, sind die Wörter zu klein, um sie zu lesen.

Die naheliegende Frage ist natürlich: Können wir noch schneller werden? Ja, das ist möglich.

7. Oberflächenstatistiken

Warum Statistiken hinzufügen?

Wenn Sie etwas schnell erledigen möchten, ist es hilfreich, zu sehen, was passiert. Mithilfe von Statistiken können Sie den Fortschritt überwachen und sehen, wie der Algorithmus in Echtzeit funktioniert. So können Sie Engpässe ermitteln, indem Sie nachvollziehen, wo der Algorithmus die meiste Zeit verbringt. So können Sie die Leistung optimieren, indem Sie fundierte Entscheidungen zu Optimierungsansätzen treffen.

Die Informationen, die Sie anzeigen, müssen aus der WorkQueue extrahiert und in der Benutzeroberfläche angezeigt werden. Ein nützlicher erster Schritt ist es, eine neue Modellklasse zu definieren, die die Informationen enthält, die Sie anzeigen möchten.

Führen Sie zunächst die folgenden Schritte aus:

  1. Bearbeiten Sie die Datei model.dart so, dass die Klasse DisplayInfo hinzugefügt wird:

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> {
  1. Nehmen Sie am Ende der Datei die folgenden Änderungen vor, um die Klasse DisplayInfo hinzuzufügen:

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;
  1. Ändern Sie die Datei isolates.dart, um das Modell WorkQueue so verfügbar zu machen:

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}',
  );
}

Da die Hintergrundisolierung die Arbeitswarteschlange verfügbar macht, stellt sich nun die Frage, wie und wo Statistiken aus dieser Datenquelle abgeleitet werden können.

  1. Ersetzen Sie den alten Kreuzworträtselanbieter durch einen Anbieter für die Arbeitswarteschlange und fügen Sie dann weitere Anbieter hinzu, die Informationen aus dem Stream des Anbieters für die Arbeitswarteschlange ableiten:

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,
      );
}

Die neuen Anbieter sind eine Mischung aus globalem Status, z. B. ob die Informationsanzeige über das Kreuzworträtselgitter gelegt werden soll, und abgeleiteten Daten wie der Laufzeit der Kreuzworträtselgenerierung. Erschwerend kommt hinzu, dass Listener für einige dieser Status vorübergehend sind. Wenn die Informationsanzeige ausgeblendet ist, wird nichts auf die Start- und Endzeiten der Kreuzworträtselberechnung geachtet. Sie müssen jedoch im Speicher bleiben, damit die Berechnung genau ist, wenn die Informationsanzeige eingeblendet wird. Der keepAlive-Parameter des Attributs Riverpod ist in diesem Fall sehr nützlich.

Beim Anzeigen des Infodisplays gibt es eine kleine Unregelmäßigkeit. Wir möchten die verstrichene Laufzeit anzeigen, aber es gibt hier nichts, was die ständige Aktualisierung der verstrichenen Zeit erzwingt. Im Codelab Building next generation UIs in Flutter finden Sie ein nützliches Widget für genau diese Anforderung.

  1. Erstellen Sie im Verzeichnis lib/widgets eine Datei ticker_builder.dart und fügen Sie ihr folgenden Inhalt hinzu:

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);
}

Dieses Widget ist ein Vorschlaghammer. Die Inhalte werden in jedem Frame neu erstellt. Das ist im Allgemeinen verpönt, aber im Vergleich zur Rechenlast der Suche nach Kreuzworträtseln wird die Rechenlast des Neumalens der verstrichenen Zeit in jedem Frame wahrscheinlich im Rauschen untergehen. Um diese neu abgeleiteten Informationen zu nutzen, müssen Sie ein neues Widget erstellen.

  1. Erstellen Sie eine crossword_info_widget.dart-Datei in Ihrem lib/widgets-Verzeichnis und fügen Sie ihr folgenden Inhalt hinzu:

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),
        ),
      ],
    ),
  );
}

Dieses Widget ist ein gutes Beispiel für die Leistungsfähigkeit der Riverpod-Provider. Dieses Widget wird zum Neuerstellen markiert, wenn einer der fünf Anbieter aktualisiert wird. Die letzte erforderliche Änderung in diesem Schritt ist die Integration dieses neuen Widgets in die Benutzeroberfläche.

  1. Bearbeiten Sie die Datei crossword_generator_app.dart so:

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),
    ),
  );
}

Die beiden Änderungen veranschaulichen unterschiedliche Ansätze zur Integration von Anbietern. In der Methode CrosswordGeneratorApp von build haben Sie einen neuen Consumer-Builder eingeführt, der den Bereich enthält, der neu aufgebaut werden muss, wenn die Infoleiste ein- oder ausgeblendet wird. Andererseits ist das gesamte Drop-down-Menü ein ConsumerWidget, das neu erstellt wird, unabhängig davon, ob das Kreuzworträtsel in der Größe angepasst oder die Infobox ein- oder ausgeblendet wird. Welcher Ansatz gewählt wird, ist immer ein technischer Kompromiss zwischen Einfachheit und den Kosten für die Neuberechnung von Layouts neu erstellter Widget-Bäume.

Wenn der Nutzer die App jetzt ausführt, erhält er mehr Einblick in den Fortschritt der Kreuzworträtselerstellung. Gegen Ende der Kreuzworträtselgenerierung sehen wir jedoch einen Zeitraum, in dem sich die Zahlen ändern, aber das Raster der Zeichen sich kaum verändert.

Das Fenster der Crossword Generator App ist diesmal kleiner. Es sind erkennbare Wörter zu sehen und unten rechts befindet sich ein unverankertes Overlay mit Statistiken zum aktuellen Generierungslauf.

Es wäre hilfreich, zusätzliche Informationen darüber zu erhalten, was passiert und warum.

8. Parallelisieren mit Threads

Gründe für Leistungseinbußen

Je näher das Kreuzworträtsel der Fertigstellung kommt, desto langsamer wird der Algorithmus, da es weniger gültige Optionen für die Platzierung von Wörtern gibt. Der Algorithmus probiert viele Kombinationen aus, die nicht funktionieren. Bei der Single-Thread-Verarbeitung können nicht mehrere Optionen gleichzeitig untersucht werden.

Algorithmus visualisieren

Um zu verstehen, warum es am Ende langsam wird, ist es hilfreich, sich zu veranschaulichen, was der Algorithmus tut. Ein wichtiger Teil ist die ausstehende locationsToTry in der WorkQueue. Die Tabellenansicht ist dafür sehr hilfreich. Wir können die Zellenfarbe je nachdem ändern, ob sich die Zelle in locationsToTry befindet.

Führen Sie zunächst die folgenden Schritte aus:

  1. Ändern Sie die Datei crossword_widget.dart so:

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,
          ),
        ),
      ),
    );
  }
}

Wenn Sie diesen Code ausführen, wird eine Visualisierung der ausstehenden Standorte angezeigt, die der Algorithmus noch untersuchen muss.

Der Crossword Generator während der Generierung Einige Buchstaben sind weißer Text auf dunkelblauem Hintergrund, andere sind blauer Text auf weißem Hintergrund.

Das Interessante daran, das Kreuzworträtsel zu beobachten, während es sich der Fertigstellung nähert, ist, dass es eine Reihe von Punkten gibt, die noch untersucht werden müssen, aber nichts Nützliches ergeben. Hier gibt es zwei Möglichkeiten: Entweder wird die Untersuchung beendet, sobald ein bestimmter Prozentsatz der Kreuzworträtselzellen ausgefüllt ist, oder es werden mehrere Points of Interest gleichzeitig untersucht. Der zweite Weg klingt nach mehr Spaß, also ist es an der Zeit, ihn zu gehen.

  1. Bearbeiten Sie die Datei isolates.dart. Dazu musste der Code fast vollständig neu geschrieben werden, um die Berechnung, die zuvor in einem Hintergrund-Isolat erfolgte, auf einen Pool von N Hintergrund-Isolaten aufzuteilen.

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);
}

Multi-Isolate-Architektur

Der Großteil dieses Codes sollte Ihnen bekannt sein, da sich die zugrunde liegende Geschäftslogik nicht geändert hat. Neu ist, dass es jetzt zwei Ebenen von compute-Aufrufen gibt. Die erste Ebene ist dafür verantwortlich, einzelne Positionen an N Worker-Isolate zu übergeben und die Ergebnisse wieder zusammenzuführen, wenn alle N Worker-Isolate fertig sind. Die zweite Ebene besteht aus den N Worker-Isolaten. Die optimale Einstellung von N hängt sowohl von Ihrem Computer als auch von den betreffenden Daten ab. Je größer das Raster, desto mehr Mitarbeiter können zusammenarbeiten, ohne sich gegenseitig zu behindern.

Interessant ist, wie in diesem Code das Problem behoben wird, dass Closures Dinge erfassen, die sie nicht erfassen sollten. Es gibt keine Schließungen mehr. Die Funktionen _generate und _generateWorker sind als Funktionen der obersten Ebene definiert, für die keine Umgebung zum Erfassen vorhanden ist. Die Argumente für und die Ergebnisse beider Funktionen sind in Form von Dart-Datensätzen. So lässt sich die Semantik „ein Wert rein, ein Wert raus“ des compute-Aufrufs umgehen.

Jetzt, da Sie einen Pool von Hintergrund-Workern erstellen können, um nach Wörtern zu suchen, die in einem Raster ineinandergreifen und ein Kreuzworträtsel bilden, ist es an der Zeit, diese Funktion für den Rest des Kreuzworträtsel-Generators verfügbar zu machen.

  1. Bearbeiten Sie die Datei providers.dart, indem Sie den WorkQueue-Anbieter so bearbeiten:

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();
}
  1. Fügen Sie den WorkerCount-Anbieter am Ende der Datei so hinzu:

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.

Durch diese beiden Änderungen bietet die Anbieterschicht jetzt die Möglichkeit, die maximale Anzahl von Workern für den Hintergrund-Isolat-Pool so festzulegen, dass die Isolatfunktionen richtig konfiguriert werden.

  1. Aktualisieren Sie die Datei crossword_info_widget.dart, indem Sie CrosswordInfoWidget so ändern:

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,
                      ),
                  ],
                ),
              ),
            ),
          ),
        ),
      ),
    );
  }
}
  1. Ändern Sie die Datei crossword_generator_app.dart, indem Sie dem _CrosswordGeneratorMenu-Widget den folgenden Abschnitt hinzufügen:

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),
    ),
  );
}

Wenn Sie die App jetzt ausführen, können Sie die Anzahl der Hintergrund-Isolates ändern, die zum Suchen nach Wörtern für das Kreuzworträtsel instanziiert werden.

  1. Klicken Sie auf das Zahnradsymbol, um das Kontextmenü zu öffnen. Dort können Sie die Größe des Kreuzworträtsels, die Anzeige der Statistiken und die Anzahl der zu verwendenden Isolierungen festlegen.

Fenster des Kreuzworträtsel-Generators mit Wörtern und Statistiken

Checkpoint: Multithread-Leistung

Durch die Ausführung des Kreuzworträtselgenerators wurde die Rechenzeit für ein 80 × 44-Kreuzworträtsel durch die gleichzeitige Verwendung mehrerer Kerne erheblich verkürzt. Das sollten Sie beachten:

  • Schnellere Kreuzworträtselgenerierung mit mehr Mitarbeitern
  • Flüssige UI-Reaktionsfähigkeit während der Generierung
  • Echtzeitstatistiken zum Fortschritt der Generierung
  • Visuelles Feedback zu Bereichen, in denen der Algorithmus nach neuen Inhalten sucht

9. Machen Sie ein Spiel daraus

Was wir entwickeln: Ein Playable-Kreuzworträtsel

Dieser letzte Abschnitt ist wirklich eine Bonusrunde. Sie wenden alle Techniken an, die Sie beim Erstellen des Kreuzworträtselgenerators gelernt haben, um ein Spiel zu entwickeln. Sie werden Folgendes tun:

  1. Rätsel erstellen: Mit dem Kreuzworträtselgenerator können Sie lösbare Rätsel erstellen.
  2. Wortvorschläge erstellen: Geben Sie für jede Position mehrere Wortoptionen an.
  3. Interaktion aktivieren: Nutzern das Auswählen und Platzieren von Wörtern ermöglichen
  4. Lösungen validieren: Prüfen Sie, ob das ausgefüllte Kreuzworträtsel korrekt ist.

Sie verwenden den Kreuzworträtselgenerator, um ein Kreuzworträtsel zu erstellen. Sie verwenden die Idiome des Kontextmenüs, damit der Nutzer Wörter auswählen und abwählen kann, die in die verschiedenen wortförmigen Lücken im Raster eingefügt werden sollen. Ziel ist es, das Kreuzworträtsel zu lösen.

Ich werde nicht sagen, dass dieses Spiel ausgereift oder fertig ist. Das ist es bei Weitem nicht. Es gibt Probleme mit dem Gleichgewicht und dem Schwierigkeitsgrad, die durch eine bessere Auswahl alternativer Wörter gelöst werden können. Es gibt kein Tutorial, das Nutzer in das Rätsel einführt. Ich möchte gar nicht erst auf den Bildschirm mit der Meldung „Du hast gewonnen!“ eingehen.

Der Nachteil ist, dass für die Entwicklung dieses Prototyps zu einem vollständigen Spiel deutlich mehr Code erforderlich ist. Mehr Code als in einem einzelnen Codelab. Stattdessen soll dieser Schritt dazu dienen, die bisher in diesem Codelab erlernten Techniken zu festigen, indem ihre Verwendung geändert wird. Hoffentlich festigt das die Lektionen, die Sie zuvor in diesem Codelab gelernt haben. Alternativ können Sie auch eigene Funktionen auf Grundlage dieses Codes entwickeln. Wir sind gespannt auf Ihre Ideen.

Führen Sie zunächst die folgenden Schritte aus:

  1. Löschen Sie alle Inhalte im Verzeichnis lib/widgets. Sie erstellen neue Widgets für Ihr Spiel. Das neue Widget ähnelt den alten Widgets sehr.
  1. Bearbeiten Sie die Datei model.dart, um die Methode addWord von Crossword so zu aktualisieren:

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;
    }
  }

Durch diese geringfügige Änderung Ihres Kreuzworträtselmodells können Wörter hinzugefügt werden, die sich nicht überschneiden. Es ist nützlich, wenn Spieler an einer beliebigen Stelle auf dem Brett spielen können und Crossword weiterhin als Basismodell zum Speichern der Züge des Spielers verwendet werden kann. Es ist nur eine Liste von Wörtern an bestimmten Stellen, die in eine bestimmte Richtung platziert werden.

  1. Fügen Sie die Modellklasse CrosswordPuzzleGame am Ende der Datei model.dart hinzu.

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;

Die Aktualisierungen der Datei providers.dart sind eine interessante Mischung von Änderungen. Die meisten Anbieter, die zur Unterstützung der Statistikerhebung vorhanden waren, wurden entfernt. Die Möglichkeit, die Anzahl der Hintergrundisolierungen zu ändern, wurde entfernt und durch eine Konstante ersetzt. Außerdem gibt es einen neuen Anbieter, der Zugriff auf das neue CrosswordPuzzleGame-Modell bietet, das Sie zuvor hinzugefügt haben.

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);

Die interessantesten Aspekte des Puzzle-Anbieters sind die Strategien, die angewendet werden, um die Kosten für die Erstellung des CrosswordPuzzleGame aus einem Crossword und einem wordList sowie die Kosten für die Auswahl eines Wortes zu verschleiern. Beide Aktionen führen ohne die Unterstützung durch einen Hintergrund zu einer trägen Benutzeroberfläche. Wenn Sie ein Zwischenergebnis anzeigen, während das Endergebnis im Hintergrund berechnet wird, erhalten Sie eine reaktionsschnelle Benutzeroberfläche, während die erforderlichen Berechnungen im Hintergrund ausgeführt werden.

  1. Erstellen Sie im jetzt leeren Verzeichnis lib/widgets eine crossword_puzzle_app.dart-Datei mit folgendem Inhalt:

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),
    ),
  );
}

Der Großteil dieser Datei sollte Ihnen inzwischen vertraut sein. Ja, es gibt undefinierte Widgets, die Sie jetzt beheben müssen.

  1. Erstellen Sie eine crossword_generator_widget.dart-Datei und fügen Sie ihr folgenden Inhalt hinzu:

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,
          ),
        ),
      ),
    );
  }
}

Das sollte Ihnen auch einigermaßen vertraut sein. Der Hauptunterschied besteht darin, dass anstelle der Zeichen der generierten Wörter jetzt ein Unicode-Zeichen angezeigt wird, um das Vorhandensein eines unbekannten Zeichens anzugeben. Die Ästhetik könnte wirklich verbessert werden.

  1. Erstellen Sie die Datei crossword_puzzle_widget.dart und fügen Sie ihr folgenden Inhalt hinzu:

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),
    );
  }
}

Dieses Widget ist etwas komplexer als das letzte, obwohl es aus Teilen besteht, die Sie bereits an anderen Stellen gesehen haben. Wenn Sie jetzt auf eine ausgefüllte Zelle klicken, wird ein Kontextmenü mit den Wörtern angezeigt, die ein Nutzer auswählen kann. Wenn Wörter ausgewählt wurden, können Wörter, die in Konflikt stehen, nicht ausgewählt werden. Um ein Wort zu deaktivieren, tippt der Nutzer auf den entsprechenden Menüpunkt.

Angenommen, der Spieler kann Wörter auswählen, um das gesamte Kreuzworträtsel auszufüllen. In diesem Fall benötigen Sie einen Bildschirm mit der Meldung „Du hast gewonnen!“.

  1. Erstellen Sie eine puzzle_completed_widget.dart-Datei und fügen Sie ihr folgenden Inhalt hinzu:

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),
      ),
    );
  }
}

Ich bin mir sicher, dass du daraus etwas Interessanteres machen kannst. Weitere Informationen zu Animationstools finden Sie im Codelab Building next generation UIs in Flutter.

  1. Bearbeiten Sie die Datei lib/main.dart so:

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
      ),
    ),
  );
}

Wenn Sie diese App ausführen, sehen Sie die Animation, während der Kreuzworträtselgenerator Ihr Rätsel erstellt. Anschließend wird Ihnen eine leere Aufgabe angezeigt, die Sie lösen müssen. Wenn Sie das Rätsel lösen, sollte ein Bildschirm wie dieser angezeigt werden:

Fenster der Kreuzworträtsel-App mit dem Text „Rätsel gelöst!“

10. Glückwunsch

Glückwunsch! Sie haben erfolgreich ein Puzzlespiel mit Flutter entwickelt.

Sie haben einen Kreuzworträtselgenerator entwickelt, der zu einem Puzzlespiel wurde. Sie haben gelernt, Hintergrundberechnungen in einem Pool von Isolaten auszuführen. Sie haben unveränderliche Datenstrukturen verwendet, um die Implementierung eines Backtracking-Algorithmus zu vereinfachen. Außerdem haben Sie sich intensiv mit TableView beschäftigt, was Ihnen beim nächsten Mal, wenn Sie tabellarische Daten präsentieren müssen, zugute kommt.

Weitere Informationen