Miklix

Máy phát mê cung thuật toán cây phát triển

Đã xuất bản: lúc 21:38:18 UTC 16 tháng 2, 2025
Cập nhật lần cuối: lúc 09:57:45 UTC 6 tháng 3, 2025

Trình tạo mê cung sử dụng thuật toán Growing Tree để tạo ra một mê cung hoàn hảo. Thuật toán này có xu hướng tạo ra các mê cung tương tự như thuật toán Hunt and Kill, nhưng có giải pháp điển hình hơi khác.

Trang này được dịch máy từ tiếng Anh để có thể tiếp cận được với nhiều người nhất có thể. Thật không may, dịch máy vẫn chưa phải là công nghệ hoàn thiện, do đó có thể xảy ra lỗi. Nếu bạn thích, bạn có thể xem phiên bản tiếng Anh gốc tại đây:

Growing Tree Algorithm Maze Generator

Thuật toán Growing Tree rất thú vị vì nó có thể mô phỏng hành vi của một số thuật toán khác, tùy thuộc vào cách chọn ô tiếp theo trong quá trình tạo. Việc triển khai trên trang này sử dụng phương pháp tiếp cận theo chiều rộng, giống như hàng đợi.

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


Tạo mê cung mới








Về thuật toán Growing Tree

Thuật toán Growing Tree là một phương pháp linh hoạt và mạnh mẽ để tạo ra mê cung hoàn hảo. Thuật toán này thú vị vì nó có thể mô phỏng hành vi của một số thuật toán tạo mê cung khác, chẳng hạn như thuật toán Prim, quay lui đệ quy và chia đệ quy, tùy thuộc vào cách bạn chọn ô tiếp theo để xử lý.

Thuật toán Growing Tree hoạt động như thế nào

Bước 1: Khởi tạo

  • Bắt đầu với một lưới các ô chưa được ghé thăm.
  • Chọn một ô bắt đầu ngẫu nhiên và thêm vào danh sách.

Bước 2: Vòng lặp tạo mê cung

  • Trong khi danh sách ô không trống:
    • Chọn một ô từ danh sách dựa trên chiến lược cụ thể (giải thích bên dưới).
    • Khắc một lối đi từ ô đã chọn đến một trong những ô lân cận chưa được ghé thăm (được chọn ngẫu nhiên).
    • Thêm người hàng xóm vào danh sách vì bây giờ họ đã là một phần của mê cung.
    • Nếu ô được chọn không có ô lân cận nào chưa được ghé thăm, hãy xóa ô đó khỏi danh sách.

Bước 3: Chấm dứt

  • Thuật toán kết thúc khi không còn ô nào trong danh sách, nghĩa là toàn bộ mê cung đã được tạo ra.

Chiến lược lựa chọn tế bào (Tính linh hoạt của thuật toán)

Tính năng xác định của thuật toán Growing Tree là cách bạn chọn ô nào để xử lý tiếp theo. Lựa chọn này ảnh hưởng đáng kể đến diện mạo của mê cung:

Cell mới nhất (Hành vi giống như ngăn xếp) – Recursive Backtracker:

  • Luôn chọn ô được thêm gần đây nhất.
  • Tạo ra những hành lang dài, quanh co với nhiều ngõ cụt (giống như mê cung tìm kiếm theo chiều sâu).
  • Mê cung thường có lối đi dài và dễ giải.

Ô ngẫu nhiên (Thuật toán Prim ngẫu nhiên):

  • Chọn một ô ngẫu nhiên từ danh sách mỗi lần.
  • Tạo ra một mê cung phân bố đều hơn với những đường đi phức tạp, rối rắm.
  • Ít hành lang dài hơn và nhiều nhánh hơn.

Tế bào cũ nhất (Hành vi giống hàng đợi):

  • Luôn chọn ô cũ nhất trong danh sách.
  • Tạo ra các mê cung có độ phân bố đồng đều hơn, giống như mô hình tìm kiếm theo chiều rộng.
  • Những lối đi ngắn, rậm rạp với những kết nối dày đặc.
  • (Đây là phiên bản được triển khai tại đây)

Các phương pháp kết hợp:

Kết hợp các chiến lược cho các đặc điểm mê cung khác nhau. Ví dụ:

  • 90% mới nhất, 10% ngẫu nhiên: Nhìn giống như mê cung theo dõi ngược đệ quy, nhưng thỉnh thoảng có các nhánh rẽ ra khỏi hành lang dài.
  • 50% mới nhất, 50% cũ nhất: Cân bằng giữa các hành lang dài với sự phát triển rậm rạp.

Chia sẻ trên BlueskyChia sẻ trên FacebookChia sẻ trên LinkedInChia sẻ trên TumblrChia sẻ trên XChia sẻ trên LinkedInGhim trên Pinterest

Mikkel Bang Christensen

Về tác giả

Mikkel Bang Christensen
Mikkel là người sáng lập và chủ sở hữu của miklix.com. Ông có hơn 20 năm kinh nghiệm làm lập trình viên máy tính/nhà phát triển phần mềm chuyên nghiệp và hiện đang làm việc toàn thời gian cho một tập đoàn CNTT lớn của Châu Âu. Khi không viết blog, ông dành thời gian rảnh rỗi cho nhiều sở thích, thú vui và hoạt động, có thể được phản ánh ở một mức độ nào đó trong nhiều chủ đề được đề cập trên trang web này.