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

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

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

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

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

Ο αλγόριθμος του Eller εισήχθη από τον David Eller.

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

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

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

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

Βήμα 1: Προετοιμασία της πρώτης γραμμής

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

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

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

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

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

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

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

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

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

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

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