das perfekte Labyrinth

[CDW]

Es gibt sogenannte "perfekte" Labyrinthe - sie besitzen von einem beliebigen Punkt zum anderen genau einen Weg, es gibt also keine Schleifen oder unerreichbaren Stellen:

+-++-++-+
| ||    |
+ ++-++ +
+ ++-++ +
|    || |
+-++ ++ +
+-++ ++ +
|       |
+-++-++-+

1.Euer Programm soll rechteckige, perfekte Labyrinthe beliebiger Größe erzeugen (möglichst zufällige und nicht nur "Schneckenlabyrinthe" )

Spoiler: Hilfe zum Algorithmus

Man nehme an, jede Zelle hätte 4 Wände. Am Anfang sind bei jeder Zelle alle Wände aufgerichtet und die Zellen somit voneinander getrennt.

Jetzt wird eine Zelle zufällig ausgewählt und der Algorithmus verbindet Schritt für Schritt die aktuelle Zelle mit einer unbesuchten Nachbarzelle (dabei die entsprechenden Wände entfernen).

Das wird dann solange gemacht, bis keine unbesuchte Zelle mehr übrig ist.

Weitere Stichworte: Tiefensuche und Backtracking.

2. Damit es nicht so langweilig wird , sollte das Programm sich noch 2 Punkte nehmen (zufällig oder vom Benutzer angeben lassen) und einen Lösungsweg dazwischen finden

S=Start,E=End und die "." markieren den Weg
+-++-++-+
| ||E  .|
+ ++-++ +
+ ++-++ +
|    ||.|
+-++ ++ +
+-++ ++ +
|      S|
+-++-++-+

Spoiler: Hilfe zum Algorithmus

Hier sind wieder Tiefensuche mit Backtracking angesagt - zumindest liefert das recht schnell eine Lösung
Man probiert also (rekursiv) alle Richtungen aus und merkt sich bei Erfolg den Weg

3.Ein Output (Konsole oder grafisch) wäre zur Kontrolle ganz gut.

Spoiler: Beispiel

+-++-++-++-++-++-++-++-++-++-+
|             ||       ||    |
+ ++-++-++-++ ++ ++-++ ++ ++ +
+ ++-++-++-++ ++ ++-++ ++ ++ +
|       ||       || || || || |
+ ++-++ ++-++-++-++ ++ ++-++ +
+ ++-++ ++-++-++-++ ++ ++-++ +
|    || ||.  .  .||          |
+-++-++ ++ ++-++ ++-++-++-++ +
+-++-++ ++ ++-++ ++-++-++-++ +
|.  .||.  .|| ||.  .||    || |
+ ++ ++ ++-++ ++-++ ++ ++-++ +
+ ++ ++ ++-++ ++-++ ++ ++-++ +
|.||.||.  .||.  S||.||    || |
+ ++ ++-++ ++ ++ ++ ++-++ ++ +
+ ++ ++-++ ++ ++ ++ ++-++ ++ +
|.||.||   .  .|| ||.  .||    |
+ ++ ++-++-++-++-++-++ ++ ++-+
+ ++ ++-++-++-++-++-++ ++ ++-+
|E||.  .  .  .  .  .  .||    |
+-++-++-++-++-++-++-++-++-++-+

Lasst euch nicht abschrecken - so groß ist die Aufgabe nicht (ca. 300 Zeilen C, wobei bei mir noch Speichern/Laden in einem bestimmten Format und paar Aspekte mehr implementiert wurden).

 

[lagalopex]

Ich würde folgende Darstellung bevorzugen, da sie imo besser zu lesen ist (zwei Zeichen für eine Breite, damit es in diesem Fall 10x10 auch in etwa quadratisch ist):

Spoiler: Beispiel-Darstellung

