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

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

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

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

Σχετικά με τον Αλγόριθμο του Wilson

Ο αλγόριθμος του Wilson για τη δημιουργία ομοιόμορφων δέντρων κάλυψης χρησιμοποιώντας ένα τυχαίο τοίχο με διαγραφή βρόχου δημιουργήθηκε από τον David Bruce Wilson.

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

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

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

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

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

Βήμα 2: Επιλέξτε ένα τυχαίο αρχικό κελί

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

Βήμα 3: Τυχαία Περιήγηση με Διαγραφή Βρόχου

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

Βήμα 4: Επαναλάβετε μέχρι να επισκεφθούν όλα τα κελιά:

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

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

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

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