Monday, October 13, 2014

Tri thức cho việc tìm đường và điểm chiến lược

Trong các game AI một trong những vấn đề quan trọng nhất là giải quyết bài toán tìm đường, có rất nhiều giải thuật giúp chúng ta giải quyết các bài toán này như A*, D*, giải thuật phân cấp đồ thị… Một điểm chung của tất cả các giải thuật này là chúng hoạt động trên một đồ thị các node đã có đầy đủ các tri thức về vị trí node, kết nối giữa các node, và lượng giá giữa các node này.
Vấn đề đặt ra là trong qui trình thiết kế game, ban đầu người thiết kế chỉ tạo ra một bản đồ thế giới game và không hề có bất kì tri thức nào trên đó, do đó cần phải có một qui trình để ánh xạ từ một bản đồ game ban đầu thành một đồ thị node với đầy đủ tri thức phục vụ cho việc tìm đường.

Thông thường các tri thức AI được cung cấp cho game theo 2 cách khác nhau: có thể làm thủ công hoặc  làm bởi các quá trình độc lập tự động, tuy nhiên để đạt hiệu suất cao nhất cách thông thường là kết hợp giữa 2 cách trên,  quá trình tự động sẽ được diễn ra dưới sự giám sát và tối ưu lại của con người.


Knowledge for Pathfinding and Waypoint Tactics

1/ Tạo dữ liệu vùng tự động bằng tay:

Ở đây chúng ta chỉ xét đến bài toán tạo các tri thức AI cho vấn đề tìm đường, với 1 bài toán tìm đường chỉ cần 3 thành phần dữ liệu sau đây :
  • Vị trí đặt các node đại diện ( tọa độ, vị trí…)
  • Liên kết giữa các node.
  • Chi phí di chuyển giữa các node.
Các thành phần trên có thể được tạo cùng một lúc với nhau, nhưng thông thường để đạt được hiệu suất cao nhất và để chi tiết hóa game, chúng  thường được chia ra và xử lý riêng biệt với những công nghệ và cách thức khác nhau.

Ví dụ như việc tạo dữ liệu các node, vùng thường được làm thủ công bởi con người bởi vì với mắt quan sát của con người sẽ dể dàng thấy được các điểm tốt cho việc tìm đường… trong khi nếu để các thuật toán tự động sinh ra có thể sẽ rất mất thời gian, ngược lại quá trình tính toán kết nối và chi phí giữa các node thì lại thường được giao cho các giải thuật tự động của máy tiến hành vì đây thường là các quá trình lặp đi lặp lại với các phép toán nên máy tính sẽ tiến hành dễ dàng hơn con người.

Một yếu tố quan trọng ảnh hưởng đến việc tạo dữ liệu tri thức thủ công cho game AI đó là vấn đề chọn cách biểu diễn thế giới game bên dưới để mô hình hóa bản đồ game.

Sau đây là 4 cách thể hiện thế giới game:

a) Sử dụng Tile Graph


Chúng ta cùng xem xét bản đồ game bên dưới:
Hình 1 - Bản đồ game đã áp lớp Tile-Base.
Ban đầu người thiết kế game chỉ tạo ra một bản đồ game với các chi tiết đồ họa như cây cỏ, rừng, đầm lầy, sông núi… khi sử dụng cách biểu diễn Tile Graph, việc đầu tiên là hệ thống sẽ áp lên bề mặt bản đồ một lưới các đa giác giống nhau ( hình 1 mô tả lưới các hình vuông) tạo nên một Tile-Base, các đa giác bên trong Tile-Base có thể có bất kì hình dạng gì tuy nhiên thông thường để tiện lợi, dễ thiết kế, dễ tính toán và dễ chi tiết hóa bản đồ người ta sẽ sử dụng lưới hình vuông.

Sau khi đã có mạng lưới các đa giác Tile-Base, hệ thống sẽ xem một đa giác vuông trong đó là một node của đồ thị .Tại đây người thiết kế game sẽ bắt đầu cung cấp các tri thức về các node để phục vụ cho việc tìm đường .Việc cung cấp chi thức bao gồm việc cung cấp các trọng số cho vùng di chuyển được ( đường dốc, đường lầy, trọng số của rừng núi, sông ngòi…) và cung cấp tri thức cho các vùng không thể di chuyển ( hình 2 ).
Hình 2 – Cung cấp tri thức AI cho bản đồ game.
Sau giai đoạn cung cấp tri thức này ta đã có các node và có thể sử dụng các thuật toán tự động như giải thuật phân cấp đồ thị để tìm kết nối giữa các node này và tính toán chi phí giữa chúng.
Việc sử dụng Tile-Graph vẫn còn một số hạn chế sau:
  • Các node trên một Tile-Graph là quá nhiều khiến cho việc tìm đường sẽ tốn rất nhiều chi phí , ví dụ trong một màn nhỏ của các game chiến thuật thường dùng Tile-Graph với vài trăm ngàn node, để khắc phục điều này chúng ta có thể áp dụng các giải thuật phân cấp đồ thị để đồ thị trở nên đơn giản hơn cho việc tính toán.
  • Các node trên một Tile-Base được đánh dấu bằng cách đánh dấu đen toàn bộ với các vùng không đi được, đánh dấu các vùng đi được với các màu khác, tuy nhiên xảy ra trường hợp một node màu trắng bị một vùng màu đen tô lên, trường hợp này có thể gây sai lệch cho kết quả tìm đường như ví dụ dưới đây:
