A * manhattan distance

Question

Tôi đã tìm kiếm thuật toán/mã giả của A * Tôi đã theo dõi nó và mã hóa nó. Tôi đã sử dụng khoảng cách Manhattan cho h (n). (F (n) = g (n) + h (n)) Và đây là kết quả,

này luôn luôn xảy ra khi không có bức tường ngăn chặn đường đi, nhưng khi tôi đặt rất nhiều các bức tường, có vẻ như nó đang đi theo con đường ngắn nhất. Đây có phải là con đường ngắn nhất không? Tôi có nghĩa là tại sao nó không giống như thế này bên dưới?

Đây cũng là A * Manhattan và chúng có cùng kích thước (19x19). Đây là từ http://qiao.github.com/PathFinding.js/visual/

Answer 1

Cả hai đường dẫn đều có cùng khoảng cách manhattan. Do đó, nó được thực hiện phụ thuộc vào con đường được chọn. Để biết lý do tại sao phần cụ thể này được chọn, chúng tôi sẽ phải xem xét mã của triển khai A * cụ thể này.

Gợi ý: Mỗi đường dẫn từ nguồn đến ô đích chỉ sử dụng Von Neumann neighborhood (tức là không đi theo đường chéo) và không đi theo hướng "sai" (nghĩa là không bao giờ đi lên hoặc bỏ trong ví dụ của bạn)) có cùng khoảng cách manhattan. Vì vậy, nếu bạn ở New York, bạn không cần phải đi qua ngã tư nào để đến một địa điểm nhất định ở Manhattan :)

Answer 2

Với khoảng cách manhattan đầu tiên là con đường ngắn nhất. Nó chỉ đơn giản là đếm số lượng các bước ngang và dọc được thực hiện. Nếu bạn muốn một cái gì đó trông giống như một con đường ngắn nhất trong khoảng cách euclidian bạn có thể thử thay đổi thuật toán của bạn để khi nó có sự lựa chọn để di chuyển theo chiều ngang hoặc chiều dọc tại một điểm nó chọn ngang nếu khoảng cách ngang lớn hơn chiều dọc một và ngược lại.

Answer 3

Bạn cần truyền một đường ngắm (pythagore/euclide) từ điểm bắt đầu đến mọi điểm (của kết quả manhattan/A *) cho đến khi kết thúc. Nếu việc truyền một đường tới một điểm nhất định bị chặn/ẩn bởi chướng ngại vật, bạn sử dụng điểm trước đó được đúc và bắt đầu truyền một đường khác từ điểm bị chặn đó về sau cho tới khi kết thúc. Điểm bị chặn là khi một điểm bị ẩn bởi đường ngắm của điểm đầu tiên của đoạn/đoạn. Vì vậy, Nó giống như:

First Line: Bắt đầu ---------> S + N (điểm trước khi bị chặn)

Second/Trung Line/s: Point Blocked ------ ----> S + N (trước một điểm bị chặn khác) lặp lại một lần nữa (dòng/phân đoạn mới) cho đến khi nó thiết lập đường ngắm cho mục tiêu.

Dòng cuối: Point Blocked -------------> Mục tiêu

Connect tất cả các dòng và bạn đã có một con đường ngắn ngắn hơn nhiều. Bạn có thể thực hiện lại, nhưng ngược lại để thêm độ chính xác khác để đường ngắm sẽ bắt đầu tại mục tiêu cho đến khi bắt đầu.