[HaBo]

Nornagest · 06.02.04, 09:44

Hallo,
ich gebe zu ich hab in letzter Zeit meine Aufgaben hier sträflich vernachlässigt, sorry!
Hatte einiges mit dem Studium um die Ohren.

Nun poste ich endlich mal wieder ne neue Aufgabe, die Anonym001 schon vor Monaten vorgeschlagen hat:

Aufgabe:
----------
Also Aufgabe ist ein Programm zu schreiben, dass ein Labyrinth erstellt, in dem ein Weg von links nach rechts führt und am besten jede Stelle erreichbar ist.

Ich würde noch vorschlagen dem Computer eine Lösungstrategie für das Labyrinth bezubringen, sodass man ihm beim Lösen zusehen kann.
----------

Ob das ganze im Textmodus oder grafisch läuft ist ja eigentlich egal, man könnte natürlich auch noch von Hand ein Labyrinth erstellen, das der Computer dann löst, aber das wären nur Erweiterungen.

viel Spaß beim coden, ich hoffe auf eure Teilnahme

mfg
Nornagest

matrixII · 10.02.04, 10:49

hi, also ich muss zugeben, dass ich nicht einmal nen Anstaz hab um das Labyrith zu generieren. kann mir da jemand auf die Sprünge helfen?
mfg

Anzeige

- Anzeige -

Nornagest · 10.02.04, 11:49

so genau hab ich mir das auch noch nicht überlegt, ich werd auch frühestens am Wochenende mal was dran machen können, aber ich denke ich werde zuerst die ganze Fläche füllen und den Computer dann (mehr oder weniger) zufällig herumlaufen lassen, sodass das Labyrinth entsteht.

Mal sehen was rauskommt

HellKnight · 17.02.04, 20:47

Ich habs nich getestet und die includes hab ich mal weggelassen:
Das is zum generieren von dem Laby und saven in ein file.
Wenn nur ein "karo"-muster rauskommt, dann die iterationen runtersetzen!
Ich hab keine Ahnung obs geht

Viel spass... (und es werden mindestens 10 errors drin sein des wette ich)

#define LABY_ROWS 30
#define LABY_COLS 30

short laby_matrix[LABY_ROWS][LABY_COLS]; // 1 = ausgefüllt , 0 = wand

int main(void)
{
int i;
int r,c;

//initialisieren:
for(r = 0; r < LABY_ROWS; r++)
for(c = 0; c < LABY_COLS; c++)
laby_matrix[r][c] = 0;

//manche labyteile setzen:
laby_matrix[0][0] = 1;
laby_matrix[LABY_ROWS][LABY_COLS] = 1;
laby_matrix[LABY_ROWS][0] = 1;
laby_matrix[0][LABY_COLS] = 1;
laby_matrix[LABY_ROSW/2][LABY_COLS/2] = 1;

srand(time(0));

gen_laby();
save_laby("meinlaby.laby");
return 0;
}

void gen_laby(void)
{
int i;
inr r,c;

for(i=0;i<1000;i++) // 1000 irgendeine zahl wie fein das laby werden soll (hab ich nicht getestet, kann auch ne schlechte const. sein)
{
r = rand() % LABY_ROWS;
c = rand() % LABY_COLS;
if(stein_erlaubt(r,c))
{
if((rand() % 3) == 0) // Jeder 3. mal (zufällig)
laby_matrix[r][c] = 1;
}
}
}

void save_laby(char *file_name)
{
int h;
int r,c;

h = open(file_name, O_WRONLY);
for(r = 0; r < LABY_ROWS; r++)
for(c = 0; c < LABY_COLS; c++)
write(h, &laby_matrix[r][c], sizeof(laby_matrix[r][c]));
close(h);
}

