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

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

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

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

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

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

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

Βήμα 1: Αρχικοποίηση

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

Βήμα 2: Βρόχος Δημιουργίας Λαβυρίνθου

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

Βήμα 3: Λήξη

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

Στρατηγικές Επιλογής Κελιών (Ευελιξία του Αλγορίθμου)

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

Νεότερο κελί (Συμπεριφορά τύπου στοίβας) – Αναδρομική παρακολούθηση οπισθοπορείας:

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

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

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

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

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

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

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

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

Περαιτέρω ανάγνωση

Αν σας άρεσε αυτή η ανάρτηση, ίσως σας αρέσουν και αυτές οι προτάσεις:

• Gennítria lavyrínthou algórithmou Kruskal
• Γεννήτρια λαβύρινθου αλγορίθμου του Eller
• Γεννήτρια λαβύρινθου αλγορίθμου του Wilson