Tôi hiện đang viết trò chơi 2D bằng Javascript bằng phần tử HTML5 <canvas>. Nó đến cùng rất độc đáo, nhưng tôi đã gặp rắc rối.Thuật toán tìm đường dẫn dựa trên lưới 2D tốt là gì?
Thiết kế cấp cho trò chơi của tôi là lưới (vì vậy chi phí đường dẫn di chuyển từ một ô đến ô phía bắc/nam/đông/tây là 1) với nhiều chướng ngại vật chiếm nhiều vị trí khác nhau trong lưới – giống như một mê cung, nhưng với rất nhiều phòng lung linh hơn. Mỗi cấp độ cá nhân là theo thứ tự 400 × 200 ô.
Tôi đang cố gắng thực hiện kẻ thù sẽ tìm kiếm người chơi bất kể họ ở đâu, nhưng tôi đang gặp sự cố khi dịch một trong các thuật toán tìm đường khác nhau để phù hợp với tình huống của tôi. Hầu hết những cái tôi đã gặp (như A * và Dijkstra) có vẻ phù hợp nhất với các tình huống 2D phức tạp hoặc 3D phức tạp hơn. Tôi đã tự hỏi nếu nó có thể đơn giản hóa đáng kể các thuật toán này để phù hợp hơn với mục đích của tôi, hoặc nếu một cái gì đó giống như tìm kiếm chiều sâu đầu tiên sẽ là một thay thế hiệu quả hơn cho kích thước cấp.
Bạn sẽ không làm tốt hơn A * mà không cung cấp cho nó một số loại kiến thức trước về các đường dẫn có thể (như chia bản đồ thành các phân đoạn có kết nối đã biết). Độ sâu đầu tiên sẽ nhiều (nhiều hơn nhiều) chậm hơn bề rộng đầu tiên. – Dave
Điều này không thực sự là những gì Stackoverflow/Stack Exchange là về; đặt câu hỏi với câu trả lời nhất định, không phải là câu hỏi mua sắm. Bằng mọi cách, hãy sử dụng những gì mọi người đề xuất, nhưng hãy quay trở lại khi bạn gặp phải vấn đề về lập trình. – Amelia
@Dave: Vâng, bạn có thể dễ dàng [tìm thấy tốt hơn so với plain-ol 'A \ *] (http://programmers.stackexchange.com/questions/197894) khi bị ràng buộc vào lưới; nhưng, JPS + A \ * phức tạp hơn chỉ là A \ * và thường không cần thiết. –