/*
Stein ist erlaubt wenn er selbst nicht gesetzt ist
und seine gesetzten Nachbarn weniger als 3 nachbarn haben
*/
bool stein_erlaubt(int r, int c)
{
if(laby_matrix[r][c])
return 0;

if(stein_nachbaranz(laby_matrix[r][c]) == 0 && stein_nachbaranz(laby_matrix[r][c]) > 2) //2 ist maximale nachbaranz
return 0;
else
{
if(r > 0 && stein_nachbaranz(r-1,c) > 2) //2 ist maximale nachbaranz
return 0;
if(r < LABY_ROWS && stein_nachbaranz(r+1,c) > 2)
return 0;
if(c > 0 && stein_nachbaranz(r,c-1) > 2)
return 0;
if(c < LABY_COLS && stein_nachbaranz(r,c+1) > 2)
return 0;

return 1;
}
}

short stein_nachbaranz(int r, int c)
{
short ret;

ret = 0;
if(r > 0 && laby_matrix[r-1][c])
ret++;
if(r < LABY_ROWS && laby_matrix[r+1][c])
ret++;
if(c > 0 && laby_matrix[r][c-1])
ret++;
if(c < LABY_COLS && laby_matrix[r][c+1])
ret++;

return ret;
}

HellKnight · 17.02.04, 20:49

Die einrückungen sind wohl verschwunden

uNsEcUrE · 03.03.04, 19:56

Zitat:

Original von HellKnight
Die einrückungen sind wohl verschwunden

das nächste mal eben als CODE posten

Nornagest · 26.03.04, 22:38

Ich hab mich endlich auch mal hingesetzt und was zusammengeschrieben, ist noch nicht wirklich toll, aber macht so ungefähr was es soll

Code:

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

char feld[25][25];

void ausgabe(){
  for(int i=0;i<25;++i){
    for(int j=0;j<25;++j)
      cout<<feld[i][j]<<feld[i][j];
    cout<<"\n";
  }
}

bool crossLab(){
  int dir=0;
  int x=0;
  int y=11;

  while(x<24 && x>=0){
    switch(dir){
      case 0:
        if(feld[y-1][x]!='#'){
          dir=3;
          y--;
        }
        else if(feld[y][x+1]!='#') {
          x++;
        }
        else if(feld[y+1][x]!='#'){
          dir=1;
          y++;
        }
        else {
          dir=2;
          x--;
        }
        break;
      case 1:
        if(feld[y][x+1]!='#'){
          dir=0;
          x++;
        }
        else if(feld[y+1][x]!='#')
          y++;
        else if(feld[y][x-1]!='#'){
          dir=2;
          x--;
        }
        else {
          dir=3;
          y--;
        }
        break;
      case 2:
        if(x==0)
          x=-1;
        else if(feld[y+1][x]!='#') {
          dir=1;
          y++;
        }
        else if(feld[y][x-1]!='#')
          x--;
        else if(feld[y-1][x]!='#') {
          dir=3;
          y--;
        }
        else {
          dir=0;
          x++;
        }
        break;
      case 3:
        if(feld[y][x-1]!='#') {
          dir=2;
          x--;
        }
        else if(feld[y-1][x]!='#')
          y--;
        else if(feld[y][x+1]!='#') {
          dir=0;
          x++;
        }
        else {
          dir=1;
          y++;
        }
        break;
    }
    feld[y][x]='x';

    //system("clear");
    //ausgabe();
    //cout<<"x: "<<x<<" y: "<<y<<" dir: "<<dir<<"\n";
    //sleep(1);
  }
  if(x<0)
    return false;
  return true;
}

void makeLab(){
  for(int i=0; i<25; i++)
    for(int j=0; j<25; j++){
      feld[i][j]=' ';
      if(i==0 || j==0 || i==24 || j==24)
        feld[i][j]='#';
      else if(i%2 == 0 && j%2 == 0)
        feld[i][j]='#';
    }
        
  feld[11][0]=' ';
  feld[11][24]=' ';
  for(int i=1; i<24; i++)
    for(int j=i%2+1; j<24; j+=2){
      if(rand()%2) feld[i][j]='#';
      else feld[i][j]=' ';
    }
}

int main(){
  time_t t1 = time(0)%1000;
  srand(t1);
 
  bool crossed; 
  do{
    makeLab();

    //system("clear");
    //ausgabe();
    crossed=false;
    crossed=crossLab();
    //ausgabe();
    //sleep(5);
 
  }while(!crossed);
  
  ausgabe();
  return 0;
}

