C# Algorithmus für Kombinationen?

[cfHxqA]

Hallo, ich habe ein Spielfeld was 8x8 Felder ist. Es geht darum, immer 3-Felder oder mehr, der gleichen Zahlenfolge zu verbinden. Die Zahlenfolgen liegen nicht immer genau nebeneinander - somit muss die jeweilige Zahl von Links nach Rechts, Oben oder Unten verschoben werden.

Ein Beispiel, vom Spielfeld:

Ein Beispiel einer Kombination, wenn erstere ausgelöst wird, wird zweite (Rechts) im Anschluss ausgelöst:


Die Zahlen sind immer gleich, minimal 1 und maximal 7. Das Kombinieren ist nicht mein eigentliches Problem. Sobald eine Kombination besteht, werden diese auch entfernt und es "fallen" neue Zahlen von unten. Es besteht somit die Möglichkeit mit einer Kombination gleich mehrere Auszulösen, durch das "fallen" der Zahlen.

Die Zahlen, die nachkommen, sind irrelevant. Es geht nur um die im Moment bestehenden Zahlen.

Gibt es einen möglicherweise einen Algorithmus bzw. hat jemand eine Idee, wie sich solch eine Kombinationsmöglichkeit am besten bewältigen lässt?

 

[X__]

Per Rekursion vielleicht ?
Als Parameter immer die veränderte Matrix übergeben und den Erfolg zurückmelden.
Maximale Rekursionstiefe nicht vergessen.

 

[benneq]

Ich bin mir nicht sicher, ob ich das Spielprinzip verstanden habe :?

Du nimmst die erste Zahl (Index: 0,0) - äußerer Iterator. Eine 7. Jetzt suchst du rund um die 7 nach einer (oder mehreren) weiteren 7 und findest eine (Index 0,1) - innerer Iterator. Jetzt von dort aus wieder dasselbe (dabei wird Index (0,0) ignoriert, weil der schon bearbeitet wurde). Nix gefunden. Also hast du nur 2 Stück: Kein Erfolg.
Dann die zweite Zahl (Index: 0,1) - äußerer Iterator. Der würde jetzt Index (0,0) finden. Und dann dasselbe Ergebnis liefern wie oben.
Dann die dritte Zahl (Index: 0,3) - äußerer Iterator. Eine 3. Aller Felder um diesen Index absuchen. Keine weitere 3 gefunden. Also weiter mit dem nächsten Index. Usw. ...
Bei Index (0,7) - äußerer Iterator - hast du dann die 5. Alle umliegenden Felder durchsuchen: Noch eine 5 gefunden (Index: 1,6) - innerer Iterator. Von dort wieder alle umliegenden Felder durchsuchen. Wieder was gefunden: Index (2,7) - innerer Iterator. Von dort aus weiter suchen. Index (3,7) gefunden - innerer Iterator. Von dort aus weitersuchen. Nix gefunden. Aber 4 Treffer am Stück im inneren Iterator. Also Erfolg.

Das lässt sich dann noch optimieren, indem man ein paar Felder auslassen kann, die man schon bearbeitet hat.

Ob iterativ oder rekursiv ist auch relativ egal. Geht beides.

 

[cfHxqA]

Das Spielprinzip ist wie folgt: Du kannst nur die Zahlen in der Horizontalen oder Vertikalen verbinden. Das heißt, Du musst mindestens 3 oder mehr Zahlen, der gleichen Zahlen in einer Folge bilden.

Das finden der möglichen Kombinationen ist nicht das Problem. Ich suche nach einem Weg, aus den vielen Kombinationsmöglichkeiten, die Kombination zu finden - welche zugleich mehrere auslöst, wenn diese ausgelöst wird. Siehe zweites Bild.

Im Fall das die 2 nach Oben geschoben wird, werden die 3x2 in Folge verbunden und entfernt. Daraufhin fällt die 5 von oben hinunter und werden ebenso entfernt, weil es ja eine gültige Kombination ist.

Per Rekursion vielleicht ?
Als Parameter immer die veränderte Matrix übergeben und den Erfolg zurückmelden.
Maximale Rekursionstiefe nicht vergessen.

Danke! Etwas anderes wird mir wohl nicht übrig bleiben. Also werde ich die Möglichen Kombinationen durchspielen und sehen, wie sich die jeweiligen Kombinationen verhalten und mit sich weitere Kombinationen auslösen.

 

[benneq]

Hmm.. also irgendwie ein bisschen wie Tetris oder Candy Crush?

 

[cfHxqA]

Eine Mischung aus beidem!

 

