Hallo, kennt jemand das Spiel "Bubble Blast 2" für Smartphones? Auf einem 5x6-Gitter sind verschiedenfarbige "Blasen" angeordnet: http://cdn.famigo.com/application-com.magmamobile.game.BubbleBlast2-screenshot-3 Ziel ist, mit möglichst wenig Berührungen alle Blasen zu zerplatzen. Rote Blasen platzen sofort beim Berühren. Grüne werden erst rot, bei der zweiten Berührung platzen sie. Gelbe Blasen werden grün, usw. (insgesamt drei Berührungen notwendig) Blaue werden gelb, dann grün, ... (insgesamt vier Berührungen) Wenn eine rote Blase platzt, sendet sie in alle vier Richtungen kleine "Bälle" aus: http://fs02.androidpit.info/ass/x74/975774-1286137720572.jpg Sobald diese auf eine andere Blase treffen, ändern Sie deren Farbe bzw. lassen eine rote Blase platzen. (Wie wenn man sie berührt hätte). Dadurch kann es Kettenreaktionen geben. Wenn ein solcher Ball bis zum Spielfeldrand vordringt, verschwindet er. Hier das Spielprinzip als Video: http://youtu.be/rFk3gljwFBw Nun zu meiner Frage: Wie löse ich so ein Level optimal mit dem PC? Iterative Tiefensuche? Ich habe überhaupt keine Ahnung von weiterführender Informatik, kann nur ein bisschen Programmieren. Problem ist halt die immense Anzahl an Möglichkeiten, die man also praktisch nicht zwischenspeichern kann (Breitensuche). Mein erster Ansatz wäre, mit iterativer Tiefensuche erst alle einzelnen Züge durchzuprobieren. Wenn das Level nicht mit einer Berührung gelöst werden kann, nochmal alles durchprobieren, aber immer jeden möglichen zweiten Zug dranhängen, usw. Gibt es bessere Algorithmen dafür oder ist das Problem nicht anders optimal lösbar?
Ich schrieb: > Gibt es bessere Algorithmen dafür oder ist das Problem nicht anders > optimal lösbar? Aus dem Bauch raus, würde ich mal sagen: Nein, da gibt es keinen eleganten Algorithmus dafür. Backtracking darauf ansetzen um zumindest die Probier-Suche organisiert über die Bühne zu bringen.
Karl Heinz Buchegger schrieb: > Backtracking darauf ansetzen um zumindest die Probier-Suche organisiert > über die Bühne zu bringen. Wie meinst du das?
Hast du mal ein Beispiellevel? Oder kann man das aus dem Video nehmen?
(Ich kann gelb und grün (fast) nicht unterscheiden, deswegen ist das mit dem Video etwas schwierig.)
Ich schrieb: > Karl Heinz Buchegger schrieb: >> Backtracking darauf ansetzen um zumindest die Probier-Suche organisiert >> über die Bühne zu bringen. > > Wie meinst du das? Aus der Menge der möglichen Kugeln eine nach der anderen auswählen und einfach ausprobieren was passiert. In dieser Stellung dann wieder alle Möglichkeiten durchprobieren usw. Bis eine maximale Tiefe erreicht ist. Danach den letzten Zug zurücknehmen und in dieser Stellung die nächste möglliche Alternative probieren, sofern noch eine vorhanden ist. Also im Grunde eh das, was du als Tiefensuche genannt hast.
Das gabs, glaube ich, als "Chain Reaction" in den 80igern für den Commodore PET. Schade das das nicht frei runterladbar ist. Ich hasse anmelden bei Google.
troll schrieb: > (Ich kann gelb und grün (fast) nicht unterscheiden, deswegen ist das mit > dem Video etwas schwierig.) Die gelben sind geringfügig kleiner als die grünen. Beispiellevel hab ich leider keine, ich habe das Spiel nur immer bei anderen auf dem Handy gesehen, selten mal gespielt. Das aus dem Video sieht eher schwer aus, aber ist daher hervorragend geeignet. Karl Heinz Buchegger schrieb: > Bis eine maximale Tiefe erreicht ist. Die Aufgabe, die ich mir stelle, ist nicht: Finde eine beliebige Lösung mit maximal X Berührungen. Sondern: Finde die optimale Lösung. Wieviele Berührungen braucht man?
Ich schrieb: > Karl Heinz Buchegger schrieb: >> Bis eine maximale Tiefe erreicht ist. > > Die Aufgabe, die ich mir stelle, ist nicht: Finde eine beliebige Lösung > mit maximal X Berührungen. > Sondern: Finde die optimale Lösung. Wieviele Berührungen braucht man? Weiter laufen lassen, bis alle Möglichkeiten ausgeschöpft sind und davon dann die Beste nehmen. Wobei du den Vorteil ausnutzen kannst, dass du mit jeder Lösung eine maximale Suchtiefe hast, ab der du nicht mehr weitersuchen musst, weil es dann in diesem Teilbaum keine bessere Lösung mehr geben kann. Erinnert mich jetzt vom Vorgehen her ein wenig an die Backtracking Variante, die als 'das Rucksackproblem' in der Algorithmenliteratur bekannt geworden ist. Auch da gehts letzten Endes um die Suche nach einer optimalen Lösung, wobei man nur durch Durchprobieren aller Lösungen zum Ziel kommt.
Ich schrieb: > troll schrieb: >> (Ich kann gelb und grün (fast) nicht unterscheiden, deswegen ist das mit >> dem Video etwas schwierig.) > Die gelben sind geringfügig kleiner als die grünen. Ach ja, richtig. Spiellogik zu implementieren ist ja einfach (gerade erledigt), aber einen (oder gar den besten) Lösungsweg berechnen... Mal sehen...
@TO Wenn du das Problem gelöst hast wäre ich sehr am Quellcode interessiert. Ich habe nämlich gerade ewig lange erfolglos versucht eine Lösung zu finden, aber offensichtlich bin ich zu doof. :-(
troll schrieb: > Spiellogik zu implementieren ist ja einfach (gerade erledigt) Wie ist der Fall geregelt, wenn eine rote Blase von mehreren Seiten gleichzeitig mit den kleinen Bällen bombardiert wird? Einer davon bringt die Blase zum Platzen, während die anderen (zusammen mit den durch das Platzen neu entstehenden Bällen) weiterfliegen. Aber welcher der Bälle tötet die Blase und welche fliegen weiter? Das hängt wohl davon ab, in welcher Reihenfolge die Bälle durch die Software abgearbeitet werden. Weiß da jemand Genaueres?
Du kannst die Tiefensuche zumindest nach $currentBest Schritten abbrechen und einen Schritt weiter zur Seite gehen. Wenn du schon eine Lösung mit 15 Schritten gefunden hast, lohnt es sich nicht nach einer Lösung mit 16 zu suchen. Das Worstcase ändert sich dadurch zwar nicht, aber ich könnte mir vorstellen, das man die durchschnittliche Dauer damit durchaus verbessern könnte.
Verwirrter Anfänger schrieb: > Das Worstcase ändert sich dadurch zwar nicht, aber ich könnte mir > vorstellen, das man die durchschnittliche Dauer damit durchaus > verbessern könnte. Durchaus Auf dem Video sieht man ein 5*6 Spielfeld. d.h. maximal sind 30 Steine im Einsatz, die sich, wenn ich das Video nehme, auch relativ schnell reduzieren. Ich erwarte eigentlich nicht, dass sich da die Rechenzeit extrem hochschaukelt. Also einfach mal: "brute force" und auf sie mit Gebrüll.
Yalu X. schrieb: > Weiß da jemand Genaueres? Bei dem Chain Reaction dass ich kenne, die Kugel die zuerst auftrifft alle anderen fliegen durch. Wenn zwei gleichzeitig drauf treffen, keine Ahnung, jedenfalls nur eine von beiden. Edit: das gleiche Spiel hat meine Gutste auch auf ihrem Android, da wird es genauso gehandhabt, die erste Kugel mahlt zuerst. AFAIK hat man doch pro Level eh nur eine begrenzte Anzahl Berührungen, d.h. du kannst prunen wenn der Suchbaum die Tiefe überschreitet und bei der kleinen Brettgröße hält sich die Laufzeit vermutlich in Grenzen. Edit 2: Ja da oben stehts, "touches left"
Karl Heinz Buchegger schrieb: > Also einfach mal: "brute force" und auf sie mit Gebrüll. Backtracking ist kein brute force... Am wichtigsten wäre die genauen Spielregeln und Abbruchkriterien, eventuell kann man sogar aus der Anzahl der Kugeln abschätzen was die höchste/niedrigste Anzahl Schritte wäre.
also 5*6 ist doch pipifax. Eine Zelle kann 5 Zustände haben. -> 3Bit 10 Zellen pro uint32_t Man braucht also 3*uint32 = 12Byte um den kompletten Zustand eines Spielfeldes zu speichern. Man kann das ganze natürlich noch mehr komprimieren, dann werden die Zugriffe aber immer ineffizienter. (5*6)^5 = 24.300.000 mögliche Kombinationen * 12 Byte = 729.000.000 Byte ~700MB Man kann also einmal berechnete Felder speichern und dazu den optimalen Zug (30 möglichkeiten -> 1 Byte --> zusätzliche 23Mb). Das sollte die Suche nochmals um einiges schneller machen. sollen es größere Felder werden, die absolut nicht mehr zu handlen werden, kann man nach dem Schema sich vielleicht eine Art Endspieldatenbank aufbauen edit: nee - 12Byte sind wirklich das Minimum 30*3/8 = 11,25Byte
Es geht doch noch effizienter, die 3 bit pro Feld werden ja nur zu 5/8 ausgenutzt. (5*6)^5 = 24.300.000 Kombinationen kann man ja einfach durchnummerieren. Nur gibt es eine effiziente Methode aus einer Feldkonfiguration die Nummer zu bilden? um dem Problem zu begegnen könnte man kleine Grüppchen bilden, innerhalb derer man die Kombinationen durchnummeriert. zB je 3 Felder 3^5 = 243 Kombinationen ~ 1Byte -->10Byte für alle. die Auflösung von Feldern -> Byte und Byte -> Feldern ließe sich effizient über kleine LUTs machen
Dein Vorschlag beruht nur auf einem entscheidenden Fehler: 30 Plätze a 5 Möglichkeiten sind nicht 30^5 sondern 5^30. Damit hat sich das Problem alle Zustände speichern zu wollen erstmal erledigt ;)
D. I. schrieb: > Dein Vorschlag beruht nur auf einem entscheidenden Fehler: > > 30 Plätze a 5 Möglichkeiten sind nicht 30^5 sondern 5^30. Ach verdammt, du hast recht. So ein Anfängerfehler. Naja sie Zahlen ändern sich ja nur geringfügig. ;-)
Vlad Tepesch schrieb: > > (5*6)^5 = 24.300.000 mögliche Kombinationen > * 12 Byte = 729.000.000 Byte ~700MB Schon. (Jetzt mal den Rechenfehler weggelassen). Aber die musst du ja nicht alle speichern. Du hast eine Spiefeldsituation die gehst du durch und für jeden Stein probierst du den Zug zu machen. Daraus ergibt sich eine neue Situation. (A) Zum jetzigen Zeitpunkt hast du gerade mal 2 Spielfelder speichern müssen. Jetzt gehts rekursiv rein. Mit der Situation aus (A) probierst du wieder alle möglichen Züge und kriegst jeweils eine neue Situation, die du aber nicht speichern musst. Es wird jeweils nachgesehen, ob damit das 'Problem' bereits gelöst ist oder ob noch eine Rekursion anhegängt werden muss. Zu diesem Zeitpunkt sind erst 3 Spielfelder gespeichert. Und die Rekursion geht maximal bis auf Ebene 30, weil es prinzipiell nicht mehr Steine geben kann. Jedes mal wenn die Rekursion dann wieder zurückkehrt, wird auch wieder ein Spielfeld aufgelöst, ehe es dann in einem anderen Pfad der Möglichkeiten in die Rekursion wieder reingeht. Maximal musst du als 30*3*12 Bytes speichern. 30, weil die Rekursion nicht über mehr als 30 Ebenen gehen kann. 3 weil jeder Stein maximal 3 Zustände annehmen kann. Plus den Weg, den man genommen hat um zur Endstellung zu kommen (zwecks Bewertung der Lösung) Plus dem Zeugs, was für die Rekursion noch notwendig ist. Wenn eine IBM 360 vor 20 Jahren die 8 Damen auf einem Schachbrett anordnen sollte und alle 96 (oder warens 92) möglichen Lösungen in unter 1/10 Sekunde fand, dann wird das doch ein PC von heute in akzeptabler Zeit hinkriegen.
Ich denke bei dem Teil ist das "Schwierigste" es die Einschlagsreihenfolge der Kugeln richtig zu implementieren. Wahrscheinlich tut man sich am einfachsten (wenn auch nicht sehr schnell) einen Zug einfach mit diskreten Zeitschritten zu simulieren (ein Zeitschritt = eine Kugel fliegt ein Feld weiter) sobald ein Zug gemacht wurde.
D. I. schrieb: > Ich denke bei dem Teil ist das "Schwierigste" es die > Einschlagsreihenfolge der Kugeln richtig zu implementieren. Das sehe ich auch so. > Wahrscheinlich tut man sich am einfachsten (wenn auch nicht sehr > schnell) einen Zug einfach mit diskreten Zeitschritten zu simulieren > (ein Zeitschritt = eine Kugel fliegt ein Feld weiter) sobald ein Zug > gemacht wurde. Genau so würde ich das machen oder probieren. Das ganze läuft so lange, bis sich am Spielfeld nichts mehr verändert und man hat das Ergebnis der Auswirkungen des Antippens einer Kugel. Schwierigkeiten bereitet * wenn mehrere Kugeln 'gleichzeitig' ein Feld erreichen auf dem schon eine andere Kugel sitzt. Welcher der Angreifer verschwindet * selber Fall, nur diesmal ohne andere Kugel. Die fliegenden Kugeln müssen über dieses eine Feld sauber drüber kommen ohne das der Rechner die Kugeln 'verliert'. Speziell letzterer Fall würde für mich ein Hinweis sein, dass man zusätzlich zum Spielfeld noch eine Liste mit allen Kugeln, deren Positionen und deren Geschwindigkeiten braucht. So gesehen wird der Speicherverbrauch wieder etwas höher.
Karl Heinz Buchegger schrieb: > Aber die musst du ja nicht alle speichern. Muss man nicht, aber es würde helfen, wenn man auf verschiedenen Wegen zu einer Konfiguration kommt. Dann müsste man nicht den kompletten Baum dahinter nochmal abarbeiten. Über kurz oder lang hätte man das komplette Spiel gelöst, wenn dieser blöde Denkfehler nicht gewesen wäre.
Karl Heinz Buchegger schrieb: > D. I. schrieb: >> Ich denke bei dem Teil ist das "Schwierigste" es die >> Einschlagsreihenfolge der Kugeln richtig zu implementieren. > > Das sehe ich auch so. Also ähhh... entweder ihr denkt alle viel zu kompliziert oder ich habe totalen Müll implementiert (das wird es wohl sein). Die Kugeln/Bälle über das Feld zu schießen ist nun wirklich nicht schwierig, ich habe das rekursiv gemacht. Zumindestens das Feld aus dem Video entspricht (wenn man die richtigen Positionen antippt) genau dem Original. Soll ich das mal hochladen? (Wäre natürlich kein Wunder dass ich keinen Lösungsweg finde wenn schon meine Spiellogik falsch ist...)
troll schrieb: > Die Kugeln/Bälle > über das Feld zu schießen ist nun wirklich nicht schwierig, ich habe das > rekursiv gemacht. die Frage ist halt, was passiert, wenn 2 Kugeln zeitgleich aus verschiedenen Richtungen auf eine rote Blase treffen. welche Kugel durchgeht und welche die Blase zerstört ist "implementation defined" aber essentiell für die optimale Lösung.
Vlad Tepesch schrieb: > die Frage ist halt, was passiert, wenn 2 Kugeln zeitgleich aus > verschiedenen Richtungen auf eine rote Blase treffen. > welche Kugel durchgeht und welche die Blase zerstört ist "implementation > defined" aber essentiell für die optimale Lösung. Da hast du wohl Recht... Dachte ich mir doch dass es nicht so einfach sein kann.
Na ja. soo schwer ist es dann auch wieder nicht. Mal sehen. Da ich ein Faible für so kleine Übungsaufgaben habe und die kleinen grauen Zellen auch wieder mal ein wenig Bewegung brauchen, setz ich mich heut abend vielleicht mal ran. Wenn mein Kopfweh nachlässt.
Karl Heinz Buchegger schrieb: > Na ja. soo schwer ist es dann auch wieder nicht. > > Mal sehen. Da ich ein Faible für so kleine Übungsaufgaben habe und die > kleinen grauen Zellen auch wieder mal ein wenig Bewegung brauchen, setz > ich mich heut abend vielleicht mal ran. Wenn mein Kopfweh nachlässt. Wenn dir langweilig ist hätte ich noch genug "kleine Fingerübungen" übrig ;) Aber meistens macht die dann doch nur Yalu :) (von dem mich mal interessieren würde was der eigtl. im echten Leben macht)
Karl Heinz Buchegger schrieb: > Na ja. soo schwer ist es dann auch wieder nicht. Wie viele 100.000 LOCs hast du im Leben bereits erzeugt? Wie viele 1000 LOCs habe ich bereits erzeugt? Findest du den Unterschied? ;-) Solange das von Vlad Tepesch angesprochene Problem nicht geklärt ist ist es sowieso schwierig das Richtige zu programmieren...
Vlad Tepesch schrieb: > die Frage ist halt, was passiert, wenn 2 Kugeln zeitgleich aus > verschiedenen Richtungen auf eine rote Blase treffen. Soweit ich weiß, verschwinden beide Kugeln, keine kommt weiter. Dafür erzeugt die zerplatzende rote Blase Kugeln in alle vier Richtungen. Zwei Kugeln genau deckungsgleich aufeinander gibt es nicht. Ich werde morgen versuchen, ein Level zu finden, bei dem man das testen kann.
@Ich: Ich habe in einem Youtube-Video (finde es leider nicht mehr) folgende Situation gesehen:
1 | o |
2 | ↓ |
3 | G R ← o |
o = Kugel R = rote Blase G = grüne Blase Beide Kugeln treffen gleichzeitig auf die rote Blase. Diese platzt, und die von rechts kommende Kugel und die durch das Platzen neu erzeugte fliegen deckungsgleich auf die grüne Blase zu. Das kann man daran erkennen, dass diese ebenfalls platzt, wozu sie von mindestens zwei Kugeln getroffen worden sein muss.
dieses Spiel suggeriert einem ja, dass man durch "Logik" weiter kommt.. (ala Sudoku) eigentlich muss man als SPIELER also auch GENAU wissen, wie das funktioniert sonst kann man ja nur durch probieren weiter kommen, solange es keine Anleitung gibt, in der dieses Verhalten beschrieben ist, scheint mir der "Wert" dieses spieles eher in >Mensch ärgere dich nicht< Niveau ...
Robert L. schrieb: > eigentlich muss man als SPIELER also auch GENAU wissen, wie das > funktioniert > sonst kann man ja nur durch probieren weiter kommen, > > solange es keine Anleitung gibt, in der dieses Verhalten beschrieben > ist, scheint mir der "Wert" dieses spieles eher in >Mensch ärgere dich > nicht< Niveau ... Du überdramatisierst.
Robert L. schrieb: > sonst kann man ja nur durch probieren weiter kommen Leren durch ausprobieren... gerade da ist doch der Reiz, das man nicht seitenweise Anleitungen lesen muss sondern einfach drauf los spielt bei solchen "Zeitvertreibern".
Wollte mir das Spiel gerade mal laden um zu prüfen, ob man eventuell auch mehrere schnell hinterinander antippen kann, das würde die Sache noch verkomplizieren. Habe es aber abgebrochen, da das Spiel die Berechtigung fordert die Telefonfunktion zu steuern u.A. die Telefonnummer, ob ein Gespräch läuft und mit welcher Nummer telefoniert wird!??!?
Läubi .. schrieb: > Habe es aber abgebrochen, da das Spiel die Berechtigung fordert die > Telefonfunktion zu steuern u.A. die Telefonnummer, ob ein Gespräch läuft > und mit welcher Nummer telefoniert wird!??!? Meines Erachtens heißt das nicht, dass die App selbstständig telefonieren darf. Sie kann aber die ID des Telefons auslesen, um dich eindeutig zu identifizieren. Oder steht bei dir was anderes als "Telefonstatus lesen und identifizieren"?
nocheinGast schrieb: > Meines Erachtens heißt das nicht, dass die App > selbstständig telefonieren darf Nein, aber sie darf neben der TelefonID halt die Nummer des Gesprächpartners auslesen (+meine eigene) und die Tatsache dass ein Gespräch geführt wird.
Heute habe ich einige Situationen getestet: Es gibt "doppelte Kugeln", also zwei Kugeln, die genau deckungsgleich übereinander fliegen. Ob es auch noch mehr Kugeln auf einmal gibt, ist noch unbekannt. Ergebnisse meiner Tests folgen in Kürze.
@Robert: Ich bin da gar nicht so hinterher, hab nix geheimes auf meinem Telefon, aber für ein Spiel muss man echt nicht solche doch weitreichenden Rechte einfordern oder? Finde ich zumindest übertrieben und die Beschreibung gibt auch nicht her wozu die das benötigen im schlimmsten Fall wird man dann schön mit Werbung zugespammt...
Thread beobachten
Seitenaufteilung abschalten
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.