Γεννήτρια λαβύρινθου αλγορίθμου του Wilson
Δημοσιεύθηκε: 16 Φεβρουαρίου 2025 στις 7:31:43 μ.μ. UTC
Γεννήτρια λαβύρινθου χρησιμοποιώντας τον αλγόριθμο του Wilson για να δημιουργήσει έναν τέλειο λαβύρινθο. Αυτός ο αλγόριθμος δημιουργεί όλους τους πιθανούς λαβύρινθους ενός δεδομένου μεγέθους με την ίδια πιθανότητα, οπότε μπορεί θεωρητικά να δημιουργήσει λαβύρινθους πολλών μικτών διατάξεων, αλλά καθώς υπάρχουν περισσότεροι πιθανοί λαβύρινθοι με μικρότερους διαδρόμους από μεγαλύτερους, θα τους βλέπετε πιο συχνά.Wilson's Algorithm Maze Generator
Ο αλγόριθμος του Wilson είναι μια μέθοδος τυχαίου περιπάτου σβησμένη με βρόχο που δημιουργεί ομοιόμορφα δέντρα για τη δημιουργία λαβυρίνθων. Αυτό σημαίνει ότι όλοι οι πιθανοί λαβύρινθοι ενός δεδομένου μεγέθους είναι εξίσου πιθανό να δημιουργηθούν, καθιστώντας την μια αμερόληπτη τεχνική δημιουργίας λαβύρινθου. Ο αλγόριθμος του Wilson μπορεί να θεωρηθεί βελτιωμένη έκδοση του αλγορίθμου Aldous-Broder, καθώς δημιουργεί λαβύρινθους με πανομοιότυπα χαρακτηριστικά, αλλά τρέχει πολύ πιο γρήγορα, οπότε δεν έχω μπει στον κόπο να εφαρμόσω τον αλγόριθμο Aldous-Broder εδώ.
Ένας τέλειος λαβύρινθος είναι ένας λαβύρινθος στον οποίο υπάρχει ακριβώς ένα μονοπάτι από οποιοδήποτε σημείο του λαβύρινθου σε οποιοδήποτε άλλο σημείο. Αυτό σημαίνει ότι δεν μπορείτε να καταλήξετε να κάνετε κύκλους, αλλά συχνά θα συναντάτε αδιέξοδα, αναγκάζοντάς σας να γυρίσετε πίσω.
Οι χάρτες λαβύρινθου που δημιουργούνται εδώ περιλαμβάνουν μια προεπιλεγμένη έκδοση χωρίς θέσεις εκκίνησης και τερματισμού, ώστε να μπορείτε να τις αποφασίσετε μόνοι σας: θα υπάρχει λύση από οποιοδήποτε σημείο του λαβύρινθου σε οποιοδήποτε άλλο σημείο. Αν θέλετε έμπνευση, μπορείτε να ενεργοποιήσετε μια προτεινόμενη θέση εκκίνησης και τερματισμού - και να δείτε ακόμη και τη λύση μεταξύ των δύο.
Σχετικά με τον αλγόριθμο του Wilson
Ο αλγόριθμος του Wilson για τη δημιουργία ομοιόμορφων δέντρων χρησιμοποιώντας έναν τυχαίο τοίχο σβησμένο με βρόχο δημιουργήθηκε από τον David Bruce Wilson.
Ο Wilson εισήγαγε αρχικά αυτόν τον αλγόριθμο το 1996, ενώ ερευνούσε τυχαία δέντρα και μαρκοβιανές αλυσίδες στη θεωρία πιθανοτήτων. Αν και το έργο του ήταν κυρίως στα μαθηματικά και τη στατιστική φυσική, ο αλγόριθμος έχει έκτοτε υιοθετηθεί ευρέως για τη δημιουργία λαβυρίνθων λόγω της ικανότητάς του να παράγει απόλυτα ομοιόμορφους λαβύρινθους.
Πώς λειτουργεί ο αλγόριθμος του Wilson για τη δημιουργία λαβυρίνθων
Ο αλγόριθμος του Wilson διασφαλίζει ότι ο τελικός λαβύρινθος είναι πλήρως συνδεδεμένος χωρίς βρόχους, χαράσσοντας επαναλαμβανόμενα μονοπάτια από μη επισκέψιμα κελιά χρησιμοποιώντας τυχαίους περιπάτους.
Βήμα 1: Προετοιμασία
- Ξεκινήστε με ένα πλέγμα γεμάτο τοίχους.
- Ορίστε μια λίστα με όλα τα πιθανά κελιά διέλευσης.
Βήμα 2: Επιλέξτε ένα τυχαίο αρχικό κελί
- Επιλέξτε οποιοδήποτε τυχαίο κελί και σημειώστε το ως επισκέψιμο. Αυτό χρησιμεύει ως σημείο εκκίνησης του λαβύρινθου κατά τη διάρκεια της γενιάς.
Βήμα 3: Τυχαίος περίπατος με διαγραφή βρόχου
- Επιλέξτε ένα μη επισκέψιμο κελί και ξεκινήστε έναν τυχαίο περίπατο (κινούμενοι σε τυχαίες κατευθύνσεις).
- Εάν ο περίπατος φτάσει σε ένα ήδη επισκεπτόμενο κελί, διαγράψτε τυχόν βρόχους στη διαδρομή.
- Μόλις ο περίπατος συνδεθεί με την περιοχή επίσκεψης, σημειώστε όλα τα κελιά στη διαδρομή ως επισκεπτόμενα.
Βήμα 4: Επαναλάβετε μέχρι να επισκεφθείτε όλα τα κελιά:
- Συνεχίστε να επιλέγετε μη επισκέψιμα κελιά και να εκτελείτε τυχαίους περιπάτους μέχρι κάθε κελί να είναι μέρος του λαβύρινθου.