[TopperHarley87]

Klingt für mich stark nach Puyo Puyo oder Doktor Mario...

Ich würde es wie folgt machen:

Hauptschleife (z.B. Endlosschleife):
1. Suche alle Kombinationen und lasse obenliegende Felder nachrutschen (per Schleife realisieren)
2. Hauptschleife verlassen wenn keine weiteren Kombinationen gefunden wurden

 

[cfHxqA]

Die Zahlen "fallen" erst nach, wenn eine Kombination gelöst wurde. Solang ist das Spielfeld auch komplett gefüllt. Das wichtige sind eigentlich die bestehenden Felder und die möglichen Kombination mit den möglichen Kettenreaktionen.

 

[benneq]

Die einfachste (und möglicherweise einzige?!) Lösung lautet: Alle Kombinationen ausprobieren und dann das beste Ergebnis auswählen.

Auf den ersten Blick sehe ich jetzt keine Möglichkeit, wie man das mathematisch lösen kann, sodass man nur einen Bruchteil der Kombinationen ausprobieren muss.

Bei 8x8 Feldern ist das aber eh relativ egal. Da sollte jeder aktuelle CPU nur kurz müde lächeln und dann wieder in den idle Tiefschlaf fallen.

 

[X__]

Danke! Etwas anderes wird mir wohl nicht übrig bleiben. Also werde ich die Möglichen Kombinationen durchspielen und sehen, wie sich die jeweiligen Kombinationen verhalten und mit sich weitere Kombinationen auslösen.

Optimierungsvorschlag:
Man könnte den veränderten und damit neu zu überprüfenden Bereich mit übergeben
und sich bei der Folgeprüfung somit auf diesen Bereich beschränken.
Wie "benneque" bereits angemerkt hat ist das bei einer 8x8-Matrix eigentlich nicht notwendig, aber
wenn es dir um die Umsetzung und die Optimierung als solches geht, könnte man da mal drüber nachdenken.
Da könnte man dann auch größere Matrizen testen

 

[SoDaTierchen]

Du kannst hier mehrere Ansätze verfolgen um das ganze effizienter zu gestalten. Ich habe das Spielprinzip glaube noch nicht ganz verstanden, daher füge ich immer ein paar Annahmen vor den jeweiligen Vorschlag:

Annahme: irrelevant
Optimierung: Auf Rekursion verzichten. Iterationen sind stets resourcenschonender, schneller, weniger problematisch als Rekursionen. Lege alle zu prüfenden Elemente in eine Schlange oder auf einen Stapel und laufe dann los.

Annahme: Eine Kombination darf keine Schleife mit sich selbst bilden
Optimierung: zum Prüfen einer Kombination quasi ein "Spiegelbrett" erschaffen, welches einfach nur markiert, ob ein Element schon verglichen wurde. So kannst du die benötigten Vergleiche reduzieren und Endlosschleifen vermeiden.

Annahme: Gleiche Folgen müssen mindestens eine Überschneidung haben, Folgen haben eine eindeutige Reihenfolge.
Optimierung: Weitere Folgen kann man über pattern matching finden - so sparst du dir bereits gelöste Vergleiche. Beispiel: Deine Folge ist 2-5-3, dein Pfad zeigt 2-5: Dann musst du jetzt nur noch nach einer angrenzenden 3 suchen, nicht mehr die ganze Folge vergleichen.
Weitere Optimierung: Auf demselben Weg kannst du auch mögliche Ketten finden. Folge Pfaden und wenn es eine Abzweigung mit mehreren gleichen Elementen gibt, dann ist der Pfad vielversprechend.

Annahme: Es gibt eine "beste Folge" und es gilt, nur diese beste Folge zu finden ODER es gibt Einschränkungen für Folgen
Optimierung: Bei der Betrachtung des Feldes mit Pfaden können wenig erfolgversprechende Pfade direkt ignoriert werden. z.B.: Es soll eine möglichst kurze Folge mit möglichst vielen Nebenfolgen gefunden werden. Du findest bereits eine Folge, die 3 lang ist und 2 Zweige hat. Dann brauchst du eine Folge, die für das zweite Element keine 2 Wege aufzeigt, gar nicht mehr beachten - denn diese Folge ist entweder länger als 3 oder höchstens genauso gut wie die bereits gefundene. Speziell dieser Punkt, also Folgen frühzeitig als untauglich zu markieren, dürfte die stärkste aller Optimierungen sein.


