询问一下，xml转ass的弹幕位置\move()是怎么计算出来的？

[MiKoto-Railgun]

如题，有哪位大佬可以说一下，xml转ass的弹幕位置\move()是怎么根据时轴与长度计算出来的，或者说具体在这个项目的哪个位置

PS：还没怎么学C语言，要喷请轻点

[MiKoto-Railgun]

它的文本长度又是怎么计算出来的？

[lengyanyu258]

思路参考这里：Mr-Quin/danmaku-anywhere#62 (comment)

项目中的文本长度为粗略估计出来的（单个长度✖总的数量），並不精确，或将在以后改进

[timerring]

\move() 源码在这里：

DanmakuFactory/AssFile/AssFile.c

Lines 2006 to 2007 in 998cac3

	fprintf(opF, "R2L,,0000,0000,0000,,{\\move(%d,%d,%d,%d)",
	resolution.x + textLen/2, PositionY, -1 * textLen / 2, PositionY);

对于 R2L 类型的弹幕，前两个参数是初始的位置 resolution.x + textLen/2, PositionY 两个参数是结束的位置 -1 * textLen / 2, PositionY，需要保证 Y 的位置不变。

计算文本长度 textLen 的源码在这里，简单地说是根据字号和字体（但是实际上并没有用到字体这个参数）累加每个字符的长度：

DanmakuFactory/AssFile/AssFile.c

Line 1945 in 998cac3

textLen += getStrLen((unsigned char *)(now -> text), fontSize, now -> fontSize, fontName);

计算字符长度的函数 getStrLen 在这里：

DanmakuFactory/String/DanmakuFactoryString.c

Lines 54 to 95 in ae05009

	int getStrLen(const unsigned char *str, const int fontSizeSet, const int fontSizeInFile, const char *fontName)
	{
	int cnt = 0;
	/* 非法判断 */
	if (str == NULL)
	{
	return -1;
	}
	/* 判断字符串编码 */
	if (isUtf8(str) == TRUE)
	{
	/*
	* 目前仅支持utf-8
	* 首字节 空间占用 起始
	* 0--- ---- 1 byte 0x00
	* 110- ---- 2 byte 0xC0
	* 1110 ---- 3 byte 0xE0
	* 1111 0--- 4 byte 0xF0
	* 1111 10-- 5 byte 0xF8
	* 1111 110- 6 byte 0xFC
	*/
	while (*str != '\0')
	{
	if (*str >= 0xC0) {
	cnt++;
	} else if (*str < 0x80) {
	cnt++;
	}
	str++;
	}
	}
	else
	{
	cnt = (int)strlen(str);
	}
	int len = cnt * (fontSizeSet + (fontSizeInFile - 25)) / 1.2;
	return len;
	}

判断该字符是否为 UTF-8 编码的单字节字符，0xC0 用来判断当前字节是否是多字节字符的起始字节，因为110- ---- 就是0xC0，而 0x00到0x7F 是 ASCII 字符是单字节字符。因此第二个判断就是要小于 0x80，

当然如果不是 UTF-8 编码的话直接就使用 strlen 函数即可。

字符总长度是一个大概的值，len = cnt * (fontSizeSet + (fontSizeInFile - 25)) / 1.2;

如果觉得不容易理解的话可以看一下 UTF-8 的编码原理。

[timerring]

另外 fontSizeInFile 参数一般默认 25，因为 b 站的 xml 弹幕中通常为 25。某些特殊的大弹幕可能不是。这个参数的起名有点误导，感觉叫做 fontSizeInXml 可能更贴切一点。

[timerring]

接下来分析一下 PositionY 的逻辑，简单来讲是：从 PositionY = 1 开始，逐步增加 PositionY，直到找到一个合适的行。每次增加 PositionY 时，检查该行是否被其他弹幕占用。

细化一下 -> 对于每个 PositionY，检查从 PositionY 到 PositionY + fontSizeSet 的每一行（这里如上省略fontSizeInFile）是否被其他弹幕占用。

具体做法是：

• 当前弹幕的开始时间 time（换句话说是 xml 中的那个弹幕 showup 时间） 小于某行的 R2LToRightTime：当本条弹幕出现该行最后一条弹幕未离开屏幕右边。
• 或者当前弹幕的结束时间 time + rollTime 大于某行的 R2LToLeftTime：当本条弹幕到达左端时该行最后一条弹幕没有完全退出屏幕。

以上 R2LToLeftTime 是个整形数组，则该行被占用，需要增加 PositionY。

一些核心的代码如下：

DanmakuFactory/AssFile/AssFile.c

