Spielfeld von Langton Ameise

Java-Forum Java-Grundlagen
1

Hallo, ich möchte die Langton Ameise nachbauen und bin grade dabei das Spielfeld nichtgrafisch zu implementieren. Ich habe bis jetzt dieses Spielfeld als Koordinatensystem, also als Array von Arrays, implementiert. Bis jetzt können aber nur die Werte bis 5 zurück geliefert werden. Das soll so aber nicht sein. Theoretisch sollen die Werte ins unendliche gehen. Wie mache ich das mit Arrays? Hier ist meine Lösung.

import java.util.*;

public class Board {
  


 
     
     
      int Matrix1 [][]= { {0,0,0,0,0}, {0,0,0,0,0}, {0,0,0,0,0}, {0,0,0,0,0},{0,0,0,0,0} }; //1. Quadrant
     int Matrix2 [][]= { {0,0,0,0,0}, {0,0,0,0,0}, {0,0,0,0,0}, {0,0,0,0,0},{0,0,0,0,0} };  //2.
      int Matrix3 [][]= { {0,0,0,0,0}, {0,0,0,0,0}, {0,0,0,0,0}, {0,0,0,0,0},{0,0,0,0,0} };  //3.
    int Matrix4 [][]= { {0,0,0,0,0}, {0,0,0,0,0}, {0,0,0,0,0}, {0,0,0,0,0},{0,0,0,0,0} };  //4.
    
   
   
    
      public int getstate (int x, int y){
    int result=0;

    if (x>=0 && x <=5 &&  y>=0 && y <= 5){                                      //1. Quadrant

                 

      result=  Matrix1[x][y];

      }

      
     
    if (x<0 && y>=0){                   //2. Quadrant
      result= Matrix2[-1*x][y];
    }
    if (x<= 0 && y <0){                   //3. Quadrant
      result= Matrix3[-1*x][-1*y];
    }
    if (x>0 && y<0){                   //4. Quadrant
      result=Matrix4[x][-1*y];
    }
    return result;
    }


    public void setstate(int x,int y, int state1){
      if (x>=0 && x<=5 && y>=0 &&y<=5){			//1.Quadrant
       Matrix1[x][y]=state1;}
     
      if (x<0 && y>=0){                   //2. Quadrant
	     Matrix2[-1*x][y]=state1;
	    }
     
      if (x<=0 && y<0){                   //Im 3. Quadrant Werte setzen
        Matrix3[-1*x][-1*y]=state1;
      }
      if (x>0 && y<0){                   //Im 4. Quadrant Werte setzen
       Matrix4[x][-1*y]=state1;
     
      }
    }}


import java.util.*;


public class Start_langton {

    /**
     * @param args
     */
    public static void main(String[] args) {
	// TODO t-generated method stub
Board test=new Board();

test.setstate(3,3,100);
test.setstate(4, -3, 33);

test.setstate(-3, -4, -337);
test.setstate(-4, 4, -64);
test.setstate(-3, 3,12);

System.out.println(test.getstate(3, 3));
System.out.println(test.getstate(4,-3));
System.out.println(test.getstate(-3,-4));
System.out.println(test.getstate(-4,4));
System.out.println(test.getstate(-3,3));
System.out.println(test.getstate(4, 4));
    }
}
2

Hm. Erstmal sieht das mit den Quadranten recht kompliziert aus. Also, falls da nicht explizit irgendwas genau SO modelliert werden soll, würde man statt 4 * 5x5-Arrays eben EINEN 10x10-Array verwenden. Die Koordinaten kann man ja einfach umrechnen: Auf die gegebenen Koordinaten (z.B. (-2,-1)) rechnet man dann einfach jeweils 5 drauf, und hat dann die Array-Indizes (3,4).

Allgemein könnte man also EINE Matrix erzeugen, mit
int matrix[][] = new int[10][10];

Wenn das ganze dynamisch wirklich “beliebig” groß werden können soll, muss man sich was überlegen (spontan wäre eine Map<Point, Integer> dann eine Option). (Dazu müsste ich mir morgen aber erstmal durchlesen, worum es bei dieser Ameise so geht).

3

Egal ob mit Arrays oder einer Map, irgendwann wird man mit der Ameise immer das Ende der Welt erreichen.
Die Frage ist nur, was einem zuerst ausgeht. Die Indizes oder der Speicher.
Computer ist eben Begrenzt und die Welt der Ameise unbegrenzt.

Das Problem das hier besteht ist ja, dass Arrays keine negativen Indizes erlauben und der TO mit den 4 Quadranten arbeitet um das ganze umzurechnen.

Die eine Möglichkeit besteht ein grösseres Koordinatensystem zu benutzen so, dass der Nullpunkt, auf der Koordinate 5;5 liegt und man nun jeweils 5 dazuaddiert um zum Array-Feld zu kommen oder jeweils 5 abzieht um wieder die Koordinate zu bekommen.

Aber auch 10 mal 10 wird irgendwann nicht ausreichen. Und der Speicherverbrauch, steigt wenn man das groß macht bei Arrays entsprechend schnell, obwohl ein Großteil leer bleiben wird.

