人工生命轉(zhuǎn)向行為綜合性實(shí)驗(yàn)設(shè)計(jì)與實(shí)現(xiàn)

吳登權(quán), 孫良旭, 李林林, 劉夢(mèng)迪, 袁 杭

(遼寧科技大學(xué) 軟件學(xué)院, 遼寧 鞍山 114051)

人工智能 (artificial intelligence)的概念 是1956年在Dartmouth學(xué)會(huì)上提出的。人工智能是研究、開(kāi)發(fā)用于模擬、延伸和擴(kuò)展人的智能的理論、方法、技術(shù)及應(yīng)用系統(tǒng)的技術(shù)科學(xué)[1]。目前“人工智能+新工科”已經(jīng)成為國(guó)內(nèi)高校工科教育的研究熱點(diǎn)[2-3]。人工生命(artificial life) 的概念是由Christopher Langton在1987年“生成以及模擬生命系統(tǒng)的國(guó)際會(huì)議”上提出的。人工生命是自然生命的模擬、延伸或擴(kuò)展,是具有類似自然生命內(nèi)在性能或外部行為的人造系統(tǒng),可以通過(guò)計(jì)算機(jī)相關(guān)技術(shù)實(shí)現(xiàn)多種形式的人工生命[4-7]。

人工智能輔助教學(xué)系統(tǒng)是現(xiàn)代科研的重要成果,是新技術(shù)的體現(xiàn)。將人工智能技術(shù)應(yīng)用到教育教學(xué)上,有利于促進(jìn)學(xué)生和教師的發(fā)展,促進(jìn)教育領(lǐng)域方面的改革[8-9]。目前多數(shù)院校的計(jì)算機(jī)編程課程教學(xué)還存在著許多問(wèn)題, 無(wú)法滿足學(xué)生的發(fā)展需求[10-11]。雖然在現(xiàn)有的計(jì)算機(jī)編程類綜合性實(shí)驗(yàn)中能夠體現(xiàn)問(wèn)題導(dǎo)向、任務(wù)驅(qū)動(dòng)等好的實(shí)驗(yàn)教學(xué)方法,但是問(wèn)題或者任務(wù)本身多是數(shù)值計(jì)算或者信息管理問(wèn)題,沒(méi)有新穎性和娛樂(lè)性,可視化效果不好,而且算法難度較低,業(yè)務(wù)邏輯簡(jiǎn)單,技術(shù)實(shí)現(xiàn)容易,不能滿足學(xué)生在綜合性實(shí)驗(yàn)中的問(wèn)題、技術(shù)、難度和工作量等方面的要求。 本文選擇人工智能與游戲開(kāi)發(fā)交叉的研究領(lǐng)域中新穎有趣的人工生命角色轉(zhuǎn)向行為作為研究問(wèn)題,設(shè)計(jì)了人工生命角色轉(zhuǎn)向行為綜合性實(shí)驗(yàn),實(shí)現(xiàn)了典型的8種轉(zhuǎn)向行為,具體描述了轉(zhuǎn)向行為理論基礎(chǔ)、類庫(kù)設(shè)計(jì)和轉(zhuǎn)向行為實(shí)現(xiàn),為解決計(jì)算機(jī)編程類課程綜合性實(shí)驗(yàn)設(shè)計(jì)問(wèn)題提供一個(gè)新穎有趣的解決方案。

1 轉(zhuǎn)向行為

轉(zhuǎn)向行為(steering behaviors)的概念是由Craig Reynolds在1999年游戲開(kāi)發(fā)者大會(huì)上提出的[12]。在AI角色的環(huán)境周圍,轉(zhuǎn)向行為施加簡(jiǎn)單的力,通過(guò)力的組合使AI角色進(jìn)行類生命體般的運(yùn)動(dòng),幫助AI角色以現(xiàn)實(shí)中的行為方式運(yùn)動(dòng)。轉(zhuǎn)向行為不使用路徑規(guī)劃或者全局計(jì)算相關(guān)的復(fù)雜策略,只使用局部信息,例如鄰居施加的力信息。這使個(gè)體的轉(zhuǎn)向行為更容易理解和實(shí)現(xiàn),個(gè)體的組合能夠產(chǎn)生非常復(fù)雜的運(yùn)動(dòng)模式。

