1. 項(xiàng)目概述

模型說明

Bird-oid object 簡稱Boids模型，是美國的一個(gè)圖形計(jì)算機(jī)科學(xué)家Craig Reynolds在 1986 年開發(fā)出來的。

他的Boids模型為集群個(gè)體抽象出三個(gè)基本行為：分離（seperation）、對齊（alignment）、與聚集（cohesion）。將這三種行為按一定權(quán)重進(jìn)行混合，可以讓群體出現(xiàn)秩序化的社會(huì)性行為。這個(gè)模型自從提出到現(xiàn)在一直持續(xù)影響著社會(huì)學(xué)、生物學(xué)、計(jì)算機(jī)科學(xué)等學(xué)科的發(fā)展?；谶@個(gè)模型的應(yīng)用其實(shí)很多， 比如現(xiàn)在的集群無人地面車輛，集群無人機(jī)燈光秀等等。

項(xiàng)目說明

本項(xiàng)目使用DE1 SoC的ARM A9處理器和FPGA邏輯的組合，不僅成功地模擬了動(dòng)態(tài)boid (bird-oid object)群集模式，而且還優(yōu)化了周期要求和執(zhí)行時(shí)間。

本項(xiàng)目首先創(chuàng)建了一個(gè)完全運(yùn)行在ARM A9處理器上的“基線”設(shè)計(jì)。這個(gè)基線設(shè)計(jì)是使用C代碼創(chuàng)建的，能夠以每秒60幀的速度計(jì)算最多3,000個(gè)對象的群集模式。

我們的第二個(gè)對比設(shè)計(jì)是在FPGA上創(chuàng)建一個(gè)更新功能可以計(jì)算和更新每個(gè)物體在x和y坐標(biāo)上的位置，以及它們在x和y方向上的速度。最后成功地在FPGA上模擬了最多顯示150個(gè)對象的boids群集模式。

這個(gè)項(xiàng)目的目標(biāo)是改善更新功能所需的周期數(shù)，并看到總體執(zhí)行時(shí)間的改進(jìn)。如果能夠減少運(yùn)行更新的專用硬件的循環(huán)次數(shù)，估計(jì)就最終可以在ARM處理器上進(jìn)行超過3000個(gè)對象的計(jì)算。

2. 實(shí)現(xiàn)原理

要?jiǎng)?chuàng)建boids群集模擬，需要遵循三個(gè)主要步驟:分離、對齊和聚集。

分離 Separation：離得太近的物體會(huì)相互遠(yuǎn)離

對齊 Alignment：對齊是指每個(gè)物體試圖匹配其可見范圍內(nèi)物體的速度，朝著周圍同伴的平均方向前進(jìn)

聚集 Cohesion：朝著周圍同伴的平均位置移動(dòng)

當(dāng)對象之間靠得太近時(shí)，執(zhí)行兩個(gè)步驟使對象之間稍微散開一點(diǎn)。第一步是計(jì)算當(dāng)前節(jié)點(diǎn)到最近節(jié)點(diǎn)的距離：

close_dx += boid.x - otherboid.x

close_dy += boid.y - otherboid.y

一旦這被計(jì)算出來，我們就創(chuàng)造了一個(gè)回避因素：avoidfactor。這個(gè)avoidfactor雖然仍然相對較小，但將乘以之前計(jì)算的close_dx和close_dy值:

boid.vx += close_dx*avoidfactor

boid.vy += close_dy*avoidfactor

下一步是對齊所需的計(jì)算。我們執(zhí)行以下步驟:

在開始更新特定對象時(shí)，三個(gè)變量(xvel_avg、yvel_avg和neighboring_boids)為零。

循環(huán)遍歷每一個(gè)其他的對象。如果到特定對象的距離小于可見范圍，則

xvel_avg += otherboid.vx
yvel_avg += otherboid.vy

neighboring_boids += 1

循環(huán)遍歷所有其他物體后，如果neighboring_boids > 0，則執(zhí)行以下操作:

xvel_avg = xvel_avg/neighboring_boids
yvel_avg = yvel_avg/neighboring_boids

然后根據(jù)以下公式更新速度:

boid.vx += (xvel_avg - boid.vx)*matchingfactor
boid.vy += (yvel_avg - boid.vy)*matchingfactor

（其中matchingfactor是一個(gè)可調(diào)參數(shù)）

最后一次物體對物體的更新是基于聚集性，因?yàn)槊總€(gè)物體對象都在其可見范圍內(nèi)緩慢地轉(zhuǎn)向其他對象的質(zhì)心。它是這樣做的:

1. 在開始更新特定對象時(shí)，三個(gè)變量(xpos_avg、ypos_avg和neighboring_boids)為零

2. 循環(huán)遍歷每一個(gè)其他的對象。如果到特定對象的距離小于可見范圍，則

xpos_avg += otherboid.x
ypos_avg += otherboid.y
neighboring_boids += 1

循環(huán)遍歷所有其他對象后，如果neighboring_boids > 0，則執(zhí)行以下操作:

xpos_avg = xpos_avg/neighboring_boids
ypos_avg = ypos_avg/neighboring_boids

然后根據(jù)以下公式更新速度：

boid.vx += (xpos_avg - boid.x)*centeringfactor
boid.vy += (ypos_avg - boid.y)*centeringfactor

（其中centeringfactor是一個(gè)可調(diào)參數(shù)）

對象更新的最后一步是確定對象何時(shí)需要轉(zhuǎn)動(dòng)，以便所有對象都保持在正在使用的VGA屏幕的范圍內(nèi)。這可以通過下面的條件語句來實(shí)現(xiàn):

ifboid.x boid.vx=boid.vx+turnfactor
ifboid.x>rightmargin:
boid.vx=boid.vx-turnfactor
ifboid.y>bottommargin:
boid.vy=boid.vy-turnfactor
ifboid.y boid.vy=boid.vy+turnfactor

當(dāng)使用不同的微控制器和顯示器時(shí)，邊界條件和背后的邏輯保持不變。

審核編輯：劉清