Langton-Ameise

Die so genannte Langton-Ameise ist nach ihrem Entdecker, Chris Langton benannt. Sie stellt eine Turing-Maschine dar. Dabei wird allgemein ein Lesekopf über eine Datei gesteuert: Steht der Lesekopf still, so liest er aus der Datei den nächsten Steuerbefehl, den er sogleich ausführt...

Die Langton-Ameise bewegt sich als Turing-Maschine über eine Fläche, die aus lauter Quadraten besteht. Ausgehend von der Mitte bewegt sie sich nach folgendem Schema: Kommt sie auf ein weißes Feld zu stehen, so wendet sie sich um 90° nach rechts, färbt das Quadrat ein und wandert um ein Feld weiter. Ist dieses bereits eingefärbt, so färbt sie es wieder weiß, dreht sich um 90° nach links und wandert wieder ein Feld weiter. Durch diesen Algorithmus scheint die Ameise nun in einem heillosen Durcheinander über das Zeichenfeld zu wuseln - tatsächlich wird die Bewegung aber nach einer endlichen Zahl von Schritten regelmäßig:

Der Programmcode ist überraschend kurz:

import java.awt.*;
import java.awt.event.*;

public class Langton extends Frame {

    Langton() {
        super("Die Langton-Ameise ;-)");
    }

    public static void main (String[] arguments) {
        Langton proggi = new Langton();
        WindowListener wl = new WindowAdapter() {
            public void windowClosing(WindowEvent e) {
                System.exit(0);
            }
        };
        proggi.addWindowListener(wl);
        proggi.setSize(500,500);
        proggi.show();
    }

    public void paint(Graphics bs) {
        int x;
        int y;
        int i;
        int j;

        int richtung;

        int[][] Welt = new int [100][100];

        for (i=0;i<100;i++) 
            for (j=0;j<100;j++)
                Welt[i][j]=0;

        bs.setColor(Color.white);
        bs.fillRect(50,50,400,400);
  
        richtung = 1;
        x = 50;
        y = 50;
        x++;
        do {
            if (Welt[x][y]==1) {
                richtung = ((richtung - 1) % 4);
                Welt[x][y]=0;
                bs.setColor(Color.white);
                bs.fillRect(4*x+50,4*y+50,4,4);
            } else {
                richtung = ((richtung + 1) % 4);
                Welt[x][y]=1;
                bs.setColor(Color.black);
                bs.fillRect(4*x+50,4*y+50,4,4);
            }
            if (richtung == 0) {
                richtung=4;
                y--;
            } else if (richtung == 1) 
                x++;
            else if (richtung == 2)
                y++;
            else if (richtung == 3)
                x--;
        } while ((x>=1) && (x<=100) && (y>=1) && (y<=100));
    }
}

Die jeweilige Richtung, nach der sich die Ameise weiter bewegen soll, wird durch die Zahlen 0, 1, 2, und 3 beschrieben. Davon abhängig werden die Koordinaten x und y inkrementiert oder dekrementiert. Die Ausgabe bricht ab, wenn der Zeichenbereich verlassen wird.