撲克子

效果

顯示大量彈幕、允許重疊、彈幕字號允許不同

約定

為了更好地進行討論，我們先聲明一些共識：

1. 彈幕會從屏幕右邊緣發射，并向左滾動

2. 彈幕出現位置應該盡量靠上

3. 幾條彈幕之間應該盡量不要重疊，如果要重疊也要盡量重疊長度少一些

此外本文會創造/使用一些概念：

1. 彈幕：計算的對象實體，有以下成員：

   • 發射時間：這個實際上決定了某時刻彈幕的x坐標
   • 坐標：只有y坐標，是算法最后計算出應該出現的位置
   • 寬度：根據彈幕字數、字號計算出的長度
   • 高度：由彈幕的字號決定

2. 屏幕右邊緣：由于彈幕是從右邊出現的，所以右邊緣和屏幕寬度都很重要

3. 屏幕寬度：由窗口大小決定

4. 位置（room），可以放置彈幕的空位，由于只需要關注屏幕右邊緣線上的空位，所以位置實際上是一個一維變量，并且屏幕邊緣上所有的位置合起來是一個一維數組，有以下成員：

   • 高度：位置的高度
   • 坐標：位置的坐標，實際上不是一個字段，而是由前面所有的位置高度綜合算出的
   • 上條彈幕：這個位置最近發射的彈幕

5. 停留時間：彈幕在屏幕上停留的時間

流程

如圖中的彈幕情況。紅色新彈幕發射時，應該插在第幾行呢？

大家肯定可以一眼看出來是第一行發射，那如何編程實現？我們先梳理一遍流程：

1. 將彈幕按照發射時間排序，然后依次判斷彈幕：

2. 從上往下依次判斷位置，如果有一個空位距離為正數，則將彈幕插入。

3. 計算該位置中上一條彈幕距離本彈幕的距離
   （如果彈幕在邊緣左側，則為正數，在右側為負數，負數意味著：此時在此處發射彈幕會和上一條彈幕重疊，正數則不會重疊）

4. 如果有正數距離，則插入在這個位置。

5. 如果沒有正數距離，而且允許彈幕重疊，則選擇最大的距離插入。

sort 彈幕 by 彈幕.發射時間
sort 位置（從上至下）
foreach 彈幕
    var 最大距離
    foreach 位置
        var 距離 := get_dictance(彈幕, 位置.上條彈幕)
        距離.對應位置 = 位置
        if 距離 > 0
            位置.上條彈幕 := 彈幕
            彈幕.坐標 = 位置.坐標
            break
        else
            最大距離 := max(最大距離, 距離)
    if 彈幕.坐標 = null 
        if 允許重疊
            最大距離.對應位置.上條彈幕 := 彈幕
            彈幕.坐標 = 位置.坐標
        else
            // 這條彈幕不會顯示

距離計算

距離表面上就是彈幕的右端距離屏幕右邊緣的距離，但實際上計算時還是要考慮蠻多因素的：

如果設置一條彈幕在屏幕上停留的時間為duration秒的話，彈幕的結束時間為：

var 結束時間 := 彈幕.發射時間 + duration

而且滾動彈幕實際上是要在duration秒內，走過屏幕寬度+自身寬度的距離。我們可以算出某時刻彈幕左邊緣和屏幕右邊緣的距離：

func get_position (彈幕, 屏幕寬度, 某時刻, duration)
    var 彈幕已發射時間 := 某時刻 - 彈幕.發射時間
    var 彈幕要走的總長度 := 屏幕寬度 + 彈幕.寬度
    var 彈幕已走的長度 := 彈幕要走的總長度 * 彈幕已發射時間 / duration
    return 彈幕已走的長度

但是也由于這個原因，長彈幕走的速度會比短彈幕快。也就是說如果本彈幕在這個位置發射：

• 如果上一條彈幕比本彈幕長（即速度比本彈幕快），那么本彈幕剛發射的時間就是兩條彈幕距離最近的時候。

• 如果上一條彈幕比本彈幕短（即速度比本彈幕慢），那么上條彈幕的結束時間就是兩條彈幕距離最近的時候。

綜上，我們可以寫出函數計算彈幕的位置：

func get_dictance (彈幕, 上條彈幕)
    var 某時刻
    if 彈幕.寬度 > 上條彈幕.寬度
        某時刻 := 彈幕.發射時間
    else
        某時刻 := 彈幕.發射時間 + duration
    var 屏幕寬度 := get_viewport_width()
    var duration := get_duration()
    var 上條彈幕位置 := get_position(上條彈幕, 屏幕寬度, 某時刻, duration)
    var 本彈幕位置 := get_position(彈幕, 屏幕寬度, 某時刻, duration)
    return 上條彈幕位置 - 本彈幕位置 - 上條彈幕.寬度

處理不同大小的彈幕

但是不一定所有彈幕都是一樣大小的，那“位置”的高度都不相同如何解決？如果只有大中小幾種，我們也許可以按最大公約數設置高度等方法解決。但我這里要給出一種方法同時兼容所有大小的彈幕：

首先使用鏈表實現，使用鏈表是因為我們遍歷位置時，更常會訪問相鄰的位置（如前一個位置、后一個位置）而非隨機訪問。

鏈表的每個節點都記錄了當前位置的高度（位置的坐標可以由之前節點高度推算出），和在該位置中上一個彈幕的信息。

• 當有小彈幕進入大位置時，可以把位置拆為兩個相同的位置，其中靠上的位置放置新彈幕，下面的位置維持原樣；

  sankey-beta big room (old danmaku), danmaku (new danmaku), 5 big room (old danmaku), rest (old danmaku), 2

• 當有大彈幕進入小位置時，可以把相鄰的幾個位置合并為一個，位置的上條彈幕取時間最近一條作為新位置的上條彈幕，然后再像上一條一樣拆為兩個處理。

  sankey-beta small room1 (old danmaku1), big room (old danmakuX), 3 small room2 (old danmaku2), big room (old danmakuX), 1 small room3 (old danmaku3), big room (old danmakuX), 3 big room (old danmakuX), danmaku (new danmaku), 5 big room (old danmakuX), rest (old danmakuX), 2

我們只需要將開始時的位置，初始化為一個節點的鏈表，這個節點的高度是屏幕的高度。

在對一條彈幕計算的最后，在彈幕中記錄下當前位置的坐標即可。

代碼示例（C#）

我使用C#實現過一個軟件，可供大家參考，如果還有不理解的歡迎大家聯系我：

DamakuPlayer: https://github.com/Poker-sang/DanmakuPlayer/blob/master/DanmakuPlayer/Models/Danmaku.Position.cs