Nornagest · 15.04.04, 18:25

Hier nochmal eine etwas komplexere Lösung, die ich fürs Studium anfertigen musste.
Aufgabe war es ein Programm zu schreiben, dass Labyrinthe aus einer Datei labys.txt ausliest und den kürzesten Weg vom Eingang (möglichst weit oben links) nach draußen sucht und am Bildschirm ausgibt.
Als Sprache musste ich Pacal nehmen.
Ich hab auch eine Beispiel Datei mit Labyrinthen angehängt.

Nornagest · 19.04.04, 21:33

Hier nochmal aktuell:
Zwei Versionen, eine (laby_tp.pas) kompiliert auch mit Turbo Pascal (allerdings sollte man sich überlegen, ob man dem dann große Labyrinthe anvertraut).
Die Turbo Pascal Version sollte überall funktionieren.
Die andere Version habe ich mit FreePascal und GnuPascal getestet unter Win, Linux und FreeBSD, sie braucht nur etwa halb so viel Speicher wie die TP Version und ist _erheblich_ schneller.
Anbei ebenfalls zwei Dateien mit Beispiellabyrinthen, eine mit Windowszeilenumbrüchen, die andere mit Unixzeilenumbrüchen.
Um die Windows Labyrinthdatei zu verwenden muss man sie vorher in labys.txt umbenennen.

Fehlerbehandlung habe ich weggelassen, da das in der Aufgabe nicht gefordert war, war auch so genug Aufwand.

ivegotmail · 19.10.04, 14:40

bin grad auf folgendes applet gestoßen welches dieses problem hier umsetzt
ich weiß dass es nicht sinn des forums ist fremde lösungen zu posten
das programm sieht aber echt gut aus und deswegen wollt ichs hier mal verlinken
http://www.math.com/students/puzzles...n/mazegen.html

Nornagest · 19.10.04, 15:49

gute Links sind immer willkommen.

Norna

Anzeige

- Anzeige -

06.02.04, 09:44	#1 (permalink)
Nornagest Registriert seit: 02.10.01 Likes: 0	Labyrinth Anzeige Hallo, ich gebe zu ich hab in letzter Zeit meine Aufgaben hier sträflich vernachlässigt, sorry! Hatte einiges mit dem Studium um die Ohren. Nun poste ich endlich mal wieder ne neue Aufgabe, die Anonym001 schon vor Monaten vorgeschlagen hat: Aufgabe: ---------- Also Aufgabe ist ein Programm zu schreiben, dass ein Labyrinth erstellt, in dem ein Weg von links nach rechts führt und am besten jede Stelle erreichbar ist. Ich würde noch vorschlagen dem Computer eine Lösungstrategie für das Labyrinth bezubringen, sodass man ihm beim Lösen zusehen kann. ---------- Ob das ganze im Textmodus oder grafisch läuft ist ja eigentlich egal, man könnte natürlich auch noch von Hand ein Labyrinth erstellen, das der Computer dann löst, aber das wären nur Erweiterungen. viel Spaß beim coden, ich hoffe auf eure Teilnahme mfg Nornagest

19.10.04, 14:40	#10 (permalink)
ivegotmail Member of Honour Registriert seit: 28.05.03 Likes: 1	bin grad auf folgendes applet gestoßen welches dieses problem hier umsetzt ich weiß dass es nicht sinn des forums ist fremde lösungen zu posten das programm sieht aber echt gut aus und deswegen wollt ichs hier mal verlinken http://www.math.com/students/puzzles...n/mazegen.html __________________ http://livehabo.hackerboard.de \| http://livebb.sourceforge.net

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
das perfekte Labyrinth	CDW	Programmieraufgaben	15	28.01.09 08:18

10.02.04, 10:49	#2 (permalink)
matrixII Registriert seit: 23.11.02 Likes: 0	hi, also ich muss zugeben, dass ich nicht einmal nen Anstaz hab um das Labyrith zu generieren. kann mir da jemand auf die Sprünge helfen? mfg