##########################################
##      ##                          ##  ##
##  ######  ##############  ######  ##  ##
##          ##      ##      ##      ##  ##
##  ##############  ##  ######  ######  ##
##                  ##  ##  ##      ##  ##
######  ##########  ##  ##  ######  ##  ##
##      ##      ##  ##  ##      ##      ##
##  ######  ##  ######  ##  ##  ######  ##
##      ##  ##      ##  ##  ##          ##
##########  ######  ##  ##########  ######
##          ##          ##      ##  ##  ##
##  ######################  ##  ##  ##  ##
##                          ##  ##      ##
##  ##########################  ######  ##
##  ##      ##              ##  ##      ##
##  ##  ##  ##  ##  ######  ##  ##  ######
##  ##  ##  ##  ##      ##  ##  ##  ##  ##
##  ##  ##  ##########  ##  ##  ######  ##
##      ##              ##  ##          ##
##########################################

Außerdem würde mich das Format, in dem du die Daten speicherst interessieren, da große Labyrithe so bei 500x500 nicht gerade leicht zu überprüfen sind, und wohl kaum irgendjemand sowas ließt^^ und man dann so ein einheitliches Format hat...

 

[CDW]

Ich würde folgende Darstellung bevorzugen

Also Darstellung war nur ein Beispiel - mir war nichts besseres eingefallen und ich fand die Darstellung jeder einzelnen Zelle am einfachsten (und in der Console bzw. bei einem entsprechenden Font sieht das auch imho besser aus ). Außerdem kann man auch eine grafische Ausgabe machen - mit Bildchen oder gezeichneten Linien

Außerdem würde mich das Format, in dem du die Daten speicherst interessieren, da große Labyrithe so bei 500x500 nicht gerade leicht zu überprüfen sind, und wohl kaum irgendjemand sowas ließt^^ und man dann so ein einheitliches Format hat...

hm, ich habe mir gedacht, dass es doch recht sprach und implementierungsspezifisch wäre.

Ich hatte die Vorgabe (ja, es war eine Übungsaufgabe ), die einzelnen Wände jeder Zelle mit jeweils einem gesetzten Bit zu kodieren, so dass ensprechend die Zellen verschiedene Werte hatten: 0 bis 15 (Binär eben 0001 bis 1111). Zusätzlich musste das Programm ein Labyrinth in "lesbarer" Form speichern: 1. Zeile wurde die Größe gespeichert:
3,3
weitere Zeilen war jeweils eine "Zeile" aus dem Labyrinth - die Zellen in Dezimaldarstellung.
Also z.B
3,3
11,9,3
10,10,10
12,6,14

Das wollte ich keinem antun .

Obwohl Textformat bei den ganzen genutzten Sprachen wohl am kompatibelsten wäre.



Wie wäre es damit:
Format: ASCII (Java &Co User können auch bei Unicode bleiben, nur dann kurz hinschreiben - die anschließende ASCII Konvertierung sollte jeder vernünftige Texteditor schaffen).

Darstellung einer einzelnen Zelle:
Dezimale Zahl.