Und noch ein paar Fragen:
- In deinem Beispiel überschneiden sich die Folgen. Ist das unbegrenzt erlaubt? Dann müsste wohl noch definiert sein, ob eine möglichst kurze oder möglichst lange Folge gesucht ist. Denn du kannst die gefundenen Folgen dadurch beliebig "verlängern", dass du nicht bei der 5 anfängst, sondern deine Folge als 77351675252 definierst, auch wenn die erste Abzweigung bei der ersten 2 stattfindet.
- Du hast im Beispiel 5252 die hinteren 3 Elemente in einem Viereck angeordnet. Sind das 2 Lösungen? Also ausgehend von der ersten 5 oben rechts die beiden Wege: runter, runter, links und runter, links, runter. Wenn das erlaubt ist, könnten solche Vierecke die Lösungsmenge erheblich vergrößern, gerade wenn es an längere Kombinationen geht.

 

[benneq]

@SoDaTierchen Deine Annahmen zur Rekursion sind Unsinn. Das hängt maßgeblich von der verwendeten Programmiersprache (bzw. eher von der ausführenden Umgebung) ab. In den üblichen C-artigen Sprachen wie Java, Python, Ruby stimmt das natürlich. Da ist Rekursion gefährlich. Aber z.B. in Haskell gibt's nicht besseres.

Und dann kommt natürlich noch dazu wie der Programmierer tickt. Ich bin da auch eher pro-iterativ, weil ich sowas ohne nachzudenken umsetzen und verstehen kann. Aber anderen geht's da genau umgekehrt (vielleicht als Kind zu oft vom Wickeltisch gefallen oder so? ).

 

[SoDaTierchen]

@benneque: Was du meinst ist nicht die Programiersprache, sondern der Compiler. Iteration braucht pro Durchlauf einen Vergleichssprung (Schleife), eine Load-Operation (neues Element anfassen), eine Store-Operation (angefasstes Element aus den Elementen entfernen) und das war es. Eine Rekursion braucht pro Durchlauf mindestens einen Sprung, 2 Store-Operationen (Befehls- und Speicher-Zeiger), 2 Load-Operationen (Befehls- und Speicher-Zeiger) und dazu irgendwann den Rücksprung. Technisch ist die Rekursion damit definitiv der Iteration unterlegen.

Es gibt natürlich durchaus Algorithmen, in denen die Performance nicht kritisch und die Rekursionstiefe überschaubar ist, sodass Rekursion sich einfach viel angenehmer programmieren lässt. Auch mag manch ein Programmierer lieber Rekursionen als Iterationen. Und du hast Sprachen wie Haskell, in denen Rekursionen quasi-forciert werden und Iterationen sehr unübersichtlich sind. Das sind aber Präferenzen, die sich aus Programmiersprache und Programmierer ergeben.

Bitte versteh mich nicht falsch, ich verteufle keine Rekursionen. Ich benutze diese selbst manchmal, weil es einfach Probleme gibt, die sich damit schnell und ohne großes Denken lösen lassen. Aber es wurde explizit nach Optimierungen gefragt (jedenfalls habe ich es so verstanden), auf Rekursion zu verzichten kann in diesem Fall eine spürbare Optimierung sein - deshalb ist Rekursion nicht verkehrt. Nur eben langsamer.

 

[benneq]

Ich schrieb doch in Klammern "bzw. eher die ausführende Umgebung". Viele dieser Sprachen werden ja nur interpretiert. Oder es gibt nur einen intermediate Compiler (ja, Compiler ist Compiler).
Und dann kommt es trotzdem auf die ausführende Umgebung an, wie dieser Code interpretiert wird. Und speziell die Laufzeitumgebungen der funktionalen Sprachen sind tausendfach schneller bei Rekursion als z.B. die JVM - auch wenn du mit Scala arbeitest und/oder dein Java Code ausschließlich aus Lambdas besteht.

Genau so kriegst du in der JVM durch Rekursion irgendwann eine Exception, weil der Stack überläuft. Ähnliches Programm in Scheme oder Haskell? Kein Problem, der Stack wird komplett anders benutzt und kann dadurch unendlich lange Rekursionen problemlos ausführen.
In Java müsste man dafür dann den Code iterativ umbauen. Dafür hast du in Scheme und Haskell den Nachteil, wenn du Schleifen benutzt. Total langsam und exorbitanter Speicherverbrauch - und das im Vergleich zu einem Programm in der JVM. Das muss man erst mal schaffen.

Daher würde ich sagen: Hängt davon ab, mit was er seinen Code schreibt und ausführt. Vielleicht ist es ja Prolog

