Zusammenhängende Blöcke bei x-gewinnt erkennen?

berndoa

Top Contributor
Hallo,
ich will mir etwas basteln das am Ende für mich ein Spiel von selbst spielt (um nicht allzu sehr grindne zu müssen).

Die Situation:
Ich habe ein Spielfeld mit 8x8 Feldern, wobei jedes Feld eine von 5 bestimmten Farben kann oder etwas Anderes (Alles was keine der 5 farben ist, ist im späteren Verlauf unwichtig).
Mit Farberkennung und Robot kann ich dadraus vermutlich eine Matrix/ 2 dimensionales Array bauen der Art
(1,1,2)
(3,1,2)
(1,1,3)

(nehmen wir einfahc mal an das Feld wäre nur 3x3 und es gäbe die Farben 1-3).

Wenn man sich das optisch vorstellt, gibt es hier eine zusammenhängende gruppen an 1sen der länge 5, eine gruppe an 2en der länge 2.

die einzelnen 3en jucken nicht, eine gruppe ist imme rnur 2 ode rmehr zusammenhängende elemente.

jedenfalls gegeben so eine oder ähnliche matrix, dann will ich irgendwie rausfinden welche Gruppen es gibt, welche farbe sie jeweils haben, wie lang sie sind (also wie viele felder jeweils bedecken) und wo sie liegen.

damit ich dann später meinem ürogramm sagen kann, es soll im obigen beispiel die größte gruppe an 1en finden und draufklicken.
zur vereinfachung sagen wir mal, eine gruppe wird angeklickt indem ihr am weitesten oben links gelegenes feld angeklickt wird.


So oder so muss ich aus einer matrix die besagten infos über die vorkommenden gruppen ablesen.

gibts da irgendeine gute vorgehensweise wie man das machen kann? :)

Ist so ähnlich wie beim 4gewinnt die senkrechtne und waagrechten reihen zu erkennen, nur können die bei mir beliebig lang sein und auch gekrümmt sein bzw. in allen formen vorkommen.

es kann auch sowas wie
(1,1,2)
(1,1,3)
(3,1,2)
geben.
Also wie die felder irgendwie zusammenhängen, ist sehr beliebig.
 

KonradN

Super-Moderator
Mitarbeiter
Was hast Du Dir denn da schon überlegt?

Im Augenblick sehe ich da ehrlich gesagt kein Problem:
a) Du brauchst ein gleich großes 2D-Array in dem Du Dir nur merkst, was Du alles schon besucht hast.
b) Dann gehst Du der Reihe nach alle Felder durch: Wenn dieses Feld noch nicht besucht wurde und der Inhalt interessant ist, dann fängst Du da an zu zählen mit Zähler = 0.

Zählen bedeutet:
  • Du markierst das Feld als besucht.
  • Du erhöhst den Zähler um 1.
  • Du schaust der Reihe nach alle Nachbarn an und prüfst: Wurde das Feld bereits besucht? Ist es dazu zu zählen? Wenn ja, dann zählst Du dieses Feld.

Man erkennt hier: Das ist also schon ein einfacher, rekursiver Algorithmus. Da jedes Feld nur einmal betrachtet werden muss, ist es relativ schnell. Ein Feld hat maximal 4 Nachbarn, daher schätze ich die Laufzeit auf ein 4n und somit auf O(n).
 

berndoa

Top Contributor
Hm, müsste ich da irgendwie eine rekursive Methode oder sowas benutzen um da so eine Gruppe zu finden?
Weil ich ja erst die Nachbarn abchecken muss. Und dann ggbfls. die Nachbarn vom Nachbarn usw.
So wie bei Tiefensuche oder sowas,
 

KonradN

Super-Moderator
Mitarbeiter
Hm, müsste ich da irgendwie eine rekursive Methode oder sowas benutzen um da so eine Gruppe zu finden?
Man erkennt hier: Das ist also schon ein einfacher, rekursiver Algorithmus.
Da man generell jeden rekursiven Algorithmus in einen iterativen Algorithmus umwandeln kann, ist es natürlich kein muss, aber ich denke, dass der Algorithmus, so wie ich diesen beschrieben habe, mit am einfachsten so umzusetzen sein könnte.
 

