树状数组的原理是什么？ - 后缀自动机·张的回答 - 知乎
https://www.zhihu.com/question/54404092/answer/139192487

非常抱歉每次都这样几乎是全文转载别人的知识，我知道这可能不好，但还请包容一下
如果以后 Stiack Note 成功做出来，这些就不会发在频道上了

我假设你知道啥是 lowbit

大前提：设节点编号为 x ，那么该节点维护的值是 (x - lowbit(x), x] 这个区间的和

现在我们分两步来分析

1. 查询
因为查询比较简单所以我就先讲查询为什么 work
先上 query 的代码

int query(s, usize index) {
  int ans = 0;
  while (index != 0) {
    ans += s[index];
    index -= lowbit(index);
  }
  return ans;
}

注意到某个点后面的值是肯定不会影响树状数组上这个点的 sum 的，那么因为我们每次取的是一段后缀，然后每次取的节点所覆盖的区域是是不重合的，所以正确性是显然的。

复杂度的话，可以发现我们每次取的lowbit是逐渐变大的，因为一个数二进制下只有 log 位，所以复杂度是 O(log(n)) 的

2. 更新
设我们更新的点的编号是 x
首先对于一种 lowbit，最多只有一个点可以覆盖 x（证明留作练习
因为一共只有 log(n) 种lowbit，所以我们可以枚举 lowbit
设 lowbit = 2^{k}

如果存在某个位置的lowbit = 2^{k}，而且他可以覆盖x的话，那么他的形式肯定是

000……0001aaaaaa

即前面是k-1个0，第k位是1，第k位之后必定每一位都和x相同（想想为什么）

现在我们分情况讨论：

2^k < lowbit(x)，显然不可能，因为这种情况覆盖不到x
2^k = lowbit(x)，这个肯定是可以的
2^k > lowbit(x)，这里有两种情况

x的第k位为0
那么根据我们上面构造的编号，他本身肯定比x大，但是他减去2^k会比x小（因为低位全部置零，而且这一位大于lowbit(x)，所以减去2^k之后在lowbit(x)这位小于x，所以这种case构造出来的编号是合法的

x的第k位不为0
那么构造出来的编号比x小（想想为什么

void update(s, usize index, int value) {
  while (a <= INT_MAX) {
    s[index] += value;
    index += lowbit(index);
  }
}

仔细观察可以发现，这个函数的作用就是每次求出下一个lowbit并且把之前的位都清零，并且保持了后缀不变嘛

每次加 lowbit 相当于清掉了若干个 1，并把碰到的第一个 0 的位置为 1（这就是进位的过程）

#book 《Streaming System》 （分布式流系统）《High Performance Spark》（大数据平台）

在游戏的发展历史中，出现过哪些有意思的加密反盗版机制和破解机制？ - Zign的回答 - 知乎
https://www.zhihu.com/question/46773069/answer/463741166

#Haha #recommended #tech #old #reveng #backend

+ 软盘激光加密
+ Int3争夺战
+ PSP的GTA破解
+ PSP的电池破解
+ Wii的破解

#recommended #ai #android https://github.com/ice1000/AIAndroid

*注意：不是人工智能产品，默认搭载一个文字游戏引擎

#recommended #ui
https://github.com/vczh-libraries/GacUI

#recommended #media #game #android #backend

https://zhuanlan.zhihu.com/p/37001473
米忽悠美工感觉 摆在全球都能算是相当先进级别的了（
国产游戏…甚至所有的卡通渲染游戏哪个比得过米忽悠
可惜摊上了什么侧滑

从图中我们可以看出，场景中使用了不少特效来提升表现力，比如 bloom 后期处理效果、动态粒子、平面反射、屏幕扭曲特效等，下面我们将会逐一对这些效果进行解析。

在移动端实现高品质的反射，平面反射是一个综合了效果和性能因素较好的办法。通常做法是以地面为对称平面，将摄像机放置在对称位置后渲染场景得到反射结果。

为了能表现出地面的金属质感，首先我们对反射结果应用六边形采样模糊，然后使用金属纹理细节法线贴图来扰动反射结果，除此之外我们还使用了镜面反射贴图和菲涅尔效果来进一步增强反射质感。

