title: 滚动弹幕出现位置算法
date: 2024-01-25
categories: 编程
tags:
- 弹幕
- 算法
- C#
效果
显示大量弹幕、允许重叠、弹幕字号允许不同
约定
为了更好地进行讨论，我们先声明一些共识：
-
弹幕会从屏幕右边缘发射，并向左滚动
-
弹幕出现位置应该尽量靠上
-
几条弹幕之间应该尽量不要重叠，如果要重叠也要尽量重叠长度少一些
此外本文会创造/使用一些概念：
-
弹幕：计算的对象实体，有以下成员：
- 发射时间：这个实际上决定了弹幕的x坐标
- 坐标：只有y坐标，是算法最后计算出应该出现的位置
- 宽度：根据弹幕内容计算出的宽度
- 高度：由弹幕的字号决定
-
屏幕右边缘：由于弹幕是从右边出现的，所以右边缘和屏幕宽度都很重要
-
屏幕宽度：由窗口大小决定
-
位置（room），可以放置弹幕的空位，由于只需要关注屏幕右边缘线上的空位，所以位置实际上是一个一维变量，并且屏幕边缘上所有的位置合起来是一个一维数组，有以下成员：
- 高度：位置的高度
- 坐标：位置的坐标，实际上不是一个字段，而是由前面所有的位置高度综合算出的
- 上条弹幕：这个位置最近发射的弹幕
-
停留时间：弹幕在屏幕上停留的时间
流程
如图中的弹幕情况。红色新弹幕发射时，应该插在第几行呢？
--- displayMode: compact --- gantt dateFormat ss axisFormat | 弹幕1 : 00, 4s 弹幕2 : 01, 5s 弹幕3 : 02, 4s 弹幕4 : 02, 2s 新弹幕 : crit, 05, 3s 屏幕右边缘 : milestone, 05, 0大家肯定可以一眼看出来是第一行发射，那如何编程实现？我们先梳理一遍流程：
-
将弹幕按照发射时间排序，然后依次判断弹幕：
-
从上往下依次判断位置，如果有一个空位距离为正数，则将弹幕插入。
-
计算该位置中上一条弹幕距离本弹幕的距离
（如果弹幕在边缘左侧，则为正数，在右侧为负数，负数意味着：此时在此处发射弹幕会和上一条弹幕重叠，正数则不会重叠） -
如果有正数距离，则插入在这个位置。
-
如果没有正数距离，而且允许弹幕重叠，则选择最大的距离插入。
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 上条弹幕位置 - 本弹幕位置 - 上条弹幕.宽度
处理不同大小的弹幕
但是不一定所有弹幕都是一样大小的，那“位置”的高度都不相同如何解决？如果只有大中小几种，我们也许可以按最大公约数设置高度等方法解决。但我这里要给出一种方法同时兼容所有大小的弹幕：
首先使用链表实现，使用链表是因为我们遍历位置时，更常会访问相邻的位置（如前一个位置、后一个位置）而非随机访问。
链表的每个节点都记录了当前位置的高度（位置的坐标可以由之前节点高度推算出），和在该位置中上一个弹幕的信息。
-
当有小弹幕进入大位置时，可以把位置拆为两个相同的位置，其中靠上的位置放置新弹幕，下面的位置维持原样；
-
当有大弹幕进入小位置时，可以把相邻的几个位置合并为一个，位置的上条弹幕取时间最近一条作为新位置的上条弹幕，然后再像上一条一样拆为两个处理。
我们只需要将开始时的位置，初始化为一个节点的链表，这个节点的高度是屏幕的高度。
在对一条弹幕计算的最后，在弹幕中记录下当前位置的坐标即可。
代码示例（C#）
我使用C#实现过一个软件，可供大家参考，如果还有不理解的欢迎大家联系我：
DamakuPlayer: https://github.com/Poker-sang/DanmakuPlayer/blob/master/DanmakuPlayer/Models/DanmakuUtilities.cs
标签：滚动,--,位置,距离,算法,屏幕,弹幕,上条 From： https://www.cnblogs.com/pokersang/p/17987543