Einfaches Legespiel: Größe des Spielfeld reduzieren

[Martin]

Hab das folgende Problem schon im Algorithmen-Forum gepostet, da es aber aus dem Bereich der Spieleprogrammierung kommt, kann mir hier vielleicht auch jemand helfen.

Gespielt wird auf einem n*m-Feld, auf das nach bestimmten Regeln verschieden große Spielsteine (im einfachtsen Fall haben die Größe 1*1) gelegt werden. Nun möchte ich einen einfachen Algorithmus schreiben um zu erkennen, dass auf einem Spielfeld alles bis auf eine k*j-Matrix (k<=n, j<=m) belegt ist.
Also zum Beispiel für n=3, m=4 (wobei X die belegten Felder kennzeichnet):

X X X
X X X
0 0 X
0 0 X

Hier sollte nun erkannt werden, dass nur noch ein 2*2-Feld frei ist.

Hat jemand eine Idee, wie ich das für möglichst allgemeine Spielfeldgrößen feststellen kann. Da es viele Spiele dieses Typs gibt, hat vielleicht jemand schon ähnliche Erfahrungen. Bin für jeden Vorschlag dankbar.

Ich hab zur Repräsentation der Spielfelder ein Spielbrett-Objekt erstellt, in dem die Belegung im Wesentlichen in einem zwei-dimensionalen Array (also einer Matrix) mit Werten 0, 1 gespeichert wird.

Grüße, Martin

 

[Reality]

Also ich habe das bei Vier gewinnt so gemacht:

import java.awt.Point;
import java.util.HashMap;

public class Fields {
  private Fields(){}

  private static Type player;
  private static HashMap<Point, Type> fields = new HashMap<Point,Type>();

  public static void put(Point point, Type player){
    fields.put(point, player);
  }

  public static boolean isSet(Point point, Type player){
    return fields.get(point) == player;
  }
}

public class Type {
  private Type(){}

  public static final Type player = new Type();
  public static final Type computer = new Type();
}

Liebe Grüße
Reality

EDIT: Habe das Anfangs auch über 2 dimensionale Arrays gemacht, aber das hat eben gewissen Einschränkungen und wird unübersichtlich.

 

[Martin]

Gut, über die Art der Implementierung kann man streiten (obwohl mir die Matrix bis jetzt ganz vernünftig vorkommt), aber hast Du einen Algorithmus, für mein Problem (finden von freien Feldern). Bzw. inwieweit lassen sich die mit Deiner Implementierung einfacher finden.

Gruß, Martin

 

[Reality]

Hi,
meine jetzige Methode ist sicherer, einfacher und kürzer als die mit der Matrix.

Sicherer: Es gibt keine ArrayIndexOutOfBoundsException
einfacher: Man setzt und holt über die beiden Methoden
kürzer: keine dämlichen for-Schleifen, wo alles durchzählt wrid(schneller ist es vielleicht deswegen auch.)

Wie du es andwendest?

Ganz einfach:

import java.awt.*;

public class Test {
  public static void main(String[] args) {
    Fields.put(new Point(5, 4), Type.player);

    // gibt true zurück, da es vorher gesetzt wurde
    System.out.println(Fields.isSet(new Point(5, 4), Type.player));
  }
}

Wenn du schreibst:

System.out.println(Fields.isSet(new Point(10, 6), Type.player)); //gibt false zurück

Dann gibt er dir false zurück, da du es vorher nicht gesetzt hast => Das Feld ist frei.

Liebe Grüße
Reality

 

[Wildcard]

Das löst das eigentlich Problem aber nicht:
http://www.java-forum.org/de/viewtopic.php?t=12001
blöde doppelpostings :roll:

 

[Reality]

Kannst du ja erweitern. Für mein Vier gewinnt reicht es jedenfalls.

Liebe Grüße
Reality

 

[Wildcard]

@Reality
Das Array ist IMO hier die bessere wahl.
Das was du schreibst hat er durch ein Array ja schon ganz automatisch, warum also komplizieren.
4 Gewinnt hat ein festes Spielfeld und man muss nur nach 4 Steinen suchen die nebeneinander liegen.
Das hier ist ein bisschen komplizierter, und das "erweitern" ist ja genau das worum es geht :wink:

 

[Reality]

Schau mal. Was ist daran kompliziert?

