Γεννήτρια λαβύρινθου αλγορίθμων δέντρων

Ο αλγόριθμος Growing Tree είναι ενδιαφέρον, επειδή μπορεί να μιμηθεί τη συμπεριφορά πολλών άλλων αλγορίθμων, ανάλογα με το πώς επιλέγεται το επόμενο κύτταρο κατά τη διάρκεια της δημιουργίας. Η υλοποίηση σε αυτήν τη σελίδα χρησιμοποιεί μια προσέγγιση εύρους πρώτα, που μοιάζει με ουρά.

Ένας τέλειος λαβύρινθος είναι ένας λαβύρινθος στον οποίο υπάρχει ακριβώς ένα μονοπάτι από οποιοδήποτε σημείο του λαβύρινθου σε οποιοδήποτε άλλο σημείο. Αυτό σημαίνει ότι δεν μπορείτε να καταλήξετε να κάνετε κύκλους, αλλά συχνά θα συναντάτε αδιέξοδα, αναγκάζοντάς σας να γυρίσετε πίσω.

Οι χάρτες λαβύρινθου που δημιουργούνται εδώ περιλαμβάνουν μια προεπιλεγμένη έκδοση χωρίς θέσεις εκκίνησης και τερματισμού, ώστε να μπορείτε να τις αποφασίσετε μόνοι σας: θα υπάρχει λύση από οποιοδήποτε σημείο του λαβύρινθου σε οποιοδήποτε άλλο σημείο. Αν θέλετε έμπνευση, μπορείτε να ενεργοποιήσετε μια προτεινόμενη θέση εκκίνησης και τερματισμού - και να δείτε ακόμη και τη λύση μεταξύ των δύο.

Σχετικά με τον αλγόριθμο ανάπτυξης δέντρων

Ο αλγόριθμος Growing Tree είναι μια ευέλικτη και ισχυρή μέθοδος για τη δημιουργία τέλειων λαβύρινθων. Ο αλγόριθμος είναι ενδιαφέρον επειδή μπορεί να μιμηθεί τη συμπεριφορά πολλών άλλων αλγορίθμων δημιουργίας λαβύρινθου, όπως ο αλγόριθμος του Prim, η αναδρομική οπισθοδρόμηση και η αναδρομική διαίρεση, ανάλογα με τον τρόπο επιλογής του επόμενου κελιού για επεξεργασία.

Πώς λειτουργεί ο αλγόριθμος ανάπτυξης δέντρων

Βήμα 1: Προετοιμασία

• Ξεκινήστε με ένα πλέγμα μη επισκέψιμων κελιών.
• Επιλέξτε ένα τυχαίο αρχικό κελί και προσθέστε το σε μια λίστα.

Βήμα 2: Βρόχος δημιουργίας λαβύρινθου

• Ενώ η λίστα κελιών δεν είναι κενή:
  • Επιλέξτε ένα κελί από τη λίστα με βάση μια συγκεκριμένη στρατηγική (εξηγείται παρακάτω).
  • Χαράξτε ένα πέρασμα από το επιλεγμένο κελί σε έναν από τους μη επισκέψιμους γείτονές του (που επιλέγονται τυχαία).
  • Προσθέστε τον γείτονα στη λίστα, καθώς είναι πλέον μέρος του λαβύρινθου.
  • Εάν το επιλεγμένο κελί δεν έχει γείτονες που δεν έχουν επισκεφθεί, καταργήστε το από τη λίστα.

Βήμα 3: Τερματισμός

• Ο αλγόριθμος τελειώνει όταν δεν υπάρχουν περισσότερα κελιά στη λίστα, πράγμα που σημαίνει ότι ολόκληρος ο λαβύρινθος έχει σκαλιστεί.

Στρατηγικές επιλογής κυττάρων (ευελιξία του αλγορίθμου)

Το καθοριστικό χαρακτηριστικό του αλγορίθμου Growing Tree είναι ο τρόπος με τον οποίο επιλέγετε ποιο κελί θα επεξεργαστείτε στη συνέχεια. Αυτή η επιλογή επηρεάζει δραματικά την εμφάνιση του λαβύρινθου:

Νεότερο κελί (συμπεριφορά που μοιάζει με στοίβα) - Αναδρομικό Backtracker:

• Να επιλέγετε πάντα το κελί που προστέθηκε πιο πρόσφατα.
• Παράγει μεγάλους, στριφογυριστούς διαδρόμους με πολλά αδιέξοδα (όπως ένας λαβύρινθος αναζήτησης βάθους).
• Οι λαβύρινθοι τείνουν να έχουν μεγάλα περάσματα και είναι εύκολο να λυθούν.

Τυχαίο κύτταρο (αλγόριθμος τυχαιοποιημένου πρώτου):

• Επιλέξτε ένα τυχαίο κελί από τη λίστα κάθε φορά.
• Δημιουργεί έναν πιο ομοιόμορφα κατανεμημένο λαβύρινθο με πολύπλοκες, μπερδεμένες διαδρομές.
• Λιγότεροι μεγάλοι διάδρομοι και περισσότερες διακλαδώσεις.

Παλαιότερο κελί (συμπεριφορά τύπου ουράς):

• Να επιλέγετε πάντα το παλαιότερο κελί στη λίστα.
• Δημιουργεί λαβύρινθους με πιο ομοιόμορφο ανάπτυγμα, όπως ένα μοτίβο αναζήτησης πρώτου εύρους.
• Μικρά, θαμνώδη περάσματα με πυκνές συνδέσεις.
• (Αυτή είναι η έκδοση που εφαρμόζεται εδώ)

Υβριδικές προσεγγίσεις:

Συνδυάστε στρατηγικές για ποικίλα χαρακτηριστικά λαβύρινθου. Για παράδειγμα:

• 90% νεότερο, 10% τυχαίο: Μοιάζει κυρίως με έναν αναδρομικό λαβύρινθο backtracker, αλλά με περιστασιακά κλαδιά που διαλύουν μεγάλους διαδρόμους.
• 50% νεότερο, 50% παλαιότερο: Εξισορροπεί μεγάλους διαδρόμους με θαμνώδη ανάπτυξη.