10.02.04, 11:49	#3 (permalink)
Nornagest Themenstarter Registriert seit: 02.10.01 Likes: 0	so genau hab ich mir das auch noch nicht überlegt, ich werd auch frühestens am Wochenende mal was dran machen können, aber ich denke ich werde zuerst die ganze Fläche füllen und den Computer dann (mehr oder weniger) zufällig herumlaufen lassen, sodass das Labyrinth entsteht. Mal sehen was rauskommt

17.02.04, 20:47	#4 (permalink)
HellKnight Registriert seit: 22.01.04 Likes: 0	Ich habs nich getestet und die includes hab ich mal weggelassen: Das is zum generieren von dem Laby und saven in ein file. Wenn nur ein "karo"-muster rauskommt, dann die iterationen runtersetzen! Ich hab keine Ahnung obs geht Viel spass... (und es werden mindestens 10 errors drin sein des wette ich) #define LABY_ROWS 30 #define LABY_COLS 30 short laby_matrix[LABY_ROWS][LABY_COLS]; // 1 = ausgefüllt , 0 = wand int main(void) { int i; int r,c; //initialisieren: for(r = 0; r < LABY_ROWS; r++) for(c = 0; c < LABY_COLS; c++) laby_matrix[r][c] = 0; //manche labyteile setzen: laby_matrix[0][0] = 1; laby_matrix[LABY_ROWS][LABY_COLS] = 1; laby_matrix[LABY_ROWS][0] = 1; laby_matrix[0][LABY_COLS] = 1; laby_matrix[LABY_ROSW/2][LABY_COLS/2] = 1; srand(time(0)); gen_laby(); save_laby("meinlaby.laby"); return 0; } void gen_laby(void) { int i; inr r,c; for(i=0;i<1000;i++) // 1000 irgendeine zahl wie fein das laby werden soll (hab ich nicht getestet, kann auch ne schlechte const. sein) { r = rand() % LABY_ROWS; c = rand() % LABY_COLS; if(stein_erlaubt(r,c)) { if((rand() % 3) == 0) // Jeder 3. mal (zufällig) laby_matrix[r][c] = 1; } } } void save_laby(char file_name) { int h; int r,c; h = open(file_name, O_WRONLY); for(r = 0; r < LABY_ROWS; r++) for(c = 0; c < LABY_COLS; c++) write(h, &laby_matrix[r][c], sizeof(laby_matrix[r][c])); close(h); } / Stein ist erlaubt wenn er selbst nicht gesetzt ist und seine gesetzten Nachbarn weniger als 3 nachbarn haben */ bool stein_erlaubt(int r, int c) { if(laby_matrix[r][c]) return 0; if(stein_nachbaranz(laby_matrix[r][c]) == 0 && stein_nachbaranz(laby_matrix[r][c]) > 2) //2 ist maximale nachbaranz return 0; else { if(r > 0 && stein_nachbaranz(r-1,c) > 2) //2 ist maximale nachbaranz return 0; if(r < LABY_ROWS && stein_nachbaranz(r+1,c) > 2) return 0; if(c > 0 && stein_nachbaranz(r,c-1) > 2) return 0; if(c < LABY_COLS && stein_nachbaranz(r,c+1) > 2) return 0; return 1; } } short stein_nachbaranz(int r, int c) { short ret; ret = 0; if(r > 0 && laby_matrix[r-1][c]) ret++; if(r < LABY_ROWS && laby_matrix[r+1][c]) ret++; if(c > 0 && laby_matrix[r][c-1]) ret++; if(c < LABY_COLS && laby_matrix[r][c+1]) ret++; return ret; }

17.02.04, 20:49	#5 (permalink)
HellKnight Registriert seit: 22.01.04 Likes: 0	Die einrückungen sind wohl verschwunden

19.10.04, 15:49	#11 (permalink)
Nornagest Themenstarter Registriert seit: 02.10.01 Likes: 0	gute Links sind immer willkommen. Norna

[HaBo]

Labyrinth