Wordament Wortfeld generieren

[Teflo]

Hallöchen!

Ich mach grade für den Game Jam im Atelier einen Wordament Klon.
Bei diesem Spiel hat man ein Feld mit 4x4 Einzelfeldern, jedes mit einem Buchstaben darauf. Nun kann man über Touch (bei mir bis jetzt mit der Maus) kreuz und quer über die Felder streichen. Diese werden markiert und sobald man loslässt wird überprüft, ob die aneinandergereihten Buchstaben ein existierendes Wort ergeben.



Mein Problem ist im Moment die Generierung eines solchen Levels. Wenn man nur durch Zufall eines erstellt findet man sehr oft viel zu wenige Wörter.

Dafür habe ich mir ein Wörterbuch als txt runtergeladen und beim Beginn des Spiels werden alle Wörter eingelesen. Dabei wird auch gezählt, welcher Buchstabe wie oft in den Wörtern vorhanden ist, um eine Wahrscheinlichkeit für jeden Buchstaben gemacht. Zusätzlich werden noch von jedem Buchstaben die Nachbarn gezählt.

Mal als Beispiel man hat als einziges Wort im Wörterbuch "HALLO", dann hat man folgende Verteilungen:
H = 0.1666
A = 0.1666
L = 0.333
O = 0.1666

Und für die Nachbarn:
H
-A = 1

A
-H = 0.5
-L = 0.5

L
-A = 0.5
-L = 0.5

O
-L = 1

Angewendet auf mehrere hunderttausend Wörter sind die Verteilungen natürlich wahnsinnig winzig. Aufjedenfall nutze ich das, um mir abhängig von einem bestimmten Feld mit einen gewichteten Zufallsgenerator einen passenden Buchstaben herausgeben zu lassen.

Von da ausgehend ist meine Generierung noch sehr simpel:
Ich beginne mit dem linken, oberen Feld und lass einen zufälligen Buchstaben generieren.
Nun geh ich ein Feld weiter nach rechts. Da gibt es jetzt 2 Möglichkeiten, je nach Zufall:
-Ich schaue mir das linkere Feld an und lasse anhand dessen Buchstaben den nächsten generieren (durch die Gewichtung der Nachbarn wie oben beschrieben)
-Ich generiere wieder einen zufälligen Buchstaben
Das wird die ganze Zeile gemacht. In der nächsten Zeile wird im Prinzip das gleiche gemacht, nur dass ich entweder das linke, das obere, oder das linke obere Feld von dem aktuellen ausgehend nehme.

Da ist mir dann aufgefallen, dass es vielleicht nicht reicht, nur einen Nachbarn auszuwählen, sondern den nächsten Buchstaben anhand mehrerer, zufälliger Nachbarfelder generiere.
Bis jetzt sind dadurch nicht spürbar mehr Wörter entstanden, aber das ist ja auch verbesserungswürdig.

Was ich aber noch brauche
ist, dass ich ja garnicht überprüfen kann, wieviele Wörter darin überhaupt zu finden sind. Ich mein, wenn ich einen Algo hab, der mir ausspuckt, wieviele Wörter in dem Wortfeld sind, kann ich schnell entscheiden ob einfach ein neues generiert wird, oder ob die Anzahl genügt.
Dafür bräuchte ich sowas wie einen "Matrix-Crawler" der im Prinzip alle möglichen Pfade durch das Feld geht und guckt, wieviele davon existierende Wörter ergeben.

Da hatte ich auch schon eine Idee. Man startet in der linken oberen Ecke und versucht von da aus immer geradeaus zu gehen, bis er an den rechten Rand kommt. Dort dreht er sich, bis er weiter kann und läuft nach unten, bis auf Rand trifft usw. bis es kein weiteres begehbares Feld gibt. Nun überprüfe ich alle Teil-Ketten dieser großen Kette ob sie ein Wort bilden. Bin ich alle durch wird wie folgt weitergemacht: Man geht ein Feld zurück und schaut, ob es ein andere Möglichkeit gibt als vorher. Wenn ja, gehe diesen entlang und prüfe die neuen Teil-Ketten. Wenn nein, gehe wieder ein Feld zurück. Das wird solange wiederholt, bis alle Möglichkeiten durch sind oder genügend Wörter gefunden wurden (wenn man zum Beispiel ein Puzzle mit 100 Wörtern drin haben will)

Vielleicht kennt ja jemand einen Algorithmus in der Richtung, hat weitere Ideen oder Vorschläge
Ich denke, das kan ganz schon interessant werden!