Cách Vẽ Mê Cung Đơn Giản

Hôm nay, chúng ta sẽ chế tạo một ứng dụng giải đố mê cung. Ứng dụng hoàn toàn có thể tạo mê cung hình chữ nhật với các hàng cùng cột tùy ý, đôi khi tìm đường truyền của chúng từ lối vào mang lại lối ra. Để góp phần thú vị, ứng dụng cuối cùng cho phép họ đi qua các mê cung bằng cách sử dụng điều phối 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ẽ thực hiện thuật toán săn và giết để sinh sản mê cung và thực hiện thuật toán tìm kiếm theo chiều sâu để xử lý chúng. Shop chúng tôi sử dụng API canvas HTML nhằm vẽ mê cung được tạo thành trên trang web và công ty chúng tôi cũng có thể vẽ những đường dẫn của riêng mình trên canvas HTML.

Ứng dụng được viết bởi Angular / TypeScript. Chúng ta có thể tìm thấy mã mối cung cấp trong kho lưu trữ GitHub của tớ và chơi các câu đố mê cung trên website demo . Phiên bản ghi màn hình dưới đây minh họa cách buổi giao lưu của ứng dụng cuối cùng.

Mê cung với Mô hình

Một mê cung có thể được coi là một lưới những ô. Vào mê cung hình chữ nhật nhị chiều, từng ô gồm tối đa tứ cạnh thay mặt cho những bức tường rất có thể chặn lối đi đến ô khác. Nếu như một ô được liên kết với một ô khác, thì từng ô bao gồm một cạnh bị giảm. Phiên bản phác thảo sau đây minh họa mô hình của những ô và một mê cung.

Những mê cung mà shop chúng tôi sắp chế tạo ra thuộc nhiều loại “mê cung trả hảo”. Một mê cung tuyệt vời nhất là một mê cung không có khu vực vòng lặp cùng không có khu vực không thể tiếp cận. Trong một mê cung hoàn hảo, phần nhiều ô hầu như được liên kết với một ô không giống và luôn luôn có một lối đi duy tốt nhất giữa nhì ô bất kỳ. Trong bài viết này, tuyến phố duy nhất cho một mê cung tuyệt vời và hoàn hảo nhất được hotline là giải pháp .

Trong vận dụng này, một mê cung được quy mô hóa như một Mazelớp bao gồm 1 lưới những ô. Các Mazelớp cần các giá trị cho số lượng hàng cùng cột để desgin một mảng hai chiều của những tế bào. Những chỉ số mảng của một ô cho thấy thêm số hàng với số cột của nó trong lưới. Một ô được mô hình hóa như 1 Celllớp, gồm bốn nằm trong tính Boolean tương ứng cho tứ cạnh của nó. Nếu như một cạnh bị quăng quật đi, thì ô sẽ đặt thuộc tính cạnh đó thành false.

Các đoạn mã sau đây hiển thị những định nghĩa quy mô của Celllớp và Mazelớp.

Trong đoạn mã trên, phương thức Mazekhởi tạo nên lớp đầu tiên khởi tạo những ô cùng với ID hàng với ID cột của chúng, kế tiếp tạo ra cấu tạo mê cung.

Máy chế tạo ra mê cung

Bây giờ bọn họ đã sẵn sàng chuẩn bị để tạo nên mê cung với lưới ô của chính nó được xác minh trước bởi các tham số số hàng với cột. Trong những nhiều thuật toán tạo mê cung (được liệt kê tại chỗ này ), tôi thấy rằng thuật toán săn với giết dễ dàng nắm bắt và dễ thực hiện. Thuật toán psuedo như sau.

Chọn một ô ban đầu ngẫu nhiên.Vào chế độ " giết ". Chọn bỗng nhiên một bạn hàng xóm không được mời từ bỏ ô hiện tại tại. Thải trừ các cạnh thân ô hiện tại và mặt hàng xóm đang chọn, và hàng xóm được chọn sẽ biến chuyển ô hiện tại tại. Lặp lại cho tới khi ô hiện tại không tồn tại hàng xóm ko được mời.Vào chính sách " săn ". Quét lưới để tìm ô chưa truy cập nằm tiếp giáp với ô đã truy cập. Ví như được tìm thấy, hãy kết nối hai ô bằng phương pháp loại bỏ các cạnh gần kề của chúng và nhằm ô trước đây không được trông nom là ô bước đầu mới.Lặp lại công việc 2 với 3 cho đến khi cơ chế “ săn ” quét cục bộ lưới và không kiếm thấy ô nào không được chọn.

