Wordament Wortfeld generieren

[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