Γεννήτρια λαβυρίνθου και παιχνίδι

Πώς να χρησιμοποιήσετε τη γεννήτρια λαβυρίνθου

1. Ορίστε το Πλάτος (στήλες) και το Ύψος (γραμμές), από 4 έως 60 κελιά το καθένα, και επιλέξτε Αλγόριθμος. Πατήστε Νέος λαβύρινθος.
2. Η θέση σας είναι η τελεία στην πράσινη είσοδο πάνω αριστερά. Φτάστε στην κόκκινη έξοδο κάτω δεξιά.
3. Κινηθείτε με τα πλήκτρα βελών ή με WASD. Κρατήστε πατημένο το Shift μαζί με ένα βέλος για να τρέξετε σε έναν διάδρομο μέχρι τον επόμενο κόμβο. Σε κινητό ή tablet, σύρετε το δάχτυλο πάνω στον λαβύρινθο για να τρέξετε προς αυτή την κατεύθυνση, ή αγγίξτε τα κουμπιά βελών κάτω από αυτόν για μεμονωμένα βήματα.
4. Ο χρονομέτρης ξεκινά με την πρώτη σας κίνηση και σταματά στην έξοδο. Το ίχνος σας σχεδιάζεται πίσω σας· αν περάσετε ξανά από πάνω του, σβήνεται, ώστε να δείχνει πάντα τη διαδρομή που ακολουθείτε.
5. Κολλήσατε; Το Εμφάνιση λύσης σχεδιάζει τη συντομότερη διαδρομή από το σημείο όπου βρίσκεστε μέχρι την έξοδο. Το Πίσω στην αρχή σας βάζει ξανά στην είσοδο και μηδενίζει τον χρόνο.
6. Για να παίξετε σε χαρτί, πατήστε Εκτύπωση ή Λήψη PDF. Επιλέξτε πρώτα Προσθήκη σελίδας με τη λύση αν θέλετε την απάντηση σε δεύτερη σελίδα.

Μοιραστείτε έναν λαβύρινθο με τον κωδικό του

Κάθε λαβύρινθος έχει έναν Κωδικό λαβυρίνθου όπως ο b20x15-k3j9x2: το γράμμα του αλγορίθμου (b, p ή k), το πλάτος × ύψος και έναν τυχαίο σπόρο. Ο ίδιος κωδικός ξαναχτίζει πάντα ακριβώς τον ίδιο λαβύρινθο σε οποιαδήποτε συσκευή, οπότε μπορείτε να προκαλέσετε έναν φίλο να νικήσει τον χρόνο σας στην ίδια διάταξη. Πληκτρολογήστε ή επικολλήστε έναν κωδικό και πατήστε Φόρτωση κωδικού, ή χρησιμοποιήστε το Αντιγραφή συνδέσμου για να μοιραστείτε μια διεύθυνση που ανοίγει απευθείας εκείνον τον λαβύρινθο.

Οι τρεις αλγόριθμοι δημιουργίας

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

• Η Αναδρομική οπισθοδρόμηση (μακριοί διάδρομοι) περπατά τυχαία από κελί σε κελί γκρεμίζοντας τοίχους και γυρνά πίσω όταν φτάσει σε αδιέξοδο. Δίνει μακριά, ελικοειδή περάσματα με λίγες διακλαδώσεις: η λύση είναι συνήθως μακριά και διασχίζει το μεγαλύτερο μέρος του πλέγματος.
• Ο Prim (πολλά κοντά αδιέξοδα) μεγαλώνει τον λαβύρινθο προς τα έξω από ένα τυχαίο κελί, προσθέτοντας κάθε φορά ένα τυχαίο κελί του μετώπου. Παίρνετε πολλά κοντά πλαϊνά κλαδιά, που κάνουν τον λαβύρινθο να φαίνεται πολυάσχολος αλλά την κύρια διαδρομή πιο ευδιάκριτη.
• Ο Kruskal (ομοιόμορφος, με διακλαδώσεις) αφαιρεί τυχαία επιλεγμένους τοίχους ανάμεσα σε κελιά που δεν είναι ήδη συνδεδεμένα (με παρακολούθηση μέσω δομής union-find). Το αποτέλεσμα έχει ομοιόμορφες διακλαδώσεις παντού, χωρίς ορατό σημείο εκκίνησης.

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

Πώς βρίσκεται η λύση

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

Συμβουλές εκτύπωσης

Οι εκτυπωμένες εκδόσεις και τα PDF σχεδιάζουν καθαρούς μαύρους τοίχους σε λευκό φόντο, με τον κωδικό του λαβυρίνθου στον τίτλο ώστε να βρείτε ξανά τον ίδιο λαβύρινθο. Μεγέθη γύρω στα 15 × 15 ταιριάζουν σε μικρά παιδιά· από 30 × 30 και πάνω γίνεται σοβαρό παζλ για ενήλικες. Οι πολύ μεγάλοι λαβύρινθοι (50 × 60) έχουν στενούς διαδρόμους σε σελίδα A4, γι’ αυτό εκτυπώστε τους σε πλήρες μέγεθος σελίδας.