Flutter弹幕组件设计

[a62527776a]

本文介绍https://github.com/flutte-danmaku/flutter_danmaku该项目的设计思路和一些实现细节。

简历筛选大大看过来 -> 简历相关扩展

技术细节：

1. 弹幕数据结构
2. 在弹幕组件中，如何规避掉帧

模块

1. 轨道
2. 子弹
3. 控制器
   该项目主要围绕这三块来进行开发。基于这三个模块，解决诸如弹幕的碰撞检测，轨道的动态更新，控制器的渲染等问题。

下文将介绍各个模块的实现细节和思路

子弹

子弹的设计要考虑碰撞检测，宽度对速度的影响，变速需求，个性化子弹的需求，偏移量，静止弹幕以及滚动弹幕的需求。

子弹的基本设计

首先简单介绍子弹模型中重要的成员变量

class FlutterDanmakuBulletModel {
  UniqueKey id; // 通过id查询该子弹
  UniqueKey trackId; // 绑定的轨道id
  UniqueKey prevBulletId; // 轨道中上一个子弹的id
  ...
  double _runDistance = 0; // 已经移动的距离
  double everyFrameRunDistance; // 每帧移动的距离
  ...

  /// 滚动子弹的x轴位置
  double get offsetX => _runDistance - bulletSize.width; 

  /// 子弹最大可跑距离 子弹宽度+墙宽度
  double get maxRunDistance => bulletSize.width + FlutterDanmakuConfig.areaSize.width; 
  
  /// 子弹整体脱离右边墙壁
  bool get allOutRight => _runDistance > bulletSize.width;

  /// 子弹整体离开屏幕
  bool get allOutLeave => _runDistance > maxRunDistance;

  /// 子弹当前执行的距离
  double get runDistance => _runDistance;

  /// 剩余离开的距离
  double get remanderDistance => needRunDistace - runDistance;

  /// 直到消失需要移动的距离
  double get needRunDistace => FlutterDanmakuConfig.areaSize.width + bulletSize.width;

  /// 离开屏幕剩余需要的时间
  double get leaveScreenRemainderTime => remanderDistance / everyFrameRunDistance;

  /// 子弹执行下一帧
  void runNextFrame() {
    _runDistance += everyFrameRunDistance * FlutterDanmakuConfig.bulletRate;
  }
}

从成员变量来看 会发现子弹的距离判断都需要依赖子弹本身的宽度和弹幕墙的宽度，这是由于子弹的出现从头部计算而子弹的隐藏和碰撞从尾部计算。

弹幕的数据结构

保存所有弹幕的方式，思考过两种方案。
一种是在轨道上通过数组保存该轨道上所有的子弹Id。使用Map作为索引Key为Id，Value为下标。
一种是以链表的形式链接轨道上的所有子弹。使用Map作为索引Key为Id，Value为Model。

最终选择以链表的形式保存弹幕的方案。
主要出于以下考虑：

1. 数组删除操作的时间复杂度为O(N)。数组中的每一项的内存地址是连续的，删除数组的其中一项，需要将后续每一项的内存地址减1。而链表的删除操作时间复杂度为O(1)。只需要将上一项指向下一项。

链表 + Map类似LRUCache算法，不过LRUCache算法使用的是双向链表 + HashMap LRUCache使用HashMap实现O(1)的查找，使用双向链表实现O(1)的节点删除和移动。

