Thuật toán để tìm các thực thể di chuyển trong mê cung

A có một mê cung và nhân vật được điều khiển bởi người chơi và một mục tiêu giả đã phải tìm anh ta (tự nó). Có ai biết một thuật toán AI (hiệu quả) để làm một cái gì đó như thế này? P.S. Tôi biết có một số thuật toán tìm đường dẫn (ví dụ A *), nhưng theo như tôi biết, chúng chỉ hoạt động để tìm đường đi giữa hai nút "không di chuyển" (điều này sẽ hoạt động nếu nhân vật của tôi đứng yên, nhưng đó là rõ ràng không phải là trường hợp).Thuật toán để tìm các thực thể di chuyển trong mê cung

Nguồn

2012-01-19 conectionist

Máy bay không người lái có biết bố trí mê cung hay không phải khám phá nó khi nó đi? Ngoài ra, nó có biết người chơi ở đâu trong mê cung khi nó di chuyển không? – cdeszaq

A * cũng yêu cầu bạn biết trước vị trí của điểm bắt đầu và điểm kết thúc. Liệu mục tiêu giả có biết người chơi ở đâu và chỉ cần đạt được nó? Không người lái của chúng tôi cũng cần phải xác định vị trí người chơi? –

@cdeszaq Vâng, nó biết cách bố trí của mê cung (mặc dù tôi sẽ không nhớ một thuật toán giả định nó không biết nó) và có, nó không biết nơi người chơi nằm trong mê cung. – conectionist

Nếu "điểm xuất phát" là nơi máy bay không người lái và "điểm kết thúc" sẽ chạy vào trình phát, điều tốt nhất bạn có thể làm chỉ bằng thuật toán "chuẩn" là sử dụng A * định kỳ và từ xác định vị trí máy bay không người lái cần di chuyển.

Khi bạn tiến gần hơn đến trình phát, bạn sẽ tính toán nhanh hơn và nhanh hơn vì không gian tìm kiếm, theo lý thuyết, nhỏ hơn.

Sử dụng tính năng này, sẽ để người chơi tìm thấy một vị trí, khi di chuyển giữa chúng khiến cho mục tiêu giả bị "kẹt" chỉ di chuyển qua lại, nhưng những loại tối ưu đó là tình huống- cụ thể và thuật toán chung sẽ không bao gồm chúng.

Về cơ bản, bạn do có không gian tìm kiếm cố định cho mỗi "khung", nhưng bạn chỉ cần chạy mỗi khung để quyết định việc cần làm.

Có nhiều khả năng chỉnh sửa đối với A * bao gồm các nhiễu loạn nhỏ giữa các lần chạy, nhưng tôi không biết bất kỳ điểm nào trên đầu của tôi.

Nguồn

2012-01-19 15:46:57 cdeszaq

Đây thực sự là điều đầu tiên tôi mặc dù. Một trong những vấn đề với giải pháp này là tính toán đường đi có thể mất nhiều thời gian và sau đó chuyển động của nó có thể trông như thế này: di chuyển một chút, sau đó dừng lại và tính toán, sau đó di chuyển một lần nữa, sau đó tính toán lại, v.v. giống như nó di chuyển liên tục (giống như cách những con ma di chuyển trong pacman). – conectionist

Tôi đồng ý, A * có thể là cược tốt nhất của bạn. Bạn sẽ muốn khả năng dừng A * ở giữa một phép tính khi con người đã di chuyển. Bạn cũng sẽ cần phải cập nhật các mục tiêu bắt đầu và kết thúc mỗi khi con người hoặc máy bay không người lái di chuyển. Tôi đoán bạn cũng có thể sử dụng một cái gì đó như thuật toán của Johnson để tìm tất cả các đường đi ngắn nhất giữa tất cả các vị trí có thể và sau đó sử dụng nó như một bảng tra cứu. Điều đó sẽ hoạt động nếu mê cung không phải là năng động. http://en.wikipedia.org/wiki/Johnson%27s_algorithm – Justin

@Justin - Tôi thích ý tưởng tra cứu ..._ Nhiều_ nhanh hơn so với liên tục thực hiện A *. Bạn có thể sử dụng cùng một ý tưởng ghi nhớ _with_ A * và lưu lại kết quả. Sau đó, bạn sẽ từ từ xây dựng bảng tra cứu dựa trên nơi mà người chơi và mục tiêu giả đã và đang có, bỏ qua các phần "chưa được truy cập" của mê cung cho đến khi chúng cần thiết. – cdeszaq

Thuật toán để tìm các thực thể di chuyển trong mê cung

Trả lời

Các vấn đề liên quan