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

Hôm nay, họ 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 và cột tùy ý, mặt khác tìm băng thông của bọn chúng từ lối vào mang lại lối ra. Để thêm phần thú vị, ứng dụng sau cùng cho phép chúng ta đi qua những 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 để chế tác 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. Shop chúng tôi sử dụng API canvas HTML nhằm vẽ mê cung được tạo trên website và cửa hàng chúng tôi cũng hoàn toàn có thể vẽ những đường dẫn của riêng bản thân trên canvas HTML.

Ứng dụng được viết bằng Angular / TypeScript. Bạn có thể tìm thấy mã mối cung cấp trong kho tàng trữ GitHub của mình và chơi các câu đố mê cung trên trang web demo . Bạn dạng ghi màn hình dưới đây minh họa cách hoạt động của ứng dụng cuối cùng.


*

Mê cung cùng Mô hình

Một mê cung rất có thể được xem như là một lưới các ô. Trong mê cung hình chữ nhật nhì chiều, mỗi ô tất cả tối đa bốn cạnh đại diện thay mặt cho những bức tường có thể chặn lối đi đến ô khác. Trường hợp 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 dạng phác thảo sau đây minh họa mô hình của các ô cùng một mê cung.


*

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

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

Các đoạn mã dưới đâ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, cách thức Mazekhởi làm cho lớp trước hết khởi tạo các ô với ID hàng và ID cột của chúng, tiếp đến tạo ra cấu tạo mê cung.

Máy sinh sản mê cung

Bây giờ bọn họ đã sẵn sàng để sinh sản mê cung cùng với lưới ô của chính nó được xác minh trước bởi những tham số số hàng với cột. Trong những nhiều thuật toán tạo ra mê cung (được liệt kê ở đâ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ễ dàng thực hiện. Thuật toán psuedo như sau.

Chọn một ô ban đầu ngẫu nhiên.Vào chính sách " giết ". Chọn tình cờ một bạn hàng xóm không được mời từ ô hiện tại. Loại trừ các cạnh thân ô lúc này và sản phẩm xóm vẫn chọn, cùng hàng làng mạc được lựa chọn sẽ biến hóa ô hiện tại. Lặp lại cho đến khi ô hiện tại tại không có hàng xóm không được mời.Vào chính sách " săn ". Quét lưới nhằm tìm ô chưa truy cập nằm liền kề với ô đã truy cập. Giả dụ được kiếm tìm thấy, hãy liên kết hai ô bằng phương pháp loại bỏ các cạnh gần kề của chúng và để ô trước đây không được lưu ý là ô ban đầu mới.Lặp lại công việc 2 cùng 3 cho tới khi chế độ “ săn ” quét tổng thể 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ới giết. Hoạt hình ảnh này là bạn dạng 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 luôn quét lưới từ trên cùng phía bên trái sang dưới cùng bên phải, thì rất có tác dụng các mê cung được tạo sẽ xong xuôi với các phương án ưu tiên các hàng trên cùng, như sau, vì các hàng trên thuộc được liên kết sớm hơn thời hạn trong đệ quy săn với giết .


*
nhì mê cung có giải mã (màu xanh lam) ưu tiên các hàng trên cùng.

Xem thêm: Kệ Trưng Bày Giày Dép Thanh Lý Kệ Trưng Bày Giày Dép Hà Nội, Hcm Giá Rẻ


Những nhiều loại mê cung này không thực sự thử thách vì chưng chúng thiếu hụt tính ngẫu nhiên. Để giảm kỹ 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 những hướng quét trong cơ chế săn . Việc triển khai sau cùng của thuật toán săn cùng 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 mặt hàng được xới trộn với một mảng ID cột được xới trộn mang lại huntAndKill()phương thức quét mê cung. Bằng cách này, Mazelớp hoàn toàn có thể tạo ra một mê cung ngẫu nhiên mạnh khỏe với số lượng 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 hiện hiện trên là đủ để chế tác mê cung được hiển thị trong hành lang cửa số trình duyệt.

Maze Solver

Nếu họ có một mê cung hoàn hảo với kết cấu không xác định, thì bạn cũng có thể sử dụng thuật toán theo dõi bức tường ( liên kết ), có cách gọi khác là quy tắc mặt trái hoặc quy tắc bên phải , để giải quyết và xử lý mê cung. Khía cạnh khác, nếu họ biết chi tiết về cấu tạo mê cung, thì bạn 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 thân hai ô bất kỳ.

Ở đây, áp dụng của cửa hàng chúng tôi đã biết toàn bộ kết cấu của mê cung được tạo, vì chưng vậy công ty 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 ô không được duyệt cho tới khi giành được mục tiêu. Đoạn mã sau cho biết một thực thi mẫu.

Các findPath()dụng cụ cách thức tìm kiếm ban đầu từ ô thứ nhất và ngừng với ô cuối cùng, và trả về một mảng của những tế bào đại diện thay mặt cho các giải pháp cho các mê cung, tức là con mặt đường từ ô thứ nhất đế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, chúng tôi đã chuẩn bị sẵn sàng để vẽ một mê cung trên canvas HTML. Trước tiên, cửa hàng chúng tôi thêm 1 phần tử canvas trong chủng loại HTML, như sau.

Sau đó, chúng tôi thiết lập cấu hình chiều rộng và độ cao của canvas dựa trên size của mê cung mong muốn và vẽ tất cả các ô bên trên canvas. Đoạn mã sau là 1 trong ví dụ về thực hiện trong một yếu tắc Angular. Vì các API bạn dạng vẽ canvas HTML là khung không thể biết được, bạn sẽ có thể chuyển mã sang những ứng dụng sử dụng các khung JavaScript khác.

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

Để thêm một số giá trị giải trí, vận dụng demo phản bội hồi các sự khiếu nại bàn phím, để fan dùng hoàn toàn 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 trong những trò đùa thú vị và là một trong những dự án phụ thuận lợi để khám phá điều nào đấy về canvas. Để bắt tắt hành trình của công ty chúng tôi trong bài viết này, cửa hàng chúng tôi đã đề cập đến những chủ đề về xây dựng mô hình mê cung, chế tạo mê cung bằng cách sử dụng thuật toán săn và giết , xử lý mê cung bằng thuật toán tìm kiếm theo chiều sâu với vẽ mê cung trên canvas HTML.

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