- Khi triển khai truy đuổi quái vật trong một game 8-bit nhìn từ trên xuống kiểu Zelda, di chuyển theo đường thẳng đơn thuần là chưa đủ; bài viết so sánh Dijkstra và A* để tìm điểm cân bằng cho tìm đường trong game
- Di chuyển theo đường thẳng sẽ dừng lại khi bị tường chặn, nhưng nếu thêm wall-sliding thì nhân vật có thể di chuyển dọc theo tường, giúp cảm giác điều khiển tốt hơn và cũng tạo ra yếu tố chiến thuật là nhốt quái vật bằng địa hình
- Thuật toán Dijkstra bảo đảm đường đi ngắn nhất, nhưng vì nó tìm kiếm rộng quanh nút bắt đầu, trong game nơi đích thay đổi ở mỗi khung hình, nó tính toán nhiều hơn mức cần thiết so với hướng tiếp theo cần dùng
- A* đặt mức ưu tiên tìm kiếm dựa trên khoảng cách đến đích để xét hướng về phía đích trước; khi gặp tường, nó kiểm tra các nút xung quanh và không quay lại các nút đã thấy, nên có thể tìm đường vòng
- Trên bản đồ game, có thể điều chỉnh tốc độ và độ khó triển khai bằng đồ thị ngầm định không tạo sẵn danh sách kề, tìm kiếm theo đơn vị ô, và các heuristic dựa trên hình học như giới hạn độ sâu lặp
Bối cảnh game và yêu cầu cơ bản
- Trong một game 8-bit nhìn từ trên xuống kiểu Zelda dựa trên PPU466, quái vật cần truy đuổi người chơi
- PPU466 có các ràng buộc tương tự một fantasy console như PICO-8: đồ họa 8-bit, 4 màu trên mỗi tile, nền cố định và số lượng sprite ít
- Mục tiêu là để quái vật đi theo người chơi nhưng không chỉ dừng lại khi bị tường chặn, hoặc bị kẹt theo những cách không mong muốn
Di chuyển theo đường thẳng và wall-sliding
- Cách đơn giản nhất là vẽ một đường thẳng giữa quái vật và người chơi rồi di chuyển theo hướng đó
- Nếu chỉ dùng cách này, quái vật dừng lại ngay khi chạm tường
- Khi áp dụng wall-sliding, nhân vật không dừng lại khi va vào tường mà di chuyển dọc theo tường
- Với chuyển động của người chơi, đây là kỹ thuật giúp việc điều khiển gần tường và góc tường phản hồi tốt hơn, được dùng trong hầu như mọi game
- Nó đã được sử dụng từ sau Pac-Man, và Pac-Man Championship Edition DX+ còn thêm hiệu ứng tia lửa khi người chơi wall-slide
- Nếu thêm wall-sliding vào di chuyển theo đường thẳng, có thể nhốt quái vật trong một địa hình nhất định
- Một số game dùng điều này như yếu tố chiến thuật; ví dụ là safespotting trong Runescape
- Trong game này, đó không phải hành vi mong muốn, nên tác giả xem xét các thuật toán tìm đường thực sự
Hạn chế của thuật toán Dijkstra
- Thuật toán Dijkstra trực quan khi triển khai và bảo đảm đường đi ngắn nhất
- Vấn đề là nó làm quá nhiều việc so với nhu cầu
- Nó tìm đường đi ngắn nhất từ nút bắt đầu đến mọi nút khác trong đồ thị
- Có thể dừng khi tìm thấy nút đích, nhưng không có cách nào dẫn hướng tìm kiếm về phía một đích cụ thể
- Trong videogame, người chơi liên tục di chuyển, nên đích của quái vật thay đổi ở mỗi khung hình
- Điều quái vật cần giống với việc nên di chuyển theo hướng nào ngay lúc này hơn là toàn bộ đường đi
- Có thể tính trước đường đi ngắn nhất cho mọi pixel hoặc tile trên bản đồ, nhưng sẽ tốn nhiều bộ nhớ
- Trên các nền tảng cũ hoặc nền tảng có tài nguyên hạn chế, Dijkstra không phù hợp
Vì sao A* phù hợp với tìm đường trong game
- Thuật toán tìm kiếm A* dùng thông tin khoảng cách từ nút bắt đầu đến đích để đặt ưu tiên tìm kiếm
- Ở bước đầu tiên, nó ưu tiên thử hướng đi thẳng về phía đích
- Khác với Dijkstra, nếu không cần thiết, nó không tốn nhiều thời gian tìm theo hướng ngược lại
- Nếu tường chặn đường, nó kiểm tra các nút xung quanh để cố đi vòng qua tường
- Vì giống Dijkstra ở chỗ không quay lại các nút đã thấy, nên dù cần quay lui nhiều, cuối cùng nó vẫn có thể tìm được đường vòng
- Trong ví dụ, quái vật dùng A* không bị kẹt sau tường
Cấu trúc dữ liệu đồ thị ngầm định
- Đồ thị theo sách giáo khoa được biểu diễn bằng danh sách nút và ma trận kề hoặc danh sách kề, nhưng trong game có thể tạo các nút kề linh hoạt hơn
- Ví dụ, trên màn hình 256×240 pixel, có thể xem mỗi tọa độ pixel là một nút
- Các pixel kề gồm 8 hướng: trên, dưới, trái, phải và 4 hướng chéo
- Trọng số di chuyển theo bốn hướng chính là 1, còn trọng số di chuyển chéo là √2, tức khoảng 1,4
- Thay vì tạo sẵn một danh sách kề khổng lồ, có thể sinh tại chỗ chỉ cho các nút thật sự được ghé thăm
- Những pixel nằm trên tường hoặc bị sprite khác chiếm chỗ không phải là vị trí hợp lệ của quái vật, nên được loại động khỏi danh sách kề
- Với cách này, không cần loại thủ công các nút không thể kề nhau trong trình biên tập bản đồ
Heuristic phản ánh hình học của bản đồ
- Một số yếu tố của A* có thể được điều chỉnh trực tiếp theo cấu trúc hình học của bản đồ
-
Kích thước bước
- Thay vì dùng pixel làm nút, trong game 2D dựa trên tile có thể dùng tile làm nút
- Tìm kiếm theo đơn vị tile giúp giảm mạnh số vòng lặp cần để tìm đường đến người chơi, khiến việc tìm kiếm nhanh hơn
- Trong trường hợp này, đường đi không phải là danh sách di chuyển chính xác theo từng khung hình, mà giống một chuỗi các hướng mà quái vật cần đi hơn
- Quái vật thường không di chuyển với tốc độ 1 tile mỗi khung hình, nên ngay cả với đường đi dựa trên tile, thông tin thật sự cần là hướng có thể đi để tới được người chơi
- Đường đi dựa trên pixel cũng có tính chất tương tự, và quái vật có thể không di chuyển 1 pixel mỗi khung hình hoặc theo số pixel nguyên
-
Độ sâu lặp
- Trong A*, khi một nút được lấy ra khỏi hàng đợi ưu tiên, nút đó là bước cuối cùng của đường đi tốt nhất đã thấy cho đến lúc này
- Nếu dừng thuật toán tại một số vòng lặp cố định, ta có thể nhận được đường đi ước lượng tốt nhất hiện tại đến đường đi ngắn nhất tới đích
- Không cần chạy thuật toán đến cuối vẫn có thể có một hướng tiến hợp lý
- Độ sâu lặp tối đa cần được điều chỉnh theo cấu trúc hình học của màn chơi
- Nếu độ sâu quá nhỏ, quái vật vẫn có thể bị kẹt sau tường
- Trong ví dụ, với độ sâu cố định 30 tile, tùy vị trí người chơi mà quái vật bị kẹt và không tiến được
- Vì A* được tính lại ở mỗi khung hình, có thể xuất hiện vòng lặp
- Ở khung hình đầu tiên khi chạm tường, thuật toán tính rằng cần đi xuống
- Ở khung hình tiếp theo, thuật toán tính rằng cần đi lên
- Sự lặp lại này khiến quái vật mắc vào một vòng lặp
- Khi người chơi đi vào phạm vi tìm kiếm của quái vật, nó có thể tìm được đường đúng
- Với độ sâu cố định
1, hiện tượng này còn cực đoan hơn: quái vật liên tục quay về pixel có khoảng cách Euclid đến người chơi ngắn nhất
Phương án dung hòa bằng tính toán trước
- Nếu muốn tinh vi hơn, có thể tính trước độ sâu tối đa cần để A* tìm được đường đi từ bất kỳ vị trí nào trên bản đồ
- Khác với việc tính trước toàn bộ đường đi theo kiểu Dijkstra, thứ cần lưu chỉ là một giá trị tối đa đó
- Khi có độ sâu tối đa này, A* có thể tìm đường hợp lệ theo thời gian thực
1 bình luận
Bình luận trên Hacker News
Những mẹo từng dùng với A* trong MMO production: 1) nếu dùng đồ thị phân cấp như cấp thành phố, giữa các phòng trong tòa nhà, bên trong phòng, thì có thể tìm đường từ một điểm trong phòng nào đó của tòa nhà nào đó ở thành phố này đến điểm khác chỉ trong một phần của mili giây
2) Nếu lưu metadata của lần tìm kiếm A* hiện tại trực tiếp trong các node của đồ thị, sẽ không cần duy trì một mảng kết hợp riêng
3) Đừng đi theo nguyên xi đường đi kết quả; tốt hơn là dùng nó làm đầu vào cho hành vi điều hướng cố cắt góc để đi tới node đường đi tiếp theo khi có thể. Nếu đó là đường đi tới một nhân vật khác, hãy để nhân vật mục tiêu thả “vụn bánh mì”, rồi thêm vị trí mới vào đường đi khi không thể di chuyển theo đường thẳng từ node cuối cùng của đường đi tới vị trí đó
2b) Nén thứ này thành bitmask 16-bit. 8 mảnh 2-bit, tức 8 hướng, và lưu trong hash table
2c) Mỗi mảnh bit có bốn trạng thái: FULL_BLOCK(tường), HARD_BLOCK(vật thể lớn khiến không thể đi qua ô từ bất kỳ hướng nào), SOFT_BLOCK(vật thể nhỏ chặn việc đi qua một góc), NO_BLOCK(ô trống hoặc ô có vật thể rất nhỏ)
Nhờ vậy, khi unit trong tòa nhà tìm đường, không cần kiểm tra chướng ngại vật ở mọi ô. Nếu vật thể không quá lớn và theo hướng xoay của nó không chặn các góc vào và ra, thì ô có vật thể vẫn có thể đi qua. Cuối cùng, để mô phỏng không bị hỏng trong các trường hợp như người chơi quên đặt cửa, tôi cho phép agent đi xuyên tường
https://store.steampowered.com/app/2287430/Metropolis_1998/
Khi nhân vật còn ở trong “bong bóng” này thì có thể bỏ qua toàn bộ kiểm tra va chạm với thế giới
Hồi đại học tôi không hiểu vì sao A* trong RTS lại khó đến thế, nhưng sau khi đọc giải thích rằng để các unit không đi xuyên qua nhau, mọi thứ đang di chuyển phải liên tục tránh mọi unit khác và tìm lại đường, tôi lại càng nể Command & Conquer hơn
Cá nhân tôi sẽ tránh trừ khi có lý do rất mạnh
Tôi đã suy nghĩ rất nhiều về tìm đường nhanh để tăng tốc AI Quoridor viết bằng Scala, và đây là các mẹo học được
MPAA(A* thích ứng đa đường đi) phù hợp khi có chướng ngại vật được thêm vào và bạn phải tìm kiếm lại nhiều lần trong cùng một vùng. Có thể đưa kết quả tìm kiếm trước đó vào để làm tìm đường nhanh hơn
JPS(tìm kiếm điểm nhảy) hấp dẫn về mặt lý thuyết vì có thể giảm đáng kể số “node” cần xét, nhưng overhead tìm điểm nhảy tăng lên nên thực tế không nhanh hơn. Có thể có cách kết hợp ý tưởng MPAA và JPS, nhưng khi sáng tạo chỉnh sửa thuật toán, bạn rất dễ tự vấp vì những chi tiết khái niệm nhỏ nhặt. Ví dụ, nếu dùng
>khi cần>=, trong một số tình huống có thể không bảo đảm được đường đi ngắn nhất thật sựKhi lưu các node mở, thay vì dùng heap đúng nghĩa, nếu giá trị ưu tiên tối đa là số nguyên tương đối nhỏ thì hàng đợi ưu tiên dạng bucket cũng đáng cân nhắc. Vì mảng nội bộ được đánh chỉ mục theo mức ưu tiên, việc chèn và lấy ra khá nhanh
Quoridor diễn ra trên lưới 9x9, và để phán đoán người chơi gần mục tiêu đến đâu cũng như mục tiêu còn có thể tới được hay không, việc tìm đường lặp lại là bắt buộc. Để xác định các nước đi hợp lệ tại một vị trí nhất định, phải kiểm tra rằng mọi nước đi không khiến mục tiêu trở nên không thể tới. Tôi dự định công khai trong vài tháng tới, và sẽ có ít nhất 3 “engine” ra quyết định: mtdf(một biến thể minimax), MCTS(phiên bản song song có thêm vài mẹo), và một hybrid trộn catboost
Điểm hay là có thể dùng nó làm bảng tra cứu cho hàm heuristic thay vì khoảng cách đường thẳng thông thường. Ví dụ, ở đầu mỗi lượt có thể khởi tạo bảng này bằng thuật toán Floyd-Warshall, phản ánh các bức tường đã đặt. Trong một bài toán tương tự, kỹ thuật này đã tăng tốc A* khá nhiều và rất đơn giản. Tuy nhiên đó là A* thuần, không dùng MPAA hay JPS
Nhiều năm trước, tôi đã thêm tính năng trực quan hóa tìm kiếm đệ quy để tìm node nhảy vào bản triển khai JPS của PathFinding.js. Demo online ở đây: https://qiao.github.io/PathFinding.js/visual/
Nếu có từ hai kẻ địch trở lên, có thể sẽ lợi hơn nếu từ góc nhìn của người chơi chỉ chạy Dijkstra một lần, rồi để mỗi quái vật tra cứu đường đi tối ưu tới người chơi
Chi phí tính toán sẽ dễ dự đoán hơn khi số quái vật thay đổi
Vấn đề độ sâu quá nhỏ ở animation cuối trông như một hành vi khá thú vị. Nó làm quái vật trông như đang “đợi xem bạn sẽ đi hướng nào”
Nếu giả vờ đi một hướng rồi đổi hướng thì có thể đánh lừa được chăng? May là con người khá dễ tính với những thứ như vậy, có vẻ như ta hay mô hình hóa mọi thứ như thể chúng có trí thông minh
Về cơ bản, chỉ cần để kẻ địch cập nhật đường đi sau một khoảng trễ ngắn thay vì mỗi frame. Khi đó do “quán tính”, nó sẽ đi theo đường cũ và người chơi có thể đánh lừa được
Một cách dùng thú vị của A* trong bối cảnh game: có một lập trình viên hồi đầu những năm 2000 phải tạo đối thủ máy cho một trò chơi
Anh ta trừu tượng hóa các lựa chọn mà AI có trong game, rồi dùng A* để tìm khoảng cách gần nhất trên đồ thị đó. Điểm hay là nó không dùng theo kiểu truyền thống là tìm đường trong thế giới game, mà tìm đường trên biểu diễn các lựa chọn máy tính có thể thực hiện, để đường ngắn nhất biểu thị chiến lược tốt nhất có thể
0 - https://www.gamedeveloper.com/design/building-the-ai-of-f-e-...
1 - https://web.archive.org/web/20230804100329/https://alumni.me...
Cũng có tài liệu tham khảo (không phải của tôi): https://github.com/agoose77/goap-resources
Con người dường như cho rằng bản thân và những người khác dùng các mẫu tư duy tương tự, với độ sâu suy nghĩ tương tự, cho những hoạt động rất khác nhau như lập kế hoạch đường đi, đánh giá rủi ro/phần thưởng, hay lên kế hoạch cho một sự kiện sau 6 tháng. Nếu có thể mã hóa nhiều “không gian tìm kiếm” khác nhau thành đồ thị phù hợp với một thuật toán chung, thì trong trạng thái nhập tâm khi chơi, AI sẽ có cơ sở để trông chín chắn và gần như có nhân cách
Khi học A* ở đại học, cùng lúc đó tôi gặp đúng vấn đề kỳ lạ ấy trên một máy chủ Minecraft công cộng
Máy chủ giật lag nghiêm trọng nên khi truy vết thử, hóa ra các zombie bị kẹt trong vòng lặp tìm đường để vào một ngôi làng đã bị rào lớn chặn kín hoàn toàn. Nghĩa là triển khai khi đó khá ngây thơ và chúng không bao giờ bỏ cuộc
Tôi nhớ là từng có một báo cáo lỗi viết khá chi tiết về cách sửa vấn đề này
Điều này có thể ảnh hưởng rất rõ tới fps, nhất là khi nhiều con vật đều cố đi qua một lối vào không thể vượt qua. Tất nhiên, nếu xem đó là hành vi mèo cứ nằng nặc đòi đi qua cánh cửa đã đóng thì cũng có thể nói là cực kỳ thực tế. Nhưng sẽ còn thực tế hơn nếu ngay khi ta mở cửa, con mèo lập tức đổi ý và mất hứng đi qua!
Có thể bạn sẽ quan tâm đến một bài báo về hệ thống đa tác tử dùng A* trên địa hình xa lạ: https://www.researchgate.net/publication/333917261_Implement...
Bài viết này và thread HN có nhiều mẹo hay. Tôi chưa có nhiều dịp dùng A*, nhưng biết là có một thư viện Haskell ổn: https://hackage.haskell.org/package/astar-monad-0.3.0.0#read...