Trình tạo mê cung thuật toán của Eller

Thuật toán Eller là thuật toán tạo mê cung có thể tạo ra các mê cung hoàn hảo (mê cung không có vòng lặp và một đường đi duy nhất giữa hai điểm bất kỳ) một cách hiệu quả bằng cách sử dụng phương pháp tiếp cận từng hàng. Thuật toán này tạo ra các mê cung tương tự như thuật toán Kruskal, nhưng nó thực hiện bằng cách chỉ tạo ra một hàng tại một thời điểm, mà không cần lưu trữ toàn bộ mê cung trong bộ nhớ. Điều đó làm cho nó hữu ích để tạo ra các mê cung rất lớn trên các hệ thống rất hạn chế và để tạo nội dung theo thủ tục.

Một mê cung hoàn hảo là một mê cung mà chỉ có đúng một đường đi từ bất kỳ điểm nào trong mê cung đến bất kỳ điểm nào khác. Điều đó có nghĩa là bạn không thể đi vòng tròn, nhưng bạn sẽ thường gặp ngõ cụt, buộc bạn phải quay lại và quay trở lại.

Bản đồ mê cung được tạo ở đây bao gồm một phiên bản mặc định không có bất kỳ vị trí bắt đầu và kết thúc nào, vì vậy bạn có thể tự quyết định: sẽ có một giải pháp từ bất kỳ điểm nào trong mê cung đến bất kỳ điểm nào khác. Nếu bạn muốn có cảm hứng, bạn có thể bật vị trí bắt đầu và kết thúc được đề xuất - và thậm chí xem giải pháp giữa hai điểm đó.

Về thuật toán của Eller

Thuật toán Eller được giới thiệu bởi David Eller.

Thuật toán này đáng chú ý vì cách tiếp cận hàng-theo-hàng hiệu quả để tạo mê cung, khiến nó trở nên lý tưởng cho các mê cung vô hạn hoặc mê cung được tạo theo thời gian thực. Nó thường được trích dẫn trong tài liệu về tạo nội dung theo thủ tục và tạo mê cung, nhưng tôi không thể tìm thấy các nguồn chính nêu chi tiết ấn phẩm gốc của nó.

Thuật toán của Eller hoạt động như thế nào để tạo ra mê cung

Thuật toán của Eller xử lý từng hàng một, duy trì và sửa đổi các tập hợp ô được kết nối. Nó đảm bảo kết nối trong khi tránh vòng lặp và mở rộng mê cung xuống phía dưới một cách hiệu quả.

Về mặt lý thuyết, nó có thể được sử dụng để tạo ra những mê cung vô hạn, tuy nhiên để đảm bảo rằng mê cung được tạo ra thực sự có thể giải được, cần phải chuyển sang logic "hàng cuối cùng" tại một thời điểm nào đó để hoàn thành mê cung.

Bước 1: Khởi tạo hàng đầu tiên

• Gán cho mỗi ô trong hàng một ID tập hợp duy nhất.

Bước 2: Nối một số ô kề nhau theo chiều ngang

• Ngẫu nhiên hợp nhất các ô liền kề bằng cách đặt chúng vào cùng một ID tập hợp. Điều này đảm bảo rằng có các đoạn ngang.

Bước 3: Tạo kết nối theo chiều dọc tới hàng tiếp theo

• Đối với mỗi tập hợp xuất hiện trong hàng, ít nhất một ô phải kết nối xuống phía dưới (để đảm bảo kết nối).
• Chọn ngẫu nhiên một hoặc nhiều ô từ mỗi bộ để kết nối với hàng tiếp theo.

Bước 4: Di chuyển đến hàng tiếp theo

• Tiếp tục các kết nối theo chiều dọc bằng cách gán cùng một ID tập hợp cho các ô tương ứng bên dưới.
• Gán ID tập hợp mới cho bất kỳ ô nào chưa được gán.

Bước 5: Lặp lại các bước 2–4 cho đến khi đạt đến hàng cuối cùng

• Tiếp tục xử lý từng hàng.

Bước 6: Xử lý hàng cuối cùng

• Đảm bảo tất cả các ô ở hàng cuối cùng đều thuộc cùng một tập hợp bằng cách hợp nhất mọi tập hợp riêng biệt còn lại.