Hình 3 – Trường hợp bị ảnh hưởng bởi vùng tô đen.
Để khắc phục nhược điểm trên thông thường người ta sẽ chi tiết hóa bản đồ thành lưới nhỏ hơn để tránh việc các ô bị tô màu 1 phần.
Hiện tại cách biểu diễn thế giới game bằng Tile-Graph được sử dụng rất rộng rải nhờ ưu điểm dễ dàng hiện thực tự động và tính tiện lợi của nó.

b) Sử dụng Dirichlet Domain

Dirichlet Domain là một khái niệm toán học nhằm chỉ các vùng mà mỗi vùng sẽ có một điểm nguồn đại diện sao cho khoảng cách từ các điểm trong miền đến điểm nguồn đó là ngắn nhất so với các điểm nguồn khác.
Hình 4 – Các miền Dirichlet Domain
Với cách sử dụng miền Dirichlet domain để biểu diễn thế giới game người thiết kế game cần phải cung cấp dữ liệu ban đầu về các điểm dại diện sau đó các giải thuật tự động sẽ được thực thi để tạo ra các vùng Dirichlet dựa trên các điểm nguồn đó.

Ví dụ ta có thể sử dụng giải thuật Fotune để tạo các miền Dirichlet, giải thuật sẽ tạo nên một thanh đứng quét ngang qua bản đồ game, mỗi khi quét qua một node nào thì lời gọi hàm tính toán với trọng số của node đó được thực hiện và tạo ra miền Dirichlet tương ứng.
Hình 5 – Giải thuật Fortune để tạo miền Dirichlet
Sau khi các miền Dirichlet đã được tạo, mỗi vùng Dirichlet được xem như một node trong đồ thị với trọng số là trọng số của nút nguồn đại diện cho vùng, sau đó các giải thuật tự động sẽ được tiến hành nhằm tạo ra kết nối giữa các vùng cũng như tính toàn chi phí di chuyển giữa các vùng.

Việc tạo miền Dirichlet có thể có một số vấn đề nảy sinh sau:
  • Sự trùng lắp giữa các miền Dirichlet domain khác nhau dẫn đến sự sai lệch cho giải thuật tìm đường.Ở ví dụ bên dưới ta sẽ thấy vùng A và B bị trùng lắp, do đó khi một nhân vật trong vùng A di chuyển đến biên của vùng A vô tình nó đã đi qua vùng B, nếu B là vùng không đi được hoặc vùng nguy hiểm thì giải thuật tìm đường sẽ không thực hiện được.
Hình 6 – Sự trùng lắp giữa 2 miền Dirichlet domain

  • Các miền Dirichlet có quá nhiều hình dạng tùy ý, vì vậy không có gì đảm bảo việc di chuyển từ 1 điểm thuộc vùng này sang điểm thuộc vùng khác hoặc thuộc chính vùng đó sẽ không đi vào một vùng thứ 3 hay gặp chướng ngại vật. Như ví dụ bên dưới chúng ta thấy nếu vật di chuyển từ vùng màu đen bên dưới lên vùng màu xám bên trên sẽ bị vướng phải bức tường tại vùng bên trên, mà điều này lại trái với lý thuyết về vùng Dirichlet đó là các điểm trong một vùng sẽ liên thông do đó làm cho việc tìm đường bị sai.
Hình 7 – Chướng ngại vật cản việc di chuyển trong 1 vùng Dirichlet
Hiện nay nhờ các ưu điểm nổi bật về khả năng điều chỉnh bằng tay dễ dàng để can thiệp vào các vùng, cũng như khả năng dễ dàng được tự động hóa mà cách biểu diễn sử dụng Dirichlet domain được sử dụng rộng rãi trong ngành công nghiệp game.

c) Sử dụng Polygonal Mesh

Trong thế giới game ngày nay, các vật thể không chỉ là hình ảnh 2D, mà đa số là những đối tượng 3D. Để biểu diễn các đối tượng 3D,  người ta thường chia đối tượng 3D thành những đa giác rất nhỏ, sau đó vẽ các đa giác nhỏ này và ghép lại thành một đối tượng. Các đối tượng này có thể là một chú cá heo, một cái cây, một con người, cũng có thể là đồi núi với mặt đất gồ ghề, những ngôi nhà cao tầng có cầu thang lên xuống,…Ở đây, chúng ta chỉ quan tâm đến những đối tượng “đi được” như những nền nhà, cầu thang, đồi núi (các đa giác mô hình cho các đối tượng này được gọi là các đa giác nền), vì từ đó, ta sẽ lấy được dữ liệu cho việc tìm đường.
Hình 8 - Biểu diễn thế giới 3D bằng lưới đa giác
Mỗi đa giác trong các đa giác nền này sẽ được xem như là những nút trong đồ thị.Việc di chuyển của nhân vật trong thế giới thực, có thể được xem như là việc di chuyển giữa hai đa giác liền kề.Mặc nhiên, các chứng ngại vật vẫn được biểu diễn trong thế giới game, nhưng vì nó không có lợi trong việc tìm đường đi, nên nó cũng sẽ không được hiện thực.Và dĩ nhiên, tại vị trí của các chướng ngại vật sẽ không có đa giác nền nào.