Arrays kann man in Java nur vergrößern, indem man bei Bedarf ein größeres Array anlegt und den Inhalt des kleineren rüberkopiert.

Der Vorteil von einer Map, deren Speicher auch begrenzt ist, ist dass eben nur schwarze Felder gespeichert werden müssen, so dass die Ameise viel weiter laufen kann, wenn sie sich erstmal für eine Richtung entschieden hat. Ansonsten erstmal keine weiteren Größenbeschränkungen.

Eine weitere Möglichkeit ist, das ganze als ein Torusfeld zu modellieren. Läuft die Ameise links aus dem Feld heraus, kommt sie rechts wieder herein und umgekehrt. Ebenso mit oben und unten.

Eine Kugel wäre die andere Alternative.

Torus

Oder eine Klein Bottle

4

Für die klassische “schwarz-weiß”-Ameise würde auch ein Set<Point> als Spielfeld ausreichen.

5

Nun, “setState” bekommt ja schon einen int übergeben, daher geht es wohl um eine bunte Ameise.

Erwähnen wollte ich das gestern schon, aber … war schon recht spät, deswegen erst jetzt: Ich würde dringendST empfehlen, das Feld as interface zu modellieren. Das wäre ja recht überschaubar

interface Board
{
    void setState(int x,int y, int state); 
    int getState(int x,int y); 
    int getSizeX();
    int getSizeY();
}

Der Vorteil ist: Man kann es implementieren, wie man will.

In bezug auf die Repräsentation: Man kann einen int[]-Array verwenden, oder auch einen byte[]-Array, wenn das reicht, um Speicherplatz zu sparen. Oder man verwendet besagte “Map<Point, Integer>”. Wenn man wüßte, dass es eine Binäre Ameise sein soll, könnte man den state auch in ein “boolean” ändern, und das ganze in ein BitSet packen.

In bezug auf das Verhalten: Man kann eine Kartesische- oder Toruswelt durch dasselbe interface abbilden. (Manch einer mag nun skeptisch auf das “getSize” schielen: Wenn man eine unendliche Welt modellieren will, könnte man da ggf. “-1” zurückgeben…)

Der Unterschied wäre dann nur noch in der Instantiierung:

//Board board = new TorusBoard();
//Board board = new CartesianBoardWithArray();
Board board = new CartesianBoardWithMap(); // Heute nehmen wir mal das hier...
6

Hallo,

könnte sein, das dieser Beitrag wieder entfernt wird, wenn ich hier ein bisschen rumpfusche… Mach’ das doch so:

 * @author CyborgBeta. 19.05.2016
 */
public class Temp {

    private static final boolean[][] spiel = new boolean[100][100]; // false == weiß
    private static final int[] ameise = new int[3]; // x, y, 0 == unten, 1 == links, 2 == oben, 3 == rechts

    public static void main(String[] args) throws InterruptedException {
        // ...
    }

