Γεννήτρια λαβύρινθου κυνηγιού και θανάτωσης

Ο αλγόριθμος Hunt and Kill είναι στην πραγματικότητα μια τροποποιημένη έκδοση του Recursive Backtracker. Η τροποποίηση συνίσταται στη συστηματική σάρωση (ή "αναζήτηση") ενός νέου κελιού για να συνεχιστεί από τη στιγμή που δεν μπορεί να προχωρήσει περαιτέρω, σε αντίθεση με μια πραγματικά αναδρομική αναζήτηση, η οποία θα επιστρέφει πάντα στο προηγούμενο κελί της στοίβας.

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

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

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

Σχετικά με τον αλγόριθμο Hunt and Kill

Ο αλγόριθμος Hunt and Kill είναι μια απλή αλλά αποτελεσματική μέθοδος για τη δημιουργία λαβυρίνθων. Είναι κάπως παρόμοιος με μια αναζήτηση βάθους-πρώτα (δηλαδή τον αλγόριθμο Recursive Backtracker), εκτός από το ότι όταν δεν μπορεί να προχωρήσει περισσότερο από την τρέχουσα θέση, σαρώνει (ή "κυνηγάει") συστηματικά πάνω από τον λαβύρινθο για να βρει ένα νέο κελί από το οποίο να προχωρήσει. Ο αλγόριθμος αποτελείται από δύο κύριες φάσεις: το περπάτημα και το κυνήγι.

Πώς λειτουργεί ο αλγόριθμος Hunt and Kill για τη δημιουργία λαβυρίνθου

Βήμα 1: Ξεκινήστε από ένα τυχαίο κελί

• Βρείτε ένα τυχαίο κελί στο πλέγμα και επισημάνετέ το ως επισκεπτόμενο.

Βήμα 2: Φάση Περπατήματος (Τυχαίος Περίπατος)

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

Βήμα 3: Φάση αναζήτησης (Ανακοίνωση μέσω σάρωσης)

• Σαρώστε το πλέγμα γραμμή προς γραμμή (ή στήλη προς στήλη).
• Βρείτε το πρώτο μη επισκεπτόμενο κελί που έχει τουλάχιστον έναν επισκεπτόμενο γείτονα.
• Συνδέστε αυτό το κελί με έναν γείτονα που επισκεφτήκατε για να συνεχίσετε τη φάση περπατήματος.
• Επαναλάβετε μέχρι να επισκεφθούν όλα τα κελιά.

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

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

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