Việc xây dựng những đa giác nền này, có vẻ thuần túy là một việc của người thiết kế màn chơi, chính xác là thiết kế địa hình cho màn chơi, và được làm dưới sự trợ giúp của một chương trình đồ họa. Kết quả có được và tập hợp các đa giác, mà mỗi đa giác có các đặc điểm riêng như: độ cao, độ nghiêng, góc nghiêng, chất liệu,... Tất cả các yếu tố này đều rất cần thiết cho việc di chuyển cũng như tìm đường tốt nhất, ví dụ như việc đi giữa sa mạc không thể nhanh bằng đi giữa đường quốc lộ, do đó người thiết kế phải mô hình hóa một cách cụ thể và chính xác nhất có thể.

Tuy nhiên, việc mô hình hóa một cách cụ thể có thể dẫn tới một khối lượng dữ liệu khổng lồ . Và để tối giản không gian dữ liệu, người ta phải thu nhỏ dữ liệu bằng cách gộp những đa giác gần nhau và có đặc tính giống nhau lại thành một đa giác lớn hơn. Tuy nhiên, việc gộp lại phải đảm bảo là độ chênh lệch không nhiều quá (chấp nhận được) so với các đa giác ban đầu . Như ví dụ dưới đây, các đa giác gần nhau cùng nằm trên một mặt phẳng (nửa dưới) hoặc có độ nghiêng gần bằng nhau (nửa trên), sẽ được gộp lại, từ một hình có 32 đa giác nền trở thành hình chỉ có 9 đa giác nền.
Hình 9 – Gộp những đa giác liền kề và gần giống nhau thành đa giác lớn hơn
Dĩ nhiên, ai cũng biết là không phải dễ dàng gì chọn những đa giác nền “gần giống nhau”, mà cần phải có một giải thuật tối ưu nhất. Còn việc tìm được một giải thuật tốt là một thách thức không nhỏ.

Như đã đề cập, vị trí của các chướng ngại vật được xem như là không có đa giác nền nào ở đó . Tuy nhiên, có một vấn đề nho nhỏ là, trong game luôn luôn có những chướng ngại vật “bị mất đi” (như một bức tường bị nổ bom, hoặc một cái bàn có thể di chuyển đến chỗ khác), do đó không thể xem như không có đa giác nền nào, mà phải xem là có một số đa giác nền “bị che khuất” (chúng mang trọng số riêng). Khi đó, các chướng ngại vật được xem như là các vật thể thông thường, không ảnh hưởng đến tri thức cho việc tìm đường . Mọi chuyện có vẻ đơn giản. Nhưng việc này là không thể nếu xét trường hợp là nhân vật có thể di chuyển qua lại, vì các đa giác nền “bị che khuất” của chúng thay đổi liên tục .

Một vấn đề nữa là việc hiện thực tri thức cho việc nhảy (jumping) . Như chúng ta biết, nhân vật luôn có nhu cầu nhảy từ đầu này qua đầu kia . Nếu cho phép nhân vật nhảy qua một hố sâu, tức nhân vật có thể di chuyển được qua cái hố . Trong cách nhìn của việc hiện thực đa giác nền, sẽ có một (hoặc một vài) đa giác nền nằm giữa hai đầu mút . Việc này kéo theo việc game sẽ cho phép nhân vật đi thẳng qua hố (giống như Doreamon đi giữa không khí vậy), dĩ nhiên, điều này là không thể chấp nhận.
Hình 10 – Một bước nhảy của nhân vật, có thể được hiểu là một sự liên thông giữa 2 nút xa nhau hoặc không

d) Bounded Regions

Để giải quyết vấn đề nhảy (jumping) mà chúng ta vừa đề cập, người ta đưa ra khái niệm “vùng được đóng biên” (bounded region). Theo đó, hai đầu mút sẽ là hai vùng riêng, và bị ngăn cách bởi một vùng ở giữa là vùng hố sâu.
Cách tiếp cận này cũng giải quyết được một vấn đề khác của miền Dirichlet (Dirichlet domains) mà chúng ta đã đề cập, khi nhân vật đang đứng ở miền này mà cứ nghĩ rằng mình đang ở miền khác . Chỉ cần xác định các vùng được đóng biên, sau đó chia miền Dirichlet trong các vùng này, sẽ đảm bảo không có việc nhầm lẫn .

