Stoppt die Vorratsdatenspeicherung! Jetzt klicken && handeln!Willst du auch bei der Aktion teilnehmen? Hier findest du alle relevanten Infos und Materialien:
 
Labyrinth rekursiv erzeugen
von Plapperkatze am 6.Dezember 2006 um 00:20
zurück zur Kategorie "Tutorials"

Um aus einem Labyrinth herauszufinden, benötigt man erstmal ein Labyrinth. Wir erzeugen eines mit folgenden Eigenschaften:
- horizontale und vertikale Gänge
- Eingang (S) und Ausgang (Z) Teil der Umrandung
- keine Schleifen (Bereiche die man umrunden kann)
- keine unerreichbaren Stellen



Das Labyrinth wird als char-array angelegt mit der Groesse breite*hoehe. Eine rekursive Funktion versucht, Gänge in das initial ausgefüllte Rechteck zu "graben". Das ist möglich, wenn die neue Stelle von Material umschlossen ist (ausser von der Richtung, aus der gegraben wird). Die Richtung ist zufällig. Ausserdem wird der Ausgang (Z) möglichst "tief" im Labyrinth angelegt (dafür die globalen Variablen lx,ly,depth,maxdepth).

rekursive Funktion um zu "graben":
void erzeuge_irrgarten(int breite,int hoehe,int xpos,int ypos,unsigned char *irrgarten)
{
 int dir_check=0;
 *(irrgarten+breite*ypos+xpos)=0;
 if(maxdepth==depth)
 {
   if(xpos==1){lx=xpos-1;ly=ypos;}
   else if(xpos==breite-2){lx=xpos+1;ly=ypos;}
   else if(ypos==1){lx=xpos;ly=ypos-1;}
   else if(ypos==hoehe-2){lx=xpos;ly=ypos+1;}
 }

 depth++;
 if(depth>maxdepth)maxdepth=depth;

 while(dir_check!~~2?5=5>5~~8)
 {
   switch(rand()%4)
   {
     case 0: // oben
       if (!valid(breite,hoehe,xpos,ypos-1,irrgarten)||
           !valid(breite,hoehe,xpos-1,ypos-1,irrgarten)||
           !valid(breite,hoehe,xpos+1,ypos-1,irrgarten)||
           !valid(breite,hoehe,xpos,ypos-2,irrgarten))
       {
         dir_check|=1;
         continue;
       }
       erzeuge_irrgarten(breite,hoehe,xpos,ypos-1,irrgarten);
       break;

     case 1: // unten
       if (!valid(breite,hoehe,xpos,ypos+1,irrgarten)||
           !valid(breite,hoehe,xpos-1,ypos+1,irrgarten)||
           !valid(breite,hoehe,xpos+1,ypos+1,irrgarten)||
           !valid(breite,hoehe,xpos,ypos+2,irrgarten))  // oben
       {
         dir_check|=2;
         continue;
       }
       erzeuge_irrgarten(breite,hoehe,xpos,ypos+1,irrgarten);
       break;

     case 2: // rechts
       if (!valid(breite,hoehe,xpos+1,ypos,irrgarten)||
           !valid(breite,hoehe,xpos+1,ypos-1,irrgarten)||
           !valid(breite,hoehe,xpos+2,ypos,irrgarten)||
           !valid(breite,hoehe,xpos+1,ypos+1,irrgarten))
       {
         dir_check|=4;
         continue;
       }
       erzeuge_irrgarten(breite,hoehe,xpos+1,ypos,irrgarten);
       break;

     case 3: // links
       if (!valid(breite,hoehe,xpos-1,ypos,irrgarten)||
           !valid(breite,hoehe,xpos-1,ypos-1,irrgarten)||
           !valid(breite,hoehe,xpos-2,ypos,irrgarten)||
           !valid(breite,hoehe,xpos-1,ypos+1,irrgarten))
       {
         dir_check|=8;
         continue;
       }
       erzeuge_irrgarten(breite,hoehe,xpos-1,ypos,irrgarten);
       break;
   }
 }
 depth--;
 return;
}

die Funktion valid() prüft, ob diese Position ein Weg sein kann:
int valid(int breite,int hoehe,int xpos,int ypos,unsigned char *irrgarten)
{
 if(xpos<0||xpos>=breite)return 0;
 else if(ypos<0||ypos>=hoehe)return 0;
 else if(*(irrgarten+breite*ypos+xpos)==0)return 0;
 return 1;
}

Eine Funktion um das Labyrinth darzustellen wäre auch nicht schlecht:
void draw(int breite,int hoehe,unsigned char *field)
{
 int m,n;
 for(n=0;n<hoehe;n++)
 {
   for(m=0;m<breite;m++)
   {
     if(*(field+n*breite+m)==0xFF)printf("%c",177);
     else if(*(field+n*breite+m)==1)printf("S");
     else if(*(field+n*breite+m)==2)printf("Z");
     else printf(" ");
   }
   printf("\n");
 }
 printf("\n");
}

Fehlt noch eine Hauptfunktion, um das array zu erzeugen, und den Startpunkt festzulegen:
int main(void)  
{
 int sx=0,sy=1,zx,zy,n,breite=16,hoehe=16;
 unsigned char *irrgarten;

 printf("%s",intro);

 printf("Groesse des Irrgartens (zB.16,16) ? ");
 scanf("%d,%d",&breite,&hoehe);

 do
 {
   maxdepth=0;
   depth=0;
   irrgarten=malloc(breite*hoehe*sizeof(char));
   for(n=0;n<breite*hoehe;n++)
   {
     *(irrgarten+n)=0xFF;
   }

   erzeuge_irrgarten(breite,hoehe,sx,sy,irrgarten);

   *(irrgarten+sy*breite+sx)=1;
   *(irrgarten+breite*ly+lx)=2;

   draw(breite,hoehe,irrgarten);

   free(irrgarten);
 }  
 while(getch()==' ');
 return 0;
}


source-code und windoof exe hier als .rar archiv:
http://katze.dead-men.de/upload/51_irrgarten.rar
linuxxer muessen das getch() entfernen (conio.h) dann sollte es kompilierbar sein.

gruesse von eurer katze

zurück zur Kategorie "Tutorials"
[0 Kommentare]

Name


Kommentar




Bitte abtippen


 
(C) 2006-20012 Plapperkatze - 215314 Besucher seit dem 23.01.2012 Login