Die Langton-Ameise

Alan M. Turing, einer der Begründer der modernen Rechnertheorie, entdeckte die nach ihm benannte Turing-Maschine, eine universelle Rechenmaschine. Im Prinzip wird dabei 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...

Chris Langton entdeckte dazu einen einfachen "Roboter", der nach ihm "Langton-Ameise" genannt wird. Dieses Tierchen sitzt zunächst in der Mitte eines Zeichenfeldes, das in lauter weiße Quadrate unterteilt ist, die entweder weiß oder schwarz umgefärbt werden können. Die Ameise bewegt sich nun nach folgendem Schema: Kommt sie auf ein weißes Feld zu stehen, so wendet sie sich um 90° nach rechts, färbt das Quadrat schwarz und wandert um ein Feld weiter. Ist dieses schwarz, so färbt sie es weiß, dreht sich um 90° nach links und wandert wieder ein Feld weiter. Durch diesen Algorithmus scheint die Ameise in einem heillosen Durcheinander über das Zeichenfeld zu wuseln - tatsächlich wird die Bewegung nach einer endlichen Zahl von Schritten regelmäßig:

Beispiel:

Die Langton-Ameise stellt eine sogenannte Turing-Maschine dar...

Code:

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

public class langton extends Applet {

    public void init() {
    }

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

	int richtung;

	int[][] Welt = new int [60][60];

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

	bs.setColor(Color.white);
	bs.fillRect(0,0,300,300);

	richtung = 1;
	x = 30;
	y = 30;
	x++;
	do {
	    if (Welt[x][y]==1) {
		richtung = ((richtung - 1) % 4);
		Welt[x][y]=0;
		bs.setColor(Color.white);
		bs.fillRect(5*x,5*y,5,5);
	    } else {
		richtung = ((richtung + 1) % 4);
		Welt[x][y]=1;
		bs.setColor(Color.red);
		bs.fillRect(5*x,5*y,5,5);
	    }
	    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<=60) && (y>=1) && (y<=60));
    }
}