Kết quả của cách làm này là một số các tri thức cho biết những vị trí nào có thể di chuyển trực tiếp được, vị trí của các biên mà dựa vào đó có thể tìm thấy các điểm chiến lược (waypoint tactics) .
Hình 11 – Các vùng khác nhau về độ cao và chất liệu có thể xem như là các vùng khác nhau
Thông thường, việc tìm các vùng được đóng biên được thực hiện một cách tự động dưới sự giám sát chặt chẽ của con người. Muốn làm được việc này, trước tiên người thiết kế màn chơi phải đặc tả chi tiết và dễ phân biệt (màu sắc khác nhau rõ rệt chẳng hạn) các vị trí . Sau đó, máy tính phải có khả năng nhận diện hình ảnh và phân biệt màu sắc để xác định các vị trí biên . Đồng thời, phải có một giải thuật tốt để việc xác định vị trí các vùng biên được diễn ra nhanh chóng . Chiến thuật thường được dùng là tạo ra một khối đa giác nhỏ (thường là hình vuông), nếu nó nằm gọn trong vùng biên thì mở rộng nó cho tới khi nó gần sát với đường biên thì thôi. Kết quả sẽ tạo ra một vùng có các biên là đường gấp khúc (hình bên phải), sau đó kết hợp các biên lại để các vùng khác nhau có thể nối với nhau qua cùng một biên (hình bên trái) .
Hình 12 – Sau khi dựng biên sẽ có khoảng cách nhỏ giữa các biên (trái), sau đó phải nối chúng lại thành một biên chung (phải).
Có một điều đáng chú ý đó là không phải vùng biên nào cũng đóng kín (ví dụ một căn phòng luôn có cửa ra vào), do đó người thiết kế phải giám sát quá trình tự động, và can thiệp để tránh trường hợp máy bị chạy vô tận.

2/ Automatics Graph Creation:

Theo các cách tiếp cận đã nói ở trên, chúng ta có thể hiểu được rằng, luôn có một giải thuật nào đó được sử dụng để tính chi phí và xác định những nút nào có thể liên thông trong đồ thị .

Một trong những cách đơn giản là việc sử dụng các điểm của việc nhìn thấy (point of visibility), tức là tính chi phí dựa trên độ dài mà chúng ta đo được. Một cách đơn giản nữa là dùng các miền Dirichlet (Dirichlet domains), theo đó các nút là các miền, và luôn liên thông nếu các nút có cạnh chung, còn tính chi phí là dựa vào tâm của miền.

Tuy nhiên, việc định vị các nút một cách tự động là một việc khó, thông thường là làm một cách thủ công . Hoặc làm tự động, với điều kiện người lập trình phải xây dựng một cơ chế mà máy có thể làm, để người thiết kế chỉ cần đưa bản đồ vào là có được các nút của đồ thị .

Có 2 cách để đưa ra một cơ chế làm tự động:

  • Geometric Analysis: Sử dụng các công thức, tính toán hình học để chọn những nút tốt nhất.
  • Data Mining: Tạo một tập dữ liệu lớn lưu trữ những vị trí mà nhân vật hay lui tới, và xác định các nút từ tập dữ liệu này.


3. Geometric Analysis:

a) Tính toán chi phí

Đây là một qua trình tương đối đơn giản, nên hiếm khi nào tìm thấy một game mà chi phí các node của nó được thực hiện bằng tay.

Phần lớn chi phí kết nối được tính toán bởi khoảng cách . Pathfinding thường liên quan tới việc tìm một đường đi ngắn, nên khoảng cách là một sự đo lường tự nhiên. Khoảng cách giữa 2 điểm có thể được tính toán một cách đơn giản. Đối với những dạng biểu diễn mà các node được xem như là điểm , khoảng cách của một kết nối có thể được xem như là khoảng cách giữa 2 điểm.

Dạng biểu diễn polygon mesh thường có chi phí kết nối dựa trên khoảng cách giữa các điểm trọng tâm của các tam giác kế cận. Dạng biểu diễn bouding region tương tự sử dụng điểm trung tâm của vùng để tính toán khoảng cách .

b) Calculating connections

Việc tính toán kết nối giữa các node là một ứng dụng phổ biến. Điều này phần lớn dựa trên việc kiểm tra line of sight giữa các điểm. Đây là cách tiếp cận dựa trên tầm nhìn.

Line of sight là một đường thẳng tưởng tượng giữa mắt của ta và đối tượng mà ta đang nhìn. Hiểu một cách đơn giản là nếu ta nhìn thấy đối tượng, ta và đối tượng đang nằm trên đường thẳng line of sight. Ví dụ : Một xe tăng ở phía sau đồi không thể nhìn thấy xe tăng địch ở phía bên kia đồi. Một nhóm lính trên đỉnh đồi có thể nhìn thấy xe tăng ở cả hai bên, nhưng 2 xe tăng có thể không thấy họ, vì line of sight phía trên của họ bị giới hạn. Tùy vào mỗi game mà người chơi không thấy được cửa, đồ vật hay quái vật ở góc tường.

Việc kiểm tra line of sight (light of sight check) được thực hiện bởi AI Vision component . Ở đây ta sẽ tìm hiểu một giải thuật line of sight check đơn giản mà AI Vision component sử dụng trong môi trường 2D.
Hình 13 – Kiểm tra kết nối dựa trên sự nhìn thấy.
Trong hình trên hình chữ nhật đỏ tượng trưng cho vật cần kiểm tra line of sight, hình chữ nhật xanh tượng trưng cho một vật cản. Nếu có ít nhất một đường thẳng từ điểm nhìn đến bất kỳ góc nào của hình chữ nhật đỏ không giao với hình chữ nhật xanh, ta kết luận là nhìn thấy được. Ngược lại thì vật cần kiểm tra đã bị che khuất hoàn toàn.

