Αναδρομική γεννήτρια λαβύρινθου backtracker

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

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

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

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

Παρά το όνομά της, δεν χρειάζεται απαραίτητα να υλοποιηθεί με χρήση αναδρομής. Συχνά υλοποιείται με επαναληπτική προσέγγιση χρησιμοποιώντας μια ουρά LIFO (δηλαδή μια στοίβα). Για πολύ μεγάλους λαβύρινθους, η χρήση αναδρομής είναι πιο πιθανό να οδηγήσει σε υπερχείλιση στοίβας κλήσεων, ανάλογα με τη γλώσσα προγραμματισμού και τη διαθέσιμη μνήμη. Μια ουρά LIFO μπορεί να προσαρμοστεί πιο εύκολα στη διαχείριση μεγάλων ποσοτήτων δεδομένων, ακόμη και διατηρώντας την ουρά σε δίσκο ή σε μια βάση δεδομένων εάν η διαθέσιμη μνήμη δεν επαρκεί.

Πώς λειτουργεί

Ο αλγόριθμος λειτουργεί χρησιμοποιώντας μια προσέγγιση αναζήτησης με βάση το βάθος που βασίζεται σε στοίβες. Ακολουθεί η αναλυτική ανάλυση βήμα προς βήμα:

1. Επιλέξτε ένα αρχικό κελί και επισημάνετέ το ως επισκεφθέν.
2. Ενώ υπάρχουν μη επισκεπτόμενα κελιά: Εξετάστε τα γειτονικά κελιά που δεν έχουν ακόμη επισκεφθεί. Εάν υπάρχει τουλάχιστον ένας μη επισκεπτόμενος γείτονας: Επιλέξτε τυχαία έναν από τους μη επισκεπτόμενους γείτονες. Αφαιρέστε το τείχος μεταξύ του τρέχοντος κελιού και του επιλεγμένου γείτονα. Μετακινηθείτε στον επιλεγμένο γείτονα και επισημάνετέ τον ως επισκεπτόμενο. Σπρώξτε το τρέχον κελί στη στοίβα. Εάν δεν υπάρχουν μη επισκεπτόμενοι γείτονες: Επιστρέψτε προς τα πίσω αφαιρώντας το τελευταίο κελί από τη στοίβα.
3. Συνεχίστε αυτή τη διαδικασία μέχρι να αδειάσει η στοίβα.

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

Στην πραγματικότητα, έχω δύο εκδόσεις αυτού του αλγορίθμου σε λειτουργία σε αυτόν τον ιστότοπο: μια που βασίζεται σε ουρά LIFO για τη δημιουργία λαβυρίνθων σε αυτήν τη σελίδα και μια που βασίζεται σε αναδρομή για την επίλυση λαβυρίνθων, επίσης λαβυρίνθων που δημιουργούνται από άλλους αλγόριθμους (έτσι κατασκευάζονται οι χάρτες με τις λύσεις). Το να έχω δύο διαφορετικές εκδόσεις είναι απλώς για αθλήματα, επειδή είμαι σπασίκλας που το βρίσκει ενδιαφέρον, και οι δύο θα μπορούσαν να λειτουργήσουν και για τις δύο ;-)

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

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

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