Lời giải cho tìm đường (Pathfinding)
Lại là vụ tìm đường :D
Vâng, xin mở lại một topic nói về AI Path-finding (Cách tự động tìm đường cho AI)
Lúc trước đã lập một topic về vụ này, nhưng dần đi vào bế tắc vì độ khó và nhiều thứ cản trở.
Nhưng sau khi tham khảo rất nhiều game online phổ biến hiện hành, mình thấy rằng cách làm Path-finding của người ta lại rất đơn giản. Cụ thể như này :
Để A đến được điểm Z trên bản đồ có nhiều vật cản không theo quy tắc,
người ta sẽ tạo ra những trục đường chính (gọi là path). Các path đã được vẽ trực tiếp trên map trước đó.
Bởi là path được thiết kế một cách thủ công (đi vòng qua các vật cản như thế nào thì đã vẽ đường đi cụ thể), cho nên sẽ không phải lo AI sẽ xử lý làm sao khi gặp địa hình không theo quy tắc.
Vì thế khi ra lệnh cho A đến Z, máy tính sẽ tự so sánh các path và tìm ra path nào ngắn nhất cho A (độ dài của path cũng đã được ghi lại trước đó để tiện cho việc này).
Câu hỏi dĩ nhiên đặt ra ở đây : nếu A ko nằm trên trục đường thì sao? Map rộng mà?
Trả lời : Vâng, dĩ nhiên, mình đã nói là trục đường chính thôi, chứ sao để vẽ hết ra các trục đường. Còn trường hợp A không nằm trên trục đường. Ta sẽ làm một bước phụ là lệnh cho A tìm ra cách đến trục đường ngắn nhất đầu tiên mà A gặp phải. Một khi đã ra được trục đường chính này thì ta lại quay về bài toán ban đầu thôi.
Nhược điểm :
- Khi hiểu được cách vận hành của cách tìm đường này. Ta thấy ngay ra rằng : con đường tìm được sẽ không phải đường ngắn nhất. Nếu ta đi sát vào các vật cản, ta sẽ tiết kiếm được thời gian, nhưng các trục đường thì không, sẽ luôn phải đi đúng như đã setup. Và vì thế đôi khi chơi 1 game, ta nhận ra : Ô ! rõ ràng là có đường kia ngắn hơn mà sao thằng nhân vật của mình nó không đi nhỉ, rõ ràng là có lỗi game gì đây.. Nhưng không phải nhé, sau bài viết này thì bạn đã hiểu rồi đấy. :D
- Điều hạn chế cũng có thể thấy ngay được chính là tính thủ công. Bạn sẽ phải tự vẽ trục đường cho tất cả các map. Chưa kể nhiều map rất rộng. Nếu sử dụng tìm đường theo AI, mọi chuyện sẽ tự động hóa và bạn hầu như bỏ luôn đi khối lượng công việc này.
- Có lẽ còn nhiều nữa nhưng mình chưa có ghi chép lại trong lúc tìm hiểu nên không nhớ.. Mong rằng sẽ tiếp thu thêm được ý kiến từ các bạn để bổ sung thêm.
- Focker C -
Vâng, xin mở lại một topic nói về AI Path-finding (Cách tự động tìm đường cho AI)
Lúc trước đã lập một topic về vụ này, nhưng dần đi vào bế tắc vì độ khó và nhiều thứ cản trở.
Nhưng sau khi tham khảo rất nhiều game online phổ biến hiện hành, mình thấy rằng cách làm Path-finding của người ta lại rất đơn giản. Cụ thể như này :
Để A đến được điểm Z trên bản đồ có nhiều vật cản không theo quy tắc,
người ta sẽ tạo ra những trục đường chính (gọi là path). Các path đã được vẽ trực tiếp trên map trước đó.
Bởi là path được thiết kế một cách thủ công (đi vòng qua các vật cản như thế nào thì đã vẽ đường đi cụ thể), cho nên sẽ không phải lo AI sẽ xử lý làm sao khi gặp địa hình không theo quy tắc.
Vì thế khi ra lệnh cho A đến Z, máy tính sẽ tự so sánh các path và tìm ra path nào ngắn nhất cho A (độ dài của path cũng đã được ghi lại trước đó để tiện cho việc này).
Câu hỏi dĩ nhiên đặt ra ở đây : nếu A ko nằm trên trục đường thì sao? Map rộng mà?
Trả lời : Vâng, dĩ nhiên, mình đã nói là trục đường chính thôi, chứ sao để vẽ hết ra các trục đường. Còn trường hợp A không nằm trên trục đường. Ta sẽ làm một bước phụ là lệnh cho A tìm ra cách đến trục đường ngắn nhất đầu tiên mà A gặp phải. Một khi đã ra được trục đường chính này thì ta lại quay về bài toán ban đầu thôi.
Nhược điểm :
- Khi hiểu được cách vận hành của cách tìm đường này. Ta thấy ngay ra rằng : con đường tìm được sẽ không phải đường ngắn nhất. Nếu ta đi sát vào các vật cản, ta sẽ tiết kiếm được thời gian, nhưng các trục đường thì không, sẽ luôn phải đi đúng như đã setup. Và vì thế đôi khi chơi 1 game, ta nhận ra : Ô ! rõ ràng là có đường kia ngắn hơn mà sao thằng nhân vật của mình nó không đi nhỉ, rõ ràng là có lỗi game gì đây.. Nhưng không phải nhé, sau bài viết này thì bạn đã hiểu rồi đấy. :D
- Điều hạn chế cũng có thể thấy ngay được chính là tính thủ công. Bạn sẽ phải tự vẽ trục đường cho tất cả các map. Chưa kể nhiều map rất rộng. Nếu sử dụng tìm đường theo AI, mọi chuyện sẽ tự động hóa và bạn hầu như bỏ luôn đi khối lượng công việc này.
- Có lẽ còn nhiều nữa nhưng mình chưa có ghi chép lại trong lúc tìm hiểu nên không nhớ.. Mong rằng sẽ tiếp thu thêm được ý kiến từ các bạn để bổ sung thêm.
- Focker C -
Comments
THAM GIA GROUP CỦA TTC TRÊN FACEBOOK
Ta chỉ cần rải node xung quanh màn chơi, và đến lúc chạy game, thuật toán sẽ tự động "nối" các node này lại, và tính khoảng cách giữa các nút với nhau, sau đó lưu vào file. Sau đó nó sẽ sử dụng khoảng cách tính sẵn (đã được lưu lại) này để tính đường đi ngắn nhất. Giả sử ta chỉ cần đi tới A, thuật toán sẽ đi từ A -> nút bên phải A -> lên trên -> sang trái. Nếu màn chơi bị sửa lại thì chỉ cần đặt lại các node và chạy lại game, vị trí giữa các node sẽ được tính toán lại. Với việc kẻ sẵn đường sẽ rất bất tiện và không hiệu quả (màn chơi rộng không thể nào kẻ hết; nếu chỉnh sửa lại map sẽ phải kẻ lại, trong khi chỉ cần đặt lại vị trí node).
Ý tưởng ngắn gọn là vậy.
- Tiếp tục kẻ đường (sẽ rắc rối).
- Chạy từ A tới B theo đường thẳng, nếu trong lúc đang chạy mà có vật cản (có thể giải quyết việc tìm vật cản bằng cách vẽ một cái vòng tròn xung quanh NPC và liên tục kiểm tra xem có gì lọt vào vòng tròn không; nếu có thì lập tức xoay NPC chạy sang hướng khác, chờ 1 - 2 giây, và quay lại đường cũ, tiếp tục lặp lại như vậy, v.. v...).
- ...