public boolean hasWon(Type type) {
    //vertikal
    for (int i = 0; i < 7; i++) {
      for (int j = 0; j < 3; j++) {
        if (Fields.isSet(new Point(i, j), type)
            && Fields.isSet(new Point(i, j + 1), type)
            && Fields.isSet(new Point(i, j + 2), type)
            && Fields.isSet(new Point(i, j + 3), type))
        {
          return true;
        }
      }
    }

    //horinzotal
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 6; j++) {
        if (Fields.isSet(new Point(i, j), type)
            && Fields.isSet(new Point(i + 1, j), type)
            && Fields.isSet(new Point(i + 2, j), type)
            && Fields.isSet(new Point(i + 3, j), type))
        {
          return true;
        }
      }
    }
    //diagonal - von links nach rechts
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 3; j++) {
        if (Fields.isSet(new Point(i,j), type)
            && Fields.isSet(new Point(i + 1, j + 1), type)
            && Fields.isSet(new Point(i + 2, j + 2), type)
            && Fields.isSet(new Point(i + 3, j + 3), type))
        {
          return true;
        }
      }
    }
    //diagonal - von rechts nach links
    for (int i = 0; i < 4; i++) {
      for (int j = 5; j > 2; j--) {
        if (Fields.isSet(new Point(i, j), type)
            && Fields.isSet(new Point(i + 1, j - 1), type)
            && Fields.isSet(new Point(i + 2, j - 2), type)
            && Fields.isSet(new Point(i + 3, j - 3), type)) {
          return true;
        }
      }
    }
    return false;
  }

Liebe Grüße
Reality

 

[Wildcard]

irgendwie ist dir das Problem nicht ganz klar!?.
Sieh dir doch einfach mal das andere Topic an, dann wird es vieleicht klarer.

 

[Reality]

Hmm, er will doch herausfinden ob 2 (oder mehr) Elemente nebeneinanderstehen oder nicht.
Meins kontrolliert ob 4 nebeneinander stehen oder diagonal sind.

Liebe Grüße
Reality

PS: Hab seine Posting nur überflogen.

 

[Wildcard]

Es geht darum möglichst große Untermatrizen aus einer Matrix zu filtern.
Da kann er mit 4 Gewinnt nicht viel anfangen.

 

[Wildcard]

Hast du dein 4 Gewinnt wirklich so geschrieben?
Du hättest nur vom zuletzt gesetzten Stein mit Rekursion in die verschiedenen Richtungen gehen müssen.
Da währ ein Array übrigens auch praktischer gewesen

 

[Reality]

Hast du dein 4 Gewinnt wirklich so geschrieben?

Ja.

Du hättest nur vom zuletzt gesetzten Stein mit Rekursion in die verschiedenen Richtungen gehen müssen.

Das stell ich mir jetzt komplizierter vor, das er nur vier mal in eine Richtung gehen darf und alle vier true sein müssen. Wie soll man das ohne weiteres über Rekursion erkennen?

Da währ ein Array übrigens auch praktischer gewesen

Ich erkenne beim besten Willen keine Vorteile beim Array, außer vielleicht etwas mehr Perfomance.
Was kann ich mit Fields nicht machen, was mit Array geht?

Liebe Grüße
Reality

 

[Wildcard]

@Reality
also mal ganz auf die Schnelle(so dirty programmier ich normal wirklich nicht, siehe Exception usw. :roll: )

public class VierGewinnt 
{
    private static int counter=0;
    private boolean[][] field;
    //Offsets für die 8 verschiedenen Richtungen
    private static Point[] offsets = { new Point(1,0),
            					new Point(-1,0),
            					new Point(0,1),
            					new Point(0,-1),
            					new Point(1,1),
            					new Point(-1,-1),
            					new Point(1,-1),
            					new Point(-1,1)
    							};
    
    /**
     * 
     *
     */
    public VierGewinnt()
    {
        //irgendein blödsinnsfeld erzeugen
        field = new boolean [10][10]; 
        for (int i=0;i<field.length;i++)
        {
            for (int j=0;j<field[0].length;j++)
            {
                if (i==4)
                {
                    field[i][j]=true;
                    System.out.print(1);
                }
                else
                    System.out.print(0);
            }
            System.out.println();
        }

    }
    
    /**
     * 
     * @param start
     * @param xOffset
     * @param yOffset
     */
    private void countStones(Point start, Point offset)
    {
        try
        {
            if (!field[start.x][start.y])
                return;
        	counter++;
        	countStones(new Point(start.x+offset.x,start.y+offset.y),offset);
        }
        catch(IndexOutOfBoundsException ex)
    	{
            return;
    	}
    }
    

    public static void main(String[] args) 
    {
        VierGewinnt test = new VierGewinnt();

        for (int i=0;i<8;i+=2)
        {
            test.countStones(new Point(4,4),offsets[i]);
            test.countStones(new Point(4,4),offsets[i+1]);
            if (counter>4)
                System.out.println("true at direction: "+(i/2+1) );
            counter = 0;
        }
        
    }
}

