DragonWind

王者荣耀解剖(一):定点数的实现

王者荣耀用的帧同步,帧同步需要用定点数。

因为帧同步需要每台机器上,给定相同的输入,都能得到确定相同的结果。浮点数不行,为什么?

1.精度不准确:十进制小数转二进制,存在转不尽;

2.运算不确定:不同机器运行有差异。例如a+b+c可能表示为(a+b)+c也可能a+(b+c)

王者实现的定点数:

数值以int形式保存,提供结构VInt,其中:

scalar设为0.001

实际存储为原值的1000倍。

小数以分子+分母的long形式保存,提供结构VFactor。

提供数学工具类IntMath,做基础数学运算

IntMath的一些操作

开平方

public static ulong Sqrt64(ulong a)
{
	ulong num = 0uL;
	ulong num2 = 0uL;
	for (int i = 0; i < 32; i++)
	{
		num2 <<= 1;
		num <<= 2;
		num += a >> 62;
		a <<= 2;
		if (num2 < num)
		{
			num2++;
			num -= num2;
			num2++;
		}
	}
	return (num2 >> 1) & 0xFFFFFFFFu;
}

四舍五入除法

public static long Divide(long a, long b)
{
    //确定ab同号还是异号
    //符号位异或,相同为0不同为1
    //与long的最小值,把数值位清空(实则多余)
    //右移63位,取出值0或1
	long num = ((a ^ b) & long.MinValue) >>> 63;
    //如果同号,值为1;如果异号,值为-1
	long num2 = num * -2 + 1;
    //加上负数的一半,实现四舍五入
	return (a + b / 2 * num2) / b;
}

求Sin

查表

public static VFactor sin(long nom, long den)
{
    //根据传进来的弧度,找到“第几份”
    //提前把2π分为4096份
    //弧度/2π获得[0,1]占比,然后*4096找到第几份
	int index = SinCosLookupTable.getIndex(nom, den);
    //返回查表结果,sin表是*FACTOR=10000之后的
	return new VFactor(SinCosLookupTable.sin_table[index], SinCosLookupTable.FACTOR);
}
public static int SinCosLookupTable.getIndex(long nom, long den)
{
    //传进来的nom和den是分子和分母,以弧度表示
    //我们要知道弧度在整个的占比,就用弧度/2π
    //然后分成了4096份,找到第几份,于是弧度/2π*4096
    
    //分子先*4096*10000
	nom *= NOM_MUL;
    //分母先*2π*10000,也就是62832
	den *= 62832;
    //计算结果
	int num = (int)(nom / den);
    //最后与一下MASK=4095,把结果限制在[0,4095]
	return num & MASK;
}
BITS = 12;
MASK = ~(-1 << BITS);
//COUNT=4096,为了把一圈分成4096份
COUNT = MASK + 1;
FACTOR = 10000;
//避免小数运算
NOM_MUL = FACTOR * COUNT;

求Cos

类似求Sin

求ACos

public static VFactor acos(long nom, long den)
{
    //首先mom/den的值在[-1,1]之间
    //*512再+512,把值在[0,1024]之间
	int value = (int)Divide(nom * AcosLookupTable.HALF_COUNT, den) + AcosLookupTable.HALF_COUNT;
    
    //进一步clamp,如果上一步的值小于-1或者大于1
    //即上一步的值小于0或者大于1014
	value = Mathf.Clamp(value, 0, AcosLookupTable.COUNT);
    
    //查表 返回结果 表里的值是*10000的
	return new VFactor
	{
		nom = AcosLookupTable.table[value],
		den = 10000L
	};
}
COUNT = 1024;
HALF_COUNT = COUNT >> 1;

求ATan2

public static VFactor atan2(int y, int x)
{
    //把x和y转到第一象限
    //存好num和num2,后面把值再转回去
    //第二象限,π-θ
    //第三象限,θ-π
    //第四象限,-θ
    //31416就是π*10000
	int num;
	int num2;
	if (x < 0)
	{
		if (y < 0)
		{
			x = -x;
			y = -y;
			num = 1;
		}
		else
		{
			x = -x;
			num = -1;
		}
		num2 = -31416;
	}
	else
	{
		if (y < 0)
		{
			y = -y;
			num = -1;
		}
		else
		{
			num = 1;
		}
		num2 = 0;
	}
    //缩放
    //让最大变成127就行
    
	int dIM = Atan2LookupTable.DIM;
	long num3 = dIM - 1;
	long b = ((x >= y) ? x : y);
	int num4 = (int)Divide(x * num3, b);
	int num5 = (int)Divide(y * num3, b);
    
    //查表,二维数组转为一维数组
	int num6 = Atan2LookupTable.table[num5 * dIM + num4];
    //返回结果,注意结果是第一象限的,要把值转回去
	return new VFactor
	{
		nom = (num6 + num2) * num,
		den = 10000L
	};
}
BITS = 7;
BITS2 = BITS << 1;
MASK = ~(-1 << BITS2);
COUNT = MASK + 1;
DIM = IntMath.Sqrt(COUNT);