Point-Based Representation

Dạng biểu diễn dựa trên điểm ( như là miền Dirichlet và dạng biểu diễn point-of-visibility) liên quan đến việc mỗi node có duy nhất một điểm đại diện. Một line of sight check được thực hiện giữa các cặp điểm này. Nếu có một line of sight giữa 2 điểm này, thì có một kết nối giữa 2 điểm.

Cách tiếp cận này có thể dẫn đến có một số lượng lớn các kết nối trong đồ thị. Hình bên dưới cho thấy một một đồ thị dạng visibility-based quá phức tạp biểu diễn cho một căn phòng tương đối đơn giản.

Do đó, các nhà lập trình AI thường bày tỏ những mối lo ngại về hiệu năng của các đồ thị visibility-based. Nhưng chúng ta có thể khắc phục bằng cách tạo ra một đồ thị dễ dùng hơn sử dụng một giải thuật tiền xử lý đơn giản :
  1. Mỗi kết nối được xem xét lần lượt.
  2. Kết nối bắt đầu ở một node và kết thúc ở một node khác. Nếu kết nối đi qua một node trung gian trên đường đi, kêt nối này sẽ bị xóa.
  3. Chỉ những kết nối còn lại mới tạo nên pathfinding graph.
Hình 14 - Trước (A) và sau (B) việc thu giảm các kết nối của đồ thị theo dạng biểu diễn Dirichlet domain
Theo giải thuật này, có những cặp node nằm trên line of sight, nhưng không có đường đi nối giữa chúng. Nhân vật sẽ phải vượt qua một node khác trên đường đi .

Arbitrary Bouding Regions- Các vùng biên bất kỳ.

Để kiểm tra có kết nối giữa hai vùng biên, ta chọn ra những cặp điểm đại diện cho từng vùng và tiến hành line of sight check . Việc kiểm tra line of sight trong trường hợp này khác với trường hợp trên . Ta thực hiện kiểm tra light of sight trên từng đoạn. Nếu phát hiện có chướng ngại vật không thể vượt qua được (thường nằm ở ngay các vùng biên) thì dừng kiểm tra line of sight và xác định không có  kết nối giữa hai vùng.

Tuy nhiên, trong một số trường hợp xảy ra các kết nối sai . Ví dụ , xét kiểm tra line of sight của 2 nhân vật, một người ở trên đỉnh dốc thẳng đứng và một người ở chân dốc. Hai người cùng nằm trong đường line of sight của nhau . Vấn đề là nếu đứng từ góc nhìn của người trên đỉnh dốc thì có kết nối giữa 2 vùng, nếu đứng từ góc nhìn người dưới chân dốc thì không có kết nối . Đây là vấn đề cần xử lý cho những kết nối một chiều ở các vùng biên .

Thời gian tính toán kết nối ở một số trường hợp này tăng rất nhiều.Ví dụ, trường hợp kiểm tra line of sight từng phần đến biên là một bức tường có một cửa sổ nhỏ, ta cần tính toàn những thông liên quan đến khả năng nhân vật có thể vượt qua cửa sổ được hay không.

Những giới hạn của cách tiếp cận dựa trên tầm nhìn .

Vấn đề chính của cách tiếp cận line of sight là vấn đề nhìn thấy nhưng có đi được hay không . Vì hai vùng trên màn game có thể nhìn thấy lẫn nhau, nhưng điều đó không có nghĩa là bạn có thể di chuyển được giữa chúng.

Nhìn chung, không có một cách kiểm tra đơn giản nào giúp cho việc xác định bạn có thể di chuyển được giữa 2 vị trí trong màn game. Trong những game phiêu lưu hành động có góc nhìn của người thứ ba, cần có những sự kết hợp phức tạp những di chuyển chính xác đến một vị trí đặc biệt. Việc lường trước những bước di chuyển như vậy rất khó .

May cho chúng ta, những nhân vật AI trong những game như vậy hiếm khi nào phải thực hiện những chuỗi hành động như vậy. Chúng đơn giản được giới hạn di chuyển trong những khu vực dễ dàng định hướng được.

Dạng biểu diễn lưới đa giác tránh được một số vấn đề của cách tiếp cận tầm nhìn . Như trong ví dụ về việc kiểm tra line of sight của hai người đứng trên đỉnh dốc thẳng đứng và một người ở chân dốc . Vấn đề xác định khả năng có thể di chuyển giữa hai vị trí trở nên dễ dàng khi ta có một đa giác đặt ở vị trí sườn dốc . Mỗi đa giác có thông tin về độ sâu (gradiant) . Đa giác ở vị trí trên đỉnh dốc có lưu thông tin cao hơn đa giác ở sườn dốc nên nhân vật có thể di chuyển từ đỉnh dốc xuống . Trong khi ngược lại từ chân dốc lên sườn dốc thì không được .

Tuy nhiên, dạng biểu diễn lưới đa giác cũng có những vấn đề của chính nó (đặc biệt là jumping).  Ngày nay, data mining là một giải pháp hứa hẹn cho việc tìm đường trong những màn game có độ phức tạp cao.

Mesh Representation - Dạng biểu diễn lưới đa giác

