Tôi đang tìm một thuật toán mà có thể tạo ra một cái gì đó giống như những gì trong hình ảnh này:Làm cách nào để tạo một đường dẫn ngẫu nhiên?
Tôi đã đọc về các thuật toán đi bộ say rượu nhưng họ dường như không hoàn toàn phù hợp với những gì tôi cần. Tôi không chắc liệu tôi có thể đạt được những gì tôi đang tìm kiếm với một thuật toán đi bộ say rượu được sửa đổi nhiều hay nếu tôi nên tìm kiếm một số thuật toán khác để gây rối.
Vì bạn muốn tránh tự ngã tư, việc đi bộ ngẫu nhiên sẽ khó thực hiện một cách chính xác. Bạn có thể dễ dàng vẽ mình vào một góc. Tôi sẽ đề nghị bắt đầu với một đoạn đường thẳng đi qua khu vực, sau đó tách đoạn đường này ở đâu đó ở giữa và dịch chuyển điểm giữa theo một số lượng ngẫu nhiên tỉ lệ theo độ dài của đoạn đường. Lặp lại quá trình này một cách đệ quy cho hai đoạn đường mới. Nếu bạn kết thúc với một điểm giữa làm cho một trong hai đoạn đường mới vượt qua một đoạn đường hiện có, sau đó thử một điểm giữa khác. Dừng đệ quy khi phân đoạn đường của bạn ngắn (tuy nhiên bạn muốn xác định điều đó).
Đường dẫn trong hình ảnh đó dường như không tự vượt qua. Điều đó có quan trọng đối với ứng dụng của bạn không? –
@TedHopp Có, điều quan trọng là con đường không tự vượt qua. – Talon876
Những gì bạn muốn được gọi là Tự tránh Randow Walk, thường được viết tắt là SAW. Google cho nó và bạn sẽ tìm thấy một số phương pháp thế hệ, vì nó là một vấn đề được nghiên cứu và rất quan trọng trong vật lý, hóa học và sinh học. ADN, các polyme và các hiện tượng khác có liên quan đến loại điều này. Đừng mong đợi để tìm các thuật toán dễ dàng và hiệu quả ... –