滚动弹幕出现位置算法

效果

显示大量弹幕、允许重叠、弹幕字号允许不同

约定

为了更好地进行讨论,我们先声明一些共识:

  1. 弹幕会从屏幕右边缘发射,并向左滚动

  2. 弹幕出现位置应该尽量靠上

  3. 几条弹幕之间应该尽量不要重叠,如果要重叠也要尽量重叠长度少一些

此外本文会创造/使用一些概念:

  1. 弹幕:计算的对象实体,有以下成员:

    • 发射时间:这个实际上决定了弹幕的x坐标
    • 坐标:只有y坐标,是算法最后计算出应该出现的位置
    • 宽度:根据弹幕内容计算出的宽度
    • 高度:由弹幕的字号决定
  2. 屏幕右边缘:由于弹幕是从右边出现的,所以右边缘和屏幕宽度都很重要

  3. 屏幕宽度:由窗口大小决定

  4. 位置(room),可以放置弹幕的空位,由于只需要关注屏幕右边缘线上的空位,所以位置实际上是一个一维变量,并且屏幕边缘上所有的位置合起来是一个一维数组,有以下成员:

    • 高度:位置的高度
    • 坐标:位置的坐标,实际上不是一个字段,而是由前面所有的位置高度综合算出的
    • 上条弹幕:这个位置最近发射的弹幕
  5. 停留时间:弹幕在屏幕上停留的时间

流程

如图中的弹幕情况。红色新弹幕发射时,应该插在第几行呢?

大家肯定可以一眼看出来是第一行发射,那如何编程实现?我们先梳理一遍流程:

  1. 将弹幕按照发射时间排序,然后依次判断弹幕:

  2. 从上往下依次判断位置,如果有一个空位距离为正数,则将弹幕插入。

  3. 计算该位置中上一条弹幕距离本弹幕的距离 (如果弹幕在边缘左侧,则为正数,在右侧为负数,负数意味着:此时在此处发射弹幕会和上一条弹幕重叠,正数则不会重叠)

  4. 如果有正数距离,则插入在这个位置。

  5. 如果没有正数距离,而且允许弹幕重叠,则选择最大的距离插入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
sort 弹幕 by 弹幕.发射时间
sort 位置(从上至下)
foreach 弹幕
var 最大距离
foreach 位置
var 距离 := get_dictance(弹幕, 位置.上条弹幕)
距离.对应位置 = 位置
if 距离 > 0
位置.上条弹幕 := 弹幕
弹幕.坐标 = 位置.坐标
break
else
最大距离 := max(最大距离, 距离)
if 弹幕.坐标 = null
if 允许重叠
最大距离.对应位置.上条弹幕 := 弹幕
弹幕.坐标 = 位置.坐标
else
// 这条弹幕不会显示

距离计算

距离表面上就是弹幕的右端距离屏幕右边缘的距离,但实际上计算时还是要考虑蛮多因素的:

如果设置一条弹幕在屏幕上停留的时间为duration秒的话,弹幕的结束时间为:

1
var 结束时间 := 弹幕.发射时间 + duration

而且滚动弹幕实际上是要在duration秒内,走过屏幕宽度+自身宽度的距离。我们可以算出某时刻弹幕左边缘和屏幕右边缘的距离:

1
2
3
4
5
func get_position (弹幕, 屏幕宽度, 某时刻, duration)
var 弹幕已发射时间 := 某时刻 - 弹幕.发射时间
var 弹幕要走的总长度 := 屏幕宽度 + 弹幕.宽度
var 弹幕已走的长度 := 弹幕要走的总长度 * 弹幕已发射时间 / duration
return 弹幕已走的长度

但是也由于这个原因,长弹幕走的速度会比短弹幕快。也就是说如果本弹幕在这个位置发射:

  • 如果上一条弹幕比本弹幕长(即速度比本弹幕快),那么本弹幕刚发射的时间就是两条弹幕距离最近的时候。

  • 如果上一条弹幕比本弹幕短(即速度比本弹幕慢),那么上条弹幕的结束时间就是两条弹幕距离最近的时候。

综上,我们可以写出函数计算弹幕的位置:

1
2
3
4
5
6
7
8
9
10
11
func get_dictance (弹幕, 上条弹幕)
var 某时刻
if 弹幕.宽度 > 上条弹幕.宽度
某时刻 := 弹幕.发射时间
else
某时刻 := 弹幕.发射时间 + duration
var 屏幕宽度 := get_viewport_width()
var duration := get_duration()
var 上条弹幕位置 := get_position(上条弹幕, 屏幕宽度, 某时刻, duration)
var 本弹幕位置 := get_position(弹幕, 屏幕宽度, 某时刻, duration)
return 上条弹幕位置 - 本弹幕位置 - 上条弹幕.宽度

处理不同大小的弹幕

但是不一定所有弹幕都是一样大小的,那“位置”的高度都不相同如何解决?如果只有大中小几种,我们也许可以按最大公约数设置高度等方法解决。但我这里要给出一种方法同时兼容所有大小的弹幕:

首先使用链表实现,使用链表是因为我们遍历位置时,更常会访问相邻的位置(如前一个位置、后一个位置)而非随机访问。

链表的每个节点都记录了当前位置的高度(位置的坐标可以由之前节点高度推算出),和在该位置中上一个弹幕的信息。

  • 当有小弹幕进入大位置时,可以把位置拆为两个相同的位置,其中靠上的位置放置新弹幕,下面的位置维持原样;

  • 当有大弹幕进入小位置时,可以把相邻的几个位置合并为一个,位置的上条弹幕取时间最近一条作为新位置的上条弹幕,然后再像上一条一样拆为两个处理。

我们只需要将开始时的位置,初始化为一个节点的链表,这个节点的高度是屏幕的高度。

在对一条弹幕计算的最后,在弹幕中记录下当前位置的坐标即可。

代码示例(C#)

我使用C#实现过一个软件,可供大家参考,如果还有不理解的欢迎大家联系我:

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