Dạng biểu diễn lưới đa giác cung cấp một cách tường minh thông tin kết nối cho pathfinding graph .

Đa giác dùng trong dạng biểu diễn lưới đa giác thường là tam giác . Mỗi tam giác được xem như là một node trong đồ thị . Vì sao lại chọn tam giác cũng có  nhiều lý do. Thứ nhất , tam giác bảo đảm là đa giác phẳng. Trong việc tính toán chi phí ,dùng tam giác sẽ có lợi hơn trong việc xác định trọng tâm. Mỗi tam giác chỉ có 3 cạnh,  đơn giản trong việc tìm đường (có thể sử dụng cây tìm kiếm nhị phân nếu không xét cạnh đi ngược lại).

Hai tam giác có kết nối nếu chúng có một cạnh chung . Điều này cũng nảy sinh hiện tượng giật hình khi nhân vật tìm đường di chuyển qua khu vực có lưới dày đặc (thường gặp ở các khu vực gần biên, nơi các tam giác được chia với diện tích nhỏ) . Vấn đề này có thể giải quyết nếu ta chấp nhận hai tam giác có kết nối khi chúng có chung một đỉnh .
Hình 15 - Biểu diễn một mặt 3D thành các tam giác.

c) Calculating Nodes

Việc cung cấp dữ  liệu tự động vị trí các node dựa trên phân tích hình học không bao giờ chính xác tuyệt đối và rất khó khăn. Sau đó sử dụng các giải thuật thu giảm đồ thị.Các nhà phát triển phải thực hiện test node để chỉnh sửa đồ thị kết quả.

Thu giảm đồ thị là một chủ đề nghiên cứu lớn trong lý thuyết đồ thị . Từ một đồ thị rất phức tạp với hàng ngàn hoặc hàng triệu node, một đồ thị mới được tạo ra chỉ nắm lấy những điểm chính yếu của đồ thị lớn hơn . Trong chương 4 chúng ta đã xem xét một cách thu giảm đồ thị là tạo đồ thị phân cấp như thế nào.

Một màn game trung bình có khoảng mười triệu node và hàng trăm triệu kết nối .Việc tạo thành đồ thị mất một lượng lớn thời gian và bộ nhớ.Ta thực hiện nhiều cách để thu giảm số node này. Đối với game dùng cách biểu diễn lưới , những node của lưới ở ngoài vùng chơi (ví dụ như tường hoặc những vùng trên mặt đất không thể tới được) sẽ bị xóa. Nếu màn game được chia thành nhiều vùng , các node lưới sẽ được thêm vào những phần này.

Những nghiên cứu về những kỹ thuật thu giảm đồ thị đang được tiến hành.Vào lúc này, các nhóm phát triển game vẫn sử dụng phương pháp hiện có trong toolchain của họ , nhưng lúc nào cũng phải trông cậy vào việc quay trở lại kiểm tra và chỉnh sửa đồ thị kết quả.

4/ Data mining:

Ta có thể hiểu tư tưởng của phần data mining này một cách hết sức đơn giản như sau: Nếu như bạn được giao nhiệm vụ tạo ra bản đồ đường đi cho thành phố này trong khi bạn chỉ có bản đồ địa hình của nó thì bạn sẽ làm sao? Có hai trường hợp sẽ xảy ra:
  1. Bạn căn cứ vào bản đồ địa hình đó và suy đoán các vị trí có thể đi được và vẽ bản đồ đường đi, tuy nhiên chúng ta dễ thấy là cách này có vẻ không ổn vì việc bạn thấy được trên bản đồ chưa hẳn là bạn có thể đi đến được. Vì đó có thể là khu vực cấm, hay là đường một chiều….
  2. Bạn trực tiếp vừa đi vừa vẽ bản đồ các nơi đi được, sau đó về nhà tổng hợp và vẽ lại bản đồ đường đi. Cách này rõ ràng là rất tự nhiên và rất thiết thực, có điều rất mất công. Tuy nhiên đây chính là cách mà data ming chọn để tạo path finding graph.
Hình 16 - Tạo logfile vị trí các nhân vật AI (màu cam) giữa thế giới có nhiều biến động (khối màu vàng đang rơi xuống)
Cách sử dụng Data Mining để tạo đồ thị xác định các nodes bằng việc theo dõi dữ liệu di chuyển của các nhân vật  trong thế giới game.

Khi môi trường game(trọng lực, gió,..) đc xây dựng và các đối tượng địa lý của màn chơi (level) đc khởi tạo xong thì sau đó nhân vật sẽ được đặt vào  trong level đó. Nhân  vật có thể được điều khiển bởi người chơi hoặc là được điều khiển tự động.Khi nhân  vật di chuyển trong màn chơi, vị trí của nó  thường xuyên được ghi lại trong 1 logfile. Các dữ liệu về vị trí đó sẽ được khai thác để lấy ra những dữ liệu mà ta quan tâm. Đó có thể là những dữ liệu dùng để xây dựng pathfinding graph cho màn chơi.

