Lập bản đồ bản đồ chiều cao sang một định dạng đường viền lưới dựa trên

Question

Tôi có một bản đồ chiều cao 2D theo định dạng sau

06 36 39 42 43 55 ... 
37 40 43 43 45 46 ... 
40 43 44 45 46 48 ... 
44 44 46 47 48 50 ... 
41 44 45 47 48 48 ... 
... 

Và tôi cần phải remap nó sang một định dạng đường viền nụ cười dựa (vì vậy nó có thể tiếp tục được ánh xạ vào sprites)

. . . . | . . 
. . . . \ . . 
. . .// . . 
. . . | . . . 
. . . | . . . 
./-/. . . 

đây . nghĩa khu vực bằng phẳng, | và - vách đá thẳng, / và \ góc vách đá (mỗi đại diện cho 2 khả năng khác nhau).

Tôi đã thử phương pháp tiếp cận hình vuông hành quân tiêu chuẩn, nhưng thấy rằng chỉ lấy mẫu 3 hàng xóm dẫn đến khá nhiều vấn đề, do quá tải các trường hợp lân cận. (Lưu ý các vách đá thẳng đứng ngoài không gian)

. . . . | . \ 
. . . . \ \ . 
. . .// - . 
. . . | - . . 
. . . | . . . 
./-/. . . 

Điều tôi muốn, là một số tham chiếu đến các thuật toán/phương pháp giúp giải quyết vấn đề này. Tôi biết rằng đường viền đi bộ với một số loại chiều sâu tìm kiếm đầu tiên là một lựa chọn nhưng chưa thử nó ra, và muốn rời khỏi đó như là một phương sách cuối cùng. Ngoài ra còn có các câu hỏi về biểu diễn một số tính năng, ví dụ như có bao gồm các vách đá vách đá dày 1 phần tử hay chỉ bỏ qua chúng. Một tùy chọn khác là chuyển qua các đường bao được tạo ra và thay đổi chúng để chúng có thể vừa vặn với nhau, nhưng điều này có vẻ thực sự khó khăn ...

Answer 1

Tạo một hàm nội suy/phù hợp nhất. Mô hình của bạn phải là đa thức 2D (trong x và y) có mức độ "vừa phải": không quá cao khiến bạn sẽ vượt quá mọi thứ, nhưng không quá thấp để bạn mất chi tiết.

Bây giờ bạn có chức năng toán học mà bạn có thể cắt, bằng cách đặt f(x,y) = height. Giải pháp cho phương trình này là một đường bao. Bây giờ bạn có hai lựa chọn, tùy thuộc vào việc bạn có thể giải quyết một cách phân tích hay không.

• Giả sử bạn không thể phân tích giải quyết, bạn vẫn có thể dễ dàng truy ra một xấp xỉ của đường cong:
  • Bắt đầu bằng cách tô đầy lên cái lưới màu trắng nếu f(x,y)>height và đen nếu f(x,y)<height. Lưu ý tất cả các vùng "chuyển tiếp" nơi có chuyển đổi màu đen trắng trong khoảng cách khoảng < 1: đây là các ô vuông đường bao sẽ nằm.
  • Chọn ngẫu nhiên một hình vuông chuyển tiếp và tìm kiếm trong khoảng < 1 bán kính lưới cho f(x,y)==height, để tìm một điểm trên đường bao. Tại thời điểm đó (không nhất thiết phải trên lưới), chúng tôi tính toán gradient ∇f(x,y) = (∂f/∂x, ∂f/∂y) ("vector lên trên"). Chúng tôi xoay nó 90 độ theo một trong hai hướng: (∂f/∂y, -∂f/∂x): cách này chỉ dọc theo đường bao. Chúng tôi rất chậm (với kích thước bước nhỏ hơn nhiều so với lưới) theo dõi các đường viền. Điều này sẽ đưa chúng ta tất cả các cách xung quanh một đường viền.
  • Mỗi khi chúng ta đi qua một ô lưới trong quá trình theo dõi này, chúng tôi gắn nhãn nó là {|, -, /,} tùy thuộc vào thứ gì đó giống như hướng trung bình của gradient đang trỏ. (Chúng tôi cũng phải dán nhãn hàng xóm là . nếu chúng chưa được gắn nhãn; xem [*].)
  • Lưu ý rằng vẫn còn có các hộp chuyển tiếp bị bỏ qua sau đó! Ví dụ, nếu bạn có hai ngọn đồi, bạn sẽ điền vào một vòng tròn, nhưng đường bao là hai vòng tròn. Lặp lại quy trình trên trên một hộp lưới "chuyển tiếp" ngẫu nhiên (không dán nhãn) (đây là lý do tại sao chúng tôi cần [*], hoặc người nào khác chúng tôi có thể sửa chữa trên các điểm lân cận mà chúng tôi đã chiếm).Lặp lại cho đến khi không có hộp lưới "chuyển tiếp" không được gắn nhãn.
  • Thực hiện việc này cho mỗi height -ngày bạn muốn vẽ dưới dạng đường bao và bạn đã hoàn tất.
• Bạn có thể giải quyết phân tích như bạn muốn cho các phần conic, nhưng điều này có thể không nằm ngoài phạm vi của câu hỏi này. Nếu bạn có thể giải quyết cho đường cong, bạn có thể "gridify" nó bằng cách sử dụng các kỹ thuật khác nhau (ví dụ, tham số hóa nó, sau đó đi bộ dọc theo đường viền bằng cách sử dụng kích thước bước có thể nửa lưới, ghi chú hàng xóm gần nhất)

(Nếu một trong các đường bao của bạn chồng lên nhau, khoảng cách giữa các đường viền của bạn quá nhỏ. Nếu bạn không hài lòng với một đường viền nhất định, tập hợp các khả năng {-, |, /,} quá nhỏ.)