Một số câu hỏi với tìm đường dẫn pacman

Question

Tôi đã học về A *, BFS, DFS và có thể triển khai chúng khá tốt. Tuy nhiên, một số vấn đề phát sinh khi tôi cố gắng làm điều đó trong việc giải quyết vấn đề tìm đường dẫn pacman. Giả sử chỉ có hai loại mê cung: một loại có đầy đủ vật phẩm, như không có ô trống, mọi thứ đều là pacman hoặc item-to-collect hoặc wall; và một chỉ có một vài mục (4 hoặc ít hơn).

1. BFS và DFS được triển khai chính xác như thế nào nếu có nhiều hơn một mục để thu thập? Trong trường hợp như vậy, họ vẫn tạo ra kết quả tối ưu?

2. Thuật toán/heuristic tốt nhất cho bản đồ toàn bộ mục là gì? Những gì tôi đã đưa ra cho đến nay là một cái gì đó như heuristic tham lam, nhưng nó là khá ngẫu nhiên do bản đồ có quá nhiều mặt hàng để thu thập và do đó, không phải là một ý tưởng tốt để giải quyết mê cung như vậy.

3. Sử dụng A *, trong bản đồ vài mục, có cách nào tốt để xác định mục nào cần được thực hiện trước không? Tôi đã nghĩ đến việc cố gắng sử dụng khoảng cách Mahattan như một ước tính sơ bộ, nhưng điều đó không có vẻ đúng, đặc biệt là trong một số tình huống khó khăn.

Answer 1

Thuật toán không thay đổi nếu bạn thêm thực phẩm. Điều duy nhất thay đổi là không gian trạng thái. Bạn phải nghĩ ra một cách mới để đại diện cho vấn đề của bạn. Khi bạn chỉ có 1 thực phẩm để ăn, bạn chỉ cần vị trí của x, y của pacman. Ví dụ, khi bạn có 3 chấm để ăn, bạn phải thêm những thông tin này vào mô hình của mình. Bạn có thể thêm 3 biến boolean để chỉ ra rằng pacman đã đi qua dấu chấm. Giờ đây, trạng thái của bạn là biểu đồ được tạo thành từ các nút thuộc các loại sau:

((x,y),FALSE,FALSE,FALSE) -> state that indicates that pacman has not eat any food 
((x,y),FALSE,TRUE,FALSE) -> state that indicates that pacman has eat only one food 
((x,y),TRUE,TRUE,TRUE) -> this is the goal state 

Để giải quyết vấn đề bạn chỉ cần chạy cùng một thuật toán trong mô hình mới của mình. BFS ans A * sẽ luôn cung cấp cho bạn giải pháp tối ưu. Vấn đề là: càng có nhiều thức ăn bạn đặt, thì càng chậm để tìm ra giải pháp. Vì vậy, các thuật toán này sẽ không đưa ra câu trả lời trong một thời gian hợp lý. Bạn đã nghĩ ra cách mới để làm điều này.

Answer 2

1) Vấn đề tôi gặp phải khi sử dụng BFS hoặc DFS trong trường hợp này là mức độ không hiệu quả của việc này, đặc biệt là trong ví dụ bản đồ đầy đủ. Để có được một trong hai thuật toán để làm việc với nhiều mục tiêu, bạn có thể xây dựng tìm kiếm để nó không kết thúc sau khi đường dẫn đầu tiên được tìm thấy, nhưng điều này vẫn sẽ không cung cấp cho bạn một con đường "tối ưu" cho mọi phần thức ăn trên bản đồ hoặc bạn có thể làm một con đường từ pacman đến thức ăn gần nhất, thức ăn đó đến gần nhất, v.v., tìm những con đường đó, sau đó so sánh chúng để tìm ra con đường thực sự tối ưu, nhưng tôi không muốn nghĩ về lấy.

2) Tôi có thể gắn bó với A * tham lam, chỉ nhìn vào thức ăn gần nhất (tôi không thấy vấn đề với khoảng cách manhattan trong hầu hết các trường hợp, vì bản đồ cho pacman đã là lưới, nó sẽ được suboptimal cho các trường hợp cạnh nơi bức tường ngăn chặn Pacman truy cập gần nhất, nhưng đây là một vấn đề khó giải quyết Manhattan sẽ là một phong nha, có thể thay đổi mật độ của thực phẩm thay vì chỉ khoảng cách, một cái gì đó như: (manhattan distance)/(tổng thức ăn trong phạm vi 3x3 hình vuông của thức ăn)

3) Ngắn sử dụng pathfinding trên mỗi mục, sau đó chọn ngắn nhất, tôi nghĩ manhattan sẽ làm tốt trong kịch bản vài mục. Nó sẽ không luôn luôn chọn tốt nhất, nhưng 100% AI tối ưu thường không phải là mục tiêu tốt nhất để chơi game.

Trong trường hợp này, tôi muốn thử tham lam A * với trọng lượng ưu tiên các cụm mục như là một giải pháp đơn giản, nhanh nhẹn.

Một giải pháp phức tạp hơn nên trở lại gần hơn với đường dẫn tối ưu để Pacman theo dõi sẽ sử dụng thuật toán để tìm một số Minimum Spanning Tree http://en.wikipedia.org/wiki/Minimum_spanning_tree nhưng tôi không biết cách thực hiện dễ dàng như thế nào. Dưới đây là một câu hỏi thảo luận về giá trị của hai thuật toán Spanning Tree tối thiểu: Kruskal vs Prim