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