在一些远离地面高度或非水平的次要反射表面上，平面反射就不在适用，为此我们使用环境贴图反射作为替代方案。为了尽量减少渲染反射场景所占用的开销，我们将反射分辨率限制在1/3以下，由于反射贴图会经过模糊处理，即使降低了较多的分辨率也并不能明显看出区别，并且我们在渲染反射的过程中还使用简化版的材质，并忽略一些不是很重要的小物体

接下来让我们看看另一个效果：全屏扭曲特效的应用。

我们在《崩坏3》的场景中较多的使用了屏幕扭曲效果，比如刀剑的拖尾特效，时空断裂效果，水流瀑布及其他场景效果。

在渲染扭曲效果的过程中，我们使用3个通道来存储扭曲的渲染结果，两个用于存储uv偏移，另一个用于存储扭曲强度mask，扭曲强度mask用于执行深度剪裁和基于距离的强度控制。

使用单独的pass渲染扭曲结果到帧缓冲纹理对于移动平台来说开销较大，所以我们在最终的后处理中整合应用了扭曲效果，相比前者要快很多。

但这种方法也可能导致靠前面的物体由于没有分层处理而混入后面扭曲材质的问题，不过考虑到移动平台的性能限制，相对于整体效果而言这种妥协是值得的。

让我们再看看bloom的实现。

整个场景如果开启HDR会使用fp16格式的render target，然后下采样到原始大小的1/4，以便之后的后处理流程使用。

首先，我们需要指定一个亮度阈值来提取图像中的高亮区域，实现方法也并不复杂，只需从源像素减去阈值，得到的结构就是提取后的高亮度区域，叠加这层内容能使结果看起来更具对比并且色彩鲜艳。

接下来，我们产生4个大小依次递半的render target，并将其内容应用半径逐渐增大的高斯模糊，最后我们将这些模糊后的结果合并起来，以获得最终的bloom效果。

从最终的效果图我们可以看到，bloom效果不仅起到用来表达高亮区域的视觉效果，还对整个图像的色彩中起着明显的润色作用。

当完成了反射渲染，扭曲效果的及bloom的处理后，最终就可以将这些中间结果合成在一起。

我们使用filmic tone mapping与曝光和对比度控制来将fp16 HDR的原图像转换为最终的LDR帧缓冲。由于这些合成操作都是在一个Pass中完成的，所以即使在移动设备上也可以满足性能方面的需求。

下面我们来介绍一下游戏中的天气和云海的实现方案。

我们想要创造一个能让玩家感受到纵深，具有各种丰富形态以及动态光照变化的云的渲染系统。而该系统也应该易于调整和使用，方便美术可以创造出不同类型的云层效果。

这对我们来说也是一个有趣的挑战，接下来就让我们来谈谈这些功能：

首先让我们看看渲染云所需要的资源，因为我们想要实现可以24小时动态变化的风格化云的光照效果，如果直接存储画好的贴图数量就会太大而且不方便调整，所以我们使用多层着色来实现这一点。

我们使用4个通道来表示云的光照及阴影：基础照明层，阴影1层，阴影2层，和边缘光层。通过为每个图层设置不同的颜色，我们就可以获得不同时刻的云的色彩方案。我们一共准备了8种形状不同的云的模板，用来构建各种不同的云海景观。

为了构建云海景观，我们使用了很多朝向屏幕发射云朵的粒子发射器，并且使用不同的云的模板以及发射模式来组合出不同的云海景观，我们实现了如各种类型的云海以及暴风雨天气等，这些预设都保存在天气配置中。此外我们还使用关键帧来定义天空背景和云彩的颜色。随着时间的流逝，云的色彩就根据关键帧来变化。

在性能方面主要的开销是overdraw问题，如果我们按照固定控制的pattern来发射云虽然可以以最小的overdraw来获得较好的云海密度，但可能会看起来较为重复，加入产生位置的随机因素可以解决这个问题，但要想获得看起来不那么稀疏的云海效果就需要相比固定pattern更多的粒子数量，我们对于粒子发射配置都有细致的参数可以调整，以便在两者之间可以找到较好的权衡点。