httpdigest

Top Contributor
Jupp, und das Spiel ist bestimmt "Bejeweled" oder ein Ableger davon. :)
Mir fehlt hier allerdings nur noch die Frage, wie man erkennt, ob bei einer Bewegung eines Steins dann ein solches zusammenhängendes Muster zustandekommt. Also 100%ig passt es noch nicht, aber kommt ja vielleicht noch. :)
 

berndoa

Top Contributor
Jupp, und das Spiel ist bestimmt "Bejeweled" oder ein Ableger davon. :)
ein Flashspiel namens "dangerous adventure" um genau zu sein.
Prinzip ist sehr ähnlich, nur dass man nicht eine vertauschung vornimmt um eine reihe zu schaffen sondern auf einem gegebenen spielfeld die gruppen mit den meisten steinen anklickt.
Aber ja, das prinzip ist sehr ähnlich :)
 

httpdigest

Top Contributor
es soll einfach die größte zusammenhängende gruppe an steinen auf dem gegebenen spielfeld gefunden und angeklickt werden.
Interessant. Ist dann dort auch der Mechanismus so, dass die durch das Anklicken verbundenen Steine gelöscht/entfernt und obere nach unten nachrutschen, mit dem Ziel, dann sogar im Idealfall durch geschicktes Wählen der angeklickten Reihe sogar noch größere zusammenhängende Reihen zu schaffen/generieren? Bzw.: Muss man immer nur die längste Reihe anklicken oder kann nicht strategisch eine kürzere anklicken, weil sich durch die Steinverschiebung anschließend eine größere Reihe ergibt?
Genau so was hatte ich mal für meinen Bejeweled Bot programmiert und damit halte ich aktuell auf einer Seite seit glaube 2005 den Rekord. :D
 

berndoa

Top Contributor
Interessant. Ist dann dort auch der Mechanismus so, dass die durch das Anklicken verbundenen Steine gelöscht/entfernt und obere nach unten nachrutschen, mit dem Ziel, dann sogar im Idealfall durch geschicktes Wählen der angeklickten Reihe sogar noch größere zusammenhängende Reihen zu schaffen/generieren? Bzw.: Muss man immer nur die längste Reihe anklicken oder kann nicht strategisch eine kürzere anklicken, weil sich durch die Steinverschiebung anschließend eine größere Reihe ergibt?
Genau so was hatte ich mal für meinen Bejeweled Bot programmiert und damit halte ich aktuell auf einer Seite seit glaube 2005 den Rekord. :D
kla, wenn eine steingruppe verschwindet rutschen die anderen steine nach unten (wobei da nicht aufgefüllt wird, da sind dann halt oben entsprechend hohlräume).
man kann insgesamt 4 mal eine gruppe auf einem feld wegklicken bevor die "runde" vorbei ist und ein neues spielfeld geladen wird.
Hier direkt das gameplay zu sehen:

es werden 4 mal ne steinegruppe weggeklickt, bevor die nächste runde losgeht.


So smart dass der bot irgendwie vorplant a la "wenn wenn ich die gruppe an gelben steienn wegklicke, rutschen die 2 blaugrupen zusammen und hilden eine sehr große gruppe" so schlau muss er gar nicht sein.

einfach nur die größte gruppe auf dem aktuellen feld anklicken reicht schon, damit sammelt er shcon genug punkte für seine grindingzwecke. :)

Vermutlich könnte man einen bot bauen, der so schlau ist auszuwerten wie das spielfeld nach dem entfernen einer bestimmten gruppe aussieht und was daher der klügste zug in vorbereitung von klick2 ist.
 

httpdigest

Top Contributor
Vermutlich könnte man einen bot bauen, der so schlau ist auszuwerten wie das spielfeld nach dem entfernen einer bestimmten gruppe aussieht und was daher der klügste zug in vorbereitung von klick2 ist.
Absolut. Wenn du sowieso nur 4 Züge mit einem gegebenen Feld hast, und noch nicht einmal neue Steine (die vorher nicht da waren) nachrutschen, dann ist das super einfach. Da kannst du dann einfach den kompletten Spielbaum aufbauen und die Bewertungen für alle Zugkombinationen errechnen.
 