链表删除节点 [https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/]
LRUCache [https://leetcode-cn.com/problems/lru-cache/]

每个子弹通过prevBulletId以链表的数据结构联接，使用Map作为索引。

class FlutterDanmakuBulletManager {
  Map<UniqueKey, FlutterDanmakuBulletModel> _bullets = {};
  Map<UniqueKey, FlutterDanmakuBulletModel> get bulletsMap => _bullets;
 ...
}

弹幕的追尾

插入弹幕的时候，需要遍历每个轨道是否允许插入新的弹幕，除了考虑该轨道最后一个子弹的一些特征外，还需要判断新插入的轨道是否会追尾。

由于弹幕越长，跑的越快(基本速率 + (宽度 / 倍率))的特性，即便前一个弹幕已经过了一半，还需要考虑新的弹幕是否会速度快到导致追尾。

  // 轨道注入子弹是否会碰撞
  static bool trackInsertBulletHasBump(FlutterDanmakuBulletModel trackLastBullet, Size needInsertBulletSize, {int offsetMS = 0}) {
    // 是否离开了右边的墙壁
    if (!trackLastBullet.allOutRight) return true;
    double willInsertBulletEveryFramerateRunDistance = FlutterDanmakuUtils.getBulletEveryFramerateRunDistance(needInsertBulletSize.width);
    bool hasInsertOffsetSpace = true;
    double willInsertBulletRunDistance = offsetMS == null ? 0 : (offsetMS / FlutterDanmakuConfig.unitTimer) * willInsertBulletEveryFramerateRunDistance;
    if (offsetMS != null) hasInsertOffsetSpace = hasInsertOffsetSpaceComputed(trackLastBullet, willInsertBulletRunDistance);
    if (!hasInsertOffsetSpace) return true;
    // 要注入的节点速度比上一个快
    if (willInsertBulletEveryFramerateRunDistance > trackLastBullet.everyFrameRunDistance) {
      // 是否会追尾
      // 将要注入的弹幕全部离开减去上一个弹幕宽度需要的时间
      double willInsertBulletLeaveScreenRemainderTime = remainderTimeLeaveScreen(willInsertBulletRunDistance, 0, willInsertBulletEveryFramerateRunDistance);
      return trackLastBullet.leaveScreenRemainderTime > willInsertBulletLeaveScreenRemainderTime;
    } else {
      return false;
    }
  }

  // 子弹剩余多少帧离开屏幕
  static double remainderTimeLeaveScreen(double runDistance, double textWidth, double everyFramerateDistance) {
    assert(runDistance >= 0);
    assert(textWidth >= 0);
    assert(everyFramerateDistance > 0);
    double remanderDistance = (FlutterDanmakuConfig.areaSize.width + textWidth) - runDistance;
    return remanderDistance / everyFramerateDistance;
  }

需要做的一些判断

1. 如果该轨道的最后一个子弹全部离开，那么就允许插入新的子弹
2. 该轨道上最后一个子弹是否已经离开右侧的墙壁，如果尾部还未离开右侧的墙壁，那么就会追尾。
3. 如果轨道上最后一个子弹已经在轨道中跑，并且速度慢于新插入的轨道，那么需要考虑轨道最后一个子弹在剩余跑的时间内是否会被新插入的子弹追尾。如果上一个子弹离开屏幕剩余帧数大于新插入子弹离开屏幕剩余帧数，就会追尾。

计算子弹离开剩余帧数 = 离开屏幕剩余距离 - 每帧需要跑的距离。

插入一颗子弹

首先需要计算该弹幕的尺寸，通过获取弹幕的宽度，用来调整弹幕每帧的行进距离，使得弹幕墙整体错落有致。

  // 根据文字长度计算每一帧需要run多少距离
  static double getBulletEveryFramerateRunDistance(double bulletWidth) {
    assert(bulletWidth > 0);
    return FlutterDanmakuConfig.baseRunDistance + (bulletWidth / FlutterDanmakuConfig.everyFramerateRunDistanceScale);
  }

需要查询可用的轨道，如果没有找到可用的轨道，返回一个错误信息，让业务层自行处理

if (track == null)
  return AddBulletResBody(
    AddBulletResCode.noSpace,
  );

如果允许插入，根据弹幕类型分别记录。

轨道

轨道使弹幕不需要计算X轴碰撞。轨道的设计需要考虑弹幕墙的高度，Y轴区间，以及满足展示弹幕区域的业务需求，并且需要提供弹幕链表的头节点以方便遍历操作。

初始化轨道

首先根据文字配置获取文字高度，然后填充满弹幕墙。并且每一条轨道都需要偏移弹幕墙的剩余高度 / 2 使其居中。

  // 补足屏幕内轨道
  void buildTrackFullScreen() {
    Size singleTextSize = FlutterDanmakuUtils.getDanmakuBulletSizeByText('s');
    while (allTrackHeight < (FlutterDanmakuConfig.areaSize.height - singleTextSize.height)) {
      buildTrack(singleTextSize.height);
    }
  }

删除轨道上所有子弹

根据轨道记录的最后一个子弹，通过遍历取上一颗子弹，来删除所有的弹幕。

  // 删除轨道上的所有子弹
  void delBullletsByTrack(FlutterDanmakuTrack track, Map<UniqueKey, FlutterDanmakuBulletModel> bulletMap) {
    if (track.bindFixedBulletId != null) bulletMap.remove(track.bindFixedBulletId);
    UniqueKey prevBulletId = track.lastBulletId;
    while (prevBulletId != null) {
      UniqueKey _prevBulletId = bulletMap[prevBulletId]?.prevBulletId;
      bulletMap.remove(prevBulletId);
      prevBulletId = _prevBulletId;
    }
  }

控制器

弹幕的播放通过控制器控制，控制器由定时器驱动，每隔一段时间，就会遍历所有的子弹，让每个子弹Model的位置数据更新到下一帧的位置数据，然后调用setState()统一渲染。

  void run(Function nextFrame, Function setState) {
    _timer = Timer.periodic(Duration(milliseconds: FlutterDanmakuConfig.unitTimer), (Timer timer) {
      // 暂停不执行
      if (!FlutterDanmakuConfig.pause) {
        // 将所有子弹的位置参数更新为下一帧
		nextFrame();
		// 最后统一渲染
        setState(() {});
      }
    });
  }

  /// 子弹执行下一帧
  void runNextFrame() {
    _runDistance += everyFrameRunDistance * FlutterDanmakuConfig.bulletRate;
  }

定时器并不会到点就执行，而是到点插入事件队列，由于Dart与JS使用相同的事件循环模型，那么定时器会被插入宏任务队列。 需要注意如果前面的执行任务耗费了过多的时间，那么会严重影响下次调用setState的时机导致掉帧。

在弹幕组件中，如何规避掉帧

1. 由于Dart是单线程语言（同JS），执行依赖于事件循环模型。单线程的特点是只能利用单核CPU进行计算。时间复杂度过高的计算操作会使CPU在60MS内来不及执行到下一个setState操作。所以针对时间复杂度高的计算，需要考虑起一个新的计算线程（Dart Isolate JS WebWorker Nodejs worker_threads）让这个计算操作在其他的CPU内核中执行，以防加入当前的任务队列使任务队列过长导致setState事件延后。
2. 参考事件委托，防止在每个子任务中调用耗时操作。在这里，将每个弹幕的数据修改后，统一调用setState。与之相同的思路有从替换不同子节点的公共祖先节点。
3. 尽量避免渲染线程执行过于复杂的计算，弹幕子弹层级过多，或者UI效果过于复杂（高斯模糊 图片 等）。

事件循环 https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/EventLoop
寻找公共父祖先 如果多次修改dom节点会导致浏览器的多次重排，那么比较好的方案是找出两个节点的公共祖先节点，从祖先节点开始替换。https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

简单介绍一下这个项目

https://github.com/flutte-danmaku/flutter_danmaku

基于Flutter的弹幕项目

实现以下功能

Features

• 色彩弹幕
• 静止弹幕
• 滚动弹幕
• 底部弹幕
• 可变速
• 调整大小
• 配置透明度
• 调整展示区域
• 播放 && 暂停
• 自定义弹幕背景
• 弹幕点击回调

欢迎点击https://a62527776a.github.io/flutter_danmaku_demo/index.html试用