Langtons Ameise läuft nicht

walterfrosch

Tach Leute,
ich programmier' seit 'ner Weile wieder C (und habe mir zu diesem Zweck den Grundkurs C von Galileo Computing gekauft) und auch halbwegs Ahnung. Nur ist es mir unbegreiflich, wieso mein Programm zu Langtons Ameise (http://de.wikipedia.org/wiki/Ameise_%28Turingmaschine%29) immer abstürzt.

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

struct ameise{
    int direction; // 0=oben; 1=rechts; 2=unten; 3=links
    int x;
    int y;};

void gotoxy(short x, short y){ // Setzt den Cursor an die Position x|y
HANDLE hCon = GetStdHandle(STD_OUTPUT_HANDLE);
COORD pos;
pos.X=x-1;
pos.Y=y-1;
SetConsoleCursorPosition(hCon, pos);}

void position(struct ameise ant, int x, int y){ // Setzt die Ameise ant auf das Feld x|y
    ant.x=x;
    ant.y=y;
    gotoxy(x,y);
    printf("X");}

void moveleft(struct ameise ant){ // Bewegt die Ameise nach links, abhaengig von ihrer Blickrichtung
    switch(ant.direction){
        case 0: if(ant.x==0){ // Befindet sich die Ameise am linken Rand, kommt sie am rechten heraus
                    position(ant,79,ant.y);}
                else{
                    position(ant,ant.x-1,ant.y);}
                ant.direction=3;
                break;
        case 1: if(ant.y==0){ // Befindet sich die Ameise am oberen Rand, kommt sie am unteren heraus
                    position(ant,ant.x,23);}
                else{
                    position(ant,ant.x,ant.y-1);}
                ant.direction=0;
                break;
        case 2: if(ant.x==79){ // Befindet sich die Ameise am rechten Rand, kommt sie am linken heraus
                    position(ant,0,ant.y);}
                else{
                    position(ant,ant.x+1,ant.y);}
                ant.direction=1;
                break;
        case 3: if(ant.y==23){ // Befindet sich die Ameise am unteren Rand, kommt sie am oberen heraus
                    position(ant,ant.x,0);}
                else{
                    position(ant,ant.x,ant.y+1);}
                ant.direction=2;
                break;}}

void moveright(struct ameise ant){ // Bewegt die Ameise von x|y nach rechts, abhaengig von ihrer Blickrichtung
    switch(ant.direction){
        case 0: if(ant.x==79){ // Befindet sich die Ameise am linken Rand, kommt sie am rechten heraus
                    position(ant,0,ant.y);}
                else{
                    position(ant,ant.x+1,ant.y);}
                ant.direction=1;
                break;
        case 1: if(ant.y==23){ // Befindet sich die Ameise am oberen Rand, kommt sie am unteren heraus
                    position(ant,ant.x,0);}
                else{
                    position(ant,ant.x,ant.y+1);}
                ant.direction=2;
                break;
        case 2: if(ant.x==0){ // Befindet sich die Ameise am rechten Rand, kommt sie am linken heraus
                    position(ant,79,ant.y);}
                else{
                    position(ant,ant.x-1,ant.y);}
                ant.direction=3;
                break;
        case 3: if(ant.y==0){ // Befindet sich die Ameise am unteren Rand, kommt sie am oberen heraus
                    position(ant,ant.x,23);}
                else{
                    position(ant,ant.x,ant.y-1);}
                ant.direction=0;
                break;}}

void wait(int milliseconds){
    clock_t endwait;
    endwait=clock()+milliseconds*CLOCKS_PER_SEC/1000;
    while(clock()<endwait){
        }}

int main(){
    bool feld[80][24]; // true=eingefaerbt; false=leer
    int cycles=0, cycleswanted, cycletime, i, j;
    struct ameise ant;
    // Wie viele Zyklen sollen durchlaufen werden und wie lange soll jeder dauern?
    printf(" Wie viele Zyklen sollen durchlaufen werden? ");
    scanf("%d", &cycleswanted);
    printf("\n Wie lange soll ein Zyklus dauern? (in Millisekunden) ");
    scanf("%d", &cycletime);
    // Das komplette Feld wird "geleert"
    system("cls");
    for(i=0;i<24;i++){
        for(j=0;j<80;j++){
            feld[j][i]=false;}}
    position(ant,40,12); // Die Ameise wird an ihre Startposition in der Mitte der Konsole gesetzt
    ant.direction=0; // Zu Beginn schaut die Ameise nach oben
    // Durchfuehrung eines Iterationsschrittes
    bewegung:
    if(feld[ant.x][ant.y]){
        feld[ant.x][ant.y]=false;
        gotoxy(ant.x,ant.y);
        printf(" ");
        moveleft(ant);}
    else{
        feld[ant.x][ant.y]=true;
        gotoxy(ant.x,ant.y);
        printf("#");
        moveright(ant);}
    cycles++;
    wait(cycletime);
    if(cycles<cycleswanted){
        goto bewegung;}
    else{
        goto end;}
    end:
    gotoxy(0,24);
    system("Pause");
    return 0;}

Hat irgendjemand 'ne Idee?
Ich benutze Code::Blocks zum Schreiben und gcc zum Kompilieren, das Ganze unter Windows 7 Professional x64.

CStoll

Kannst du denn etwas genauer eingrenzen, wo und wie das Programm abstürzt?

Auf Anhieb fallen mir nur Konstruktionen wie void position(struct ameise ant, int x, int y) auf - du übergibst die Ameise als Kopie, das heißt die Variable aus dem Hauptprogramm wird nichts davon mitbekommen, wenn du die Elemente dieses Parameters änderst.

Deinen besten Freund, den Debugger schon bemüht? Und was sagt der Compiler? Irgendwelche Warnungen/Fehlermeldungen? (eventuell den debugger-warnlevel auf höchste stufe stellen).

Wutz

position(ant,40,12); /* Die Ameise wird an ihre Startposition in der Mitte der Konsole gesetzt */

Fehler. Dies macht nicht das was du glaubst.

und habe mir zu diesem Zweck den Grundkurs C von Galileo Computing gekauft

Nächster und viel größerer Fehler, sich auf JW Pfusch einzulassen.

walterfrosch

Also...
Kompilieren tut der Spaß ohne Warnings und sonstwas, schmiert allerdings anscheinend bei Zeile 103 mit 'nem "Segmentation Fault" ab...
Vorschläge?

CStoll

walterfrosch schrieb:

Vorschläge?

Ja, du solltest lernen, wie eine Funktion Werte zurückgeben kann an den Aufrufer - auf das Problem wurdest du ja schon doppelt hingewiesen.

Außerdem ist ant nicht initialisiert, d.h. es steht Datenschrott drin, welcher vermutlich deine Arraygrenzen von feld sprengt. Mit einem Debugger btw. würdest du das sehen.

itedvo

weiteres, wie wutz schon erwähnte, von J.W.
ich glaub sonst wäre er nicht auf die verwendung von goto gekommen

da sind einige dinge die ich anders machen würde und vorallem auch den code verkürzen
würde... ich schick dir mal morgen, wenn ich zeit hab, ne version von mir...

EOP

Au ja, das hab' ich Mitte der 90er Jahre auch programmiert nachdem ich einen Artikel im "Spektrum der Wissenschaft" gelesen hatte.

War damals in C und ich hab' es mit einem Automaten gemacht der die Zustände und Aktionen in Tabellen gespeichert hatte.
Mit DOS und sogar 4-farbig. :p

Leider hab ich das Programm nicht mehr, weil meine boshafte Ex-Frau bei unserer Trennung alle meine Programme + backups gelöscht hat.

Edit:
Ich erinnere mich aber, daß die Initialisierung ganz wichtig war. Du konntest nicht mit einem x-beliebigen Zustand anfangen. Es musste schon der richtige sein sonst kam nur Schrott raus.

Edit #2:
Originalartikel in Englisch:
http://www.fortunecity.com/emachines/e11/86/langton.html
...und in Deutsch:
http://bio-alp.de/21302.html
"Turmiten" hatte er die Dinger damals genannt.
Und aufgrund dieses eher abstrakten Artikels hab ich damal das Programm geschrieben.

itedvo

EOP schrieb:

Leider hab ich das Programm nicht mehr, weil meine boshafte Ex-Frau bei unserer Trennung alle meine Programme + backups gelöscht hat.

böse frau --> beileid

desswegen: lass niemals deine frau/freundin an deinen rechner... schütze deinen
PC doppelt und dreifach und schließ ihn weg... schmeiß dich notfallshalber davor
aber lass niemals die freundin/frau auch nur den pc mit einem milimeter haut
berühren... ein halbes jahr arbeit an einem projekt hinüber nur weil die freundin
nen Film angucken wollte

[PS:] Für die Frauen unter uns, gilt natürlich auch umgekehrt

Entweder ich hab das nicht verstanden oder im Quelltext ist noch einiges im Argen.

Findest du für das goto-label keine andere Lösung?

Hier mal ein Filmchen wie das Tierchen laufen soll:
http://www.youtube.com/watch?v=1X-gtr4pEBU
Ich denke der Quelltext sollte erst mal die zwei Farben- Variante darstellen.
Sollte das mit dem Link nicht erwünscht sein, versenkt diesen Absatz.

MfG f.-th.

EOP

Bei mir hatte die Turmite (siehe meine erste, editierte Antwort) erst ganz chaotisch angefangen, dann plötzlich drum herum ein schönes, symmetrisches Muster gemacht (immer abwechselnd im und gegen den Uhrzeigersinn) und dann ist sie irgendwann nach oben rechts abgehauen.

Recht erstaunlich.

Wutz

void wait(int milliseconds){
    clock_t endwait;
    endwait=clock()+milliseconds*CLOCKS_PER_SEC/1000;
    while(clock()<endwait){
        }}

Da du mit windows.h sowieso schon auf Portabilität verzichtest, kannst du diese "busy-loop" auch besser durch prozessorschonendes Sleep(sekunden) aus windows.h ersetzen.

camper

void gotoxy(short x, short y){ // Setzt den Cursor an die Position x|y
HANDLE hCon = GetStdHandle(STD_OUTPUT_HANDLE);
COORD pos;
pos.X=x-1;
pos.Y=y-1;
SetConsoleCursorPosition(hCon, pos);}

Keine Ahnung ob das ein Problem ist, aber eine gotoxy(0,0) landet möglichwerweise nicht dort wo es soll.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

const int dim_x = 80;
const int dim_y = 24;

struct ameise
{
    int direction;                              // 0 = oben; 1 = rechts; 2 = unten; 3 = links
    int x;
    int y;
};

void gotoxy(short x, short y)                   // Setzt den Cursor an die Position x|y
{
    HANDLE hCon = GetStdHandle( STD_OUTPUT_HANDLE );
    COORD pos = { x, y };
    SetConsoleCursorPosition( hCon, pos );
}

void position(struct ameise* ant, int x, int y) // Setzt die Ameise ant auf das Feld x|y
{
    ant->x = x;
    ant->y = y;
    gotoxy( x, y );
    printf( "X" );
}

void move(struct ameise* ant, bool left)        // Bewegt die Ameise nach links oder rechts, abhaengig von ihrer Blickrichtung
{
    int d = ant->direction;
    position(
        ant,
        ( ant->x + dim_x + ( 2 * left - 1 ) * ( d % 2 == 0 ) * ( d - 1 ) ) % dim_x, 
        ( ant->y + dim_y + ( 2 * left - 1 ) * ( d % 2 == 1 ) * ( d - 2 ) ) % dim_y );
    ant->direction = ( d + 1 + 2 * left ) % 4;
}

int main()
{
    bool feld[ dim_x ][ dim_y ] = { 0 };
    int cycles = 0, cycleswanted = 0, cycletime = 0;
    struct ameise ant = { 0, dim_x / 2, dim_y / 2 };
    printf( " Wie viele Zyklen sollen durchlaufen werden? " );
    scanf( "%d", &cycleswanted );
    printf( "\n Wie lange soll ein Zyklus dauern? (in Millisekunden) " );
    scanf( "%d", &cycletime );
    system( "cls" );
    while ( cycles++ < cycleswanted )
    {
        bool ate = feld[ ant.x ][ ant.y ];
        gotoxy( ant.x, ant.y );
        feld[ ant.x ][ ant.y ] = !ate;
        printf( ate ? " " : "#" );
        move( &ant, ate );
        Sleep( cycletime );
    }
    gotoxy( 0, dim_y );
    system( "Pause" );
    return 0;
}

Kein richtiges C, aber so kann man das Programm einigermaßen verstehen und lesen. Ohne unsinnige switch und goto Orgien.

Es könnte C-Compiler geben die das so schlucken.

Wenn nicht:
Header für bool ergänzen oder selbst etwas für bool schreiben
und/oder Zeile 43:

bool feld[ 80 ][ 24 ] = { 0 };	// this should run with C

Hab nochmal nachgesehen. So wie ich die Compiler meist betreibe, akzeptiert mein gcc 4.4.? den Quelltext als C-Source mit den beschriebenen Änderungen. Der alte free bcc 5.5 und der aktuelle DMC wollen noch weiter Änderungen am Quelltext.

Der free bcc hat keinen C-Header für bool -> selbst etwas erstellen.
Der dmc hat einen Header für C und auch einen Compilerschalter für bool. Da habt ihr die Wahl.

Da ich noch nicht alle Compilerschalter mit einander kombiniert und getestet hab sind eventuell auch noch andere Ergebnisse möglich.

Es soll da Compilerschalter geben C-Quellen wie C++ Quellen zu verarbeiten.
Aber könnte man ja gleich ...

camper

ein

typedef char bool;

würde in diesem Fall völlig ausreichen