sieht auf den ersten Blick länger aus als deine Lösung, aber eigentlich sinds nur die paar Zeilen der
countStones() Methode.
Die lässt man einfach in alle 8 Richungen laufen und das wars.
Hab der Einfachheit halber boolean verwendet, bei 4gewinnt braucht man natürlich int's

 

[Reality]

sieht auf den ersten Blick länger aus als deine Lösung, aber eigentlich sinds nur die paar Zeilen der
countStones() Methode.

Aber was für ein Krampf man anwenden muss, damit deine Rekursion klappt. Und man muss auch die Zeit berücksichtigen, die ein anderer Programmierer braucht, um dein Code zu verstehen im Vergleich zu meinem, das schön OOP implementiert ist.

Wie gesagt: Ich hatte es zuerst auch durch 2-dimensionale Arrays gelöst und für mich war es ein Chaos mit dem ich zugegebenermasen leben konnte. Nur muss ich das ganze für die Schule machen und mein Lehrer wird schon so enorme Probleme haben mein Code zu verstehen, da er in programmieren wirklich kaum Ahnung hat.

Liebe Grüße
Reality

 

[Wildcard]

Aber was für ein Krampf man anwenden muss, damit deine Rekursion klappt. Und man muss auch die Zeit berücksichtigen, die ein anderer Programmierer braucht, um dein Code zu verstehen im Vergleich zu meinem, das schön OOP implementiert ist.

Wenn man es in ein paar minuten schreiben kann, braucht man auch keine Stunde um es zu verstehen.
Welcher Krampf?(Gut, Kommentare währen hilfreich gewesen )
Man braucht das Feld, die Koordinaten des Steines der zuletzt gesetzt wurde, und die Richtung in die
gezählt werden soll. Eine lösbare Anforderung würde ich sagen.
Bis auf die Tatsache das du bei deiner Lösung Objekte verwendest sehe ich da keine OOP
(oder wie willst du diese Methode wiederverwenden?)
Ist ja ok das es funktioniert, denn darum geht es ja schließlich, aber du wirst zugeben müssen das es
keine gelungene Lösung ist bei jedem gesetzten Stein über das gesamte Spielfeld zu iterieren
und nach 4 Steinen zu suchen die nebeneinander liegen?

 

[Martin]

Was ist an einer 2-dimensionalen Matrix so kompliziert?. Ich sprech die außerdem nicht direkt an, sondern über ein Spielbrett-Objekt.

Hab dann also

Board b=new Board(3,5);
b.getValueAt(x,y);

bzw.

b.isFree(x,y);

In meinem Objekt erfolgt die Repräsentierung halt durch ein Array. Am Algorithmus ändert die Art der Implementierung aber sowieso nichts. Eine Methode wie isFree(int x, int y) oder isSet(int x, int y) wird es immer geben (müssen).

Martin

 

[Reality]

Wenn man es in ein paar minuten schreiben kann, braucht man auch keine Stunde um es zu verstehen.

Drei globale Variablen
Drei Methoden (bzw. 2 Methoden und ein Konstruktor), die nur EINE Aufgabe erfüllen sollen, erschweren unnötig das Lesen des Programms.

Ist ja ok das es funktioniert, denn darum geht es ja schließlich, aber du wirst zugeben müssen das es
keine gelungene Lösung ist bei jedem gesetzten Stein über das gesamte Spielfeld zu iterieren
und nach 4 Steinen zu suchen die nebeneinander liegen?

Stimmt, da muss ich noch etwas ändern.

Liebe Grüße
Reality

 

[Wildcard]

Drei globale Variablen
Drei Methoden (bzw. 2 Methoden und ein Konstruktor), die nur EINE Aufgabe erfüllen sollen, erschweren unnötig das Lesen des Programms.

War wie schon erwähnt nur als Anregung zu verstehen um zu zeigen das man das Problem auch ganz
anders angehen kann.

Überleg mal, dein Programm ist so wie es da steht unbrauchbar. Bei Vier gewinnt, gibt es zwei Spieler. D.h., dass du erkennen musst, wer was gesetzt hat.

Hab der Einfachheit halber boolean verwendet, bei 4gewinnt braucht man natürlich int's

Stimmt, da muss ich noch etwas ändern.

Diese rekursive Grundidee lässt sich problemlos auf deine Map übertragen, zwingt dich ja niemand mit Arrays zu arbeiten.

Zu deiner Frage
Welche Sprache würdet ihr lernen?
würde ich dir antworten SML!
Wenn man zu Rekursion gezwungen wird lernt man einiges dazu, und das hilft bei jeder Sprache.
Wenn ich das richtig verstanden habe möchtest du studieren: an vielen Universitäten wird diese Sprache
als erstes gelehrt.

 

[Reality]

Jetzt hast du geantwortet, bevor ich noch einige Sachen rauseditieren konnte.

Liebe Grüße
Reality