berndoa

Top Contributor
Naja, für meine Grindignzwecke jetzt ist es mir shcon kompliziert genug mal einenpassenden Bot für die erste Stufe an Intelligenz zu bauen :)
 

berndoa

Top Contributor
Ich habe mittlerweile, nach viel Umstand mit den verschiedenen skalierten und unskalierten koordinatesystemen, nun was zusammengebaut was soweit funktioniert :cool:


Java:
package a;

import java.awt.Color;
import java.awt.Robot;
import java.awt.event.InputEvent;

public class Fight {
    Robot bot;

    public Fight(Robot bot) {
        try {
            this.bot=bot;
        } catch (Exception e) {
        }

        while (fightStillGoing()) {
            for (int i = 0; i < 4; i++) {
                if (!(fightStillGoing())) {
                    //System.out.println("break!");
                    break;
                }
                new Feld(bot);
                try {
                    if(i<3) {Thread.sleep(100);}
                    else {
                    Thread.sleep(3700);}
                } catch (Exception e) {
                }
                // sleep
            }
            // different sleep
            // isFightOver?
            try {
                Thread.sleep(3000);
            } catch (Exception e) {
            }
        }
        //fight over, wait for victory screen to finish
        
        try {
            Thread.sleep(500);
            //click victory screen away
            click(1040,637);
            Thread.sleep(500);
            //click victory screen away
            click(1040,637);
        } catch (Exception e) {
        }
        
        
        try {
            Thread.sleep(1500);
        } catch (Exception e) {
        }
        

    }

    public boolean fightStillGoing() {


        Color color = bot.getPixelColor(1220, 802);

        int g = color.getGreen();
        int r = color.getRed();
        int b = color.getBlue();
        //return false;
        return (g > 215 && b > 140 && r > 245);
    }

    public void click(int x, int y) {

        bot.mouseMove(x, y); // ggbfls. mit custom funktion ersetzen
        bot.delay(100);
        bot.mousePress(InputEvent.BUTTON1_DOWN_MASK);
        bot.delay(100);
        bot.mouseRelease(InputEvent.BUTTON1_DOWN_MASK);

    }
}

sowie

Code:
package a;

import java.awt.Color;
import java.awt.Robot;
import java.awt.event.InputEvent;

public class Feld {
    Robot bot;

    int width = 8;
    int height = 8;

    int topleftx = 668;
    int toplefty = 267;
    int bottomrightx = 1248;
    int bottomrighty = 844;
    

    int stopleftx = (int)(668/1.25);
    int stoplefty = (int)(267/1.25);
    int sbottomrightx = (int)(1248/1.25);
    int sbottomrighty = (int)(844/1.25);

    int[][] feld = new int[height][width];

    boolean[][] unusedFeld = new boolean[height][width];
    Group maxGroup;
    Group dummyGroup;

    public Feld(Robot bot) {
        this.bot = bot;
        initFeld();
        // init unusedFeld
        for (int i = 0; i < unusedFeld.length; i++) {
            for (int j = 0; j < unusedFeld[i].length; j++) {
                unusedFeld[i][j] = true;
            }
        }

        //System.out.println("unusedFeld initialized!");
        //printFeld();
        findAndClickMaxGroup();

    }

