Datei:MAZE 30x20 DFS.gif
Seiteninhalte werden in anderen Sprachen nicht unterstützt.
Werkzeuge
Allgemein
Drucken/exportieren
In anderen Projekten
Erscheinungsbild
Aus Wikibooks
MAZE_30x20_DFS.gif (732 × 492 Pixel, Dateigröße: 4,5 MB, MIME-Typ: image/gif, Endlosschleife, 609 Bilder, 1 min 1 s)
Hinweis: Aufgrund technischer Beschränkungen werden Vorschaubilder hochauflösender GIF-Dateien wie dieser nicht animiert.
Dieses Medium wird direkt von Wikimedia Commons aus eingebunden. Quellenangaben und Lizenzbedingungen befinden sich auf der unten zusätzlich eingeblendeten Commons-Beschreibungsseite.
Beschreibung
BeschreibungMAZE 30x20 DFS.gif |
English: The generation of a maze using a depth-first search algorithm. This maze is 30x20 in size. The C++ source code used to create this can be seen at w:User:Purpy Pupple/Maze. |
Datum | |
Quelle | Eigenes Werk |
Urheber | Purpy Pupple |
Andere Versionen |
C src code
//Purpy Pupple's amazing maze generator.
//Released under the CC-BY-SA 3.0 License and the GFDL
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define UP 0 //-y
#define DOWN 1 //+y
#define LEFT 2 //-x
#define RIGHT 3 //+x
#define OUTFILE "MAZE"
#define WHITE fprintf(outfile, "%c%c%c", 255,255,255)
#define BLACK fprintf(outfile, "%c%c%c", 0,0,0)
#define RED fprintf(outfile, "%c%c%c", 0,0,255)
#define nodeadend//generate a maze without any dead ends! (consequently, many solutions to maze)
//#define prim //enable this to generate mazes using prim's algorithm.
#define backtrack//enable this to generate mazes using depth-first search. Don't enable both.
//#define movie //this option spams bitmaps to illustrate each step of generation.
long numin=1; //Number of cells in the maze.
const int xsize=152;
const int ysize=122;
void initialize();
void generate();
void savebmp(int xspecial, int yspecial);
struct cell{
bool in; //Is this cell in the maze?
bool up; //Does the wall above this cell exist?
bool left;//Does the wall to the left of this cell exist?
int prevx, prevy; //The coordinates of the previous cell, used for backtracking.
};
cell MAZE[xsize][ysize];
int main(){
srand((unsigned int)time(NULL)); //seed random number generator with system time
initialize(); //initialize the maze
generate(); //generate the maze
#ifdef movie
for(int i=1;i<10;i++){
numin++;
savebmp(0,0); //output the bitmap
}
#else movie
savebmp(0,0);
#endif
return 0;
}
void initialize(){
//Initialize the maze!
for(int x=0;x<xsize;x++){
for(int y=0;y<ysize;y++){
//The maze cells on the edges of the maze are "in" to provide padding. Otherwise, all maze cells are not in.
MAZE[x][y].in = (x==0||x==xsize-1||y==0||y==ysize-1)?1:0;
//All maze cells have all walls existing by default, except the perimeter cells.
MAZE[x][y].up = (x==0||x==xsize-1||y==0)?0:1;
MAZE[x][y].left = (x==0||y==0||y==ysize-1)?0:1;
}
}
return;
}
void generate(){
int xcur=1, ycur=1;//start growing from the corner. It could theoretically start growing from anywhere, doesn't matter.
MAZE[xcur][ycur].in = 1;
int whichway;
bool success;
do{
#ifdef movie
savebmp(xcur,ycur);
#endif
#ifdef nodeadend
if( MAZE[xcur][ycur-1].in&&MAZE[xcur][ycur+1].in&&
MAZE[xcur-1][ycur].in&&MAZE[xcur+1][ycur].in ){
//If at a dead end, randomly destroy a wall to make it not a dead end!
do{
success=0;
whichway=rand()%4;
switch(whichway){
case UP:
if(MAZE[xcur][ycur].up&&ycur!=1){
success=1;
MAZE[xcur][ycur].up=0;
}
break;
case DOWN:
if(MAZE[xcur][ycur+1].up&&ycur!=ysize-2){
success=1;
MAZE[xcur][ycur+1].up=0;
}
break;
case LEFT:
if(MAZE[xcur][ycur].left&&xcur!=1){
success=1;
MAZE[xcur][ycur].left=0;
}
break;
case RIGHT:
if(MAZE[xcur+1][ycur].left&&xcur!=xsize-2){
success=1;
MAZE[xcur+1][ycur].left=0;
}
break;
}
}while(!success);
}
#endif
#ifdef backtrack
while( MAZE[xcur][ycur-1].in&&MAZE[xcur][ycur+1].in&&
MAZE[xcur-1][ycur].in&&MAZE[xcur+1][ycur].in ){
//If all the neighbourhood cells are in, backtrack.
int xcur2=MAZE[xcur][ycur].prevx;
ycur=MAZE[xcur][ycur].prevy;
xcur=xcur2;
}
#endif
#ifdef prim
do{
//randomly find a cell that's in the maze
xcur=rand()%(xsize-2)+1;
ycur=rand()%(ysize-2)+1;
}while(!MAZE[xcur][ycur].in ||
MAZE[xcur][ycur-1].in&&MAZE[xcur][ycur+1].in&&
MAZE[xcur-1][ycur].in&&MAZE[xcur+1][ycur].in);
#endif
do{
//Randomly grow the maze if possible.
success=0;
whichway=rand()%4;
switch(whichway){
case UP:
if(!MAZE[xcur][ycur-1].in){
success=1;
MAZE[xcur][ycur].up=0;
MAZE[xcur][ycur-1].prevx=xcur;
MAZE[xcur][ycur-1].prevy=ycur;
ycur--;
}
break;
case DOWN:
if(!MAZE[xcur][ycur+1].in){
success=1;
MAZE[xcur][ycur+1].up=0;
MAZE[xcur][ycur+1].prevx=xcur;
MAZE[xcur][ycur+1].prevy=ycur;
ycur++;
}
break;
case LEFT:
if(!MAZE[xcur-1][ycur].in){
success=1;
MAZE[xcur][ycur].left=0;
MAZE[xcur-1][ycur].prevx=xcur;
MAZE[xcur-1][ycur].prevy=ycur;
xcur--;
}
break;
case RIGHT:
if(!MAZE[xcur+1][ycur].in){
success=1;
MAZE[xcur+1][ycur].left=0;
MAZE[xcur+1][ycur].prevx=xcur;
MAZE[xcur+1][ycur].prevy=ycur;
xcur++;
}
break;
}
}while(!success);
MAZE[xcur][ycur].in=1;
numin++; //Every iteration of this loop, one maze cell is added to the maze.
}while(numin<(xsize-2)*(ysize-2));
#ifdef movie
savebmp(xcur,ycur);
#endif
return;
}
void savebmp(int xspecial, int yspecial){
//save a bitmap file! the xspecial, yspecial pixel is coloured red.
FILE * outfile;
int extrabytes, paddedsize;
int x, y, n;
int width=(xsize-1)*2-1;
int height=(ysize-1)*2-1;
extrabytes = (4 - ((width * 3) % 4))%4;
char filename[200];
sprintf(filename, "%s_%dx%d_n%d.bmp", OUTFILE, xsize, ysize, numin);
paddedsize = ((width * 3) + extrabytes) * height;
unsigned int headers[13] = {paddedsize + 54, 0, 54, 40, width, height, 0, 0, paddedsize, 0, 0, 0, 0};
outfile = fopen(filename, "wb");
fprintf(outfile, "BM");
for (n = 0; n <= 5; n++){
fprintf(outfile, "%c", headers[n] & 0x000000FF);
fprintf(outfile, "%c", (headers[n] & 0x0000FF00) >> 8);
fprintf(outfile, "%c", (headers[n] & 0x00FF0000) >> 16);
fprintf(outfile, "%c", (headers[n] & (unsigned int) 0xFF000000) >> 24);
}
fprintf(outfile, "%c", 1);fprintf(outfile, "%c", 0);
fprintf(outfile, "%c", 24);fprintf(outfile, "%c", 0);
for (n = 7; n <= 12; n++){
fprintf(outfile, "%c", headers[n] & 0x000000FF);
fprintf(outfile, "%c", (headers[n] & 0x0000FF00) >> 8);
fprintf(outfile, "%c", (headers[n] & 0x00FF0000) >> 16);
fprintf(outfile, "%c", (headers[n] & (unsigned int) 0xFF000000) >> 24);
}
//Actual writing of data begins here:
for(y = 0; y <= height - 1; y++){
for(x = 0; x <= width - 1; x++){
if(x%2 == 1 && y%2 == 1){
if(x/2+1 == xspecial && y/2+1 == yspecial) RED;
else{
if(MAZE[x/2+1][y/2+1].in) WHITE; else BLACK;
}
}else if(x%2 == 0 && y%2 == 0){
BLACK;
}else if(x%2 == 0 && y%2 == 1){
if(MAZE[x/2+1][y/2+1].left) BLACK; else WHITE;
}else if(x%2 == 1 && y%2 == 0){
if(MAZE[x/2+1][y/2+1].up) BLACK; else WHITE;
}
}
if (extrabytes){ // See above - BMP lines must be of lengths divisible by 4.
for (n = 1; n <= extrabytes; n++){
fprintf(outfile, "%c", 0);
}
}
}
printf("file printed: %s\n", filename);
fclose(outfile);
return;
}
Lizenz
Ich, der Urheberrechtsinhaber dieses Werkes, veröffentliche es hiermit unter der folgenden Lizenz:
Diese Datei ist unter der Creative-Commons-Lizenz „Namensnennung – Weitergabe unter gleichen Bedingungen 3.0 nicht portiert“ lizenziert.
- Dieses Werk darf von dir
- verbreitet werden – vervielfältigt, verbreitet und öffentlich zugänglich gemacht werden
- neu zusammengestellt werden – abgewandelt und bearbeitet werden
- Zu den folgenden Bedingungen:
- Namensnennung – Du musst angemessene Urheber- und Rechteangaben machen, einen Link zur Lizenz beifügen und angeben, ob Änderungen vorgenommen wurden. Diese Angaben dürfen in jeder angemessenen Art und Weise gemacht werden, allerdings nicht so, dass der Eindruck entsteht, der Lizenzgeber unterstütze gerade dich oder deine Nutzung besonders.
- Weitergabe unter gleichen Bedingungen – Wenn du das Material wiedermischst, transformierst oder darauf aufbaust, musst du deine Beiträge unter der gleichen oder einer kompatiblen Lizenz wie das Original verbreiten.
Es ist erlaubt, die Datei unter den Bedingungen der GNU-Lizenz für freie Dokumentation, Version 1.2 oder einer späteren Version, veröffentlicht von der Free Software Foundation, zu kopieren, zu verbreiten und/oder zu modifizieren; es gibt keine unveränderlichen Abschnitte, keinen vorderen und keinen hinteren Umschlagtext.
Der vollständige Text der Lizenz ist im Kapitel GNU-Lizenz für freie Dokumentation verfügbar.http://www.gnu.org/copyleft/fdl.htmlGFDLGNU Free Documentation Licensetruetrue |
Du darfst es unter einer der obigen Lizenzen deiner Wahl verwenden.
In dieser Datei abgebildete Objekte
Motiv
Einige Werte ohne einen Wikidata-Eintrag
5. Februar 2011
Dateiversionen
Klicke auf einen Zeitpunkt, um diese Version zu laden.
Version vom | Vorschaubild | Maße | Benutzer | Kommentar | |
---|---|---|---|---|---|
aktuell | 02:37, 5. Dez. 2012 | 732 × 492 (4,5 MB) | Dllu | User created page with UploadWizard |
Dateiverwendung
Die folgenden 2 Seiten verwenden diese Datei:
Abgerufen von „https://de.wikibooks.org/wiki/Datei:MAZE_30x20_DFS.gif“