我们主要通过全局雾效，Skybox颜色和方向光的设置来改变场景的天气和氛围。对于雾效同样有许多参数可以调整。我们给雾效基于深度划分为远近距离两个区间，远近区间都可以设置不同的颜色和强度值来创造各种各样的气氛。Skybox也可以控制天空颜色渐变，云的受光及阴影颜色等。

综合上述调整选项，我们就可以创建晴天，雨天和大雾，多云和夜间等天气。

另外人物的光照也会受环境的影响，主要的光照颜色由方向光决定，局部区的阴影的变化比如角色走进阴影区域，由一些从关卡编辑器中手工放置的Lighting Volume定义。

让我们再来看看游戏中使用景深的情况。

手游中使用景深一般并不常见，因为常见的景深实现对于移动平台来讲还是开销较大，我们主要在人物选择界面和任务简报会话中使用景深效果来突出表现人物。

由于这些场景不需要景深的过度，我们使用一种特殊的方法来提高移动性能。不使用depth buffer做COC混合，而是使用单独的相机直接绘制背景图层。在应用模糊通过后，通过将背景和前景人物组合在一起来获得最终图像。

为了得到更好的视觉效果，我们使用六边形采样模式来获得更好的bokeh形状。除此之外还有bokeh强度调整参数，以使其看起来更清晰，我们使用亮度值作为增量因子，2通常是一个合适的值。

性能方面为了保持性能的稳定，我们模糊背景的分辨率视模糊程度而定，更大的模糊尺寸使用更低的分辨率并且更不容易察觉，我们还使用Unity内置的曲线来描述它们之间的转换关系。

当给最后一个敌人致命一击的时候就会激发子弹时间，这时所有高速运动的物体都会慢下来，在下雨天我们就可以明确的看到雨滴的形状。
为了实现这个效果，我们使用了4个代表雨滴不同速度下形态的关键帧，再根据时间快慢尺度对其进行垂直拉伸。在正常的时间尺度下，雨滴看起来像一条直线，在时间变慢的时候逐渐缩短变成雨滴形状。

在这里我们同样使用了动画曲线来控制拉伸，关键帧选择和时间快慢的关系，调整起来非常灵活方便。

刚才我们谈到的都是一些针对移动端优化的渲染功能，下面我们来介绍一下用于动画风格real-time CG或次世代游戏的渲染方法。

在过去的两年中，我们陆续制作了两个短片音乐视频，其中体现了我们的新渲染风格。
首先我们来看看角色的渲染，我们的目标是实现完全动态的光照和阴影，所有材质都对各种光照现象做出正确的反应，包括主光源和区域环境光。这就要求我们不能使用任何在纹理上画死的光照表现。

用于角色渲染的主要特性有：多通道Ramp的材质shading方法，眼睛，头发和其他各向异性材料等特殊材料的处理，以及PCSS角色软阴影和高品质的勾线。
首先我们来看一下多通道Ramp的shading方法。我们希望角色的阴影和颜色的变化可以表现出更细腻的插画风格，所以我们使用2D ramp纹理来表示这些细微的变化，其中RGB通道分辨用于描述于不同阴影层的漫射阴影范围。

每个层都可以制定不同的颜色，这样就能在明暗变化中做到精细的色彩变化控制，对于卡通风格的画面，如果上色只是纯明暗变化，阴影处就会显得比较脏，缺乏表现力，而如果提升暗处的饱和度和色相变化，整体色彩看起来就会比较鲜活。而且通过调整垂直纹理采样坐标，我们可以实现动态的软硬风格转换。

从另一角度来看这种方法还间接表现了皮肤的次表面散射效果。这四幅图展示了多通道逐层上色叠加的效果。

... 太多了暂时不转了，喜欢顶层图形学渲染啥的可以看看

duangsuse 现在正准备完成 ApkBundler Scheme 😶

为了明确 ABS 的设计，我打算首先分析一下 Lice 语言（当然，这是冰冰 2017 年末的作品）和 BiwaScheme（仅虚拟机执行模式）

https://t.me/dsuses/2486

吐槽：真是有点乱呢，太「多范式」化了，居然在类似 Scheme 的同时支持流程控制特性...

