Notifications
Article
基于Compute Shader的生命游戏
Published a year ago
586
0
原文参见:https://zhuanlan.zhihu.com/p/43516971

什么是生命游戏

生命游戏是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。在二维的矩形世界中,每个方格被视为一个细胞,该细胞的下一个状态取决于周围邻居的当前状态。假如邻居活着的细胞过多,那么这个细胞下一刻会因为资源匮乏而死;假如活着的邻居过少,则细胞会因为过度孤独而死;而适当数量的邻居又能繁衍出新的细胞。
本文使用的规则是:
1.假如本细胞在这一刻活着,那么若邻居细胞存活数少于2或大于等于4,则本细胞下一刻死亡。
2.假如本细胞在这一刻死亡,那么若邻居细胞存活数等于3,则本细胞下一刻为活着。
通过简单的规则,二维矩形上会演变出各式各样的生命群落。但是大部分情况下,它们最终会维持稳定,只有少数经过精心设计的图形才能长期变幻、扩张,形成宏观上令人震撼的群落。具体内容参见【1】

C#版本的生命游戏

我们根据生命游戏的概念,可以很快编写出生命游戏的原型。演示可以在工程中名为cpu的场景上找到。不过,其运行效率着实令人头大。

Compute Shader版本的生命游戏

当我们思索生命游戏的逻辑的时候,不难发现,生命游戏大部分的运算量实际上都是一个并行的任务,而且该并行任务并没有顺序要求,每个像素需要遍历其周围的邻居,对于什么时候遍历并不关心。因此我们会敏锐想到Compute Shader,通过将计算任务转嫁到GPU,利用GPU的针对并行任务的设计来快速完成计算任务。
但这里又存在一个问题,那就是生命游戏中存在一个串行的逻辑——状态的变化必须发生在统计邻居之后——这个逻辑表明我们需要将生命游戏拆分成两个流程,也就是两个Kernel。
Compute Shader在Unity中的使用,可以参考【2】中所述,在此不再赘述。
// kernel is GameOfLifeUpdate #pragma kernel GameOfLifeUpdate #pragma kernel UpdateNext struct Cell { float4 xynn; //四通道信息为:x轴位置、y轴位置、当前是否活着,下一刻是否活着(活着=1) }; RWStructuredBuffer<Cell> Cells; //用来输出给C#进行展示 RWTexture2D<float4> GameTex; //定义活着和死了的颜色 float4 AliveColor; float4 DeadColor; //定义边界 float4 BorderVec; bool IsCellAlive(int x, int y) { if (x < BorderVec.x || x >= BorderVec.y || y < BorderVec.z || y >= BorderVec.w) return false; return Cells[x + y * BorderVec.y].xynn.z == 1; } //展示并统计 [numthreads(32, 32, 1)] void GameOfLifeUpdate (uint3 id : SV_DispatchThreadID) { int product = id.x + id.y * BorderVec.y; Cell curCell = Cells[product]; //展示上一回合的生命结果 if (curCell.xynn.z == 1) GameTex[id.xy] = AliveColor; else GameTex[id.xy] = DeadColor; //计算邻居存活数 int liveNum = 0; if (IsCellAlive(id.x-1, id.y-1)) liveNum++; if (IsCellAlive(id.x-1, id.y)) liveNum++; if (IsCellAlive(id.x-1, id.y+1)) liveNum++; if (IsCellAlive(id.x+1, id.y-1)) liveNum++; if (IsCellAlive(id.x+1, id.y)) liveNum++; if (IsCellAlive(id.x+1, id.y+1)) liveNum++; if (IsCellAlive(id.x, id.y-1)) liveNum++; if (IsCellAlive(id.x, id.y+1)) liveNum++; //生命游戏规则 if (curCell.xynn.z == 1) { if (liveNum < 2) curCell.xynn.w = 0; else if (liveNum < 4) curCell.xynn.w = curCell.xynn.z; else curCell.xynn.w = 0; } else if (liveNum == 3) { curCell.xynn.w = 1; } Cells[product] = curCell; } //当前状态变更 [numthreads(32, 32, 1)] void UpdateNext(uint3 id : SV_DispatchThreadID) { int product = id.x + id.y * BorderVec.y; Cells[product].xynn.z = Cells[product].xynn.w; }
将游戏的逻辑转移到Compute Shader中之后,我们在C#中只需要做两件事:初始化、以及每帧调用一次。
using System.Collections; using System.Collections.Generic; using UnityEngine; public struct GPUCell { public Vector4 xynn; public GPUCell(float x, float y, float z, float w) { xynn = new Vector4(x, y, z, w); } } public class SendTex : MonoBehaviour { public ComputeShader GoLComputeShader; public Texture InputTex; public Color AliveColor; public Color DeadColor; public Renderer Shower; [SerializeField] private RenderTexture GameTex; private ComputeBuffer CellBuffer; private bool needRendering = false; int kernelIdx; int updateIdx; #region Mono void OnGUI() { if (GUILayout.Button("开始生命游戏")) { Init(); needRendering = true; } } void Update () { if (!needRendering) return; //运算 GoLComputeShader.Dispatch(kernelIdx, Mathf.CeilToInt(InputTex.width / 32f), Mathf.CeilToInt(InputTex.height / 32f), 1); GoLComputeShader.Dispatch(updateIdx, Mathf.CeilToInt(InputTex.width / 32f), Mathf.CeilToInt(InputTex.height / 32f), 1); } #endregion #region Logic private void Init() { //找到核心地址 kernelIdx = GoLComputeShader.FindKernel("GameOfLifeUpdate"); updateIdx = GoLComputeShader.FindKernel("UpdateNext"); InitTexture(); InitColor(); InitBuffer(); Shower.material.mainTexture = GameTex; } private void InitColor() { GoLComputeShader.SetVector("AliveColor", AliveColor); GoLComputeShader.SetVector("DeadColor", DeadColor); } private void InitTexture() { //传入展示和逻辑用纹理 GameTex = new RenderTexture(InputTex.width, InputTex.height, 24); GameTex.enableRandomWrite = true; GameTex.filterMode = FilterMode.Point; GameTex.Create(); GoLComputeShader.SetTexture(kernelIdx, "GameTex", GameTex); //传入边界 GoLComputeShader.SetVector("BorderVec", new Vector4(0, InputTex.width, 0, InputTex.height)); } private void InitBuffer() { int count = InputTex.width * InputTex.height; CellBuffer = new ComputeBuffer(count, 16); GPUCell[] values = new GPUCell[count]; for (int y = 0 ; y < InputTex.height; y++) for (int x = 0; x < InputTex.width; x++) { Color c = ((Texture2D)InputTex).GetPixel(x, y); GPUCell cell = new GPUCell(x, y, c.a != 0 ? 1 : 0, c.a != 0 ? 1 : 0); values[x + y * InputTex.width] = cell; } //装填数据 CellBuffer.SetData(values); GoLComputeShader.SetBuffer(kernelIdx, "Cells", CellBuffer); GoLComputeShader.SetBuffer(updateIdx, "Cells", CellBuffer); } #endregion }
不得不提到之前走的一个弯路,那就是C#里的Dispatch所传入的XYZ值,是线程组的数量,Shader中的numthreads的XYZ值,是每组的线程数量。为了保证线程们能遍历到每个像素和数据,必须在C#里予以自适应。
关于线程和线程组更多的内容,请参考【3】。
通过转嫁计算任务,我们在面对8192*8192规模的图片时,亦能得到70帧的高效率运行——当然,除了最开始向GPU输出数据时的卡顿。

结语

本文尝试利用Compute Shader解决了生命游戏规模上升时带来的效率问题。除此之外,Compute Shader还有更多的应用,比如加速粒子计算等。
当然本文的可视化还略显粗糙,若想对游戏做更多风格客制化,例如显示时附带细线网格、细胞被展示为小球或立方体等,可以配合Geometry Shader,实现效果的同时,保证运算的高效率。
Github地址:https://github.com/noobdawn/GameOfLife-Unity-ComputeShader

参考文献

[1]https://tieba.baidu.com/p/4423464677?red_tag=1935055758
[2]http://www.emersonshaffer.com/blog/2016/5/11/unity3d-compute-shader-introduction-tutorial
[3]https://docs.microsoft.com/zh-cn/windows/desktop/direct3dhlsl/sm5-attributes-numthreads
N
Noobdawn
3
Comments