基于FPGA加速的bird-oid object算法實現

1. 項目概述

模型說明

Bird-oid object 簡稱Boids模型，是美國的一個圖形計算機科學家Craig Reynolds在 1986 年開發出來的。

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

項目說明

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

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

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

這個項目的目標是改善更新功能所需的周期數，并看到總體執行時間的改進。如果能夠減少運行更新的專用硬件的循環次數，估計就最終可以在ARM處理器上進行超過3000個對象的計算。

2. 實現原理

要創建boids群集模擬，需要遵循三個主要步驟:分離、對齊和聚集。

分離 Separation：離得太近的物體會相互遠離

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

聚集 Cohesion：朝著周圍同伴的平均位置移動

當對象之間靠得太近時，執行兩個步驟使對象之間稍微散開一點。第一步是計算當前節點到最近節點的距離：

close_dx += boid.x - otherboid.x

close_dy += boid.y - otherboid.y

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

boid.vx += close_dx*avoidfactor

boid.vy += close_dy*avoidfactor

下一步是對齊所需的計算。我們執行以下步驟:

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

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

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

neighboring_boids += 1

循環遍歷所有其他物體后，如果neighboring_boids > 0，則執行以下操作:

xvel_avg = xvel_avg/neighboring_boids
yvel_avg = yvel_avg/neighboring_boids

然后根據以下公式更新速度:

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

（其中matchingfactor是一個可調參數）

最后一次物體對物體的更新是基于聚集性，因為每個物體對象都在其可見范圍內緩慢地轉向其他對象的質心。它是這樣做的:

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

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

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

循環遍歷所有其他對象后，如果neighboring_boids > 0，則執行以下操作:

xpos_avg = xpos_avg/neighboring_boids
ypos_avg = ypos_avg/neighboring_boids

然后根據以下公式更新速度：

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

（其中centeringfactor是一個可調參數）

對象更新的最后一步是確定對象何時需要轉動，以便所有對象都保持在正在使用的VGA屏幕的范圍內。這可以通過下面的條件語句來實現:

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

當使用不同的微控制器和顯示器時，邊界條件和背后的邏輯保持不變。

審核編輯：劉清