Khi nhân vật đã di chuyển loanh quanh trong màn chơi đủ nhiều, thì sau đó phần lớn các vị trí hợp lệ của nhân vât đó sẽ được ghi  vào log file(chẳng hạn trường hợp 2 điểm quá gần nhau thì ta có thể chỉ lưu 1 điểm trong logfile cho đỡ tốn). Bởi vì nhân vật trong game engine sẽ có thể  sử dụng tất cả mọi cách di chyển có thể có như: nhảy, bay, vân vân nên sẽ ko cần thiết dùng những tính toán phức tạp để xác định nơi nhân vật có thể đi đến.

a) Tính toán các Nodes của đồ thị

Các vị trí mà nhân vật thường ở gần sẽ có khả năng chứa các các mối nối của các con đường và những  con  đường lớn  trong game level. Những vị trí này có  thể được nhận diện và gán luôn là các nodes trong  đồ  thị tìm đường.

Logfile được sắp xếp để các điểm được log gần nhau được tập hợp lại thành những vị trí đơn. Việc này có  thể  được thực  hiện bởi giải thuật "ngưng tụ" trong chương 4.

Sau đó Data mining được dùng kết hợp với biểu diễn miền  Dirichlet trong  màn chơi. Lúc này,  node được đặt vào khu vực nhân vật di chuyển dày đặc nhất. Thông thường, đồ thị có 1 kích thước cố định nghĩa là số điểm cho 1 đồ thị tìm đường thường  được cho trước. Trong trường hợp này giải thuật sẽ chọn ra số lượng các điểm được yêu cầu đó sao cho những điểm này có cùng mật độ di chuyển của nhân vật và giữa hai điểm trong tập được chọn đó không quá gần nhau .
Hình 17 - Từ mật độ di chuyển của các nhân vật AI, có thể suy ra các nút, kết nối của đồ thị

b) Tính toán kết nối giữa các nodes của đồ thị

Sau khi đã có nodes, đồ thị sẽ được tạo ra bằng một trong 2 cách sau :
  1. Point-of-Visibility approach.
  2. Cách phân tích  sâu hơn dữ liệu trong log file, là cách tốt hơn cách ở trên.
Point-of-Visibility approach chạy nhanh, nhưng không có gì đảm bảo rằng các node được chọn chọn sẽ ở  trong đường  ngắm trực tiếp .Nghĩa là 2 điểm đó sẽ có thể được nhìn thấy nhưng chưa chắc là có đường đi đến đó. Như vậy việc thêm vào connection này coi như là vô nghĩa.Đây là một điểm yếu của cách tiếp cận Point-of-Visibility. Mặt khác, nếu như có 1 góc tường thành lớn hình chữ L thì theo cách tiếp cận này hai node nằm ở mỗi cạnh của chữ L đó sẽ không có đường nối, đơn giản là vì chúng đã bị bước tường che mất. Như vậy là mất đi một connection hữu ích cho đồ thị tìm đường.

Dù rằng cách tiếp cận Point-of-Visibility ở trên chạy rất nhanh nhưng do còn nhiều bất cập nên người ta thường chọn cách thứ 2 để tạo connections. Đó là phân tích sâu hơn các dữ liệu ở trong logfile . Ta dễ thấy là những connection được tạo ra từ cách phân tích này có độ tin cậy cao hơn và chính xác hơn cách đầu do đây là đường mà nhân vật thực sự đi được. Để dùng data mining, trước hết, người ta dùng 1 giải thuật để ánh xạ hai chiều giữa node và entry được lưu trong logfile . Sau đó thì connections sẽ được thêm vào nếu như logfile chỉ ra được rằng nhân vật di chuyển được trực tiếp giữa những nodes đó . Vậy rõ ràng path finding graph được tạo ra theo cách này có chất lượng rất cao.

Sau khi đã có nodes và connections thì việc tính toán chi phí giữa các node có thể được thực hiện một cách tự động bằng cách sử dụng giải thuật .

c) Sự di chuyển của các nhân vật game

Để hiện thực giải thuật datamining thì nhân vật cần phải “cày” khắp bản đồ của màn chơi do đó cần 1 cơ chế để di chuyển nhân vật trong màn game. Điều này có thể hiểu đơn giản  như việc  có một người chơi điều  khiển nhân vật hoặc người đó chơi bản beta của game.

Việc dùng người thật để chơi rõ ràng là rất tốn kém, nhất là trong trường hợp màn game quá lớn, do đó cần có một giải pháp kỹ thuật tổng thể để có thể thay thế người thật trong việc này.Để giải quyết trường hợp này, nhân  vật sẽ đc điều khiển bởi AI với cách  tiếp cận đơn giản nhất là sử dụng sự kết hợp của các steering behaviors(cách thức di chuyển sẵn có của nhân vật như bay, nhảy, đi bộ…) kèm thêm các kỹ thuật như tránh chướng ngại vật, các bức tường…. rồi sau đó người ta sẽ cho nhân vật AI này đi lang thang trong màn game với kỳ vọng là nhân vật sẽ khám phá hết được mọi ngõ ngách trong cả màn game. Từ đó logfile được ghi nhận bởi nhân vật sẽ thật đầy đủ .

Với các nhân vật có thể nhảy hoặc bay thì không nên giới hạn cự ly di chuyển của nhân vật sử dụng steering behaviors để logfile được đầy đủ, và do đó pathfinding graph được tạo ra sau đấy có thể bao phủ được toàn bộ màn chơi một cách chính xác.

