Boggle
Übersicht
BlitzBasic Allgemein
|
SpionAtomBetreff: Boggle |
 Di, Jun 07, 2005 13:24Antworten mit Zitat 
|
|---|---|---|
|
Hi @ all!
Nach einem halben Jahr hier im Forum, hier meine erste Frage: 
Ich suche verschiedene Ansätze für das Spiel Boggle. Was Boggle ist? Boggle ist ein Wort-Such-Spiel. Dabei werden Würfel mit unterschiedlichen Buchstaben drauf in eine 4x4-Form gelegt. Dabei ergibt sich beispielsweise dieses Muster: HLOT LAQL NBEK SSPI Nun muss man aus diesem Buchstabensalat Wörter finden( mind. 3 Buchstaben lang, für eine Wörterschlange darf man jeden Würfel nur einmal verwenden). Zum Beispiel findet man Spiel, wenn man unten mit dem zweiten 'S' anfängt. Die Wortkette darf auch diagonal verlaufen und darf sogar gekreuzt werden, wie bei 'Hallo'(oben links angefangen). Nun habe ich mir schon einige Gedanken darüber gemacht. Ich habe dieses Buchstaben-Feld und eine Liste mit Wörtern. Was ist da sinnvoller? Nehme ich die Wörterliste und schaue, ob Wörter daraus im Buchstabensalat zu finden sind, oder nehme ich den Salat und schaue, ob sich daraus Wörter ergeben? Wie durchsuche ich das Buchstabenfeld? (Soll ich das mit Graphenstruktur und traversieren machen?) Fragen über Fragen. Über Vorschläge wäre ich dankbar. 
|
||
- Zuletzt bearbeitet von SpionAtom am Di, Jun 07, 2005 15:22, insgesamt einmal bearbeitet
Dreamora |
Di, Jun 07, 2005 13:27 Antworten mit Zitat
|
|
|---|---|---|
|
Worte suchen:
Rekursiv die Positionen durchgehen und schauen ob es mit nachbaren (rekursiv) eine Wortmöglichkeit gibt. Wenn nicht dann kann die Rekursion dieses Feldes abgebrochen werden. Dazu brauchst du eine alphabethisch sortierte Wortliste, damit du möglichst schnell feststellen kannst ob ein Wort bis zum aktuellen Buchstaben vorkommen könnte. |
||
| Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen. | ||
|
|
SpionAtom |
Di, Jun 07, 2005 13:30 Antworten mit Zitat
|
|---|---|---|
|
Danke für die schnelle Antwort.
Sowas hab ich auch schon überlegt. Das ist also die Graphen-traversierungs-methode, wie ich sie im Informatik Lk kennengelernt habe. Gibt es dazu noch andere Meinungen? |
||
|
stfighter01 |
Di, Jun 07, 2005 14:28 Antworten mit Zitat
|
|---|---|---|
|
wie dreamora gesagt hat.
damit wirst du hausnummer auf ca 100 vergleiche mit der mit der wortbibliothek kommen. wenn du alle worte durchgehst vermutlich auf n paar zigtausend. mfg stf |
||
| Denken hilft! | ||
Dreamora |
Di, Jun 07, 2005 14:43 Antworten mit Zitat
|
|
|---|---|---|
|
Ich würde es nicht als Graphentraversierung bezeichnen, denn dieser Typus von Algorithmus ist für Distanzberechnungen erdacht.
Es ist lediglich Rekursion. (wie sie Tiefen- und Breitensuche aus der Graphentraversierung auch verwenden, was wohl zum falschen Rückschluss bezüglich des Namens geführt hat). Allerdings wäre es vielleicht nicht schlecht zu warnen, dass Aufgrund der Möglichkeiten auch zurück und über Kreuz zu gehen eine sehr grosse Rekursionstiefe entstehen kann, die Berechnung bei einem "zu guten Feld" also "ewig" dauern könnte, was dann noch verschlimmert wird durch die Grösse des Wörterbuches bei einer ungeschickten Wörterbuch-Suchstruktur (wenn du zb über lineare oder Interpolationssuche gehst - Es gibt dafür spezielle Baumstrukturen wie AVL Bäume und andere) |
||
| Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen. | ||
Klaas |
Di, Jun 07, 2005 14:48 Antworten mit Zitat
|
|
|---|---|---|
|
Zitat: die Berechnung bei einem "zu guten Feld" also "ewig" dauern könnte
Nö, spätestens wenn im Wörterbuch ab der aktuellen Position nix mehr zu holen ist, ist schluss. Da auch umfangreiche Wörterbücher noch recht überschaubar sind wird das nicht so sehr lange dauern. |
||
Dreamora |
Di, Jun 07, 2005 14:53 Antworten mit Zitat
|
|
|---|---|---|
|
Dachte ich auch bis ich das erste Mal das Springerproblem programmieren musste.
Nur läuft Rekursion jedes Feld unzählige Male an, so das es sich im exponentiellen Bereich bewegt und nicht mehr potentiel ... |
||
| Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen. | ||
|
|
SpionAtom |
Di, Jun 07, 2005 15:21 Antworten mit Zitat
|
|---|---|---|
|
Spätestens bei 16 Buchstaben ist ja Schluss.
Siehe nochmals 1. Beitrag. |
||
Dreamora |
Di, Jun 07, 2005 15:37 Antworten mit Zitat
|
|
|---|---|---|
|
Das ist klar
Aber du musst von jedem der 16 Buchstaben aus jeden der restlichen 15 Buchstaben besuchen und zwar in jeder möglichen Permutation ausser du kannst die bereits vorhandene Kombination vorher schon als Wortmöglichkeit ausschliessen. Naja mal schauen wenn du es lauffähig hast 
|
||
| Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen. | ||
Übersicht
BlitzBasic Allgemein
Powered by phpBB © 2001 - 2006, phpBB Group