基于群智能的NPC行為建模研究

魏凌華,張棟冰,范 祺

（淮北師范大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，安徽 淮北 235000）

自1956年正式提出以后，人工智能［1］獲得極大的發(fā)展，成為一門交叉前沿的學(xué)科，在多個領(lǐng)域得到應(yīng)用，特別是在游戲中的應(yīng)用，極大地提高游戲的可玩性，這些技術(shù)包括：有限狀態(tài)自動機，、腳本設(shè)計、基于規(guī)則的人工智能和系統(tǒng)、人工生命、決策樹、遺傳算法［2-4］等.

其中有限狀態(tài)機（Finite State Machine，簡稱FSM）是最常見的人工智能技術(shù)之一，有限狀態(tài)機被廣泛地應(yīng)用于游戲［5-6］設(shè)計研究中，有限狀態(tài)機技術(shù)極大地提高了游戲中NPC（非玩家角色，Non-Player Character）的智能程度，但在NPC之間并沒有協(xié)同［7-9］能力，這極大地降低游戲的可玩性.

1 相關(guān)知識

1.1 有限狀態(tài)機概念

FSM是表示有限個狀態(tài)以及在這些狀態(tài)之間轉(zhuǎn)移和動作等行為的數(shù)學(xué)模型，在給定輸入集IN和狀態(tài)集SN，一旦輸入in和狀態(tài)sn確定，通過狀態(tài)轉(zhuǎn)移函數(shù)T，則能確定下一個狀態(tài)sn+1和輸出o+1.它把復(fù)雜的行為抽象為多種狀態(tài)，且不同狀態(tài)在一定的條件下可以相互轉(zhuǎn)移.

1.2 群智能概述

群智能（Swarm Intelligence）作為人工智能的一個重要分支，最初是受社會性昆蟲的集體行為的啟發(fā)而提出的，群智能［10-11］是一種有限智能個體表現(xiàn)出來的集體智能方法，最早由多瑞哥等于1999年在《群智能：從自然到人工系統(tǒng)》中首先正式提出，其算法在眾多領(lǐng)域得到廣泛的應(yīng)用.

群智能中最經(jīng)典的算法有蟻群算法、粒子群算法以及其他一些算法，這些算法在旅行商問題、工業(yè)問題、生物信息學(xué)問題［12-14］等眾多領(lǐng)域取得了非常好的效果.這些算法都體現(xiàn)協(xié)同處理的優(yōu)勢，實驗表明在自然界中動物之間存在多種通訊方式，包括物理和化學(xué)刺激，其中物理通訊有光、聲音、壓力，對應(yīng)于視覺、聽覺和觸覺通訊，化學(xué)的刺激對應(yīng)于嗅覺和味覺的化學(xué)通訊［15］.

在自然界中，覓食、棲息地選擇、遷徙以及競爭等動物的本能行為，是為了更好的生存，特別是對具有社會性的昆蟲.社會性昆蟲具有高度發(fā)達的社會組織，其重要特征就是分工與合作.在蜜蜂、螞蟻、鳥類以及魚類等群居性動物中表現(xiàn)尤為明顯.

作為一個智能體應(yīng)該具備兩個方面的能力，第一，自控能力.對自己的行為和狀態(tài)具有控制權(quán)；第二社交能力.能與其他主體進行交互交流和溝通，可以實現(xiàn)合作、協(xié)商和競爭等行為.

1.3 游戲中的知識定義

定義1人工智能是計算機科學(xué)中涉及研究、設(shè)計和應(yīng)用智能機器的一個分支.其近期的主要目標在于研究用機器來模仿和執(zhí)行人腦的某些智力功能，并開發(fā)相關(guān)理論和技術(shù).

定義2群智能：任何一種受昆蟲群體或其他動物社會行為機制啟發(fā)而設(shè)計出的算法或分布式解決問題的策略均屬于群智能范疇.

設(shè)NPC的狀態(tài)有S=｛巡邏P，進攻A，逃跑E｝；T=｛敵人出現(xiàn)1；敵人死亡或逃跑2；NPC處于危險狀態(tài)3｝.斜線的左邊表示輸入，斜線的右邊表示輸出，初始狀態(tài)從P開始.當(dāng)前狀態(tài)sn和條件t的組合指示出下一個狀態(tài)sn+1，從圖1中可以看出狀態(tài)轉(zhuǎn)換的過程.

圖1 NPC的三狀態(tài)機

鑒于系統(tǒng)設(shè)計的需要，本系統(tǒng)中設(shè)置以下兩條規(guī)則.

規(guī)則1：系統(tǒng)中每種NPC都可以和其他NPC進行通信；

規(guī)則2：系統(tǒng)中所有的NPC狀態(tài)變化都遵循FSM規(guī)則.

2 基于群智能的協(xié)同算法

在沒有通信和交流的能力之前，NPC各自為戰(zhàn)，沒有合作的功能，這極大地降低游戲的可玩性和模擬真實情況的能力.

算法NPC-Coop

＜1＞NPC處于巡邏狀態(tài)；

＜2＞NPC遇到敵人，讀取敵人信息，判斷敵人狀態(tài)和自我狀態(tài)；

＜3＞NPC開始進攻，做以下選擇：

（1）開始進攻目標；

（2）根據(jù)規(guī)則1，在進攻的同時向其他NPC發(fā)出請求支援信息；

