游戏迷雾算法

　　战争迷雾除了客户端要表现出来之外，服务器也要计算，因为服务器要计算那此敌人是你能看见的，能看见才会发它的数据给你。如果服务器不计算，很容易作假，比如CF游戏中，由利用外挂可以穿墙看到敌人。这是因为服务器没有计算，把所有敌人的数据都下发给了客户端，客户端根据障碍物计算那个敌人是看不见的。所以为了防止作假，最好的方面是服务器(数据层)和客户端(表示层)都计算。这个一来性能很重要，毕竟一张地图有很有人物，而且必须时时计算。

　　1、迷雾算法-无障碍物情况

　　我们把一个透明图元分成4份(灰色-不可见，绿色-可见)，得到4个半透明图元，并编号为1，2，4，8。

　　为什么编号是1，2，4，8，而不是1，2，3，4呢?(看完本节，再看解答)

　　4个图元自由组合，我们可以用4个0或1表示组合中是否有对应的图元。

　　比如0101表示第1张无，第2张有，第3张无，第4张有。

　　所以0101序列中每一位表示一个图元。把下列二进制换成十进制：

　　1000=1，1号图元

　　0100=2，2号图元

　　0010=4，4号图元

　　0001=8，8号图元

　　按“或”运算。1号 + 2号 + 4号 + 8号 = 15号。(1|2|4|8 = 15)

　　那么由这4个基本图元，我们可以得到16个不同的图元。为什么是16个?0号图元怎么得来的?

　　1、为什么是16个图元?

　　根据高中数学的“组合分式”， 4个基本图元，自由组合，总共有16种组合方式。比如：

　　1号 + 2号 + 4号 + 8号 = 15号

　　2号 + 8号 = 10号

　　5号 + 12号 = 13号(按或算法)

　　2、0号图元怎么得来的?

　　由问题1可知，当没有1，2，4，8图元，可得到0号图元。

　　根据4个基本图元(1，2，4，8)，我们来考虑游戏中的实际情况。

　　1、假如一个队友站在地图上，那么他周围的可见度，如下：

　　2、假如两个队友站在地图上，那么他们周围的可见度，如下：

　　为什么会出现5号和10号图元呢?

　　5号图元是由【队友1的1号图元】和【队友2的4号图元】组成的。

　　10号图元是由【队友1的2号图元】和【队友2的8号图元】组成的。

　　以下5个队友同时出现在一起的情况。

　　2、迷雾算法-有障碍物情况

　　基本上所有的游戏地图都是有障碍物的，所以【迷雾算法-无障碍物】是不适合的。

　　那么怎么样才能现实有障碍物的迷雾算法呢?从人的思维出发，视线如果被障碍物挡住了，障碍物后面是不可见的。

　　下面以LOL为例：

　　假如一个队友站在地图上，如下。

　　这样我们可以得到8个基本图元，分别编号为1，2，4，8…，通过自由组合生成256个不同的图元。

　　1、 假如一个队友的可见度为3米，中间出现了一个障碍物。

　　障碍物后面应该是不可见的，程序怎么样处理才能得到这种效果呢?

　　1、 首先我们确定视线前方是否有障碍物?

　　2、 其次我们确定遇到障碍物了怎么办?

　　以A格子为例，我们以1，3号视线来判断A格子是否被障碍物挡住了。

　　初中数学知识，1，3直线为矩形的对角线，求直线穿过的小正方形?这个容易吧。

　　1、 如果两条直线均没有遇到障碍物，则该格子完全可见。(此可见，并非该格子完全透明，而是在不考虑障碍物时的可见度)

　　2、 如果两条直线均有障碍物，则该格子完全不可见(比如： B格子。2，4视线均有障碍物)。

　　3、 如果一条遇到障碍物，一条没遇到障碍物，则该格子可见区域一半可见(可见区域的一半，并非整个格子的一半可见。比如：A格子)。

　　那么图元可见区域一半可见，怎么实现?是分割吗?

　　肯定不能用分割，分割得到的图元，不能用8个基本图元组合得到，但是我们只有256张图元。比如：

　　既然分割不可以，那就只能模糊处理了，从256张(8个基本图元自由组合)图元中找出一张与分割图相似的图元。对于单个队友在无障碍物情况下只需要8张基本图元和一张完全可见图，就可以实现迷雾算法，有障碍物无非是有些需要分割。所以只需要找到这9张显示一半可见的图元(大概18张)。