Labyrinth

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
 
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
 
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 :)
 
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;
}
 
Ich hab mich endlich auch mal hingesetzt und was zusammengeschrieben, ist noch nicht wirklich toll, aber macht so ungefähr was es soll :D

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;
}
 
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.
 
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. ;)
 
Java-Code

Ich seh grad dass der Thread schon etwas älter ist aber ich habe jetzt schon ein paar Std an der Aufgabe rumprogrammiert und würde meine Arbeit gern präsentieren...
Ist der längste Code den ich bis jetzt geschrieben habe und dementsprechend sieht er auch aus :) (ziemlich unübersichtlich)
Das Programm ist in der Lage ein Labyrinth zu erstellen, die Mauern sind 0-en, der Start eine 1 und der Freiraum besteht aus Leerzeichen.
Den Weg kann der Pc noch nicht selbst finden und das "Labyrinth" ist auch nicht wirklich perfekt.. aber ich arbeite dran :)

Bsp. Labyrinth:
Code:
00000000000000000000000000000000000000000000000000
0   0 0  0 00  00 0 00 0     0   0    00    00 0 0
0  00   0 0   0 00       0 00   00 00 000    0   0
0 00  0 00       0         0    000   00        00
0 00  00   00  0  00  0  0 0000    0   0  0  0  00
0   0 0     0 0   0  0 000 0            00    00 0
0   00     0    0  00 00      0     0      0 0  00
1  0    00   00     0     0000 0  0   00    0    0
0    0     0        0     0       0   0 0 000  0 0
0        0 0  00   0      000       00  000   00 0
0     00 00   0 00 00 000    00 00 0    0 000    0
00      0       0    0      00  0               00
000                                               
0   0 0      00 000 0  00   0 0  0  000  0     0 0
00000000000000000000000000000000000000000000000000
Code:
import java.awt.*;

public class BinaryLabyrinth {

    static int zufallx() {                                // gibt einen wert zwischen 1 und 49 zurück (x-achse)
        int zufallszahl = 0;
        while (zufallszahl < 1)
            zufallszahl = (int)((Math.random() * 49));
        return zufallszahl;
    }
    
    static int zufally() {                                // gibt einen wert zwischen 1 und 14 zurück (y-achse)
        int zufallszahl = 0;
            while (zufallszahl < 1)
        zufallszahl = (int)((Math.random() * 14));
        return zufallszahl;
    }
        
    void labyrinth() {
        int zufaellegibts = zufally();
        Point start = new Point( 0, zufaellegibts);        // startpunkt des labyrinths
        Point end = new Point();            // ziel/endpunkt des labyrinths
        if (zufaellegibts>8)
            end.setLocation(49, zufaellegibts-5);
        else
            end.setLocation(49, zufaellegibts+5);
        Point blocks[] = new Point[750];                // erzeuge 750 hindernisse (MAX)
        for (int i=0; i<blocks.length; i++) {
            blocks[i] = new Point(); 
        }
        int zaehler = 0;                                 
        for (int i=0; i<50; i++) {                        // - wand oben
            blocks[zaehler].setLocation( i, 0); 
            zaehler++;
        } 
        for (int i=0; i<15; i++) {                        // - wand rechts
            blocks[zaehler].setLocation( 49, i); 
            zaehler++;
        } 
        for (int i=0; i<15; i++) {                        // - wand links
            blocks[zaehler].setLocation( 0, i); 
            zaehler++;
        } 
        for (int i=0; i<50; i++) {                        // - wand unten
            blocks[zaehler].setLocation( i, 14); 
            zaehler++;
        }
        
        for (int y=0; y<15; y++) {                        // z
            for (int x=0; x<50; x++) {
                Point pcheck = new Point(x, y);
                boolean bcheck = false;
                for (int i=0; i<zaehler; i++) {
                    if(pcheck.equals(blocks[i]) && ((!pcheck.equals(start) && !pcheck.equals(end)))) {
                            bcheck = true;
                    }
        
                }
                if (bcheck == true) {
                    //System.out.print("0");                // 0 steht für einen block/ ein hinderniss
                } else {
                    if (zufallx() > 30 && ((!pcheck.equals(start) && !pcheck.equals(end)))) {
                        blocks[zaehler].setLocation(pcheck);
                        zaehler++;
                        //System.out.print("0");
                    } else {
                        //System.out.print(" ");                // ' ' steht für freiraum im labyrinth
                    }
                } 
            }
            //System.out.println();
        }
        Point weg = new Point();
        weg.setLocation(start);
        Point wegz[] = new Point[200];
        for (int i=0; i<wegz.length; i++)
            wegz[i] = new Point();
        int wegzaehler = 0;
        weg.setLocation(start);
        int wegerschwerer = 0;
        while(!weg.equals(end)) {
            if (wegerschwerer < 5) {
                weg.x++;
                wegz[wegzaehler].setLocation(weg);
                wegzaehler++;
                wegerschwerer++;
            } 
            if (end.y > weg.y) {
                weg.y++;
                wegz[wegzaehler].setLocation(weg);
                wegzaehler++;
                wegerschwerer++;
            }
            if (end.y < weg.y) {
                weg.y--;
                wegz[wegzaehler].setLocation(weg);
                wegzaehler++;
                wegerschwerer++;
            } 
            if (wegerschwerer>1 && wegerschwerer<2) {
                weg.y++;
                wegz[wegzaehler].setLocation(weg);
                wegzaehler++;
            } else if (wegerschwerer>4) {
                wegerschwerer = 0;
                weg.y--;
                wegz[wegzaehler].setLocation(weg);
                wegzaehler++;
            } 
                
            
                
        }
        for (int y=0; y<15; y++) {                        // z
            for (int x=0; x<50; x++) {
                Point pcheck = new Point(x, y);
                boolean bcheck = false;
                boolean bweg = false;
                for (int i=0; i<zaehler; i++) {
                    if(pcheck.equals(blocks[i]) && ((!pcheck.equals(start) && !pcheck.equals(end)))) {
                        bcheck = true;
                    } else {
                        for (int j=0; j<wegz.length; j++)
                        if(pcheck.equals(wegz[j])) {
                            bweg = true;
                        }
                    }
                }
                if (bcheck == true && bweg == false) {
                    System.out.print("0");                // 0 steht für einen block/ ein hinderniss
                } else if (bweg == true){
                    System.out.print(" ");                
                } else if (pcheck.equals(start)) {
                    System.out.print("1");                // 1 steht für den start des labyrinths
                } else { 
                    System.out.print(" ");                // ' ' steht für freiraum im labyrinth
                } 
            }
            System.out.println();
        }

    }
}


Code:
public class StartLabyrinth {
    public static void main(String[] args) {
        BinaryLabyrinth dasLabyrinth = new BinaryLabyrinth ();                    
        dasLabyrinth.labyrinth();                            // zeichnet mit der labyrinth()-methode ein labyrinth
    }
}
 
Zurück
Oben