杂项

public static bool IsPowerOfTwo(int x)
{
	return (x & (x - 1)) == 0;
}

public static int CeilPowerOfTwo(int x)
{
	x--;
	x |= x >> 1;
	x |= x >> 2;
	x |= x >> 4;
	x |= x >> 8;
	x |= x >> 16;
	x++;
	return x;
}

物理相关

public static void SegvecToLinegen(ref VInt2 segSrc, ref VInt2 segVec, out long a, out long b, out long c)
{
	a = segVec.y;
	b = -segVec.x;
	c = (long)segVec.x * (long)segSrc.y - (long)segSrc.x * (long)segVec.y;
}

private static bool IsPointOnSegment(ref VInt2 segSrc, ref VInt2 segVec, long x, long y)
{
	long num = x - segSrc.x;
	long num2 = y - segSrc.y;
	return segVec.x * num + segVec.y * num2 >= 0 && num * num + num2 * num2 <= segVec.sqrMagnitudeLong;
}

public static bool IntersectSegment(ref VInt2 seg1Src, ref VInt2 seg1Vec, ref VInt2 seg2Src, ref VInt2 seg2Vec, out VInt2 interPoint)
{
	SegvecToLinegen(ref seg1Src, ref seg1Vec, out var a, out var b, out var c);
	SegvecToLinegen(ref seg2Src, ref seg2Vec, out var a2, out var b2, out var c2);
	long num = a * b2 - a2 * b;
	if (num != 0L)
	{
		long num2 = Divide(b * c2 - b2 * c, num);
		long num3 = Divide(a2 * c - a * c2, num);
		bool result = IsPointOnSegment(ref seg1Src, ref seg1Vec, num2, num3) && IsPointOnSegment(ref seg2Src, ref seg2Vec, num2, num3);
		interPoint.x = (int)num2;
		interPoint.y = (int)num3;
		return result;
	}
	interPoint = VInt2.zero;
	return false;
}

public static bool PointInPolygon(ref VInt2 pnt, VInt2[] plg)
{
	if (plg == null || plg.Length < 3)
	{
		return false;
	}
	bool flag = false;
	int num = 0;
	int num2 = plg.Length - 1;
	while (num < plg.Length)
	{
		VInt2 vInt = plg[num];
		VInt2 vInt2 = plg[num2];
		if ((vInt.y <= pnt.y && pnt.y < vInt2.y) || (vInt2.y <= pnt.y && pnt.y < vInt.y))
		{
			int num3 = vInt2.y - vInt.y;
			long num4 = (long)(pnt.y - vInt.y) * (long)(vInt2.x - vInt.x) - (long)(pnt.x - vInt.x) * (long)num3;
			if (num3 > 0)
			{
				if (num4 > 0)
				{
					flag = !flag;
				}
			}
			else if (num4 < 0)
			{
				flag = !flag;
			}
		}
		num2 = num++;
	}
	return flag;
}

public static bool SegIntersectPlg(ref VInt2 segSrc, ref VInt2 segVec, VInt2[] plg, out VInt2 nearPoint, out VInt2 projectVec)
{
	nearPoint = VInt2.zero;
	projectVec = VInt2.zero;
	if (plg == null || plg.Length < 2)
	{
		return false;
	}
	bool result = false;
	long num = -1L;
	int num2 = -1;
	for (int i = 0; i < plg.Length; i++)
	{
		VInt2 seg2Vec = plg[(i + 1) % plg.Length] - plg[i];
		if (IntersectSegment(ref segSrc, ref segVec, ref plg[i], ref seg2Vec, out var interPoint))
		{
			long sqrMagnitudeLong = (interPoint - segSrc).sqrMagnitudeLong;
			if (num < 0 || sqrMagnitudeLong < num)
			{
				nearPoint = interPoint;
				num = sqrMagnitudeLong;
				num2 = i;
				result = true;
			}
		}
	}
	if (num2 >= 0)
	{
		VInt2 vInt = plg[(num2 + 1) % plg.Length] - plg[num2];
		VInt2 vInt2 = segSrc + segVec - nearPoint;
		long num3 = (long)vInt2.x * (long)vInt.x + (long)vInt2.y * (long)vInt.y;
		if (num3 < 0)
		{
			num3 = -num3;
			vInt = -vInt;
		}
		long sqrMagnitudeLong2 = vInt.sqrMagnitudeLong;
		projectVec.x = (int)Divide(vInt.x * num3, sqrMagnitudeLong2);
		projectVec.y = (int)Divide(vInt.y * num3, sqrMagnitudeLong2);
	}
	return result;
}