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

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

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

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

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

Ο Αλγόριθμος του Έλερ εισήχθη από τον Ντέιβιντ Έλερ.

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

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

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

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

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

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

Βήμα 2: Ενώστε μερικά γειτονικά κελιά οριζόντια

• Συγχωνεύστε τυχαία γειτονικά κελιά ορίζοντας τα στο ίδιο αναγνωριστικό συνόλου. Αυτό διασφαλίζει ότι υπάρχουν οριζόντια περάσματα.

Βήμα 3: Δημιουργήστε κάθετες συνδέσεις στην επόμενη σειρά

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

Βήμα 4: Μετακίνηση στην επόμενη σειρά

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

Βήμα 5: Επαναλάβετε τα βήματα 2–4 μέχρι να φτάσετε στην τελευταία σειρά

• Συνεχίστε την επεξεργασία γραμμή προς γραμμή.

Βήμα 6: Επεξεργαστείτε την τελική σειρά

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

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

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

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