    public void findAndClickMaxGroup() {
        //System.out.println("findAndClickMaxGroup started!");
        dummyGroup = new Group(0, 0, feld[0][0]);
        builtGroup(0, 0);
        maxGroup = dummyGroup;
        //System.out.println("New found group's info:");
        //dummyGroup.printInfo();
        for (int i = 0; i < feld.length; i++) {
            for (int j = 0; j < feld[i].length; j++) {
                if ((i + j == 0) || (!(unusedFeld[i][j]))) {
                    continue;
                }
                // built dummyGroup and explore its lengths
                dummyGroup = new Group(i, j, feld[i][j]);
                builtGroup(i, j);
                //System.out.println("New found group's info:");
                //dummyGroup.printInfo();
                // change maxGroup if applicable
                if(maxGroup.getFarbe()<=0) {maxGroup=dummyGroup;}
                if ((dummyGroup.getFarbe()>0)&&(dummyGroup.getLength() > maxGroup.getLength())) {
                    //System.out.println("New maxGroup found!");
                    maxGroup = dummyGroup;
                }
                //System.out.println("final maxGroup's info:");
                //maxGroup.printInfo();
            }
        }
        // Click maxGroup's position

        //System.out.println("Now clicking on maxGroup!");
        click(maxGroup.x, maxGroup.y);
    }

    public void click(int Zeile, int Spalte) {

        int x = (int) (stopleftx + (1.0 * Spalte / width) * (sbottomrightx - stopleftx) + 15);
        int y = (int) (stoplefty + (1.0 * Zeile / height) * (sbottomrighty - stoplefty) + 15);
        

        bot.mouseMove(x, y); // ggbfls. mit custom funktion ersetzen
        bot.delay(100);
        bot.mousePress(InputEvent.BUTTON1_DOWN_MASK);
        bot.delay(100);
        bot.mouseRelease(InputEvent.BUTTON1_DOWN_MASK);

    }

    public void builtGroup(int i, int j) {
        if (!(unusedFeld[i][j])) {
            return;
        }
        if (feld[i][j] == dummyGroup.getFarbe()) {
            dummyGroup.add();
            unusedFeld[i][j] = false;
        }
        // feld rechts
        if ((j < width - 1) && (!(unusedFeld[i][j]))) {
            builtGroup(i, j + 1);
        }
        // feld unten
        if ((i < height - 1) && (!(unusedFeld[i][j]))) {
            builtGroup(i + 1, j);
        }
        // feld links
        if ((j > 0) && (!(unusedFeld[i][j]))) {
            builtGroup(i, j - 1);
        }
    }

    // ****Feldkram****

    public void initFeld() {
        for (int x = 0; x < height; x++) {
            for (int y = 0; y < width; y++) {
                feld[x][y] = getElement(x, y);
            }
        }

    }

    public int getElement(int Zeile, int Spalte) {
        /*
         * int x = topleftx + 15 + Spalte * deltax; int y = toplefty + 15 + Zeile *
         * deltay;
         */

        int x = (int) (stopleftx + (1.0 * Spalte / width) * (sbottomrightx - stopleftx) + 15);
        int y = (int) (stoplefty + (1.0 * Zeile / height) * (sbottomrighty - stoplefty) + 15);

        return readElement(x, y);
    }

    public void printFeld() {
        System.out.println("***************************");
        for (int i = 0; i < feld.length; i++) {
            for (int j = 0; j < feld[i].length; j++) {
                System.out.print(feld[i][j] + " ");
            }
            System.out.println("");
        }
        System.out.println("***************************");
    }

    public int readElement(int p, int q) {
        //System.out.println("Read element at p,q="+p+","+q+"!");
        // read color at (x,y)=(a,b)
        Color color = bot.getPixelColor(p, q);
        //bot.delay(50);
        //bot.mouseMove(p, q);

        int g = color.getGreen();
        int r = color.getRed();
        int b = color.getBlue();
        // return certain integer based on said color
        // rot
        if (r > 180 && g < 100 && b < 100) {
            return 1;
        }
        // grün
        else if (g > 180 && r < 100 && b < 100) {
            return 2;
        }
        // blau
        else if (b > 180 && r < 120 && g < 120) {
            return 3;
        }
        // gelb
        else if (g > 200 && r > 200 && b < 100) {
            return 4;
        }
        // lila
        else if (r > 150 && b > 200 && g < 100) {
            return 5;
        }
        // sonstiges
        else if (r < 100 && g < 100 && b < 100) {
            return 0;
        }
        return -1;

    }

    class Group {
        int x = 0;
        int y = 0;
        int farbe = 0;
        int length = 0;