1.1 自主角色及行為

在動(dòng)畫(huà)和游戲中,自主角色在其周圍的環(huán)境中需要按照類生命體的行為進(jìn)行運(yùn)動(dòng)。轉(zhuǎn)向行為提供了解決方案,這些轉(zhuǎn)向行為很大程度上獨(dú)立于角色運(yùn)動(dòng)方式的細(xì)節(jié),轉(zhuǎn)向行為組合可以實(shí)現(xiàn)更高層次的目標(biāo),例如從源點(diǎn)到目標(biāo)點(diǎn)間的避障處理、路徑跟隨和排隊(duì)等。

自主角色是一種自治代理,用于計(jì)算機(jī)動(dòng)畫(huà)和交互媒體,例如游戲和虛擬現(xiàn)實(shí)。這些代理代表故事或游戲中的一個(gè)角色,具有即興行為的能力,與動(dòng)畫(huà)電影中的角色不同,動(dòng)畫(huà)電影角色的行為都是事先通過(guò)腳本定義好的,也與游戲和虛擬現(xiàn)實(shí)中的“化身”不同,那些行為是人類玩家或者參與者實(shí)時(shí)引導(dǎo)的。在游戲中,自主角色有時(shí)被稱作非玩家角色。一個(gè)自主角色必須結(jié)合自主機(jī)器人的一些功能和劇場(chǎng)中即興人類表演者的一些技巧。這些角色通常并不是真正的機(jī)器人,也不是人類演員,而是共享了各自的一些屬性。

術(shù)語(yǔ)“行為”具有很多含義。它可以表示基于意識(shí)或本能的人類或者其他生物的復(fù)雜行為,也可以表示一個(gè)簡(jiǎn)單機(jī)械系統(tǒng)很大程度上的預(yù)測(cè)行為,或者表示一個(gè)混沌系統(tǒng)的復(fù)雜行為。在虛擬現(xiàn)實(shí)和多媒體應(yīng)用中,“行為”有時(shí)用來(lái)作為動(dòng)畫(huà)的同義詞,在本文中,術(shù)語(yǔ)“行為”用來(lái)表示自主角色類生命體的行為。

1.2 轉(zhuǎn)向行為定義

轉(zhuǎn)向行為是一種移動(dòng)自主角色的方式,使它看起來(lái)像具有智慧一樣。幾乎每一個(gè)游戲都使用轉(zhuǎn)向行為產(chǎn)生類似人類的行為。但是,實(shí)際上它沒(méi)有任何智能,僅僅是一種錯(cuò)覺(jué),全部都是通過(guò)數(shù)學(xué)計(jì)算實(shí)現(xiàn)的。

典型的轉(zhuǎn)向行為包括尋找(Seek)、逃離(Flee)、到達(dá)(Arrive)、漫游(Wander)、路徑跟隨(Path Following)、聚集(Cohesion)、對(duì)齊(Alignment)、分離(Separation),上述行為的說(shuō)明如表1所示。

表1 轉(zhuǎn)向行為定義

2 實(shí)驗(yàn)設(shè)計(jì)

2.1 向量定義

轉(zhuǎn)向行為所涉及到的力影響角色的速度和位置,使用向量表示角色的速度和位置。如圖1所示,一個(gè)角色的位置向量position (x,y)、速度向量velocity (a,b)，角色更新后的位置向量計(jì)算偽代碼為：position=position+velocity。

圖1 位置和速度向量

