Hôm nay, chúng ta sẽ tạo một ứng dụng giải đố mê cung. Ứng dụng có thể tạo mê cung hình chữ nhật với các hàng và cột tùy ý, đồng thời tìm đường dẫn của chúng từ lối vào đến lối ra. Để thêm phần thú vị, ứng dụng cuối cùng cho phép chúng ta đi qua các mê cung bằng cách sử dụng điều hướng bàn phím hoặc nhấp chuột.Bạn đang xem: Cách vẽ mê cung đơn giản
Chúng tôi sẽ sử dụng thuật toán săn và giết để tạo mê cung và sử dụng thuật toán tìm kiếm theo chiều sâu để giải quyết chúng. Chúng tôi sử dụng API canvas HTML để vẽ mê cung được tạo trên trang web và chúng tôi cũng có thể vẽ các đường dẫn của riêng mình trên canvas HTML.
Ứng dụng được viết bằng Angular / TypeScript. Bạn có thể tìm thấy mã nguồn trong kho lưu trữ GitHub của tôi và chơi các câu đố mê cung trên trang web demo . Bản ghi màn hình sau đây minh họa cách hoạt động của ứng dụng cuối cùng.
Mê cung và Mô hình
Một mê cung có thể được coi là một lưới các ô. Trong mê cung hình chữ nhật hai chiều, mỗi ô có tối đa bốn cạnh đại diện cho các bức tường có thể chặn đường đi đến ô khác. Nếu một ô được kết nối với một ô khác, thì mỗi ô có một cạnh bị giảm. Bản phác thảo sau đây minh họa mô hình của các ô và một mê cung.
Những mê cung mà chúng tôi sắp tạo thuộc loại “mê cung hoàn hảo”. Một mê cung hoàn hảo là một mê cung không có khu vực vòng lặp và không có khu vực không thể tiếp cận. Trong một mê cung hoàn hảo, mọi ô đều được kết nối với một ô khác và luôn có một đường đi duy nhất giữa hai ô bất kỳ. Trong bài viết này, con đường duy nhất cho một mê cung hoàn hảo được gọi là giải pháp .
Trong ứng dụng này, một mê cung được mô hình hóa như một Mazelớp bao gồm một lưới các ô. Các Mazelớp cần các giá trị cho số lượng hàng và cột để xây dựng một mảng hai chiều của các tế bào. Các chỉ số mảng của một ô cho biết số hàng và số cột của nó trong lưới. Một ô được mô hình hóa như một Celllớp, có bốn thuộc tính Boolean tương ứng cho bốn cạnh của nó. Nếu một cạnh bị bỏ đi, thì ô sẽ đặt thuộc tính cạnh đó thành false.
Các đoạn mã sau đây hiển thị các định nghĩa mô hình của Celllớp và Mazelớp.
Trong đoạn mã trên, phương thức Mazekhởi tạo cho lớp trước tiên khởi tạo các ô với ID hàng và ID cột của chúng, sau đó tạo ra cấu trúc mê cung.
Máy tạo mê cung
Bây giờ chúng ta đã sẵn sàng để tạo mê cung với lưới ô của nó được xác định trước bởi các tham số số hàng và cột. Trong số nhiều thuật toán tạo mê cung (được liệt kê ở đây ), tôi thấy rằng thuật toán săn và giết rất dễ hiểu và dễ thực hiện. Thuật toán psuedo như sau.
Chọn một ô bắt đầu ngẫu nhiên.Vào chế độ ” giết “. Chọn ngẫu nhiên một người hàng xóm không được mời từ ô hiện tại. Loại bỏ các cạnh giữa ô hiện tại và hàng xóm đã chọn, và hàng xóm được chọn sẽ trở thành ô hiện tại. Lặp lại cho đến khi ô hiện tại không có hàng xóm không được mời.Vào chế độ ” săn “. Quét lưới để tìm ô chưa truy cập nằm liền kề với ô đã truy cập. Nếu được tìm thấy, hãy kết nối hai ô bằng cách loại bỏ các cạnh liền kề của chúng và để ô trước đây không được duyệt là ô bắt đầu mới.Lặp lại các bước 2 và 3 cho đến khi chế độ “ săn ” quét toàn bộ lưới và không tìm thấy ô nào chưa được chọn. Hình dung về Thuật toán săn và giết. Hoạt ảnh này là bản ghi màn hình tiện ích JavaScript từ Buckblog của Jamis Buck (liên kết)
Các hunt-và-diệt thuật toán là khá đơn giản để thực hiện. Tuy nhiên, nếu chế độ săn luôn quét lưới từ trên cùng bên trái sang dưới cùng bên phải, thì rất có khả năng các mê cung được tạo sẽ kết thúc với các giải pháp ưu tiên các hàng trên cùng, như sau, vì các hàng trên cùng được kết nối sớm hơn thời gian trong đệ quy săn và giết .
Hai mê cung có lời giải (màu xanh lam) ưu tiên các hàng trên cùng.Xem thêm: Cách Làm Vương Miện Bằng Ống Hút, Cách Làm Vương Miện Handmade
Những loại mê cung này không quá thử thách vì chúng thiếu tính ngẫu nhiên. Để giảm khả năng xuất hiện các giải pháp hàng đầu, chúng ta có thể ngẫu nhiên hóa các hướng quét trong chế độ săn . Việc triển khai cuối cùng của thuật toán săn và giết được hiển thị bên dưới.
Trong đoạn mã trên, chúng ta có một mảng ID hàng được xáo trộn và một mảng ID cột được xáo trộn cho huntAndKill()phương thức quét mê cung. Bằng cách này, Mazelớp có thể tạo ra một mê cung ngẫu nhiên mạnh mẽ với số lượng hàng và cột.
Có thể có một số tối ưu hóa cho huntAndKill()phương pháp, nhưng việc triển khai hiện tại là đủ để tạo mê cung được hiển thị trong cửa sổ trình duyệt.
Maze Solver
Nếu chúng ta có một mê cung hoàn hảo với cấu trúc không xác định, thì chúng ta có thể sử dụng thuật toán theo dõi bức tường ( liên kết ), còn được gọi là quy tắc bên trái hoặc quy tắc bên phải , để giải quyết mê cung. Mặt khác, nếu chúng ta biết chi tiết về cấu trúc mê cung, thì chúng ta có thể sử dụng thuật toán tìm kiếm theo chiều sâu ( liên kết ) để đi qua mê cung giữa hai ô bất kỳ.
Ở đây, ứng dụng của chúng tôi đã biết toàn bộ cấu trúc của mê cung được tạo, vì vậy chúng tôi sẽ áp dụng thuật toán tìm kiếm theo chiều sâu , thuật toán này chỉ đơn giản lặp lại qua các ô chưa được duyệt cho đến khi đạt được mục tiêu. Đoạn mã sau cho thấy một triển khai mẫu.
Các findPath()dụng cụ phương pháp tìm kiếm bắt đầu từ ô đầu tiên và kết thúc với ô cuối cùng, và trả về một mảng của các tế bào đại diện cho các giải pháp cho các mê cung, tức là con đường từ ô đầu tiên đến ô cuối cùng.
Vẽ Mê cung trên Canvas
Với tất cả các mô hình đã được thiết lập, chúng tôi đã sẵn sàng để vẽ một mê cung trên canvas HTML. Trước tiên, chúng tôi thêm một phần tử canvas trong mẫu HTML, như sau.
Sau đó, chúng tôi thiết lập chiều rộng và chiều cao của canvas dựa trên kích thước của mê cung mong muốn và vẽ tất cả các ô trên canvas. Đoạn mã sau là một ví dụ về triển khai trong một thành phần Angular. Vì các API bản vẽ canvas HTML là khung không thể biết được, bạn sẽ có thể chuyển mã sang các ứng dụng sử dụng các khung JavaScript khác.
Phương pháp vẽ đường dẫn mê cung rất giống với đoạn mã trên, vì vậy tôi sẽ không mở rộng các bản vẽ ở đây.
Để thêm một số giá trị giải trí, ứng dụng demo phản hồi các sự kiện bàn phím, để người dùng có thể điều hướng xung quanh mê cung bằng các phím mũi tên. Bạn có thể dùng thử trên trang web demo này .
Câu đố mê cung là một trò chơi thú vị và là một dự án phụ dễ dàng để tìm hiểu điều gì đó về canvas. Để tóm tắt hành trình của chúng tôi trong bài viết này, chúng tôi đã đề cập đến các chủ đề về xây dựng mô hình mê cung, tạo mê cung bằng cách sử dụng thuật toán săn và giết , giải quyết mê cung bằng thuật toán tìm kiếm theo chiều sâu và vẽ mê cung trên canvas HTML.Xem thêm: #1 Cách Cài Đặt Chế Độ Theo Dõi Trên Facebook, Bật, Cách Bật Chế Độ Theo Dõi Trên Facebook
Đó là tất cả cho ngày hôm nay. Một lần nữa, bạn có thể kiểm tra mã nguồn từ kho lưu trữ GitHub của tôi . Cảm ơn vì đã đọc.