Codierung:
(hab gerade etwas gegoogelt: die "gängigeren" Sprachen, die mir eingefallen sind, unterstützen bitweise Operatoren - c#/java/perl/PHP/pascal/c usw. - also gibt es keine Ausreden, sich nicht damit zu beschäftigen )
Für jede existierende Wand gibt es ein gesetztes Bit.
Wand oben gesetzt: 0001b
Wand rechts gesetzt: 0010b
Wand unten gesetzt: 0100b
Wand links gesetzt: 1000b

Damit repräsentiert z.B die Zahl 15 eine Zelle, dessen Wände noch alle "ganz" sind,
1 ist eine Zelle, die eine obere Wand hat, 3 ist eine Zelle, dessen obere und rechte Wand gesetzt sind usw. Wenn ich gerade keinen Denkfehler hab, sollte es auch OS/Plattformunabhängig sein.

Gesamtformat:

erste Zeile: eine Größenangabe (Dezimal, getrennt durch Komma)
folgende: jeweils eine Zeile aus dem Labyrinth, repräsentiert durch eine Zahl, getrennt durch Kommata. Beispiel (so sieht das Labfile in einem Texteditor aus)

3,3
11,9,3
10,10,10
12,6,14

was als Labyrinth so ausschaut:

+-++-++-+
| ||    |
+ ++ ++ +
+ ++ ++ +
| || || |
+ ++ ++ +
+ ++ ++ +
|    || |
+-++-++-+

Wie man eine Dezimalzahl erstellt bzw. aus der Zahl informationen ausliest:
Bitweise Operatoren - per "and" (bitweisem natürlich) kann man feststellen, ob eine Wand gesetzt ist. Per bitweisem "or" kann man einzelne Informationen reinschreiben:
Zahl=0
Zahl "bitweises or" 1 => obere Wand setzen
Zahl "bitweises or" 8 => linke Wand setzen

Zahl=lese Zahl aus Datei
Zahl "bitweises and" 1 ->ungleich 0 => obere Wand ist gesetzt
Zahl "bitweises and" 8 -> ungleich 0 => linke Wand ist gesetzt

 

[lagalopex]

aha... was mich jetzt bloss wundert, ist dass du ja für alle inneren Wände je 2 bit hast... etwas überflüssig und dass immer außen immer Wände sind...

naja, ich hatte es so gemacht, dass sozusagen jede Zelle zwei bit hat: Wand links / Wand unten
sind zwar immernoch zuviele bits... :]

Aber sonst ist das Format gut... werds wohl mal aufnehmen... muss nur noch(tm) einen Weg S zu E berechnen...
Wie groß kann dein Labyrinth eigentlich werden?

 

[CDW]

ha... was mich jetzt bloss wundert, ist dass du ja für alle inneren Wände je 2 bit hast... etwas überflüssig

Naja, das Format war Vorgabe (man musste alle Wände mit einem Bit kodieren ).