位置向量用于表示角色的位置,其方向一般被忽略,角色的方向通過(guò)速度向量表示。速度向量的方向控制角色的朝向,而大小控制角色每幀移動(dòng)的多少,越大角色移動(dòng)越快。速度向量通過(guò)截?cái)嗵幚砜梢员ＷC其不會(huì)大于某個(gè)閾值,閾值一般為最大速度。

2.2 類設(shè)計(jì)

實(shí)驗(yàn)中的核心類定義包括Vector2類、SteeringBehaviours類、SBC類和Vehicle類。各類的主要字段、屬性和方法如圖2所示。

Vector2類定義了2維向量,實(shí)現(xiàn)向量計(jì)算功能,包括向量長(zhǎng)度、歸一化和截?cái)?向量之間的和、差、點(diǎn)積,向量與數(shù)值之間的加、乘和除。

SteeringBehaviours類定義了轉(zhuǎn)向行為方法,包括Seek、Flee、Arrive、Wander、Path Following、Cohesion、Alignment和Separation,方法返回完成上述轉(zhuǎn)向行為施加到角色上的轉(zhuǎn)向向量。

SBC(steer behavior controller)類定義了轉(zhuǎn)向行為控制器,管理所有角色的功能,包括輸出信息、初始化、轉(zhuǎn)向行為設(shè)置和運(yùn)動(dòng)更新。

圖2 核心類的類圖

Vehicle類定義了小車角色,包括位置、運(yùn)動(dòng)限制和轉(zhuǎn)向行為信息,以及參數(shù)設(shè)置、位置更新功能。

3 實(shí)驗(yàn)實(shí)現(xiàn)

3.1 實(shí)現(xiàn)技術(shù)

由于轉(zhuǎn)向行為的實(shí)現(xiàn)獨(dú)立于編程技術(shù),所以本文以.NET編程技術(shù)為例說(shuō)明實(shí)驗(yàn)實(shí)現(xiàn)過(guò)程,其他編程技術(shù)類似。

在Visual Studio 2017開(kāi)發(fā)環(huán)境中創(chuàng)建WinForm項(xiàng)目,使用C#編程,利用.NET框架的Timer和Graphics類,周期性在窗體上繪制圖形,實(shí)現(xiàn)角色施加轉(zhuǎn)向行為后連續(xù)動(dòng)態(tài)變化的界面效果。

3.2 轉(zhuǎn)向行為實(shí)現(xiàn)

3.2.1 Seek行為實(shí)現(xiàn)

Seek轉(zhuǎn)向行為如圖3所示,為了使角色獲得期望的速度向量(desired velocity),對(duì)角色(方塊)施加轉(zhuǎn)向向量(steering),改變當(dāng)前速度向量(current velocity)方向,指向目標(biāo)(target)。

轉(zhuǎn)向向量計(jì)算偽代碼為：

desired_velocity=normalize(target-position)*max_velocity

steering =desired_velocity-current_velocity

首先計(jì)算目標(biāo)和角色的位置向量差,進(jìn)行歸一化,乘以最大速度,計(jì)算期望速度向量,然后計(jì)算期望速度和當(dāng)前速度向量差,獲得轉(zhuǎn)向向量。

3.2.2 Flee行為實(shí)現(xiàn)

Flee轉(zhuǎn)向行為如圖4所示,為了使角色獲得期望的速度向量,對(duì)角色施加轉(zhuǎn)向向量,改變當(dāng)前速度向量方向,從目標(biāo)指向角色。

圖4 Flee轉(zhuǎn)向行為計(jì)算

轉(zhuǎn)向向量計(jì)算偽代碼為：

desired_velocity = normalize(position-target) * max_velocity

steering =desired_velocity - current_velocity

Flee與Seek的desired_velocity向量正好相反,其他計(jì)算過(guò)程一致。

3.2.3 Arrive行為實(shí)現(xiàn)

