Một số thuật toán ứng dụng điều khiển NPC trong bài toán mô phỏng huấn luyện rà phá bom mìn

Công nghệ thông tin Đ. V. Bình, , N. H. Liêm, “Một số thuật toán ứng dụng huấn luyện rà phá bom mìn.” 50 MỘT SỐ THUẬT TOÁN ỨNG DỤNG ĐIỀU KHIỂN NPC TRONG BÀI TOÁN MÔ PHỎNG HUẤN LUYỆN RÀ PHÁ BOM MÌN Đỗ Việt Bình1*, Đặng Hoàng Minh1, Ngô Duy Đô1, Trần Quang Dũng2, Nguyễn Huy Liêm2 Tóm tắt: Trong bài toán mô phỏng huấn luyện, NPC (non-player character), tạm dịch là những đối tượng người chơi không điều khiển được, đóng một vai trò quan trọng vào sự thành công của bài toán. Bài báo này đề xuất ứng dụng hai mô hình toán học vào mô phỏng NPC. Chúng tôi sử dụng thuật toán đồng bộ tọa độ giữa không gian 2D và 3D để xác định vị trí NPC trên bản đồ, kết hợp với nội suy đường cong spline để làm “mịn” chuyển động của NPC. Phương pháp đã được áp dụng trong đề tài mô phỏng thực địa của binh chủng công binh trong công tác rà phá bom mìn. Từ khóa: Mô phỏng; NPC; Nội suy; Đồng bộ; Thực tại ảo. 1. ĐẶT VẤN ĐỀ Ngày nay, đi cùng với sự phát triển mạnh mẽ của công nghệ thông tin thì công nghệ mô phỏng cũng đang có những bước phát triển vượt bậc. Trên thế giới đã có rất nhiều quốc gia áp dụng công nghệ thực tại ảo với phương tiện thật để huấn luyện cho binh lính trong quân đội. Việc ứng dụng công nghệ thực tại ảo vào vừa đem lại an toàn, hạn chế thương vong cho bộ đội, vừa đào tạo cho người lính thuần thục các kỹ năng cơ bản của công việc. Tại Việt Nam đã có một số lĩnh vực ứng dụng công nghệ thực tại ảo, tuy nhiên trong quân sự chưa được ứng dụng rộng rãi. Đặc biệt trong các công việc nguy hiểm như rà phá bom mìn. Đây là công việc sẽ trả giá bằng thương tật đi theo suốt cuộc đời, thậm chí cả mạng sống của người lính và đồng đội nếu không thuần thục các kỹ năng. Ưu điểm của việc ứng dụng công nghệ thực tại ảo vào huấn luyện rà phá bom mìn gồm: + Không phụ thuộc vào môi trường, địa hình. Chỉ cần triển khai trong một diện tích nhỏ là có thể huấn luyện, điều này tiết kiệm một cách đáng kể các chi phí di chuyển và chuẩn bị trước các buổi huấn luyện. + Linh hoạt thay đổi các bài tập, các địa hình để học viên có thể làm quen với các chủng loại bom, mìn, với các địa hình thời tiết khác biệt. + Bộ đội có thể luyện tập mọi lúc để nâng cao kỹ năng cũng như trình độ. + Thoải mái triển khai các ý tưởng của người giảng viên, kiểm tra. + Không có thương vong trong quá trình luyện tập. Điều quan trọng để tạo nên một không gian mô phỏng thực tế ảo là chúng ta phải xây dựng một môi trường mô phỏng gồm các NPC giống với thật nhất. Để tối ưu hóa các NPC ta cần quan tâm các thành phần cấu tạo nên chúng. Hầu hết các NPC được cấu tạo từ 3 thành phần. = + + (1) Ở đó Model: mô hình thực thể, Animation: hành động của thực thể, AI: ứng xử của thực thể với từng trường hợp cụ thể trong “game” [1, 2]. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 51 Để tạo ra một NPC thành công yêu cầu người thiết kế phải tối ưu cả 3 thành phần trên: mô hình, hành động và ứng xử của NPC. Trong bài báo này chúng tôi sử dụng quy trình mô phỏng NPC như sau: 1. Xây dựng mô hình dựa trên các công cụ thiết kế (3DS max, Maya...), model đã bao gồm animation. 2. Đưa các animation vào Animator Component của Unity dùng để quản lý và điều khiển model. 3. Xây dựng các ứng xử của NPC theo các tình huống trong game dựa trên tập luật và máy học. Phần 2 của bài báo này chúng tôi trình bày phương pháp “phép chiếu ngược” để đồng bộ tọa độ (x, y) trong không gian 2D với tọa độ (x’,y’,z’) trong không gian 3D. Đây cũng là đóng góp chính của bài báo. Các phần còn lại, chúng tôi sẽ trình bày thuật toán để làm “mịn” sự di chuyển của các NPC tránh việc giật cục và nhiễu khi di chuyển và phương pháp ứng dụng AI vào các ứng xử của NPC. 2. PHƯƠNG PHÁP ĐỒNG BỘ TỌA ĐỘ 2D VÀ 3D 2.1. Xây dựng lý thuyết Khi triển khai các mô hình huấn luyện mô phỏng, một trong các yêu cầu tiên quyết là mô hình phải linh hoạt, chi tiết, đáp ứng được yêu cầu, ý tưởng của người ra đề. Một thành phần quan trọng để giải quyết được yêu cầu trên đó là việc đồng bộ giữa bản đồ 2D (của giảng viên, người ra đề) với môi trường mô phỏng 3D (nơi các học viên tập bài). Bài toán được phát biểu như sau: Hệ thống huấn luyện gồm 2 thành phần chính: Máy tính giáo viên, môi trường mô phỏng huấn luyện. Trên máy tính của giáo viên tích hợp một bản đồ số 2D để bố trí bom, mìn, vật cản,... cũng như theo dõi vị trí di chuyển của học viên. Môi trường 3D là môi trường ở đó học viên thực hành các động tác vòng vượt, dò mìn,... như vậy ta coi môi trường mô phỏng cho học viên là một bản đồ số 3D. Yêu cầu đặt ra là khi giáo viên thay đổi vị trí của bom, mìn, vật cản thì môi trường 3D sẽ thay đổi theo. Hay khi giáo viên thay đổi bản đồ, địa hình thì môi trường huấn luyện của học viên cũng thay đổi theo. Dựa theo cách giải quyết thông thường chúng ta sẽ phải có một bản đồ 2D cỡ nhỏ khoảng 1:5000 và đường bình độ trên các bản đồ đó để xây dựng mô hình mô phỏng 3D. Tuy nhiên theo cách giải quyết này chúng ta sẽ gặp một số khó khăn như sau: + Một là các bản đồ cỡ nhỏ 1:5000 kèm theo đường bình độ rất ít, chi phí để số hóa một bản đồ là khá lớn. Một số bản đồ tỉ lệ nhỏ còn được bảo mật vì vậy rất khó tìm đến. + Hai là, cho dù có bản đồ thì độ chi tiết không cao, không thể hiện được hết các chướng ngại vật, sự đa dạng của địa hình. + Ba là, khi thực hành huấn luyện mô phỏng chúng ta cần cho học viên làm quen với nhiều loại địa hình và thời tiết, cho nên yêu cầu số lượng bản đồ khá lớn 52 để tập b dựng ra cũng không đ ra đ đó s m đồ 2D v y) dài ( giáo viên đồ 2D chú Đ Trư ề có thể thoải mái bố trí các địa h ử dụng phép chiếu đứng để l ỗi lần thay đổi ý t Bài toán đư trên b Như v Đ Đ. V. B ể khắc phục các ớc hết chúng tôi xây dựng mô h w) và ể tính toán vị trí của đối t ài. D à 3D tương ản đồ 2D của giáo vi ậy để giải b . V ình, , N. H. Liêm chi ị trí của gốc tọa độ bản đồ 2D trong bản đồ 3D ng tôi s ẫn đến phát sinh chi phí xây dựng bản đồ v ợc đặt ra l ều cao ử dụng thuật toán (2.1) khó khăn trên chúng tôi s ưởng khác nhau ta sẽ đ ứng n ài toán này chúng ta c ược chi tiết. Hình 1. (h) c Hình 2. ày s à chúng ta ph ủa bản đồ , “ ẽ đ ên v Một số thuật toán ứng dụng huấn luyện r ư Mô hình h Mô hình ượng tr ấy bản đồ 2D tr ợc l ới tọa độ ưu l 2D ên đ ình b ình: ao h ải đồng bộ đ , v đ . ư ại l ệ thống mô phỏng (x ần quan tâm đến một số thông số: chiều ị trí ồng bộ 2D v ịa h ử dụng giải pháp giải b ản đồ số 3D. Ở tr ợc mỗi bản đồ 2D khác nhau. Các bản àm d ’, y ình 3D t ồ, sông ng ’, z’ (x, y ên m ữ liệu tập b ư ) ợc tọa độ của các các điểm trên mô hình hu ) đ à 3D ương ặt phẳng xOz. Nh ặt vật cản à các b òi, . (X . ứng với tọa độ tr ên b đồi núi, vật cản... Sau ài ( 0, Y Công ngh Hình 1 trong b 0, Z ản đồ đ ài toán ngư ản đồ n 0 à phá bom mìn ). ấn luyện ) (H ệ thông tin ày ngư ư v ản đồ ình ược xây ậy với ên b ợc. 3D. c 2). .” ời (x, ủa ản Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 53 Thuật toán 2.1: Đồng bộ tọa độ từ 2D sang 3D Input: (x, y), (w, h), (X0, Y0 , Z0) Output: (x’, y’,z’) [1]. 0 0' 2 | | w x x X X    (2) [2]. 0 0' 2 | | y z Z Z h     (3) [3]. = 0 [4]. ’ = . . ℎ(’, ’, ’) [5]. Return (x’, y’,z’) Thuật toán 2.1 dùng để xác định vị trí của các NPC trong môi trường huấn luyện của học viên. Tại đây máy mô phỏng sẽ tính lại vị trí (x’, y’, z’) sao cho vị trí ở trong 3D hiện có độ trễ không đáng kể ( hầu như đồng thời). Trước hết dựa vào tọa độ đầu vào chúng tôi xác định tọa độ x’, z’. Đặt mặc định độ cao bằng 0 và sử dụng hàm Terrain.activeTerrain.SampleHeight để đặt đối tượng lên bề mặt địa hình. Để xác định đường đi của học viên hiển thị trên màn hình của giảng viên chúng tôi sử dụng thuật toán 2.2 để đồng bộ tọa độ 3D về 2D. Thuật toán 2.2: Đồng bộ tọa độ từ 3D sang 2D Input: (x’, z’), (w, h), (X0, Y0 , Z0) Output: (x, y) [1]. = /2 + ′ ⋅ /|2 ∙ | (4) [2]. 0' / | 2 | 2 h y z h Z    (5) [3]. Return (x,y) Như vậy khi tích hợp đồng thời thuật toán 2.1 và 2.2 vào hệ thống mô phỏng, người giáo viên có thể đồng thời thiết kế các tình huống và quan sát hành động, đường hướng di chuyển của học viên. Từ đó đưa ra các nhận xét giúp cho người tập bài rút kinh nghiệm, và điều chỉnh. Đồng thời người học viên cũng sẽ được làm quen với các tình huống bất ngờ và sát với thực tế nhất. 2.2. Thực nghiệm, đánh giá Để kiểm chứng tính đúng đắn và hiệu suất của thuật toán chúng tôi đã thực nghiệm trên môi trường mô phỏng thực tế ảo chạy trên máy trạm với cấu hình Intel(R) Core(TM) i7-7800X CPU @ 3.50GHz (12 CPUs), ~3.5GHz, 16384MB RAM và máy tính giáo viên với cấu hình Intel(R) Core(TM) i3-6100U CPU @ 2.30GHz (4 CPUs), ~2.3 GHz, 4096MB RAM Chúng tôi đã tiến hành thử nghiệm với hơn 20 địa hình trên các môi trường khác nhau, được xây dựng theo các giáo trình rà phá bom mìn của binh chủng công binh. Trên thực nghiệm cho thấy sự chính xác khi đồng bộ các tọa độ trên bản đồ của máy giáo viên và môi trường mô phỏng. Bên cạnh đó khi thay đổi các loại địa hình đã tiết kiệm được rất nhiều thời gian và chi phí chuẩn bị, điều này giúp đa dạng hóa các loại hình huấn luyện. Bên cạnh đó việc sử dụng 2 thuật toán Công nghệ thông tin Đ. V. Bình, , N. H. Liêm, “Một số thuật toán ứng dụng huấn luyện rà phá bom mìn.” 54 chúng tôi đề xuất đã tiết kiệm một cách đáng kể chi phí về thời gian cũng như tiền bạc để số hóa các bản đồ 3D và xây dựng địa hình 3D. Sự đơn giản và hiệu quả của thuật toán đã đáp ứng được sự liên tục trong việc triển khai các hạng mục trong bài toán huấn luyện, không có độ trễ, làm gián đoạn các công việc tiếp theo của việc huấn luyện. 3. PHƯƠNG PHÁP LÀM MỀM ĐƯỜNG DI CHUYỂN CỦA NPC “Animation” hay chuyển động của NPC góp phần quan trọng vào sự thành công của một dự án mô phỏng. Bài toán đặt ra là mô phỏng đường di chuyển của NPC từ điểm A đến điểm B một cách tự nhiên nhất. Thông thường để các NPC di chuyển một cách “mượt mà” thì người ta sẽ chia nhỏ đường đi từ AB làm n đoạn nhỏ, mỗi đoạn có độ dài di. Khi n càng lớn thì di càng nhỏ tức là khi đó đường di chuyển của các NPC sẽ không còn là các đường gấp khúc nữa mà là các đường cong tự nhiên. Tuy nhiên việc tạo ra các điểm trung gian trên đường di chuyển của các NPC bằng thủ công rất tốn thời gian. Để giải quyết điều này chúng tôi sử dụng thuật toán nội suy để tìm các điểm trung gian giữa 2 đầu mút A và B. Có nhiều phép nội suy như tuyến tính, Lagrange, Newton[3]. Phép nội suy tuyến tính tuy có độ phức tạp thấp nhưng nhược điểm rõ ràng nhất là các chuyển động của NPC sẽ bị giật cục. Để tăng độ “mịn” ta phải chia nhỏ đường đi từ 2 điểm thành nhiều điểm khác điều này làm nâng cao độ phức tạp. Thuật toán nội suy Lagrange và Newton là những phép nội suy đáp ứng được hình dạng di chuyển của NPC nhưng có một điểm hạn chế to lớn là nếu số lượng lấy mẫu càng lớn thì kích thước bậc của đa thức nội suy càng tăng. Điều này làm tăng độ phức tạp tính toán theo cấp lũy thừa. Để đảm bảo được việc cân bằng tài nguyên hệ thống và đường di chuyển của NPC vẫn đảm bảo được yêu cầu của người dùng chúng ta đề xuất giải pháp sử dụng giải phá nội suy Spline bậc 3 (Hình 3). Hình 3. Nội suy SPLine và tuyến tính trong khớp đường cong. Trong môi trường mô phỏng Unity chúng tôi sử dụng n đa thức SPLine bậc 3 liên tiếp nhau để khớp đường di chuyển từ A đến B [2, 4]. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 55 4. ỨNG DỤNG AI TRONG ỨNG XỬ CỦA NPC Trò chơi là một lĩnh vực ứng dụng từ rất sớm trí tuệ nhân tạo. Càng ngày các trò chơi phát triển các NPC càng tinh tế hơn và thông minh hơn. Các hệ thống đầu tiên sử dụng AI dựa trên quy tắc (Rule-based Systems) như Máy trạng thái hữu hạn (Finite-state Machine) hay Logic mờ (Fuzzy Logic), và chúng vẫn được sử dụng rộng rãi tới ngày hôm nay. Trong bài báo này chúng tôi đề xuất phương án sử dụng các tập luật để xây dựng mô hình ứng xử cho NPC. Do việc phải cần đối tài nguyên hệ thống giữa các hành động của người tập bài và phản ứng với môi trường cho nên việc sử dụng độ phức tạp tính toán cho AI của NPC còn ở mức hạn chế [5]. Nền tảng Navmesh được sử dụng để xây dựng các ứng xử cơ bản cho các NPC khi gặp chướng ngại vật cũng như các tính huống đơn giản. Ví dụ về di chuyển của NPC khi gặp các vật cản khác nhau (Hình 4). Khi gặp chướng ngại ngại vật với độ cao vừa phải hoặc tường vát thì NPC có thể trèo qua, còn khi gặp tường đứng và cao thì NPC phải vòng qua. Hình 4. Mô tả di chuyển của NPC với các chướng ngại vật. 5. KẾT LUẬN Trong bài báo này chúng tôi đã phân tích các thành phần cấu tạo nên một NPC hoàn chỉnh. Qua đó đề xuất các phương án để tối ưu hóa 3 thành phần của NPC là Model, Animation, AI. Dựa trên các phương án đề xuất chúng tôi đã ứng dụng vào việc xây dựng các NPC cho mô hình huấn luyện mô phỏng rà phá bom mìn. Qua việc áp dụng các công nghệ thông minh vào công tác mô phỏng thực hiện huấn luyện của quân đội, chúng tôi hi vọng sẽ xây dựng được một mô hình vừa đảm bảo nâng cao kỹ năng, trình độ của bộ đội lại vừa hạn chế thương vong của bộ đội. Tuy nhiên các NPC vẫn còn hạn chế về tính “thông minh” do việc ứng dụng AI vào chưa nhiều. Trong tương lai chúng tôi sẽ nghiên cứu thêm việc ứng dụng máy học vào các ứng xử của NPC. TÀI LIỆU THAM KHẢO [1]. Warpefelt. Henrik, “The Non-Player Character: Exploring the believability of NPC presentation and behavior,” Sweden by Publit (2016). [2]. https://docs.unity3d.com. [3]. Hoàng Xuân Huấn, “Giáo trình các phương pháp số,” NXB Đại học Quốc gia Hà Nội (2004), tr. 20-27. Công nghệ thông tin Đ. V. Bình, , N. H. Liêm, “Một số thuật toán ứng dụng huấn luyện rà phá bom mìn.” 56 [4]. Gustav Grund Pihlgren ; Martin Nilsson ; Mikael Larsson ; Oskar Olsson ; Tobias Foughman ; Victor Gustafsson, “Realistic NPCs in Video Games Using Different AI Approaches,” Chalmers University of Technology, (2016). [5]. S. Risi; J. Togelius, “Neuroevolution in Games: State of the Art and Open Challenges”, IEEE Transactions on Computational Intelligence and AI in Games (2017), pp 25-41. ABSTRACT THE METHODS TO CONTROL NPC IN MINE CLEARANCE TRAINING SIMULATION SYSTEM In the simulation systems, non-player character (NPC) plays an important role in the success of them. In this paper, we propose two mathematical models to naturally control NPC. We use coordinate synchronization algorithm between 2D and 3D space to locate the NPC on the map and then combines with spline curve interpolation to make smooth movement of NPC. These method has been applied in field simulation which ordnance army uses in mine clearance trainning. Keywords: Simulation; NPC; Interpolation; Synchronization. Nhận bài ngày 16 tháng 08 năm 2018 Hoàn thiện ngày 06 tháng 11 năm 2018 Chấp nhận đăng ngày 25 tháng 3 năm 2019 Địa chỉ: 1 Viện Công nghệ thông tin/Viện KH-CN quân sự; 2 Học viện Kỹ thuật quân sự. * Email: binhdv@gmail.com.