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!

[Whiz-zarD]

Das klingt eher, wie ein rekursiver Ablauf.

Code:

funktion MatrixCrawler (teilwort, ref wörterliste, xPos, yPos)
begin
  
  wenn IstTeilEinesWortes(teilwort) 
    und xPos >= 0 und xPos < anzahlSpalten 
    und yPos >= 0 und yPos < anzahlZeilen
  dann
  
    // Finden eines Wortes
    wenn teilwort in Wörterbuch
    dann
      füge teilwort in Wörterliste    
    wenn_ende
	
    // erstellen eines neuen Teilwortes
    buchstabe = gibBuchstabe(xPos, yPos)
    neuesTeilwort = teilwort + buchstabe
	
    // durchlaufe alle verfügbaren Richtungen
    MatrixCrawler(neuesTeilwort, wörterliste, xPos - 1, yPos)
    MatrixCrawler(neuesTeilwort, wörterliste, xPos + 1, yPos)
    MatrixCrawler(neuesTeilwort, wörterliste, xPos, yPos - 1)
    MatrixCrawler(neuesTeilwort, wörterliste, xPos, yPos + 1)
	
  wenn_ende
  
end

Dies hab ich nun innerhalb von ein paar Minuten hingeschmiert. Kann sein, dass ich an der Abbruchbedingung was übersehen habe.
In der Funktion IstTeilEinesWortes() werden alle Wörter im Wörterbuch mit dem Teilwort verglichen. Ein Wort im Wörterbuch muss dann mit dem Teilwort anfangen.
Wenn dies wahr ist, dann soll noch mal überprüft werden, ob wir uns noch in der Matrix befinden.
Wenn alle Bedingungen erfüllt sind, wird geschaut, ob das Teilwort ein komplettes Wort im Wörterbuch entspricht. Wenn ja, dann wird das Teilwort in die Wörterliste gespeichert.
Nun wird die Rekursion gestartet. Es wird ein neues Teilwort gebildet, und durchläuft nun alle Richtungen.

wörterliste ist ein Referenzparameter, je nach Sprache müsste es ein wenig anders implementiert werden.

[Teflo]

Hey, danke sehr!
Das einzige was noch fehlt ist, dass alle Teilwörter von dem neuen überprüft werden müssten. Wenn man die Felder X-O-E-H-A-L-L-O_R hat, muss natürlich Hallo drin gefunden werden. Außerdem kann man ja von jedem Feld aus anfangen zu wischen, das hieße die Funktion müsste auch einmal für jedes Feld aufgerufen werden, oder?

Ich setz mich schonmal an eine erste Implementation

[Whiz-zarD]

Das einzige was noch fehlt ist, dass alle Teilwörter von dem neuen überprüft werden müssten. Wenn man die Felder X-O-E-H-A-L-L-O_R hat, muss natürlich Hallo drin gefunden werden.

...

Nein, das muss nicht. Erklärung folgt im nächsten Abschnitt.

Außerdem kann man ja von jedem Feld aus anfangen zu wischen, das hieße die Funktion müsste auch einmal für jedes Feld aufgerufen werden, oder?

...

Ja, man muss diese Methode für jedes Feld aufrufen. Also ne verschaltete for-schleife, oder wie auch immer du durch die Felder iterieren möchtest.
Dann brauchst du auch die Überprüfung, die du vorgeschlagen hast, nicht machen, denn irgendwann landet er beim H und durchläuft dann die Buchstaben H-A-L-L-O, findet das Wort im Wörterbuch und schreibt es in die Wörterliste.

[Teflo]

Ja, du hast Recht! Ich habs jetzt eingebaut und es funktioniert absolut perfekt!

Mein Code sieht jetzt so aus:

Code:

public void Crawl()
{
    for (int x = 0; x < width; x++)
        for (int y = 0; y < height; y++)
        {
              visited = new bool[width, height];
              Crawl("", x, y);
        }
}