Arrive轉(zhuǎn)向行為如圖5所示,當(dāng)角色遠(yuǎn)離目標(biāo)時(shí)采取Seek行為,而當(dāng)角色進(jìn)入以目標(biāo)為中心的減速區(qū)域(slowing area)時(shí),角色逐漸減速,直到停到目標(biāo)位置上。

圖5 Arrive轉(zhuǎn)向行為計(jì)算

轉(zhuǎn)向向量計(jì)算基于減速區(qū)域半徑和角色與目標(biāo)距離,轉(zhuǎn)向向量計(jì)算偽代碼為：

desired_velocity = target - position

distance = length(desired_velocity)

if (distance

desired_velocity = normalize(desired_velocity) * max_velocity * (distance / slowingRadius)

}

else {

desired_velocity = normalize(desired_velocity) * max_velocity

}

steering =desired_velocity - current_velocity

3.2.4 Wander行為實(shí)現(xiàn)

Wander轉(zhuǎn)向行為如圖6所示,在角色速度向量方向上選擇一個(gè)點(diǎn)定義一個(gè)圓,在圓周上隨機(jī)選擇一個(gè)位移點(diǎn),生成位移向量displacement,執(zhí)行Seek,位移點(diǎn)的位置可以讓角色隨機(jī)向左右不同強(qiáng)度進(jìn)行轉(zhuǎn)向。

圖6 Wander轉(zhuǎn)向行為計(jì)算

位移向量的計(jì)算基于隨機(jī)的位移角度和圓半徑Radius。圓心位置向量計(jì)算基于速度向量方向和角色與圓心距離Distance,轉(zhuǎn)向向量計(jì)算偽代碼為：

Angel=(Math.Random-0.5)*MaxAngel

displacement=vector(Radius*Math.Cos(Angel), Radius*Math.Sin(Angel))

circleCenter = velocity.clone()

circleCenter.normalize()

circleCenter.scaleBy(Distance)

steering=circlecentre+displacement

3.2.5 Path Following行為實(shí)現(xiàn)

Path Following轉(zhuǎn)向行為如圖7所示,路徑定義為多個(gè)點(diǎn)連接的曲線,依次選擇路徑上的每個(gè)點(diǎn)作為目標(biāo),執(zhí)行Seek,直至到達(dá)路徑上的最后一個(gè)目標(biāo)點(diǎn)。

圖7 Path Following轉(zhuǎn)向行為計(jì)算

轉(zhuǎn)向向量計(jì)算偽代碼為：

foreach(target in path){

steering= Seek(position , target)

velocity=velocity+steering

position=position+ velocity

}

3.2.6 Cohesion行為實(shí)現(xiàn)

Cohesion轉(zhuǎn)向行為如圖8所示,找到角色鄰域內(nèi)的其他角色群體,計(jì)算群體的平均中心,作為目標(biāo)點(diǎn),執(zhí)行Seek。

圖8 Cohesion轉(zhuǎn)向行為計(jì)算

轉(zhuǎn)向向量計(jì)算偽代碼為：

centre=vector(0,0)

count=0

foreach(othercharacter in localarea){

centre=centre+ othercharacter.position;

count=count+1

}

centre.scaleBy(1/count)

steering=Seek(position , centre)

3.2.7 Alignment行為實(shí)現(xiàn)

Alignment轉(zhuǎn)向行為如圖9所示,找到角色鄰域內(nèi)的角色群體,計(jì)算群體平均速度,則轉(zhuǎn)向向量為群體平均速度與角色當(dāng)前速度的向量差。

圖9 Alignment轉(zhuǎn)向行為計(jì)算

轉(zhuǎn)向向量計(jì)算偽代碼為：

desired_velocity =vector(0,0)

foreach(othercharacter in localarea){

desired_velocity = desired_velocity + othercharacter.current_velocity

}

steering= desired_velocity-current_ velocity