Như chúng ta đã thấy thì rõ ràng việc tạo  ra một nhân vật di chuyển tự động kiểu này là một thử thách đối với AI. Vì trong trường hợp lý  tưởng, nhân vật sẽ phải đi khai phá tất cả các khu vực  của  màn game, bất kể là khu vực đó rất khó cho nhân vật AI có thể đến được(thường đây là những khu vực mà đòi hỏi phải kết hợp một cách khéo léo và chính xác các các cách thức di chuyển mới đến được). Trường hợp lý tưởng là vậy nhưng trong thực tế, các nhân vật AI tự động thường bị mắc kẹt ở một khu vực nào đóhoặc là cứ liên tục  lặp đi lặp lại  việc  khám phá chỉ một khu vực nhỏ của level.

Do nhân vật AI có những vấn đề như đã đề cập ở trên nên để xây dựng được 1 logfile  chính xác, đầy đủ cho mỗi màn chơi thì nhân vật AI sẽ được khởi động đi khởi động lại từ những vị trí ngẫu nhiên nhiều lần. Như thế sẽ hạn chế đến mức tối thiểu nhất có thể việc nhân vật mà bị kẹt và kết quả là việc sử dụng kết hợp các logfiles thu được có thể bao phủ được  phần lớn màn game.

d) Các hạn chế của Data mining

Cách tiếp cận bằng data mining hiện nay có hai hạn chế lớn đó là:
  1. Thời gian.
  2. Lưu trữ logfile.
Đầu tiên là mặt bất cập thứ nhất: thời gian. Chúng ta thấy để đảm bảo rằng ko khu vực nào của level vô tình bị bỏ quên, và để đảm bảo rằng tất cả  các sự kết nối có thể xảy ra giũa các nodes được biểu điễn hết trong logfile thì nhân vật cần phải di chuyển loanh quanh trong một thời gian dài. Nhất là đối với những khu vực đòi hỏi những di chuyển phức tạp mới đến được thì con người phải can thiệp vào, như vậy sẽ gây tốn kém thời gian của người chơi.

Vấn đề thứ hai là dung lượng để lưu trữ logfile. Người ta đã thống kê và nhận thấychỉ một level game trung bình ( mà một nhân vật mất khoảng 30s để vượt qua với tốc độ tối đa) sẽ cần đến hàng triệu các log points được ghi lại. Trong việc khai phá cả màn chơi, đòi hỏi một lượng thời gian rất lớn, như vậy logfile sẽ rất khổng lồ…để xứng đáng được gọi là “mỏ” và rõ ràng công việc khai thác nó cũng chẳng khác gì “đào mỏ”. Để khắc phục dung lượng logfile thì ta có thể sử dụng người chơi vì dưới sự điều khiển của người chơi, ko cần nhiều các mẫu log points như nhân vật AI. Mặt khác người chơi  có thể kết hợp chính xác các cách thức di chuyển và lần lượt khám phá tất cả những khu  vực  từ dễ đến khó của màn gamemột cách thấu đáo. Không may, các tiếp cận này, như đã nói ở trên, bị giới hạn bởi thời  gian .

Trên thực tế thì các nhà phát triển thường dùngcách tiếp cận “lai”. Đó cách kết hợp  sự lang thang tự động của các nhân vật AI với người chơi  tạo logfile cho các khu vực khó.Như ta đã thấy, nhân vật AI thì có thể làm việc suốt 24/7 nên việc dùng chúng để tạo logfile các khu vực dễ di chuyển đến rõ ràng là rất hiệu quả, còn các khu vực khó thì có con người can thiệp nên vấn đề được giải quyết khá ổn.

Tuy giải pháp “lai: khá hiệu quả nhưng rõ ràng là vẫn chưa thỏa mãn được tính “lười” lao động cũng như những tham vọng trong lĩnh vực AI nên họ tiếp tục nghiên cứu để cho ra đời các giải pháp tự động tối ưu hơn. Trong số đó người ta đang nghiên cứu để tạo ra những nhân vật AI lang thang biết cách phân tích dữ liệu logfile trong đó để khám phá 1 cách có hệ thống những khu vực được log một cách nghèo nàn (tức có thể khu vực này chưa được khai phá), mặt khác nhân vật này phải biết sử dụng phối hợp của các cách di chuyển nhằm tạo ra một cách di chuyển mới lạ, hiệu quả để đến các vị trí khó trong màn game.

Như vậy như chúng ta đã thấy thì đến khi khi nào những AI exploring character đáng tin cậy được phát minh ra, thì lúc đó con người mới không cần can thiệp, tối ưu hóa một cách thủ công để tạo ra các path finding graph hữu ích.


======================

Bài này được viết theo nhóm, ngoài Nguyễn Kim Kha còn có Lương Duy Hoài, Nguyễn Thị Kim TuyênMai Thành Luân, là những người bạn cùng lớp.
Bài này được viết dựa trên cuốn Artificial Intelligence for Games của Ian Millington, nhà xuất bản Morgan Kaufmann, 2006

No comments:

Post a Comment

Biểu mẫu liên hệ

Name

Email *

Message *