Γεννήτρια λαβύρινθου κυνηγιού και θανάτωσης
Δημοσιεύθηκε: 16 Φεβρουαρίου 2025 στις 8:52:26 μ.μ. UTC
Γεννήτρια λαβύρινθου χρησιμοποιώντας τον αλγόριθμο Hunt and Kill για να δημιουργήσετε έναν τέλειο λαβύρινθο. Αυτός ο αλγόριθμος είναι παρόμοιος με το Recursive Backtracker, αλλά τείνει να δημιουργεί λαβύρινθους με κάπως λιγότερο μεγάλους, ελικοειδής διαδρόμους.Hunt and Kill Maze Generator
Ο αλγόριθμος Hunt and Kill είναι πραγματικά μια τροποποιημένη έκδοση του Recursive Backtracker. Η τροποποίηση συνίσταται στη συστηματική σάρωση (ή "κυνήγι") για ένα νέο κελί που θα συνεχίσει από όταν δεν μπορεί να προχωρήσει περαιτέρω, σε αντίθεση με μια πραγματική αναδρομική αναζήτηση, η οποία θα επιστρέφει πάντα στο προηγούμενο κελί στη στοίβα.
Εξαιτίας αυτού, αυτός ο αλγόριθμος μπορεί εύκολα να προσαρμοστεί για να δημιουργήσει λαβύρινθους με διαφορετική εμφάνιση και αίσθηση, απλά επιλέγοντας να εισέλθει στη λειτουργία "κυνηγιού" πιο συχνά ή σύμφωνα με συγκεκριμένους κανόνες. Η έκδοση που εφαρμόζεται εδώ εισέρχεται σε λειτουργία "κυνηγιού" μόνο όταν δεν μπορεί να προχωρήσει περισσότερο από το τρέχον κελί.
Ένας τέλειος λαβύρινθος είναι ένας λαβύρινθος στον οποίο υπάρχει ακριβώς ένα μονοπάτι από οποιοδήποτε σημείο του λαβύρινθου σε οποιοδήποτε άλλο σημείο. Αυτό σημαίνει ότι δεν μπορείτε να καταλήξετε να κάνετε κύκλους, αλλά συχνά θα συναντάτε αδιέξοδα, αναγκάζοντάς σας να γυρίσετε πίσω.
Οι χάρτες λαβύρινθου που δημιουργούνται εδώ περιλαμβάνουν μια προεπιλεγμένη έκδοση χωρίς θέσεις εκκίνησης και τερματισμού, ώστε να μπορείτε να τις αποφασίσετε μόνοι σας: θα υπάρχει λύση από οποιοδήποτε σημείο του λαβύρινθου σε οποιοδήποτε άλλο σημείο. Αν θέλετε έμπνευση, μπορείτε να ενεργοποιήσετε μια προτεινόμενη θέση εκκίνησης και τερματισμού - και να δείτε ακόμη και τη λύση μεταξύ των δύο.
Σχετικά με τον αλγόριθμο Hunt and Kill
Ο αλγόριθμος Hunt and Kill είναι μια απλή αλλά αποτελεσματική μέθοδος για τη δημιουργία λαβυρίνθων. Είναι κάπως παρόμοιο με μια αναζήτηση βάθους (δηλαδή τον αλγόριθμο Recursive Backtracker), εκτός από όταν δεν μπορεί να προχωρήσει περισσότερο από την τρέχουσα θέση, σαρώνει συστηματικά (ή "κυνηγά") πάνω από το λαβύρινθο για να βρει ένα νέο κελί για να προχωρήσει. Ο αλγόριθμος αποτελείται από δύο κύριες φάσεις: περπάτημα και κυνήγι.
Πώς λειτουργεί ο αλγόριθμος Hunt and Kill για τη δημιουργία λαβυρίνθων
Βήμα 1: Ξεκινήστε από ένα τυχαίο κελί
- Βρείτε ένα τυχαίο κελί στο πλέγμα και σημειώστε το ως επισκέψιμο.
Βήμα 2: Φάση βάδισης (τυχαίος περίπατος)
- Επιλέξτε έναν τυχαίο γείτονα που δεν επισκέπτεστε.
- Μετακινηθείτε σε αυτόν τον γείτονα, επισημάνετε τον ως επισκεπτόμενο και χαράξτε μια διαδρομή μεταξύ του προηγούμενου και του νέου κελιού.
- Επαναλάβετε μέχρι να μην υπάρχουν γείτονες που δεν έχουν επισκεφθεί.
Βήμα 3: Φάση κυνηγιού (Backtracking μέσω σάρωσης)
- Σαρώστε το πλέγμα γραμμή προς γραμμή (ή στήλη προς στήλη).
- Βρείτε το πρώτο μη επισκέψιμο κελί που έχει τουλάχιστον έναν γείτονα που επισκέπτεται.
- Συνδέστε αυτό το κελί με έναν γείτονα που επισκεφθήκατε για να συνεχίσετε τη φάση περπατήματος.
- Επαναλάβετε μέχρι να επισκεφθείτε όλα τα κύτταρα.