（3）根據(jù)規(guī)則2，所有參與的NPC根據(jù)自身狀態(tài)，直至所有參與的NPC全部死亡或撤退或敵人撤退或死亡；

＜4＞本次戰(zhàn)斗暫時結(jié)束.

3 量化分析

3.1 設(shè)計分析

根據(jù)NPC-Coop算法，本文在輸出函數(shù)中加入通信的能力，以此提高協(xié)調(diào)能力.

圖2 NPC的新三狀態(tài)機

O’=｛攻擊A，巡邏P，逃跑E，盟友通信M｝，此時的狀態(tài)見表2.

表2 NPC的新狀態(tài)

根據(jù)圖2和圖1比較可以看出，NPC狀態(tài)沒有增多，也沒有提高狀態(tài)轉(zhuǎn)移表的復(fù)雜度，唯一變化的是NPC多了通信的能力.

3.2 時間比較

在時間方面，主角消耗的時間主要包括搜索時間和作戰(zhàn)時間.

設(shè)Search（t）為搜索時間，F(xiàn)ight（t）為作戰(zhàn)時間，F(xiàn)ullTime（t）為主角消耗總時間；

假設(shè)主角消滅一個NPC需要K秒，尋找一個NPC需要M秒，NPC的數(shù)目為N個.

為了做一個平均時間測試，做兩個假設(shè)前提：

前提1：巡邏時，不同NPC不會同時和其他NPC出現(xiàn)在一個地方；

前提2：主角生命值無限大.

在NPC-Coop算法下，會出現(xiàn)兩種較為極端的情況.

第一：最好情況.在主角尋找到并消滅第一個NPC的時候，其他NPC都接收到指令并趕到現(xiàn)場，則主角消滅所有NPC的時間N*K+M秒；

第二：最差情況.主角需要找到每個NPC并且分別消滅每個NPC的時間N（K+M）秒；

由此可以看出，在時間上隨著NPC數(shù)量的增加，主角節(jié)約的時間越多，在相同NPC數(shù)目下最好情況和最壞情況時間比N（K+M）/（N*K+M），當(dāng)N?M時兩者時間相差為一倍多.

假設(shè)K為2，M為6，由圖3可以看到兩者時間的對比情況.

圖3 時間對比

通過NPC-Coop算法，增加NPC之間的通信能力和智能程度，提高游戲的可玩性.

4 結(jié)語

通過協(xié)同算法提高NPC之間的協(xié)同能力，完成單個NPC無法完成的任務(wù)，也優(yōu)化NPC的智能程度，并以此提高游戲的可玩性.希望可以為其他游戲的開發(fā)提供一些有意義的借鑒.由于系統(tǒng)在實際設(shè)計時需要考慮較多的參數(shù)，因此游戲的數(shù)值平衡、NPC的通信方式等問題還有待完善.

［1］史忠植.高級人工智能［M］.3版.北京：科學(xué)出版社，2011.

［2］BARAS J S，JAMES M R.Robust and risk-sensitive output feedback control for finite state machines and hidden markov models［J］.To Appear J Math Systems，Estimation and Control.

［3］胡喜玲，李洪波，胡俊.基于自適應(yīng)混沌遺傳算法的路徑規(guī)劃［J］.計算機工程與應(yīng)用，2013，49（9）：68-73.

［4］李志強，胡曉峰，楊雪生，等.虛擬環(huán)境中大規(guī)模群體行為建模研究進展［J］.計算機工程與應(yīng)用，2008，44（8）：45-48.

［5］朱全銀，章慧，孫文杰.基于J2ME技術(shù)的手機網(wǎng)絡(luò)游戲研究與開發(fā)［J］.計算機工程與應(yīng)用，2008，44（32）：76-78.

［6］董改芳，許道云.游戲中尋找路徑的改進算法［J］.計算機工程與應(yīng)用，2009，45（23）：38-39.

［7］HILLS D.Co-evolving parasites improves simulated evolution as an optimization procedure［J］.Physica D，1990，42（1）：228-234.

［8］PAREDIS J.Coevolutionary computation［J］.Artificial Life，1995，2（4）：355-375.

［9］董紅斌，黃厚寬，印桂生，等.協(xié)同演化算法研究進展［J］.計算機研究與發(fā)展，2008，45（3）：454-463.

［10］余建平，周新民，陳明.群體智能典型算法研究綜述［J］.計算機工程與應(yīng)用，2010，46（5）：1-4.

［11］BLUM C，MERKLE D.群智能［M］.龍飛，譯.北京：國防工業(yè)出版社，2011.

［12］ONWUBOLU G，CLERC M.Optimal path for automated drilling operations by a new heuristic approach using parti?cle swarm optimization［J］.International Journal of Production Research，2004，42（3/1）：473-491.

［13］李德福，郭海湘，劉龍輝，等.改進型粒子群優(yōu)化算法求解車輛路徑優(yōu)化問題［J］.計算機工程與應(yīng)用，2012，48（20）：216-223.

［14］冀俊忠，黃振，劉椿年，等.基于多粒度的旅行商問題描述及其蟻群優(yōu)化算法［J］.計算機研究與發(fā)展，2010，47（3）：434-444.

［15］孫儒泳.動物生態(tài)學(xué)原理［M］.3版.北京：北京師范大學(xué)出版社，2001.