Thuật toán hướng dẫn đường dẫn sao cho bề mặt khối lập phương

Question

Tôi đang xây dựng một snake game phát trên bề mặt hình lập phương. Hiện tại nó sử dụng thuật toán của Dijkstra cho pathfinding. Mặc dù tối ưu hóa với cấu trúc dữ liệu xếp hàng ưu tiên và thiết lập, nó vẫn còn hơi chậm. Bạn nhận thấy sự chậm trễ khi con rắn ăn một món ăn và bắt đầu tìm kiếm một món ăn mới.

Tôi đang cố gắng sử dụng A * thay vào đó nhưng tôi không thể tìm thấy một phương pháp phỏng đoán tốt. Trên một mạng lưới phẳng với 4 hướng di chuyển, tôi sẽ sử dụng khoảng cách Manhattan. Tôi đã thử sử dụng 3D Manhattan khoảng cách abs(dx) + abs(dy) + abs(dz) mà không làm việc vì lý do tốt: cho con rắn, thế giới trò chơi thực sự là 6 grids (corresponding to the faces of the cube) với bất thường xung quanh tài sản.

Trong mã, mỗi ô được lưu trữ trong mảng grid[15][15] 2D. Có 6 mảng như vậy để lưu trữ từng khuôn mặt. Vì vậy, mỗi ô vuông có một số (arrayX, arrayY, d) để mô tả độ lệch trong mảng 2D và chỉ định mảng nào. Ngoài ra, mỗi ô vuông có một vị trí không gian mô tả (x, y, z) ba.

Đây là khu vực của mã trò chơi, nơi pathfinding xảy ra:

https://github.com/mhluska/Snakeception/blob/master/src/js/game.coffee#L105

Dưới đây là mã thư viện cho A *:

https://github.com/mhluska/Stimpack/blob/master/src/js/graph.coffee#L60

một phù hợp, heuristic ngắn gọn là gì cho điều này thế giới game?

Answer 1

Một cách để giải quyết điều này là, thay vì thực hiện tất cả các đường dẫn ngay khi bạn lấy một món ăn, hãy để con rắn di chuyển về phía cạnh có thức ăn tiếp theo và khi nó ở bên đó , sử dụng thuật toán A * lưới cơ bản để lấy mục thực phẩm. Nói cách khác:

Bất cứ khi nào con rắn lấy một mặt hàng thực phẩm hoặc di chuyển đến một khía cạnh mới của khối lập phương, thực hiện như sau:

• Nếu mặt hàng thực phẩm là ở phía bên khối hiện tại, hãy tìm một con đường để bằng cách sử dụng thuật toán A * với khoảng cách 2D Manhattan heuristic
• Nếu mặt hàng thực phẩm nằm ở cạnh liền kề của khối lập phương, hãy tìm đường dẫn đến cạnh của khối lập phương giáp với mặt hiện tại và phía đích sử dụng cùng thuật toán pathfinding .
• Nếu mặt hàng thực phẩm nằm ở phía đối diện của hình lập phương, hãy tìm đường đi của phía hiện tại bằng cùng một thuật toán tìm đường.

Điều này sẽ không đảm bảo đường đi ngắn nhất, nhưng thường phải gần đường ngắn nhất và nhanh hơn vì nó tách đường dẫn thành nhiều giai đoạn và sử dụng thuật toán hiệu quả hơn cho từng giai đoạn.