Labyrinth generieren (Rekursion)



  • Hallo,

    ich komme leider bei einer Aufgabe nicht weiter und wäre für einen Hinweis wo mein Fehler liegen könnte sehr dankbar.

    Die Aufgabe besteht darin automatisch ein Labyrinth zu generieren bei dem ein Weg von links oben nach rechts unten existiert.

    Dazu soll zufällig ein Mauersegment ausgewählt werden, welches keine Außenwand ist. Wenn es zwischen den beiden Angrenzenden Feldern noch keinen Weg gibt soll das Mauersegment entfernt werden. Zum testen ob schon ein Weg zwischen diesen Zellen Existiert kann z.b. die Tiefensuche oder generell Rekursion benutzt werden.

    Ein Feld hat intern allerdings nur eine linke und eine untere Mauer. (Die Mauern ganz oben und ganz rechts werden in der print Methode einfach dazu gezeichnet).

    Das Problem an meinem Algorithmus ist das der Weg immer nur nach rechts/oben geht, er dadurch natürlich in einer Sackgasse landet und so am Ende immer ein durchgängiger Weg ganz links und ganz unten existiert:
    http://www2.pic-upload.de/img/30975998/UnbenanntesBild.png

    Psuedocode:

    void findRoute(maze, posY, posX){
        if(Feld schon besucht oder außerhalb des Labyrinths) { return; }
        Aktuelles Feld als besucht makieren
    
        findRoute(maze, posY + 1, posX);
        findRoute(maze, posY, posX + 1); 
        findRoute(maze, posY - 1, posX); 
        findRoute(maze, posY, posX - 1); 
    
        bool randomWall = random bool Wert
        if (posX ist nicht ganze links und posY ist nicht ganz unten)
            enferne zuzfällig eines der beiden Mauersegmente
    
        else (bist du ganz links oder ganz unten)
            entferne nicht das äußere Maugersegment sondern das andere
    }
    

    Bei Bedarf kann ich auch den richtigen Code posten.

    Vielen Dank
    Dentho



  • Dieser Thread wurde von Moderator/in Arcoth aus dem Forum C++ (alle ISO-Standards) in das Forum Rund um die Programmierung verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.



  • Verstehe ich das richtig? Du entfernst bei jedem Feld das Du bearbeitest entweder die linke oder die untere Wand (außer du bist am Rand) und nun wunderst Du Dich, dass Du von jedem Feld aus nach links oder unten laufen kannst?



  • Zum Problem kann ich keine Hinweise geben, aber an einem Irrgarten-Programm arbeite ich auch, BTW. ein Labyrinth ist etwas anderes, das Labyrinth stammt
    aus der Antike und diente der Kontemplation.

    Aber falls es jemanden interessiert kann er ja mal auf den Code hier

    klaus-juergen-reinke.eu/maze/a-maze.tgz

    schauen, die liesmich-Datei ist hier

    klaus-juergen-reinke.eu/maze/readme

    hier wurde mithilfe der Graphen-Theorie ein Irrgarten aufgebaut,
    es gibt keine Grafik sondern nur Orte und Wege, was mir nun fehlt
    wären Ideen was man damit noch weiter anfangen könnte.

    mfg Herbert


Log in to reply