Thuật toán tìm kiếm đường đi là một trong số các thuật toán hay áp dụng nhiều nhất trong quá trình phát triển game. Thuật toán tìm kiếm đường đi đưa ra lời giải cho vấn đề làm cách nào đi từ điểm A đến điểm B trong một bản đồ.
Hẳn các bạn làm việc với unity, khi nghĩ đến thuật toán tìm kiếm đường đi chúng ta thường sử dụng component NavMesh do unity phát triển và có mã nguồn mở đặt ở đây https://github.com/Unity-Technologies/NavMeshComponents.
Và rất nhanh chóng, chúng ta có thể cài đặt vào trong game, giải quyết vấn đề như di chuyển nhân vật của chúng ta đi từ điểm A đến điểm B tránh các vật cản hay cài đặt logic cho những con Bot theo dấu nhân vật chính, hoặc một ví dụ cụ thể là cài đặt logic di chuyển theo đội hình...
Việc cài đặt và ứng dụng component NavMesh như thế nào mình sẽ không đi sâu vào chi tiết mà hướng đến các vấn đề mình ứng dụng navmesh trong game như thế nào. Các bài viết về NavMesh dễ hiểu các bạn có thể tham khảo ở video sau:
Như video trên, việc cài đặt NavMesh là khá dễ dàng đúng không? Có thể liệt kê các bước đơn giản như sau:
Bước 1: Add Component NavMesh Surface vào GameObject Map.
Bước 2: Setting các thông số Bake (Thiết lập tĩnh) NavMesh Surface dựa vào Geometry Mesh (dựa vào mesh của object) hay dựa vào Physics Collider (dựa vào các GameObject có component Collider).
Bước 3: Nhấn Bake. Và chúng ta có thể thấy ngay bản đồ đựa chia thành các vùng xanh da trời, và các vùng trống. Các vùng xanh da trời thể hiện các khu vực mà NavMesh Agent có thể đi được, các vùng trống không được tô màu là các vùng không thể đi được, hoặc đại diện cho các Obstacle (vật cản).
Bước 4: Add Component NavMesh Agent và tinh chỉnh các thông số về khung vật lý của NavMesh Agent vào GameObject mình muốn điểu khiển di chuyển trên NavMesh Surface.
Bước bổ sung: Ở một số game, chúng ta có các dạng Obstacle động, có thể di chuyển như Trap, chúng ta cần Add Component NavMesh Obstacle để cấu hình object đó là một Obstacle động. Lúc runtime, các NavMesh Agent sẽ tự động điều chỉnh hướng đường đi của mình nếu gặp phải các Obstacle này.
Đối với prototype Counting Sheep, mình đưa NavMesh Component vào logic tìm đường cho cừu nhằm giới thiệu đến các bạn component này. Có thể thấy, NavMesh giúp chúng ta cài đặt việc tìm đường đi của nhân vật khá tự nhiên và đơn giản.
Trong các dự án thực tế, mình cũng đã dùng NavMesh Component giúp giảm thiểu thời gian làm việc lại rất nhiều, ví dụ như project dưới đây:
Ứng dụng component này trong logic các Bot có khả năng chạy đến tấn công gần nhân vật chính hay logic các nhân phụ tá di chuyển theo nhân vật chính. Tất cả các logic đó đều được thực hiện một cách nhanh chóng và đơn giản với navmesh.
Tuy nhiên, NavMesh vẫn có những trường hợp mình cảm thấy không mang lại kết quả tốt đặc biệt là Perfomance, giảm FPS gây giật lag nếu như số lượng NavMesh Agent quá nhiều. Ví dụ như game Crowd City, hay một project zombie shooter mình thực hiện.
Để giải quyết vấn đề này, chúng ta có thể dùng một số thuật toán tìm đường khác như Astar, FlowField pathfinding. Ở bài viết này, mình sẽ giới thiệu đến các bạn một assets về astar pathfinding mà mình đã dùng trong thực tế dự án là https://arongranberg.com/astar/.
Cách cài đặt cơ bản:
https://arongranberg.com/astar/docs/getstarted.html
Tổng về assets này khá giống với NavMesh component. Project này có hai phiên bản gồm miễn phí và bản trả phí 100$. Với bản miễn phí, chúng ta cũng đã có thể thực hiện việc cài đặt tìm đường đi với thuật toán A*. Với bản trả phí, assets cung cấp cho chúng ta thêm một số tính năng như Local Avoidance, setting optimize cho thuật toán... Local Avoidance là cơ chế thực hiện tính toán các object trong lúc tìm đường sẽ không đi xuyên qua nhau. Các bạn có thê tự mình implement cơ chế này hoặc tham khảo thư viện sau: https://unitylist.com/p/1qp/RVO-2-Unity
Điều đặc biệt của assets này là có xử lý multi threading giúp tối ưu performance. Đó cũng là một phần mình sử dụng assets này trong project zombie shooter. Ngoài việc, assets đã tối ưu tuy nhiên khi cài đặt với số lượng lớn các object thực hiện công việc tìm đường là khá nặng nề. Để hiệu quả hơn nữa, chúng ta có thể thêm một số điều chỉnh giúp tối ưu hiệu năng như sau:
- Qui hoạch hành vi của Bot, lúc nào cần gọi function Tìm Đường, lúc nào thì dừng lại. Điều này làm giảm thiểu bớt thời lượng gọi function Tìm Đường, tránh việc frame nào cũng thực hiện tính toán tìm đường đi.
- Cấu hình hoặc code optimize các thuật toán Heuristic.
- Cân nhắc dùng Physics như Dynamic RigidBody với số lượng lớn các objects.
- Gom nhóm các Bot lại với nhau, thực hiện tìm kiếm theo nhóm. Ví dụ chúng ta có 1000 bot, nhưng phân ra nhiều cụm khác nhau như 10 nhóm, mỗi nhóm 100 bot. Sau đó, qui hoạch tìm đường theo nhóm. Đây cũng là cơ chế optimize runtime ở bài viết https://blogs.unity3d.com/2015/12/23/1k-update-calls/
- Không nên gọi function tìm đường (navAgent.SetDestination(transfrorm) hay aiPath.SearchPath(Position)) ở mỗi frame (trong xử lý hàm Update) mà nên gọi theo mỗi thời điểm cố định, ví dụ như 0.5s gọi tìm đường một lần (có thể dùng Coroutine hoặc async method) . Riêng với cơ chế này, game của mình cũng đã có sự ổn định rõ rệt, không còn lag và đạt được target FPS.
Nhận xét
Đăng nhận xét