有时候在看 CS 相关的内容，甚至是一些富有技巧的代码时会感到自己很菜，什么都搞不懂
（当然目前还是很菜的）所以做不好，请见谅了

尝试测试了一下，很失败，貌似是 glib 的 pkgconfig 的问题出的错，为此实在感觉 CMake 作为一个构建工具，居然连自定义 build dir 都做不到...

#PL #code #guide #daily #scheme

关于 Lice lice-lang/lice 解释器的分析

我们只看解释器实现，不看测试和文档什么的，目标为理解官方 Lice 解释器实现和汲取精华、以及提出充分利用 Kotlin 特性的建议

org/lice/api/scripting/*

javax.script 的 API 接口

我们可以看到，LiceScriptEngineFactory 类提供以下信息

LanguageVersion EngineVersion Extensions MimeTypes LanguageName Names EngineName

ScriptEngine()
OutputStatement(toDisplayString)
Program(statementsCode)

MethodCallSyntax(obj: String, mid: String, vararg args: String)

Parameter(paramString)
"javax.script.engine_version", "javax.script.language_version"
"javax.script.engine", "javax.script.language", "javax.script.name"

而 LiceScriptEngine 做这些

class LiceScriptEngine : JavaxScriptEngine
  private var context: LiceContext = LiceContext()
  getContext()
  setContext(context)
    setContextIfIsLiceContext()

  getFactory()

  eval(scriptString, context) = eval(script, context.bindings)
  eval(script: String) = eval(script, context.bindings)

  eval(reader: Reader) = eval(reader.readText(), context.bindings)
  eval(reader: Reader, n: Bindings) = eval(reader.readText(), n)
  eval(reader: Reader, context: ScriptContext)

  eval(script: String, n: Bindings)

  get(key: String?): Any? = context.bindings[key]
  put(key: String, value: Any?)

  createBindings() = SymbolList()
  getBindings(scope: Int) = context.bindings
  setBindings(bindings: Bindings?, scope: Int)

并且 LiceContext 做这些

bindings: SymbolList
reader: Reader
writer: Writer
errorWriter: Writer

getAttribute(name: String)
getAttribute(name: String, scope: Int)
setAttribute(name: String, value: Any?)
setAttribute(name: String, value: Any?, scope: Int)
removeAttribute(name: String) = bindings.removeVariable(name)
removeAttribute(name: String, scope: Int)

getScopes(): MutableList<Int>
getAttributesScope(name: String?): Int

getBindings(scope: Int)
setBindings(bindings: Bindings, scope: Int)

然后是 org/lice/core/*

AbstractBindings

variables: MutableMap<String, Any?>
provideFunctionWithMeta(name: String, node: ProvidedFuncWithMeta)
provideFunction
defineFunction
getVariable
defineVariable
isVariableDefined
removeVariable

containsValue
clear
putAll(from: Map<out String, Any>)
containsKey
get
put
isEmpty
remove
var size = fun ...
entries: MutableSet<LiceEntry>
keys
values

... 说得太详细了实在是脑洞啊

简要说一下每个类的功能（看了一点后我还是觉得 Lice 的设计有点大了... 不知道为什么）

我大概看了一遍，已经找到分词、解析器、数值类型自动提升运算工具、内部函数位置、辅助扩展函数、AST 求值逻辑位置
目前依然需要确定的可能是内部函数分派逻辑

刚才去迂腐的编译原理裙里看看，冰封不在所以为啥要给 Kotlin 的内部 handler 加 mangle 我就没问到

然后我怂了... 因为我感觉 InScript + JNI Bison + Flex Lexer 会更好玩一些，之前没玩过，都是自写的分词器，然后递归下降 Recursive descent method 解析器不会写... 二元运算优先级和左优先级右优先级不了解... 所以都不知道如何整理 BinaryNode

不过我还是乐意出一个支持最新基本词法语法定义的 Lime 去和 Lice 比速度

平时指令式 imperative 写多了声明式 declarative 写少了的 duangsuse 不会看满屏括号（
至少不知 C++ template 元编程 metaprogramming 为何物

补充：现在问到了，是 JVM 方法名不支持某些特殊字符的锅