3.2.8 Separation行為實(shí)現(xiàn)

Separation轉(zhuǎn)向行為如圖10所示,當(dāng)前角色首先找到鄰域內(nèi)的其他角色,對(duì)于每一個(gè)鄰居角色,計(jì)算其對(duì)當(dāng)前角色的排斥力。計(jì)算方法為當(dāng)前角色與鄰域角色位置向量差,進(jìn)行歸一化處理,獲得位置偏移向量,乘以權(quán)重1/r2,參數(shù)r可根據(jù)分離需求,例如相鄰距離,進(jìn)行計(jì)算或設(shè)置,每一個(gè)鄰居角色的排斥力求和,最終獲得轉(zhuǎn)向向量。

圖10 Separation轉(zhuǎn)向行為計(jì)算

轉(zhuǎn)向向量計(jì)算偽代碼為：

steering=vector(0,0)

foreach(othercharacter in localarea){

repulsion=position - othercharacter.position

repulsion.normalize()

repulsion.scaleBy(1/r2)

steering = steering + repulsion

}

3.3 實(shí)現(xiàn)效果

通過(guò)設(shè)置角色數(shù)量、轉(zhuǎn)向行為和初始位置,人工生命轉(zhuǎn)向行為綜合性實(shí)驗(yàn)的Seek、Flee、Arrivement、Wander、Path Following、Cohesion、Alignment、Seperation行為實(shí)現(xiàn)效果如圖11(a)—(h)所示。

圖11 轉(zhuǎn)向行為實(shí)現(xiàn)效果

圖11(a)中,角色逐漸向白色目標(biāo)點(diǎn)靠近；圖11(b)中,角色一旦進(jìn)入白色目標(biāo)點(diǎn)鄰域,逐漸遠(yuǎn)離目標(biāo)點(diǎn)；圖11(c)中,角色逐漸向白色目標(biāo)點(diǎn)減速靠近；圖11(d)中,角色根據(jù)圓上隨機(jī)點(diǎn)擾動(dòng)進(jìn)行隨機(jī)轉(zhuǎn)向；圖11(e)中,角色依次向指定路徑上的目標(biāo)點(diǎn)靠近；圖11(f)中,角色向鄰域內(nèi)的角色群體中心聚集；圖11(g)中,角色與鄰域內(nèi)的其他角色運(yùn)動(dòng)方向?qū)R；圖11(h)中,角色與鄰域內(nèi)的其他角色保持一定距離。通過(guò)對(duì)目前所實(shí)現(xiàn)的轉(zhuǎn)向行為的合理組合,可以實(shí)現(xiàn)更復(fù)雜、更高層次的角色行為。

4 結(jié)語(yǔ)

本文針對(duì)計(jì)算機(jī)編程類課程缺乏新穎有趣的綜合性實(shí)驗(yàn)問(wèn)題,選擇游戲中具有一定智能的人工生命作為研究對(duì)象,以實(shí)現(xiàn)游戲角色轉(zhuǎn)向行為為例,詳細(xì)描述了該綜合性實(shí)驗(yàn)的算法基礎(chǔ)、實(shí)驗(yàn)設(shè)計(jì)和編程實(shí)現(xiàn)過(guò)程。通過(guò)該綜合性實(shí)驗(yàn),可以完成對(duì)學(xué)生語(yǔ)言基礎(chǔ)語(yǔ)法、面向?qū)ο笤O(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)、算法和用戶界面等知識(shí)點(diǎn)的訓(xùn)練,具有一定的技術(shù)難度,又具有較強(qiáng)的趣味性,同時(shí)讓學(xué)生了解所學(xué)的數(shù)學(xué)知識(shí)在計(jì)算機(jī)編程中的實(shí)際應(yīng)用,為解決目前計(jì)算機(jī)編程類課程綜合性實(shí)驗(yàn)中存在的問(wèn)題提供了一個(gè)新穎的解決方案。