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

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

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

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

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

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

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

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

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

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

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