tưởng tượng về Thuật toán săn và giết. Hoạt ảnh này là phiên bản ghi màn hình hiển thị 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 dễ dàng để thực hiện. Tuy nhiên, nếu cơ chế săn luôn quét lưới từ trên cùng bên trái sang dưới cùng mặt phải, thì rất có công dụng các mê cung được sinh sản sẽ ngừng với các chiến thuật ưu tiên các hàng bên trên cùng, như sau, vì những 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 bên trên cùng.

Xem thêm: Tác Dụng Của Men Vi Sinh - 10 Khó Tin Đối Với Sức Khỏe

Những các loại mê cung này không thực sự thử thách bởi vì chúng thiếu tính ngẫu nhiên. Để giảm tài năng xuất hiện tại các chiến thuật hàng đầu, chúng ta cũng có thể ngẫu nhiên hóa các hướng quét trong chế độ săn . Câu hỏi triển khai cuối cùng của thuật toán săn với giết được hiển thị mặt dưới.

Trong đoạn mã trên, bọn họ có một mảng ID mặt hàng được xáo trộn cùng một mảng ID cột được xáo trộn đến huntAndKill()phương thức quét mê cung. Bằng cách này, Mazelớp rất có thể tạo ra một mê cung ngẫu nhiên trẻ trung và tràn trề sức khỏe với con số hàng và cột.

Có thể có một vài tối ưu hóa đến huntAndKill()phương pháp, nhưng mà việc thực thi hiện tại là đầy đủ để tạo mê cung được hiển thị trong cửa sổ trình duyệt.

Maze Solver

Nếu bọn họ có một mê cung hoàn hảo với cấu tạo 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 mặt trái hoặc quy tắc bên phải , để xử lý mê cung. Phương diện khác, nếu chúng ta biết chi tiết về kết cấu mê cung, thì bạn có thể sử dụng thuật toán tìm kiếm theo chiều sâu ( links ) để trải qua mê cung thân hai ô bất kỳ.

Ở đây, ứng dụng của công ty chúng tôi đã biết toàn bộ cấu trúc của mê cung được tạo, vì chưng 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 tới khi dành được mục tiêu. Đoạn mã sau cho thấy thêm một xúc tiến mẫu.

Các findPath()dụng cụ cách thức tìm kiếm bắt đầu từ ô thứ nhất và chấm dứt với ô cuối cùng, cùng trả về một mảng của những tế bào thay mặt cho các chiến thuật cho những mê cung, có nghĩa là con mặt đường từ ô đầu tiên đến ô cuối cùng.

Vẽ Mê cung trên Canvas

Với tất cả các quy mô đã được thiết lập, công ty chúng tôi đã sẵn sàng chuẩn bị để vẽ một mê cung bên trên canvas HTML. Trước tiên, công ty chúng tôi thêm một trong những phần tử canvas trong chủng loại HTML, như sau.

Sau đó, bọn chúng tôi tùy chỉnh chiều rộng lớn và chiều cao của canvas dựa trên form size của mê cung ước muốn và vẽ toàn bộ các ô trên canvas. Đoạn mã sau là một trong ví dụ về triển khai trong một thành phần Angular. Vì các API phiên bản vẽ canvas HTML là khung cấp thiết biết được, bạn sẽ có thể gửi mã sang những ứng dụng sử dụng những khung JavaScript khác.

Phương pháp vẽ đường dẫn mê cung khôn cùng giống với đoạn mã trên, do vậy tôi vẫn không mở rộng các bạn dạng vẽ sinh hoạt đây.

Để thêm một số giá trị giải trí, áp dụng demo phản hồi những sự khiếu nại bàn phím, để tín đồ dùng hoàn toàn có thể điều hướng bao phủ mê cung bằng các phím mũi tên. Chúng ta có thể dùng demo trên website demo này .

Câu đố mê cung là một trong trò chơi thú vị và là một dự án phụ tiện lợi để tò mò điều nào đó về canvas. Để nắm tắt hành trình dài của cửa hàng chúng tôi trong nội dung bài viết này, shop chúng tôi đã nhắc đến các chủ đề về xây dựng mô hình mê cung, chế tạo mê cung bằng phương pháp sử dụng thuật toán săn với 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 bên trên canvas HTML.

Đó là toàn bộ cho ngày hôm nay. Một đợt nữa, bạn có thể kiểm tra mã mối cung cấp từ kho lưu trữ GitHub của mình . Cảm ơn vì đã đọc.