Anderseits erscheint es logischer bei der Konstruktion oder Wegsuche: z.B
zwei Zellen:
linke Zelle hat keine obere und keine rechte Wand, die rechte Zelle keine linke und keine untere Wand und bildet damit eine "Eckdurchgang" (Zugang von oben, dann nach rechts gehen und nach unten.
Wie willst Du diese Situation mit nur 2 Bits informationen abspeichern?

  _
|_ |

Wie groß kann dein Labyrinth eigentlich werden?

ich hab festgestellt, dass es sehr Compilerabhängig ist:
gcc unter Windows: irgendwo knapp über 100x100 ist Schluss
lcc32: irgendwo nach 300x300
gcc unter Knoppix 3.4: imho ging es bis 1000x1000 - was ich sehr erfreulich fand

 

[merker]

ich hab festgestellt, dass es sehr Compilerabhängig ist:
gcc unter Windows: irgendwo knapp über 100x100 ist Schluss
lcc32: irgendwo nach 300x300

Wie kommt das ?!? Gab es irgendwelche Fehlermeldungen ?

 

[CDW]

Wie kommt das ?!? Gab es irgendwelche Fehlermeldungen ?

Lcc32 Kompilat: "Software Fehlercode 0xFD" aufgetreten (im Olly kann man "StackOverflow" Excetion" bewundern). Der Gcc kompilat unter Windows (DJGPP) beendet sich entweder komplett ohne Meldung oder reagiert nicht mehr.Die Meldung unter Knoppix weiß ich nicht mehr - afaik ging das auch Richtung Stackoverflow.

Je nach Compiler werden afaik auch per Default unterschiedliche Stack-Größen reserviert. Man könnte hier ein wenig mit den Einstellungen spielen. Aber sowohl die Erstellung wie auch die Lösung des Labyrinths sind bei mir rekursiver Natur - da geht irgendwann eben der Speicher aus.

 

[merker]

Man könnte hier ein wenig mit den Einstellungen spielen.

Das ist die einzig saubere Lösung.

Hier eine unsaubere (für Leute die keine Zeit haben :

Spoiler: so wird es nicht gemacht

Patch doch einfach den EXE-Header :

1. Suche nach 'PE'

2. Von dort :

PE + Offset 0x60 -> SizeOfStackReserve
PE + Offset 0x64 -> SizeOfStackCommit
PE + Offset 0x68 -> SizeOfHeapReserve
PE + Offset 0x6C -> SizeOfHeapCommit

Patch dort die gewünschte Stack-Grösse rein.

Faustregel :

Default + ((SummeLokalerVariablen+80) * Rekursionstiefe)

Allerdings lässt sich das Labyrinthproblem auch ohne Rekursion lösen. Ich zumindest habe lieber einen "OutOfMemory" anstatt den in jeder Hinsicht fatalen "StackOverflow".

 

[lagalopex]

Also ich hab nichts am Programm geändert (auch rekursiver Ansatz) und kann Labyrinthe von 7000x7000 erstellen (dauert eine knappe halbe Minute, wird mit Schleifen nicht ganz so schnell gehen, imo [oder es braucht auch Unmengen an Speicher]). Zeitweise braucht das Programm dann zwar fast ein GB, aber egal...

Unter Linux kann es sein, dass mit "ulimit -s" eine Stack-Beschränkung gesetzt wurde.
Bei Gentoo war das standardmäßig bei 8MB ... Softlimit kann mit "ulimit -S -s 300000" auf 300 MB gesetzt werden...

Die Konsolen-Ausgabe ist auch knapp 370 MB groß... (wenn das einer haben will^^ gepackt wirds wohl nichtmehr soooo groß sein)

und da ich die letzten Tage unter anderem knapp 550 km weiter im Süden war, bin ich erst heute wieder hierzu gekommen =) ...

 

[CDW]

Ok, hab ein bisschen in der DJGPP Dokumentation gelesen. Die Stackgröße kann man per globalvariable ändern.
unsigned _stklen = 1048576;
Denn standardmäßig soll sie auf 512KB beschränkt sein. Auf "sichere" 100 MB erhöht, konnte ich 4000x4000 Labyrinthe testen (größere dauern mit zu lange - da ich sofort das erstellte Labyrinth erstmal ausgebe ).

So, hier ist erstmal eine Lösung. Sollte mit Lcc32 bzw. gcc auf Windows kompilierbar sein.
Zusätzlich auf Knoppix 3.4 getestet. Wer ein anders OS nutzt, muss eventuell zuerst die Headerdatei anpassen (die OS spezifischen Definitionen um ein einheitliches Clearscreen zu implementieren )
Wer "übergroße" Labyrinthe testen mag, sollte selbst für die nötigen Stackeinstellungen sorgen.
Dass C nicht meine Lieblingssprache ist, merkt man wahrscheinlich schnell
Der Codestil ist etwas gewöhnungsbedürftig - aus mir inzwischen unerklärlichen Gründen habe ich die Namensgebung der Funktions/Variablennamen auf den deutschen Sprachraum beschränkt.

Edit: die Binarys drangehängt: einmal eine Exe für Windows und einmal einen "ELF", der unter Knoppix 3.4 erstellt wurde

 

[merker]

Ich hoffe doch, dass die Programmieraufgabe mit dem Posten einer Lösung noch nicht als gelöst gilt. Schliesslich besitzt sie einen interessanten Nebenaspekt.

Offenbar ist die maximale Labyrinthgrösse plattform- und / oder kompilerabhängig.

Das kann aber nicht sein, da Algorithmen immer plattform- und kompilerunabhängig arbeiten.

Was also muss geändert werden um Labyrinthe zu generieren, die 100.000 * 100.000 Felder gross sind ?

 

[CDW]

einer Lösung noch nicht als gelöst gilt.

Nein, ist sie nicht - eine Lösung kann allerdings einige Denkansätze liefern, falls jemand nicht weiterkommt.

Das kann aber nicht sein, da Algorithmen immer plattform- und kompilerunabhängig arbeiten.

Die Implementierungen dieser Algorithmen sind aber plattform/kompilerabhängig, da sie letzendlich darauf laufen müssen, ich sehe hier keinen Widerspruch

 

[lagalopex]

Mittlerweile kann ich auch ein Labyrinth lösen und speichern... fehlt nur noch das laden...

Spoiler: gelöstes Labyrinth

##########################################################################
##########################################################################
##########################################################################
##########################################################################
##########################################################################
##########################################################################
##########################################################################
##########################################################################
##########################################################################
##########################################################################
##########################################################################
##########################################################################
##########################################################################
##########################################################################
##########################################################################
##########################################################################
##########################################################################
##########################################################################
##########################################################################
##########################################################################
##########################################################################

@merker: Und vom Algorithmus her. Der ist an sich durch die Speichergröße der verwendeten Datentypen und dem zur Verfügung stehenden Speicher begrenzt. An sich also wie CDW sagte, keine Beschränkung des Algorithmus. Allerhöchstens eine Beschränkung der Implementierung / Betriebssystems...
Hast du eigentlich schon eine Lösung mit Schleifen? Im Grunde geht es, klar, aber bei großen Labyrinthen hatte mein Algorithmus ein Problem: Wie finde ich noch nicht zugängliche Zellen, und das möglichst zufällig...

@CDW: Diese Schleife "while (nachbar_versuche!=NORD+WEST+OST+SUED)" wird manchmal doppelt so häufig durchlaufen, wie nötig. (nachbar_versuche wird geändert, wenn der nachbar nichtmehr frei ist, also bei dem zweiten versuch) . Und manchmal ziemlich oft^^ (je nach dem, was rand()%4 liefert...)
Das bei mir mehr Speicher gebraucht wird, könnte an den 64bit liegen X( denn wieviele pointer müssen gesichert werden?!...

 

[xsheep]

Hier ein Labyrinth von meinem Programm:

##########################################
##::  ::##::  ::##::  ::##::  ::  ::##  ##
######  ##  ##  ##  ##  ##  ######  ##  ##
##  ##::  ::##::  ::##::##::##  ##::##  ##
##  ##################  ##  ##  ##  ##  ##
##          ##::  ::  ::##::##  ##::##  ##
##  ##########  ##########  ##  ##  ##  ##
##::  ::##::  ::##  ##    ::##::  ::##  ##
##  ##  ##  ######  ##  ##  ##  ######  ##
##::##::  ::##          ##::##::  ::##  ##
##  ##########  ##########  ######  ##  ##
##::  ::##  ##          ##::##  ##::  ::##
######  ##  ######  ######  ##  ######  ##
##::  ::##          ##::  ::##        ::##
##  ##############  ##  ##############  ##
##::  ::  ::  ::##  ##::  ::  ::  ::##::##
##############  ##########  ######  ##  ##
##  ##      ##::  ::  ::##      ##::##::##
##  ##  ##  ##########  ##########  ##  ##
##      ##            ::  ::  ::  ::##::##
##########################################

Mein Programm beherrscht das Speichern/Laden, Generieren und Lösen von Labyrinthen. Das einzige Problem: nach 300x300 macht es schlapp, kA wieso.

cya xsheep

 

[merker]

Huch ! (Teil 1)

Ihr seid mir alle zu schnell .

Deshalb hier ein Test für den Algorithmus :

Spoiler: Testlauf

1. Der manipulierte Zufallsgenerator

Die Implementation des Algorithmus muss sich auch ordnungsgemäss beenden, wenn er folgendes generiert :

1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 oder
1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2 oder
1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1 oder (...)

2. Das rechte Randgruppenproblem

Technisch gesehen existieren keine mehrdimensionalen Arrays. Dimensionen sind nur eine Frage der Zählweise :

Spoiler: Testlauf

MyArray [3][4]

x   : 1   2   3   4
y   : 1234123412341234
ram : 123456789.......

MyArray[1][7] == MyArray[2][3]

-> Zugriff über die rechte Kante generiert keine Zugriffsverletzung !

Es muss "PerHand" ausgeschlossen sein, dass inkonsistente Daten entstehen.

@lagalopex

Wie finde ich noch nicht zugängliche Zellen, und das möglichst zufällig...

Das geht in dem man sich bei "step_forward" sämtliche freien Richtungen merkt. Dann liegen sie bei "step_back" wieder vor.


+E+D+I+T+1+


Huch ! (Teil 2)

Hoffentlich ist das Interesse an dieser Aufgabe noch nicht verschwunden. Deshalb erst mal ein bischen angeben (siehe Anhang .

Meine nichtrekursive Lösung schafft ohne besondere Linkereinstellungen locker 8000 * 8000 grosse Labyrinthe. Allerdings braucht mein Rechner (Celeron,350MHz,RAM 64MB, FP 6 GB) dafür bereits mehrere Minuten.
Die Maximalgrösse ist nur begrenzt durch folgenden Ausdruck : ((4,75 * x_sz * y_sz) < 4 GB).

Und hier wird die Aufgabe wieder interessant :

Wie lässt sich beweisen, dass ein "sehr" grosses Labyrinth auch wirklich "ok" ist ?

Ausdrucken läuft nicht. Nur Vertrauen haben in die eigene Implementation ist inakzeptabel. Irgendwelche Ideen ?

 

[MontyPerl]

*up*
Hehe, haben die Threads in diesem Subforum eigentlich ein Verfallsdatum?

Naja, ich hab mich mal rangesetzt.

Spoiler: labyrinth.c

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

#define UPPER 1
#define RIGHT 2
#define LOWER 4
#define LEFT  8

#define START   16
#define END     32
#define VISITED 64

typedef struct {
    int xdim, ydim;   /* size */
    char **lab;
} labyrinth;

void *xmalloc(int size);    /* malloc() with automatic errorchecking */
labyrinth *getLab(int xdim, int ydim);
void createWays(labyrinth *l, int x, int y);
int solveRecur(labyrinth *l, int x, int y);
void solve(labyrinth *l);
void printLab(labyrinth *l);

int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(stderr, "usage: %s <x-dimension> <y-dimension>\n", argv[0]);
        exit(EXIT_FAILURE);
    }
    int x, y;
    x = atoi(argv[1]);
    y = atoi(argv[2]);
    labyrinth *l = getLab(x, y);

    srand( time(NULL) );
    createWays(l, rand() % l->xdim, rand() % l->ydim);
    solve(l);

    printLab(l);

    return EXIT_SUCCESS;
}

void solve(labyrinth *l) {
    int endx, endy;
    int startx = rand() % l->xdim;
    int starty = rand() % l->ydim;
    l->lab[starty][startx] ^= START;
    do {
        endx = rand() % l->xdim;
        endy = rand() % l->ydim;
    } while (endx == startx && endy == starty);

    l->lab[endy][endx] ^= END;
    solveRecur(l, startx, starty);
}

int solveRecur(labyrinth *l, int x, int y) {
    l->lab[y][x] ^= VISITED;
    if (l->lab[y][x] & END) {
        return 1;
    }
    int i;
    for (i = 0; i < 4; i++) {
        if (i == 0) {
            if (
                y > 0
             && !(l->lab[y][x] & UPPER)
             && !(l->lab[y-1][x] & VISITED)
            ) {
                if (solveRecur(l, x, y-1)) {
                    return 1;
                }
            }
        }
        else if (i == 1) {
            if (
                y < (l->ydim - 1)
             && !(l->lab[y][x] & LOWER)
             && !(l->lab[y+1][x] & VISITED)
            ) {
                if (solveRecur(l, x, y+1)) {
                    return 1;
                }
            }
        }
        else if (i == 2) {
            if (
                x > 0
             && !(l->lab[y][x] & LEFT)
             && !(l->lab[y][x-1] & VISITED)
            ) {
                if (solveRecur(l, x-1, y)) {
                    return 1;
                }
            }
        }
        else if (i == 3) {
            if (
                x < (l->xdim - 1)
             && !(l->lab[y][x] & RIGHT)
             && !(l->lab[y][x+1] & VISITED)
            ) {
                if (solveRecur(l, x+1, y)) {
                    return 1;
                }
            }
        }
    }
    l->lab[y][x] ^= VISITED;
    return 0;
}

void createWays(labyrinth *l, int x, int y) {
    int choice, gone = 0;
    while (gone != 15) {
        do {
            choice = rand() % 4;
            choice = 1 << choice;
        } while (choice & gone);

        if (choice == UPPER) {
            if (y > 0 && l->lab[y-1][x] == 15) {
                l->lab[y][x] &= ~ UPPER;
                l->lab[y-1][x] &= ~ LOWER;
                createWays(l, x, y-1);
            }
            gone |= UPPER;
        }
        else if (choice == LOWER) {
            if (y < (l->ydim-1) && l->lab[y+1][x] == 15) {
                l->lab[y][x] &= ~ LOWER;
                l->lab[y+1][x] &= ~ UPPER;
                createWays(l, x, y+1);
            }
            gone |= LOWER;
        }
        else if (choice == LEFT) {
            if (x > 0 && l->lab[y][x-1] == 15) {
                l->lab[y][x] &= ~ LEFT;
                l->lab[y][x-1] &= ~ RIGHT;
                createWays(l, x-1, y);
            }
            gone |= LEFT;
        }
        else if (choice == RIGHT) {
            if (x < (l->xdim-1) && l->lab[y][x+1] == 15) {
                l->lab[y][x] &= ~ RIGHT;
                l->lab[y][x+1] &= ~ LEFT;
                createWays(l, x+1, y);
            }
            gone |= RIGHT;
        }
    }
}

labyrinth *getLab(int xdim, int ydim) {
    char *rows = xmalloc(xdim * ydim);
    char **cols = xmalloc(ydim * sizeof(char *));
    int i, j;
    for (i = 0; i < ydim; i++) {
        cols[i] = &rows[i * xdim];
        for (j = 0; j < xdim; j++) {
            cols[i][j] = 15; /* all walls are up */
        }
    }
    labyrinth *l = xmalloc(sizeof(labyrinth));
    l->lab = cols;
    l->xdim = xdim;
    l->ydim = ydim;
    return l;
}

void printLab(labyrinth *l) {
    int x, y, floor;
    char *e, *e2, *f = "##";
    printf("\n\n");
    for (x = 0; x < l->xdim; x++) {
        printf("%s%s", f, f);
    }
    printf("##\n");
    for (y = 0; y < l->ydim; y++) {
        for (floor = 0; floor < 2; floor++) {
            for (x = 0; x < l->xdim; x++) {
                e =   (l->lab[y][x] & START)
                    ? ":o"
                    : (l->lab[y][x] & END)
                    ? ":D"
                    : (l->lab[y][x] & VISITED)
                    ? ".."
                    : "  ";
                e2 = e;
                if (floor == 0) {
                    if (x > 0 && !(l->lab[y][x-1] & VISITED)) {
                        e2 = "  ";
                    }
                    printf("%s%s", l->lab[y][x] & LEFT ? f : e2, e);
                }
                else if (floor == 1) {
                    if (y < (l->ydim - 1) && !(l->lab[y+1][x] & VISITED)) {
                        e2 = "  ";
                    }
                    printf("%s%s", f, l->lab[y][x] & LOWER ? f : e2);
                }
            }
            printf("##\n");
        }
    }

}

void *xmalloc(int size) {
    void *ptr = malloc(size);
    if (ptr == NULL) {
        fprintf(stderr, "not enough memory\n");
        exit(EXIT_FAILURE);
    }
    return ptr;
}

$ ./labyrinth 20 20


##################################################################################
##......        ##..............    ##..............##......    ##......    ##  ##
##..##..##  ######..##########..##  ##..##########..##..##..##  ##..##..##  ##  ##
##..##..##  ##......##      ##..##  ##..##      ##..##..##..##  ##..##..##      ##
##..##..######..##########  ##..######..##  ##  ##..##..##..##  ##..##..######  ##
##..##..........##      ##  ##..........##  ##  ##..##..##..##  ##..##......##  ##
##..##############  ##  ##  ##################  ##..##..##..##  ##..######..##  ##
##..##:D        ##  ##          ##              ##......##..##  ##..##  ##..##  ##
##..##:D######  ##  ##########  ##  ##  ##################..##  ##..##  ##..######
##......##          ##      ##  ##  ##  ##              ##..##  ##......##......##
##############  ######  ##  ##  ######  ##  ##########  ##..##  ######..######..##
##          ##  ##      ##  ##          ##  ##      ##  ##..##  ##......##  ##..##
##  ######  ######  ######  ##########  ##  ##  ######  ##..######..######  ##..##
##  ##  ##          ##  ##      ##      ##  ##          ##..........##      ##..##
##  ##  ##############  ######  ##########  ##  ##############  ######  ######..##
##  ##                  ##  ##              ##  ##          ##  ##          ##..##
##  ##########  ######  ##  ##################  ##  ######  ##  ######  ##  ##..##
##  ##      ##      ##                      ##      ##  ##  ##      ##  ##  ##..##
##  ##  ##  ##  ##  ##################################  ##  ######  ##  ##  ##..##
##      ##  ##  ##          ##      ##              ##      ##  ##  ##  ##  ##..##
##########  ##############  ##  ##  ##  ######  ######  ######  ##  ######  ##..##
##      ##  ##              ##  ##      ##  ##      ##  ##      ##  ##      ##..##
##  ######  ##  ##########  ##  ##########  ######  ##  ##  ######  ##  ######..##
##      ##  ##  ##          ##  ##          ##  ##      ##      ##  ##      ##..##
######  ##  ##  ##  ##########  ######  ##  ##  ##########  ##  ##  ######  ##..##
##      ##  ##  ##  ##  ##      ##      ##              ##  ##              ##..##
##  ######  ##  ##  ##  ##  ######  ##################  ######  ##############..##
##  ##      ##  ##      ##          ##          ##  ##      ##  ##..............##
##  ######  ##  ######################  ######  ##  ######  ######..##############
##          ##                          ##              ##      ##:o    ##      ##
##############  ##############  ######  ##############  ######  ##  ##  ##  ##  ##
##          ##              ##  ##  ##  ##          ##      ##  ##  ##      ##  ##
##  ######  ##############  ##  ##  ##  ##  ######  ######  ##  ##############  ##
##      ##  ##      ##      ##  ##      ##  ##  ##      ##  ##      ##      ##  ##
##  ##  ######  ##  ##  ######  ##  ######  ##  ######  ##########  ##  ##  ##  ##
##  ##          ##  ##  ##      ##  ##  ##  ##      ##              ##  ##  ##  ##
##  ##############  ##  ##  ######  ##  ##  ######  ##################  ##  ##  ##
##  ##          ##      ##  ##          ##      ##          ##      ##  ##      ##
##  ##########  ##########  ##################  ######  ##  ##  ##  ##  ######  ##
##                      ##                              ##      ##      ##      ##
##################################################################################

$ time ./labyrinth 800 800 >/dev/null

real    0m1.360s
user    0m1.239s
sys     0m0.027s
$ time ./labyrinth 1000 1000 >/dev/null

real    0m2.144s
user    0m2.016s
sys     0m0.024s
$ time ./labyrinth 5000 5000 >/dev/null

real    0m53.948s
user    0m51.399s
sys     0m0.536s