private void Crawl(String partword, int x, int y)
{
    if (x < 0 || x >= width) return;
    if (y < 0 || y >= height) return;
    if (visited[x, y]) return;

    visited[x, y] = true;

    partword += cards[x, y];
    if (language.CheckWord(partword) && !words.ContainsKey(partword))
        words.Add(partword, partword);

     for (int i = -1; i < 2; i++) 
          for (int j = -1; j < 2; j++)
              if (i != 0 || j != 0)
                  Crawl(partword, x + i, y + j);
            
    visited[x, y] = false;
}

Ich habe noch ein 2D Boolean Array erstellt, das besagt, welche Felder ich schon durchgegangen bin auf dem aktuellen Pfad und welche nicht. Wenn der Pfad nicht weitergeht, wird ein Feld im Pfad zurückgegangen und es wird wieder auf false gesetzt.

Vielen Dank, das hat mir wirklich geholfen. Wenn ich in meinem Kopf anfange wird das meist zu schnell zu kompliziert, weil ich alle möglichen Fälle durchgehe. Jetzt merke ich, dass die ja schon abgedeckt sind ^^

Edit:
Zwar funktioniert der Algorithmus wunderbar, ist er doch leider viel zu langsam um ihn sinnvoll einzusetzen. Bei einem 4x4 Feld wird schon gerne mal ein zwei Minuten gerechnet bis alle Wörter gelistet werden. Aber ich habe diesen interessanten Thread auf Stackoverflow gefunden: http://stackoverflow.com/questions/7...-boggle-solver
Dort werden solche Puzzle in wenigen Millisekunden gelöst. Umgesetzt wird das ähnlich wie hier, nur als Datenstruktur wird ein Buchstabenbaum.

[Ineluki]

Du koenntest natuerlich auch den umgekehrten Weg gehen ...
1. Du generierst dir eine Liste mit n Woertern aus dem Woerterbuch, die du verstecken willst.
2. Du verteilst die Buchstaben der n Woerter regelkonform in deiner Matrix
3. Du füllst so mit Fremdbuchstaben auf, dass keine neuen Woerter entstehen.

Damit hast du eine wohl definierte Anzahl an Woertern und deine Ueberpruefung sollte schneller gehen, da du weniger zu pruefen hast.

[FF]

Genau wie Luki es vorschlägt hätte ich es auch gemacht.

[Teflo]

Hmmm, ja, das ist dann eher die Version von Kreuzworträtseln wie man sie aus der Zeitung kennt, nur kruez und quer. Was mir dabei wichtig ist, ist dass möglichst jedes Feld mehrfach einsetzbar ist für verschiedene Wörter. Aber ich hab noch keine gute Idee, wie ich am besten die Buchstaben dafür positioniere.

ABER!
Ich hab in den Algorithmus jetzt einen Trie verwendet. Als erstes schaut er sich an, welche Buchstaben in dem Puzzle vorhanden sind und filtert demnach das Wörterbuch nach möglichen Wörtern. Wobei das Wörterbuch auch schon gefiltert ist, je nachdem wieviele Buchstaben in das Puzzle passen, hier also Wörter mit max. 16 Buchstaben.
Von da an kann man mit einem Buchstaben anfangen und im Trie nachschlagen, ob es zu diesem Buchstaben Kinder im Baum gibt (es also Wörter gibt, die mit diesem Buchstaben anfangen). Dann wird genau nach dem Algorithmus aus dem vorherigen Post durch das Feld gegangen, und geht immer tiefer in den Baum. Sobald es für einen Knoten keine passenden Kinder mehr gibt, kann direkt abgeborchen werden, weil es kein Wort mit dieser Buchstabenreihenfolge gibt.
Jetzt ist es so schnell, dass ich ein 4x4 Puzzle mit mindestens 100 Wörtern darin in weniger als einer Sekunde generieren kann
Es wird einfach so oft ein neues Feld zusammengewürfelt, bis eins rauskommt mit über 100 Wörtern. Das kann natürlich auch mehrere Versuche brauchen, aber bei der Geschwindigkeit ist das kein Problem mehr.

Also vielen lieben Dank, damit kann ich morgen zum Gamejam ein tatsächlich spielbares Ding abgeben! /o/

Edit: Habs soweit recht spielbar http://www.multimediaxis.de/threads/...=1#post3082734