        public Group(int x, int y, int farbe) {
            this.x = x;
            this.y = y;
            this.farbe = farbe;
        }

        public void add() {
            length++;
        }

        public int getFarbe() {
            return farbe;
        }

        public int getLength() {
            return length;
        }

        public void printInfo() {
            System.out.println("Group is based at (i,j)=(" + x + "," + y + ") with farbe=" + farbe + " und length="
                    + length + "!");
        }

    }

}


Es ist nicht zwingend shcön, aber funktioniert relativ stabil und tut Alles Nötige :)
 

berndoa

Top Contributor
Nächster Schritt wäre nun wohl, dem Ganzen etwas Intelligenz zu verpassen.
Also bspw. vorzugeben, welche Gegener (farben) in einem bestimmten Kampf vorgehen und nur eine "beste" Steingruppe auszuwählen die den meisten Schaden beim gegener bewirkt.

Damit er nicht beispielsweise eine Steingruppe auswählt, die dem Gegner wegen falscher Farbe gar keinen Schaden zufügt...
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
S Zusammenhängende Comboboxen? Java Basics - Anfänger-Themen 2
missy72 Catch Blöcke zusammenfassen Java Basics - Anfänger-Themen 6
S Array 2x2 Blöcke mit 0 und 1 Java Basics - Anfänger-Themen 10
L Blöcke bei verschachtelten Schleifen Java Basics - Anfänger-Themen 3
T Blöcke für ein Jump and Run Spiel Java Basics - Anfänger-Themen 8
C [Bukkit Plugin] Blöcke eine bestimmte route entlang fliegen Java Basics - Anfänger-Themen 3
W Countdown auf "schwarze Blöcke" Java Basics - Anfänger-Themen 3
G Exceptionfreie Anweisungen in try-catch-Blöcke, Java Basics - Anfänger-Themen 6
E BlockChallenge: Problem beim löschen der Blöcke Java Basics - Anfänger-Themen 3
M Minimax-Algorithmus für Vier gewinnt Java Basics - Anfänger-Themen 11
M GUI für Vier-Gewinnt. Java Basics - Anfänger-Themen 4
M monte carlo Algorithmus für 4 gewinnt Java Basics - Anfänger-Themen 12
J Vier gewinnt in Java,Spieler Konstruktor Java Basics - Anfänger-Themen 8
Kamy Ein einfaches "Vier Gewinnt" Spiel für Anfängerin Java Basics - Anfänger-Themen 51
shiroX Methoden MinMax 4 Gewinnt Java Basics - Anfänger-Themen 2
K Methoden 4 Gewinnt checkDiagonal Methode Java Basics - Anfänger-Themen 10
O Methoden Fehlermeldung(Illegal start of expression) bei 4-Gewinnt-Spiel Java Basics - Anfänger-Themen 5
M Erste Schritte KI für 4 Gewinnt Hilfe! Java Basics - Anfänger-Themen 5
H 3 Gewinnt, Fehler bei Neustart Java Basics - Anfänger-Themen 6
A Tic Tac Toe - Vier Gewinnt Java Basics - Anfänger-Themen 5
L 5 Gewinnt Array[][] probleme Java Basics - Anfänger-Themen 20
B 4 Gewinnt KI? Java Basics - Anfänger-Themen 9
E Weiteres Vier Gewinnt-Spiel Java Basics - Anfänger-Themen 2
J Reset Button im Spiel Vier gewinnt einrichten Java Basics - Anfänger-Themen 8
JFeel-x 4 gewinnt-Versuch + Probleme Java Basics - Anfänger-Themen 2
G boolean Methode Vier gewinnt Java Basics - Anfänger-Themen 6
B Problem mit Drei-Gewinnt-Spiel Java Basics - Anfänger-Themen 24
G Problem mit Array bei einem 4-Gewinnt Spiel Java Basics - Anfänger-Themen 2
A MiniMax- Algorithmus für 4-Gewinnt Java Basics - Anfänger-Themen 3
G Algorithmus im Spiel "vier gewinnt" Java Basics - Anfänger-Themen 3

Ähnliche Java Themen

Neue Themen


Oben