Tạo một Đa giác 2D Lõm Ngẫu nhiên Cảnh JavaScript

Question

Tôi đang viết một bản sao hạ cánh mặt trăng đơn giản trong JavaScript (http://www.isogenicengine.com/demos/1.1.0/lander/) và thay vì cảnh quan cơ bản chỉ có mức cao và thấp, tôi muốn một thuật toán tạo ra các hang giống ngẫu nhiên không gian. Cho một khu vực hình chữ nhật để làm việc với [0, 0, 1920, 1200] thuật toán sẽ có thể tạo ra một cái gì đó giống như hình ảnh dưới đây. Lý tưởng nhất là bất kỳ "lối vào" nào vào khu vực hang động nên có chiều rộng đặt để người hạ cánh có thể nhận được "bên trong" nó.

Tôi đã cho rằng điều này có thể không thực hiện được và rằng tôi thay vì có thể chỉ cần vẽ một loạt các hình ảnh như trên và chuyển đổi dữ liệu pixel vào dữ liệu đa giác thô, nhưng nó sẽ là cách mát để có mức độ được tạo ngẫu nhiên!

Đối với điểm thưởng siêu hardcore, khả năng xác định số lượng cấu trúc giống như hang động sẽ tuyệt vời hơn nữa.

Đầu ra của thuật toán sẽ là một mảng điểm, mỗi điểm là đối tượng chứa thuộc tính x và y {x: val, y: val} khi bạn vẽ liên tục giữa điểm hiện tại và điểm tiếp theo, tạo nên đa giác.

Nếu ai đó có triển khai JavaScript về nội dung nào đó tương tự cũng sẽ giúp ích rất nhiều!

Answer 1

Bắt đầu với việc tìm hiểu sơ đồ bong bóng là gì khi được sử dụng trong kiến ​​trúc. Đó là một sơ đồ tôpô của một không gian, với các bong bóng là các khoảng trắng và các đường để biểu diễn các lối đi. Tôi không tìm thấy bất kỳ trang web tuyệt vời nào để giới thiệu nhanh, nhưng việc tìm kiếm hình ảnh mang lại rất nhiều ví dụ.

Sơ đồ bong bóng có thể được coi là biểu đồ có bong bóng làm đỉnh. Trong ví dụ của bạn, mô hình hóa "bầu trời", đốm màu bao gồm cạnh trên cùng, như một đỉnh. Hang động là một đỉnh khác và lối vào là một cạnh. Với quan điểm này, thật dễ dàng để tạo ra sự phức tạp giống như hang động như bạn muốn.

Bí quyết tiếp theo là biến nó thành hình học. Về cơ bản, bạn muốn đẩy ra khỏi bộ xương của biểu đồ và tạo khoảng trống nơi người chơi có thể điều hướng. Đồng thời, bạn muốn chắc chắn rằng những khoảng trống không đẩy ra quá xa và mỏng ra hoặc loại bỏ các bức tường. Vì vậy, bạn cũng cần phải mô hình hóa khu vực rắn và được thực hiện với dual graph. Đồ thị kép đi "bên dưới" bản gốc, theo nghĩa là các giao điểm cạnh đại diện cho xung đột được giải quyết có lợi cho void trên solid.

Tóm tắt: (1) Tạo biểu đồ tôpô với các tính năng bạn muốn. (2) Tạo hình học cho đồ thị, gán một vị trí cho mỗi đỉnh và một đường dẫn đến mỗi cạnh. (3) Xây dựng một đồ thị kép và gán hình của nó. (4) Khai thác không gian liên kết với mỗi biểu đồ bằng cách phát triển chúng ra ngoài, giải quyết các xung đột có lợi cho đoạn văn thay vì tắc nghẽn.

Bạn có thể muốn thuyết phục bản thân rằng danh sách chu vi của hình học cuối cùng có thể được tạo ra bằng cách di chuyển nửa cạnh của biểu đồ, giống như đi một mê cung bằng một tay trên tường.

Answer 2

Diễu hành Hình vuông có thể được sử dụng, nếu bạn quan tâm, để biến trường giá trị vô hướng 2D (có thể được lấy từ Perlin hoặc Simplex Noise) thành một tập hợp các đường cạnh. Tất nhiên, những gì mà kết thúc lên trông giống như sẽ phụ thuộc vào chính xác làm thế nào bạn nhận được các giá trị vô hướng trường 2D (cách bạn thao tác Perlin hoặc Simplex Noise).

This là trang web tốt nhất mà tôi có thể tìm thấy để xem xét kỹ các chi tiết.(Nó không được ghi chép đầy đủ ở đó như Marching Cubes, 3D twin của nó)

Trên thực tế, trang Wiki trên đó là khá tốt.