A.I. có thể điều hướng thành phố 2D được tạo ngẫu nhiên

Question

Tôi đang viết một trò chơi iOS (Sử dụng UIView), trong đó có một thành phố 2D được tạo ngẫu nhiên. Tôi cần tấn công A.I., sẽ có một con đường thông minh để tìm người chơi (mà không va chạm với các tòa nhà). Ai đó có thể chỉ cho tôi đúng hướng như loại thuật toán nào tôi sẽ sử dụng để đạt được điều này không?

Chỉnh sửa: Tôi đã quyết định sử dụng A *. Tôi sẽ tạo một lưới trên bản đồ, kiểm tra mọi điểm giao nhau của lưới, nếu điểm đó nằm trong một tòa nhà, tôi sẽ làm mất hiệu lực điểm. Tấn công A.I. người chơi sau đó sẽ di chuyển từ vị trí hiện tại của nó, đến một điểm lưới hợp lệ, gần với mục tiêu của nó (trong phạm vi bán kính nhất định của vị trí của nó).

Answer 1

Bạn đang tìm kiếm một lớp thuật toán có tên là pathfinding algorithms. Có nhiều cách tiếp cận bạn có thể sử dụng.

Thuật toán cổ điển ở đây là Dijkstra's algorithm và A* search, có thể hướng dẫn một đối tượng từ vị trí này đến vị trí khác dọc theo đường dẫn tối ưu. Các thuật toán này hoạt động bằng cách mô hình hóa thế giới 2D dưới dạng graph và sau đó tìm đường đi ngắn nhất từ ​​vị trí bắt đầu của đối tượng đến vị trí đích trong biểu đồ đó. Hai thuật toán này được sử dụng rộng rãi trong AI và pathfinding, và tôi mạnh mẽ khuyên bạn nên đầu tư thời gian để đọc thêm về chúng. Có một số solid tutorial on A* search có sẵn trực tuyến nếu bạn muốn.

Nếu bạn có nhiều đối tượng khác nhau cần di chuyển đến mục tiêu mà không can thiệp, bạn có thể muốn xem xét các trường tiềm năng, cung cấp khung đơn giản và linh hoạt để có nhiều đối tượng tiếp cận mục tiêu. Cách tiếp cận này đã được sử dụng bởi the Berkeley "Overmind" StarCraft AI và thường được sử dụng trong lập kế hoạch chuyển động robot. Bằng trực giác, cách tiếp cận này hoạt động bằng cách gán một giá trị "tiềm năng" cho mỗi vị trí, sau đó có các đối tượng tiếp tục di chuyển từ tiềm năng cao đến tiềm năng thấp cho đến khi chúng đạt được mục tiêu. Cách tiếp cận này là một chút phức tạp hơn để có được quyền, nhưng một khi nó hoạt động nó có xu hướng dẫn đến AI linh hoạt, tùy biến mà cư xử thông minh.

Hy vọng điều này sẽ hữu ích!

Answer 2

Câu hỏi này ở đây: Pacman: how do the eyes find their way back to the monster hole? là khảo sát tốt về cách tiếp cận điều hướng AI của lưới 2D ngẫu nhiên để tìm kiếm trình phát di chuyển. Sự đồng thuận chung (và cách tiếp cận được sử dụng bởi Pacman) là không phải lo lắng về việc nướng các thuật toán đường dẫn thông minh trong AI, mà thay vào đó sử dụng bản đồ để lưu trữ thông tin agout vị trí của người chơi. Đó là một bài đọc hấp dẫn, đặc biệt là câu trả lời thứ hai và thứ ba (và các liên kết bên ngoài của họ) bởi ammoQ và Dan Vinton.

Liên kết này tại đây Pacman scent antiobject pattern mô tả cách tiếp cận rẻ và hiệu quả.