EDIT: Der Fachbegriff den ich gesucht habe, heißt: TCO (Tail Call Optimization), dadurch können die funktionalen Sprachen trotz Rekursion so verdammt effizient arbeiten. Dadurch entfällt dann die gesamte übliche Speicherverwaltung.

Also ja, das ist ein Compiler Feature. Aber in den üblichen C / Java / wasauchimmer Compilern ist es nicht vorhanden. Bzw. dort wäre es auch überaus kompliziert anzuwenden. In den meisten funktionalen-programmiersprachen-Compilern ist es eingebaut, weil der Code dort eh so geschrieben wird, dass der Compiler diese Optimierung einfach vornehmen kann.

 

[new Account()]

Kein Problem, der Stack wird komplett anders benutzt und kann dadurch unendlich lange Rekursionen problemlos ausführen.

Halte ich für einen Mythos.

 

[benneq]

Dann erkläre mir wieso ein Java / C Programm mit Rekursion irgendwann abbricht (und dazu noch ewig braucht), aber ich z.B. in Haskell sagen kann: "Gib mir die Fibonacci Zahl für n=10000" und es dauert nur 0,01 Sekunden bis zum Ergebnis.

Gerade noch mal In Java getestet. Mit Rekursion dauert selbst das Berechnen von fib(45) schon mehrere Sekunden. Ab 50 wird es unerträglich. Iterativ kommt man in Java auch auf die Geschwindigkeit, die Haskell mit Rekursion braucht.

Variablen und Code kann man quasi ausschließen als Übeltäter, sind ja nur 2-3 Zeilen. Also bleibt wohl nur der Stack.

 

[new Account()]

Dann erkläre mir wieso ein Java / C Programm mit Rekursion irgendwann abbricht (und dazu noch ewig braucht), aber ich z.B. in Haskell sagen kann: "Gib mir die Fibonacci Zahl für n=10000" und es dauert nur 0,01 Sekunden bis zum Ergebnis.

Weil der Compiler in Haskell die Rekursion wegoptimiert und zu einer iterativen Lösung macht.
Die Java-Entwickler könnten eine solche Optimierung auch problemlos einbauen, wenn sie wollten. (Machen sie aber nicht, da das in der Realität praktisch nie vorkommt und zudem i.d.R. vom Programmierer selbst einfach lösbar ist. Weiterhin wird das Debugging erschwert.)

aber das mal beiseite gelassen: n = 10000 ist immer noch nicht unendlich lange…

Ergänzung (24. September 2018)

Für C++: kompilier mal mit -O3 ...

 

[SoDaTierchen]

Das Thema driftet ein wenig ab

 

[cfHxqA]

Ich bedanke mich herzlichst für die zahlreichen Anstöße und die daraus unzähligen Ideen, welche ich daraus entwickeln konnte!Ich musste es teils mit Iteration sowie Rekursionen umsetzen, weil es an manchen stellen einfach nicht anders funktionierte. Nach zahlreichen Stunden des Kopfzerbrechens, funktioniert alles, wie gewollt und weitaus besser, als zuvor gedacht.

Der Sinn und zweck dahinter war oder das, was mich bewegt hat dazu: Einen Weg zu finden, einen möglichst großen Effekt zu erzielen mit den möglichen Kombinationsvielfalten.

Das komplexe war oder ist für mich gewesen, dass die Steine aus jeglichen Richtungen kombiniert werden können. Aber immer mindestens 3-Steine in der Vertikalen oder Horizontalen ergeben müssen. Somit kann also ein Stein oben nur ein Feld Oben unter Unten liegen, hinter oder auch davor zwei-Steine entfernt.

Nachdem ich die zahlreichen Kombinationen gefunden habe, konnte ich zugleich anhand der bestehenden Matrix jede Kombination ausprobieren und somit einen Zug simulieren. Mit jedem Zug wird natürlich auch alles wieder gewürfelt.
Eines der weiteren Probleme war natürlich gewesen, dass die Steine, die ich kombiniert habe, entfernt werden müssen und natürlich die darüberliegenden einen Stein nach unten rutschen müssen. Dazu habe ich die Steine, welche ich habe ge-nullt und diese Nullen solang nach oben geschoben, bis der Anfang der Matrix begonnen hat. Somit war auch das erledigt gewesen.

Im ganzen erzielt es nun seinen Sinn und zweck. Ich kann in etwa berechnen, wie viele Kombinationen mit einer Kombination ausgelöst werden, wie viele Steine ich verbinde und kann das ganze so oft wiederholen, bis keine Kombinationen mehr möglich sind bzw. neue Steine bereitstehen.