Lines 1959 to 1976 in ae05009

	int PositionY;
	for(PositionY = 1; PositionY < rollResY - textHei; PositionY++)
	{
	for(cnt = 0; cnt < fontSize; cnt++)
	{
	if(now->time < R2LToRightTime[PositionY + cnt] ||
	now->time + GET_ASS_MS_FLT(rollTime / 1000.0f * resolution.x / (resolution.x + textLen)) < R2LToLeftTime[PositionY + cnt])
	{/* 当本条弹幕出现该行最后一条弹幕未离开屏幕右边 或
	当本条弹幕到达左端时该行最后一条弹幕没有完全退出屏幕 */
	PositionY = PositionY + cnt + 1;
	break;
	}
	}
	if(cnt >= textHei)
	{
	break;
	}
	}

DanmakuFactory/AssFile/AssFile.c

Lines 1992 to 1996 in 998cac3

	for(cnt = 0; cnt < textHei; cnt++)
	{/* 登记位置占用信息 */
	R2LToRightTime[PositionY + cnt] = now -> time + GET_ASS_MS_FLT(rollTime / 1000.0f * textLen / (resolution.x + textLen));
	R2LToLeftTime[PositionY + cnt] = now -> time + rollTime;
	}

找到合适位置：

• 如果找到一个 PositionY，使得从 PositionY 到 PositionY + fontSizeSet 的所有行都没有被占用，则停止增加 PositionY。说明以下空行都是 available 的。
• 如果没有找到合适的 PositionY，则选择 R2LToRightTime 中最小值对应的行作为 PositionY。相当于见缝插针。

[timerring]

这个问题进一步转化我认为还有最优解以及更加快的方式，这里的每一行可以看作高铁的座位。

[MiKoto-Railgun]

感谢大佬！！！

[timerring]

从某种程度上来看这种计算方式反而把事情想复杂了，我再看能不能尽量简化一下限制条件。

[timerring]

我认为不用考虑左边的边界条件，还有右边的边界条件，存储过多的数据，因为本质上可以回归到当前弹幕和前一条弹幕之间距离的问题，为了避免追及即重叠的情况，我们只需要确保一件事情，就是接下来前一条弹幕到达终点 X 坐标的这一段时间内，同一个轨道中的弹幕后一条无法追及到前一条即可（因为 n 无法追及到 n-1 同时就能保证无法追及到 n-2 的一条）。如果能追及到则比较下一条轨道弹幕数据。

首先每条弹幕的总路程 text_length + resolution.X 是固定的。然后滚动的时间是固定的，我看 cli 中的默认时间是 12s，那么就能算出 每条弹幕的速度 V_i，每个轨道的数组中只需要存储当前轨道最后一条弹幕的 开始时间 start_time，弹幕文本长度 length 即可。

然后需要判断下一条弹幕 B 是否能够追及到前一条弹幕 A ，首先需要算出两者的距离差 Delta_X，即 Delta_X = (start_time_B - start_time_A) x V_a - text_length_A / 2 - text_length_B / 2，当然为了美观可以再预留一定的 margin 距离。然后判断这个距离是否能在剩余的时间内被追及，那么速度差就是 Delta_V = V_B - V_A，就可以算出追及所需要的时间大概是 Delta_T = Delta_X / Delta_V，只需要保证 Start_time_B - Start_time_A > Delta_T 则确保两条弹幕不会追及重叠。

所以最后实际上只需要一个数组和一个公式即可。当然可能在大量弹幕的情况难免会追及，所以还需要 fallback 策略，这个 fallback 策略也很容易，只需要在每次比较时多加一个 flag 用于保存最大负时间差的轨道号即可。这样哪怕会追及，弹幕也会在弹幕的最右侧两者相遇，在大量弹幕的情况下也能保证观看的体验。

这种方式理论上能在极限情况下比当前的方式容纳更多不会重叠的弹幕。

我整理一下，看看具体的测试效果如何。

[timerring]

https://github.com/timerring/DanmakuConvert

我按照想法写了一个 demo，渲染出来效果还算不错。

[renmu123]

我觉得在不知道具体文字长度情况下做一些比较精细化的算法没什么意义，多留点余量就行

[timerring]

我觉得在不知道具体文字长度情况下做一些比较精细化的算法没什么意义，多留点余量就行

按照 getStrLen 的方式计算的话，每个弹幕的长度都是已知的。况且也是流程里计算 x 轴本身需要的，留余量完全可以加 margin。

在大概相同的计算量情况下，只开更少的空间能容纳更高的性能，感觉还是挺有意思的。

[renmu123]

我觉得在不知道具体文字长度情况下做一些比较精细化的算法没什么意义，多留点余量就行

按照 getStrLen 的方式计算的话，每个弹幕的长度都是已知的。况且也是流程里计算 x 轴本身需要的，留余量完全可以加 margin。

在大概相同的计算量情况下，只开更少的空间能容纳更高的性能，感觉还是挺有意思的。

是我之前的理解有点问题，我同意你的看法，如果有更优性能的算法自然是再好不过。
ps：我指得长度未知是指程序计算出来的长度与最终渲染的长度实际上是不一致