Đường dẫn đa giác dựa trên

Question

Tôi đã triển khai một đường dẫn dựa trên A * cơ bản dựa trên lưới trong Java. Tôi muốn thực hiện một lưới/đa giác dựa pathfinder điều hướng, nhưng vấn đề tôi có là thế này:

Nếu tôi tìm thấy con đường màu cam sau đó tôi có thể sử dụng một cái gì đó giống như a funnel algorithm để thẳng nó để có được những mong muốn tuyến đường (màu xanh). Tuy nhiên, nếu chương trình tính toán chi phí của mỗi tuyến đường, màu đỏ và màu da cam, thì nó sẽ cho biết màu đỏ là rẻ hơn. Làm thế nào để lập trình thuật toán A * của tôi và/hoặc tạo các mắt lưới của tôi để điều này không xảy ra.

Answer 1

Chương 15 trong Computational Geometry: Algorithms and Applications mô tả và giải quyết chính xác vấn đề này: không gian trống có thể được mô tả bằng bản đồ hình thang, nhưng đường dẫn được tìm thấy bằng bản đồ không nhất thiết phải là ngắn nhất. Các đại diện được đề nghị (cũng được thảo luận trong LaValle's Planning Algorithms (Section 6.2.4)) là một cái gọi là đồ thị tầm nhìn, trong đó có các cạnh kết nối đỉnh của các chướng ngại vật.

Mã giả và số liệu có sẵn từ trang chủ của sách và Google preview cũng chứa các phần của chương.

Answer 2

bạn nên kiểm tra liên kết này: http://alienryderflex.com/shortest_path/ nó giải thích cách tính đường đi ngắn nhất bên trong đa giác, giải thích và triển khai mã rất rõ ràng.

Answer 3

Xin lỗi tôi không thể giúp trực tiếp câu hỏi của bạn, nhưng chúng tôi đã chuyển một đường dẫn đa giác dựa vào mật khẩu và nó có thể biên dịch sang java (chỉ thử với swing cho đến nay nhưng có thể thử slick2d sớm) và có thể được tích hợp vào Java dự án đưa ra một số nghiên cứu. Nó được gọi là hxDaedalus và trên github và có thể là một điểm tham khảo thú vị.