摘要：本文愿從彈幕設計這個場景來描述算法在前端中的應用，我們先來看下實現效果圖彈幕效果開場之前我們先來描述彈幕開發的難度，再集中精力描述算法設計的思路。軌道軌道這個角色很重要，它可以解決彈幕位置計算速度控制碰撞檢測問題。

大家都說前端寫頁面較多，幾乎用不到算法。本文愿從彈幕設計這個場景來描述算法在前端中的應用，我們先來看下實現效果：

                                    圖1.1 彈幕效果

開場之前我們先來描述彈幕開發的難度，再集中精力描述算法設計的思路。

如何保證不同字號的彈幕不碰撞

彈幕的位置計算

彈幕的速度控制及動畫實現

彈幕與視頻的同步

如何保證不同字號的彈幕不碰撞

如果彈幕采用相同的字號，碰撞的問題處理起來比較簡單，只要考慮相鄰彈幕的播放速度和偏移的位置就可以計算出來。然而使用不同字號的彈幕處理起來就麻煩了許多，彈幕的起始位置不可以線性的增加，比如第一行放了字幕，接下來的字幕可以按順序從上至下依次放置即可。

彈幕的位置計算

只有設計好彈幕的初始位置，才可以動態、高效的管理不同字號彈幕的碰撞問題。打個比方，我們通過接口獲取了2秒之內的彈幕數據1000條，每個字幕的長度、速度、字號都不同，怎么管理這些彈幕，示意圖如下：

                                圖2.1 彈幕管理示意圖

這是第一種情況，按照從上到啊的順序依次擺放以后會有幾個問題：

彈幕五、六、七該怎么計算位置，按top值循環取模+累加嗎？

當彈幕一或者彈幕三足夠長的時候，如何準時的跳過當前位置計算？

當前屏幕的彈幕播放結束，如何再計算的時候利用空出來的位置

空出的位置是否滿足當前彈幕的高度

……

一系列問題就不統統列舉出來了，基于這個背景我們結合數學建模的思維方式，找到了彈幕場景相似度非常高的機場運營。我們可以把彈幕當做飛機，每個時間段播放多少彈幕和機場每個時間段放飛多少飛機一個道理。

首都國際機場一共有3條跑道，兩條4E級跑道、一條4F級跑道，2016年的吞吐量為9000萬人次。它的運行機制就是所有飛機通過搭臺有順序的共用3條跑道來完成運輸任務的。

同理，我們也設計了幾個個角色：一個是軌道(跑道)、一個是調度(塔臺)、一個是彈幕(飛機)，我們為每個角色設計一個類分為為Track、Main、Bullet。

軌道

軌道這個角色很重要，它可以解決彈幕位置計算、速度控制、碰撞檢測問題。
首先，我們要來初始化軌道。通俗的說我們要修建幾個跑道呢，我們不是實物，可以動態調整軌道的 數量，計算的原則：

軌道數量 = 播放器有效高度 / 設備基準字號

播放器有效高度：播放器的實際高度減去控制條的高度，因為彈幕不可以遮擋控制條。

設備基準字號：移動端是10px，pc端是12px；
為啥計算公式是這樣的？因為我們要支持不同字號的彈幕。試想不同的字號對物理空間的占用是不同的，然而如果要求軌道的尺寸是動態的，那就帶來很復雜的計算。本文提出“虛擬軌道”的概念，在交通管制中最常見的就是道路合并或者改向。我們也是采用將相鄰的物理軌道臨時合并為一條軌道。這樣就可以輕松的解決不同字號的軌道占用問題。原理圖如下：

                        圖2.2 軌道計算示意圖

其次我們來回憶下機場的工作流程：

機長呼叫塔臺，CZ6132請求起飛

目前跑道均被占用，請等待

N時刻后再次執行步驟1

目前跑道 A1 空閑，準許進入

執行步驟3

塔臺查看跑道使用情況

進入跑道，起飛完成

機長通知塔臺，本次起飛完成，釋放跑道的占用

其他飛機同樣執行上述步驟

按照這個思路，我們的彈幕工作流程：

彈幕進入播放器

軌道根據彈幕的播放速度、尺寸計算是否有合適的軌道提供

沒有

通知彈幕尚無合適軌道提供，請等待；同時，彈幕隊列中的其他彈幕依次執行步驟1

有

執行步驟3

播放器加載彈幕DOM，開始播放，待播放完成

播放完成通知軌道更新軌道占用情況

其他彈幕同樣執行上述步驟

                            圖2.3 軌道可用性計算示意圖

關于軌道的基本原理我們整理清楚了，當然還有不少細節比如如何和調度通信、如何和彈幕通信以及虛擬軌道檢測算法等。有興趣的同學可以參考代碼吧。https://github.com/bytedance/...

彈幕
彈幕基本是實現“飛機”的角色，我們要求它具有自身的屬性和方法。比如調度中心通過id能拿到它所有的基本信息，軌道控制也可以通過彈幕進行檢查和更新。當然彈幕也必須具備狀態自動更新、移動、播放結束通知、自動銷毀等功能。

調度

調度就是搭臺的化身，承接著軌道、彈幕的控制，也保持著與播放器的步調一致。它的職責如下：

播放器交互控制

彈幕隊列控制

自身狀態更新

數據格式轉換

動畫執行
還是直接用流程圖來描述更直接些：

在彈幕啟動之后，首先要檢查本地是否已有緩存數據，沒有的話直接請求數據并緩存，然后執行數據讀取，首次過濾數據進入彈幕隊列，同時啟動定時器。彈幕隊列的數據會定期請求軌道，檢測隊列里的彈幕是否可以進入，一旦確認后軌道做好登記，彈幕就可以進入播放器開啟動畫播放了。定時器每隔2秒就會再次更新數據進入到彈幕隊列（這塊不同的業務可以定制不同的規則）。彈幕播放結束后會通知調度和軌道，調度會在彈幕隊列中移除該彈幕實例，軌道也會移除該彈幕實例的軌道占用。

所有代碼實現來自帶解析器、能節省流量的西瓜播放器, Github