    private static void nextSchritt() {
        if (spiel[ameise[0]][ameise[1]]) { // schwarz
            ameise[2]--;
        } else { // weiß
            ameise[2]++;
        }
        if (ameise[2] < 0) {
            ameise[2] = 4 + ameise[2];
        } else if (ameise[2] > 3) {
            ameise[2] %= 4;
        }
        spiel[ameise[0]][ameise[1]] = !spiel[ameise[0]][ameise[1]];
        switch (ameise[2]) {
            case 0:
                ameise[0]++;
                break;
            case 1:
                ameise[1]--;
                break;
            case 2:
                ameise[0]--;
                break;
            case 3:
                ameise[1]++;
                break;
            default:
                throw new AssertionError();
        }
        if (ameise[0] < 0) {
            ameise[0] = spiel.length + ameise[0];
        } else if (ameise[0] >= spiel.length) {
            ameise[0] %= spiel.length;
        }
        if (ameise[1] < 0) {
            ameise[1] = spiel[0].length + ameise[1];
        } else if (ameise[1] >= spiel[0].length) {
            ameise[1] %= spiel[0].length;
        }
    }
}```

Ich konnte es nicht lassen, das zu testen. DAS ist 1:1 der Code, der im Beispiel von Wikipedia verwendet wurde ( https://de.wikipedia.org/wiki/Ameise_%28Turingmaschine%29 ). Alle Werte sind bereits "richtig" gesetzt. So ergab sich bei mir:

Nach 100:



Nach 12000:



(Jedes einzelne Kästchen gezählt :D ).
7

Ach, ich Blödi, Werte bis ins unendliche überlesen, das kommt davon, wenn man etwas Neues direkt ausprobieren will.

Einfache Antwort: Nicht möglich, Zeit und Raum begrenzt.

Komplizierte Antwort: Doch möglich, nimm Set oder Map<Point, Integer> - dann ist das “Spielfeld” aber nicht mehr fest, seine Grenzen werden immer größer. Für Speicherplatz und Zeit bedeutet das weiterhin nix Gutes.

Weiterhin befindet die Ameise nach etwa ungefähr 11.000 Durchläufen sich in einem Zyklus. D. h., das ganze Gebilde wächst nach oben rechts, wird es klassisch implementiert (so wie ich gemacht hab).

Wenn du bei der Implementierung oder GUI Fragen hast, schieß einfach drauf los, ich beantworte sie dann.

vergessen Marcos Hint mit Interfaces scheint stimmig, du solltest seinen Hint beherzigen.

8

Ich weiß schon, man glaubt erst etwas, wenn man es sieht, deshalb reiche ich nochmal ein animiertes Gif nach:

Schritte: 50,
Schrittweite: 240,
time Between Frames: 10ms,
loop Continuously: true,

Dateigröße: 493 KB (~),
erlaubte Dateigröße: 500 KB :frowning: .

Hat ganz schön gedauert, bis ich das hatte. Im Webbrowser wäre gut.

9

[ot][quote=CyborgBeta]Dateigröße: 493 KB (~),
erlaubte Dateigröße: 500 KB .[/quote]
Hab die erlaubte Größe verdoppelt.[/ot]

10

Na gut, dann nutze ich das mit Größe verdoppelt.

Marco hat es mit unendlichen Board richtig beschrieben:


    void setState(int x, int y, int state);

    int getState(int x, int y);

    int getWid();

    int getHid();
}

class CartesianBoardWithMap implements Board {

    HashMap<Point, Integer> map = new HashMap<Point, Integer>();
    int xmin = 0;
    int xmax = 0;
    int ymin = 0;
    int ymax = 0;

    @Override
    public int getHid() {
        return ymax - ymin + 1;
    }

    @Override
    public int getState(int x, int y) {
        Point p = new Point(x, y);
        if (map.containsKey(p)) {
            return map.get(p);
        }
        return 0;
    }

    @Override
    public int getWid() {
        return xmax - xmin + 1;
    }

    @Override
    public void setState(int x, int y, int state) {
        map.put(new Point(x, y), state);
        if (xmin > x) {
            xmin = x;
        }
        if (xmax < x) {
            xmax = x;
        }
        if (ymin > y) {
            ymin = y;
        }
        if (ymax < y) {
            ymax = y;
        }
    }
}

// ...

/**
 * @author CyborgBeta. 21.05.2016.
 */
public class Temp {

    private static final Board board = new CartesianBoardWithMap(); // 0 == weiß, 1 == schwarz
    private static final int[] ameise = new int[3]; // x, y, 0 == unten, 1 == links, 2 == oben, 3 == rechts

    public static void main(String[] args) throws InterruptedException, IOException {
        JFrame jf = new JFrame("LT-Ameise_0.2");
        // ...
    }

    private static void nextSchritt() {
        if (board.getState(ameise[0], ameise[1]) == 1) {
// schwarz
            ameise[2]--;
        } else {
// weiß
            ameise[2]++;
        }
        ameise[2] = (ameise[2] + 4) % 4;
        board.setState(ameise[0], ameise[1], board.getState(ameise[0], ameise[1]) == 0 ? 1 : 0);
        switch (ameise[2]) {
            case 0:
                ameise[0]++;
                break;
            case 1:
                ameise[1]--;
                break;
            case 2:
                ameise[0]--;
                break;
            case 3:
                ameise[1]++;
                break;
            default:
                throw new AssertionError();
        }
    }
}```

nextSchritt() ist kompakter und board wächst dynamisch, wenn ameise aus dem board laufen würde.

So hab ich jetzt für die ersten 100:



Und dann noch nebenbei, wenn das GridLayout größer als 100x100 wird, gibt's Probleme bei der Darstellung (Schritte bis 15.000):
11

Danke für Eure Beiträge. Ich würde das aber lieber mit Arrays machen, hat jemand eine Idee wie ich das realisieren könnte?

12

Arrays und “unendlich”, wie am Anfang gefragt, geht logischerweise nicht,
wobei die anderen Lösungen auch alle mit Arbeitsspeicher/ Festplatte/ Internet-Cloud/ Papier-Ausdruck + Scannen/ Höhlenmalerei + Scannen theoretisch irgendwann ein Ende haben,
aber Array ist eben besonders verschwenderisch in alle Richtungen

nichtsdestotrotz kann man mit Arrays ein wenig erreichen, deine Lösung von Posting #1 ist ja bereits was,
Wechsel auf nur noch EIN Array mit Index-Rechnen sollte klar sein,
wenn du andere Fragen hast stelle sie genauer,

von einem gewissen User wurde auch schon was mit Arrays gepostet und vielleicht demnächst weitere vier Postings,
ob zum Vorteil oder Nachteil möge jeder selber entscheiden…

13

Ich hab doch schon Array Init und Array Berechnung nächster Schritt gezeigt, du darfst einfach kopieren.

Arrays habn für mich zwei wesentliche Vorteile:
Berechnung nächster Schritt unabhängig von Darstellung UI,
Berechnung nächster Schritt in der schnellsten Geschwindigkeit.

Edit: Das static ist aber nur für Profis geeignet, du solltest (vielleicht) einen OO-Ansatz wählen. Andere habn das schon richtig angemerkt.

Bei weiteren Fragen einfach deinen Ansatz zeigen und wir können helfen…