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

Thuật toán Eller là một thuật toán tạo mê cung hiệu quả, tạo ra các mê cung hoàn hảo (mê cung không có vòng lặp và chỉ có một đường đi giữa hai điểm bất kỳ) bằng cách tiếp cận từng hàng một. Nó tạo ra các mê cung tương tự như thuật toán Kruskal, nhưng chỉ tạo ra từng hàng một, mà không cần lưu trữ toàn bộ mê cung trong bộ nhớ. Điều này 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 có tài nguyên hạn chế và để tạo nội dung theo quy trình.

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 đó.

Giới thiệu về thuật toán Eller

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

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

Cách thuật toán Eller hoạt động để tạo mê cung

Thuật toán 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 tính liên thông đồng thời tránh các 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 các 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 mã định danh duy nhất.

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

• Hợp nhất ngẫu nhiên các ô liền kề bằng cách gán cho chúng cùng một ID tập hợp. Điều này đảm bảo có các lối đi ngang.

Bước 3: Tạo kết nối dọc vớ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 được kết nối xuống dưới (để đảm bảo tính liên thông).
• Chọn ngẫu nhiên một hoặc nhiều ô từ mỗi nhóm để kết nối với hàng tiếp theo.

Bước 4: Chuyển sang hàng tiếp theo

• Tiếp tục duy trì các kết nối 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 bộ dữ liệu 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 hoàn thành hàng cuối cùng.

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

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

• Hãy đảm bảo tất cả các ô trong hàng cuối cùng thuộc cùng một tập hợp bằng cách hợp nhất bất kỳ tập hợp riêng biệt nào còn lại.

Đọc thêm

Nếu bạn thích bài viết này, bạn cũng có thể thích những gợi ý sau:

• Máy phát mê cung thuật toán cây phát triển
• Máy phát mê cung săn và giết
• Máy phát mê cung thuật toán Kruskal