Thuật toán Dijkstra tính đường dẫn ngắn nhất tới tất cả các nút trong biểu đồ có thể truy cập được từ vị trí bắt đầu. Đối với trò chơi hiện đại trung bình của bạn, đó sẽ là cả hai không cần thiết và cực kỳ tốn kém.
Bạn phân biệt giữa 2D và 3D, nhưng đáng lưu ý rằng đối với bất kỳ thuật toán dựa trên biểu đồ nào, số lượng không gian tìm kiếm của bạn không tạo ra sự khác biệt. Trang web bạn đã liên kết để thảo luận về các biểu đồ điểm tham chiếu và các lưới điều hướng; cả hai đều dựa trên đồ thị và có thể hoạt động theo nguyên tắc trong bất kỳ số thứ nguyên nào. Mặc dù không có "không gian hình vuông riêng biệt để di chuyển đến", có là "khe" rời rạc trong không gian mà AI có thể di chuyển đến và đã được các nhà thiết kế trò chơi xếp đặt cẩn thận.
Kết luận, A * thực ra là thuật toán sử dụng trong trò chơi 3D cũng giống như trong trò chơi 2D. Hãy xem cách A * hoạt động:
- Khi bắt đầu, bạn biết tọa độ vị trí hiện tại của mình và vị trí mục tiêu của bạn. Bạn ước tính lạc quan về khoảng cách đến đích của bạn, ví dụ: chiều dài của đường thẳng thẳng giữa vị trí bắt đầu và mục tiêu.
- Cân nhắc các nút liền kề trong biểu đồ. Nếu một trong số đó là mục tiêu của bạn (hoặc chứa nó, trong trường hợp lưới điều hướng), bạn đã hoàn tất.
- Đối với mỗi nút liền kề (trong trường hợp của một lưới định vị, điều này có thể là geometric center của đa giác hoặc một số loại khác của trung điểm), ước tính chi phí liên quan đến đi du lịch cùng có như tổng của hai biện pháp: chiều dài của con đường mà bạn đã đi du lịch như vậy xa và một ước tính lạc quan khác về khoảng cách vẫn sẽ là .
- Sắp xếp các tùy chọn của bạn từ bước trước đó bằng chi phí ước tính cùng với tất cả các tùy chọn mà bạn đã xem xét trước đó và chọn tùy chọn có chi phí ước tính thấp nhất. Lặp lại từ bước 2.
Có một số chi tiết tôi chưa thảo luận ở đây, nhưng điều này là đủ để xem A * về cơ bản độc lập với số không gian của bạn như thế nào. Bạn cũng sẽ có thể thấy lý do tại sao điều này làm việc cho không gian liên tục.
Có một số thuật toán liên quan chặt chẽ giải quyết các vấn đề nhất định trong tìm kiếm A * chuẩn.Ví dụ: tìm kiếm đầu tiên tốt nhất đệ quy (RBFS) và A * (SMA *) bị giới hạn bộ nhớ đơn giản yêu cầu ít bộ nhớ hơn, trong khi học A * (LRTA *) thời gian thực cho phép tác nhân di chuyển trước khi đường dẫn đầy đủ được tính toán. Tôi không biết liệu các thuật toán này có thực sự được sử dụng trong các trò chơi hiện tại hay không.
Đối với làm tròn các góc, điều này có thể được thực hiện với các đường khoảng cách (nơi các góc được thay thế bằng vòng cung tròn), hoặc với bất kỳ loại chức năng nào spline để làm phẳng toàn bộ đường.
Ngoài ra, các thuật toán có thể dựa vào độ dốc trên không gian tìm kiếm (trong đó mỗi điểm trong không gian được liên kết với một giá trị), chứ không phải là biểu đồ. Đây có thể không được áp dụng trong hầu hết các trò chơi bởi vì họ mất nhiều thời gian và bộ nhớ hơn, nhưng có thể thú vị khi biết về mọi thứ. Ví dụ bao gồm các phương thức hill-climbing algorithms (mặc định theo thời gian thực theo mặc định) và potential field.
Các phương pháp để lấy biểu đồ theo cách thủ tục từ một không gian liên tục cũng tồn tại, ví dụ: cell decomposition, Voronoi skeletonization và probabilistic roadmap skeletonization. Trước đây sẽ sản xuất một cái gì đó tương thích với một lưới điều hướng (mặc dù nó có thể được khó khăn để làm cho nó hiệu quả như nhau như một lưới điều hướng bằng tay) trong khi hai sản phẩm sau đó sẽ giống như đồ thị waypoint. Tất cả những điều này, cũng như các phương pháp trường tiềm năng và tìm kiếm A * có liên quan đến robot.
Nguồn:
Đây sẽ là một câu hỏi hay cho [Phát triển game] (http: // gamedev. stackexchange.com) trang web. – Matthias