Unity使用波函数坍缩 (Wave Collapse Function)算法生成随机地图
在游戏领域和人工智能领域有一个随机生成地图用的比较多的算法叫做波函数坍缩 (Wave Collapse Function)算法，这个算法可以根据自己定制的规则生成随机地图。
根据波函数坍缩算法的源码 Wave Collapse Function C#版，我将源码修改适配到了Unity上使用。
这种随机生成地图或者说图片纹理，在做Roguelike游戏地图或者生成地板纹理横版2D游戏环境背景之类都十分好使。
源码地址：
C#版Wave Collapse Function (算法源码)
Unity适配版Wave Collapse Function (本文代码)
本文后面展示的代码其实就是 Unity适配版Wave Collapse Function (本文代码) 链接的代码。
有兴趣的话建议直接下载来在Unity打开看，因为其配置环境都在源码项目里，因为看这里展示的代码无法了解其项目纹理资源和XML配置文件。
运行生成的随机地图/纹理如图：
代码文件：
WFCMain.cs
Model.cs
OverlappingModel.cs
SimpleTiledModel.cs
Stuff.cs
详细：
WFCMain.cs
using System;
using System.Xml.Linq;
using UnityEngine;
namespace WFC
{
public class WFCMain : MonoBehaviour
{
public TextAsset XML;
private void Awake()
{
System.Random random = new System.Random();
XDocument xdoc = XDocument.Parse(XML.text);
int counter = 1;
foreach (XElement xelem in xdoc.Root.Elements("simpletiled", "overlapping"))
{
Model model;
string name = xelem.Get<string>("name");
string subName = string.Empty;
Debug.Log($"< {name}");
if (xelem.Name == "overlapping")
{
model = new OverlappingModel(
name,
xelem.Get("N", 2),//N每个overlapping类型的tile的像素大小，即宽高N*N。
xelem.Get("width", 48),//结果绘图的像素宽，下同理。
xelem.Get("height", 48),
xelem.Get("periodicInput", true),//从原料图片中取N*N tile大小时是否可以周期性获取。
xelem.Get("periodic", false),
xelem.Get("symmetry", 8),
xelem.Get("ground", 0)
);
}
else if (xelem.Name == "simpletiled")
{
subName = xelem.Get<string>("subset");//subset，结果绘图生成设置。
model = new SimpleTiledModel(
name,
subName,
xelem.Get("width", 10),
xelem.Get("height", 10),
xelem.Get("periodic", false),
xelem.Get("black", false)
);
}
else
{
continue;
}
for (int i = 0; i < xelem.Get("screenshots", 2); i++)
{
for (int k = 0; k < 10; k++)
{
Debug.Log("> ");
int seed = random.Next();
bool finished = model.Run(seed, xelem.Get("limit", 0));
if (finished)
{
Debug.Log("DONE");
Texture2D texture2D = model.Graphics();
Sprite sprite = Sprite.Create(texture2D, new Rect(0, 0, texture2D.width, texture2D.height), Vector2.zero);
GameObject go = new GameObject($"{name} {subName}");
SpriteRenderer sr = go.AddComponent<SpriteRenderer>();
sr.sprite = sprite;
break;
}
else Debug.Log("CONTRADICTION");
}
}
counter++;
}
}
}
}
Model.cs
using System;
namespace WFC
{
abstract class Model
{
protected bool[][] wave;//构成效果图的每个图块元素的tile的是否被选中来绘图的bool集合。
protected int[][][] propagator;//计数，记录每个wave第一维元素中的每个 tile 4个方向的可匹配相邻的 tile 数量集合，它的值来自读取xml的配置，所以值是固定不变的。
int[][][] compatible;//计数，记录每个wave第一维元素中的每个 tile 的各4个方向的T集合对自己的匹配成功次数而计数，并随着坍塌传递的进行计数递减，所以值是递减变化的。
protected int[] observed;//坍塌运算完成后被观察的结果，保存每个wave第一维元素中被选中的tile索引用于绘图。
(int, int)[] stack;
int stacksize;
protected Random random;
protected int FMX, FMY, T;//T==action.count
protected bool periodic;
protected double[] weights;
double[] weightLogWeights;
int[] sumsOfOnes;
double sumOfWeights, sumOfWeightLogWeights, startingEntropy;
double[] sumsOfWeights, sumsOfWeightLogWeights, entropies;
protected Model(int width, int height)
{
FMX = width;
FMY = height;
}
void Init()
{
wave = new bool[FMX * FMY][];
compatible = new int[wave.Length][][];
for (int i = 0; i < wave.Length; i++)
{
wave[i] = new bool[T];
compatible[i] = new int[T][];
for (int t = 0; t < T; t++) {
compatible[i][t] = new int[4];
}
}
weightLogWeights = new double[T];
sumOfWeights = 0;
sumOfWeightLogWeights = 0;
for (int t = 0; t < T; t++)
{
weightLogWeights[t] = weights[t] * Math.Log(weights[t]);
sumOfWeights += weights[t];
sumOfWeightLogWeights += weightLogWeights[t];
}
//以下公式来自熵值法公式，熵值法公式的由来Google一。
startingEntropy = Math.Log(sumOfWeights) - sumOfWeightLogWeights / sumOfWeights;
sumsOfOnes = new int[FMX * FMY];
sumsOfWeights = new double[FMX * FMY];
sumsOfWeightLogWeights = new double[FMX * FMY];
entropies = new double[FMX * FMY];
stack = new(int, int)[wave.Length * T];
stacksize = 0;
}
bool? Observe()
{
double min = 1E+3;
int argmin = -1;
for (int i = 0; i < wave.Length; i++)
{
if (OnBoundary(i % FMX, i / FMX)) continue;
int amount = sumsOfOnes[i];
if (amount == 0) return false;//如果第i个格子所有的tile都被ban了，那么失败
double entropy = entropies[i];
if (amount > 1 && entropy <= min)//如果wave的第i个元素中候选的tile数量>1,且熵值小于限定值
{
double noise = 1E-6 * random.NextDouble();
if (entropy + noise < min)//找出熵值+扰动(noise)后最小的tile的索引argmin
{
min = entropy + noise;
argmin = i;
}
}
}//根据以上for循环代码，熵值就是用于寻找出wave中第一维元素中最小的argmin索引作为首个目标进行坍塌
if (argmin == -1) //argmin == -1 那么所有wave的第一维元素的tile被确定了下来，或者进入矛无法在进行坍塌运算。
{
observed = new int[FMX * FMY];
for (int i = 0; i < wave.Length; i++) for (int t = 0; t < T; t++)
{
if (wave[i][t])
{
observed[i] = t;//observed 将确定下来的tile的索引记录下来，用于绘图。
break;
}
}
return true;//返回true开始进行绘图。
}
//一下则是所有wave的第一维元素的tile没有被确定了下来，将进行坍塌运算
double[] distribution = new double[T];
for (int t = 0; t < T; t++)
{
distribution[t] = wave[argmin][t] ? weights[t] : 0;
}
int r = distribution.Random(random.NextDouble());//r是随机一个wave[argmin]中为true的tile的索引，随机中的概率跟其xml配置的weight成正比。
bool[] w = wave[argmin];
for (int t = 0; t < T; t++)
{
if (w[t] != (t == r))//只有w[t]==true,并且t==r时被保留，其它都被ban，而根据以上r的生成，w[t]为false时r!=t, 简写成这种判断形式。
{
Ban(argmin, t);
}
}
return null;
}
//
protected void Propagate()
{
while (stacksize > 0)
{
var e1 = stack[stacksize - 1];
stacksize--;
int i1 = e1.Item1;
int x1 = i1 % FMX, y1 = i1 / FMX;
for (int d = 0; d < 4; d++)
{
int dx = DX[d], dy = DY[d];//获取上下左右个方向的tile
int x2 = x1 + dx, y2 = y1 + dy;
if (OnBoundary(x2, y2)) continue;
if (x2 < 0) {
x2 += FMX;
}else if (x2 >= FMX) {
x2 -= FMX;
}
if (y2 < 0) {
y2 += FMY;
}else if (y2 >= FMY) {
y2 -= FMY;
}
int i2 = x2 + y2 * FMX;
int[] p = propagator[d][e1.Item2];
int[][] compat = compatible[i2];//compatible[i][t][d]
for (int l = 0; l < p.Length; l++)
{
int t2 = p[l];//那么t2就是当前被ban的t(e1.Item2的四个)的相邻匹配的tile。
int[] comp = compat[t2];//comp是t2在d方向上的匹配数量，因为t要被ban掉，所以d方向要减去1，如下。
comp[d]--;
if (comp[d] == 0)//如果d方向已经没有适合t2的tile，==0，那么t2将要被ban掉，如此循环。
{
Ban(i2, t2);
}
}
}
}
}
public bool Run(int seed, int limit)
{
if (wave == null) Init();
Clear();
random = new Random(seed);
for (int l = 0; l < limit || limit == 0; l++)
{
//为默认值limit==0时，进入Observe()和Propagate()循环。
//Observe()通过权重算熵值观察，选出要被ban的tile进行ban。
//Propagate()对被ban的tile的周围4个方向tile，对引用被ban的t的t2的compatible第i/4个方向进行递减1，如t2 compatible第i/4个方向为0那么ban t2如此循环。
bool? result = Observe();
if (result != null)
{
return (bool)result;
}
Propagate();
}
return true;
}
/// <summary>
/// 将wave[i][t]淘汰，并放入stack，将自己被淘汰引起的数据变化在Propagate()函数中传递出去。
/// </summary>
protected void Ban(int i, int t)
{
wave[i][t] = false;
int[] comp = compatible[i][t];
for (int d = 0; d < 4; d++)
{
comp[d] = 0;//如果我自己被ban了，那么自己的四个方向的能适合我的tile计数强制设为0，将自己报废。
}
stack[stacksize] = (i, t);
stacksize++;
sumsOfOnes[i] -= 1;//第i个格子为true的T总数，即没被坍塌淘汰的数量
sumsOfWeights[i] -= weights[t];
sumsOfWeightLogWeights[i] -= weightLogWeights[t];
double sum = sumsOfWeights[i];
entropies[i] = Math.Log(sum) - sumsOfWeightLogWeights[i] / sum;
}
protected virtual void Clear()
{
for (int i = 0; i < wave.Length; i++)
{
for (int t = 0; t < T; t++)
{
wave[i][t] = true;
for (int d = 0; d < 4; d++)
{
//propagator 记录每个 T 4个方向的可匹配相邻的 T 集合
//所以，compatible 为记录第i个T的各4个方向的T集合对自己的匹配成功次数
compatible[i][t][d] = propagator[opposite[d]][t].Length;
}
}
sumsOfOnes[i] = weights.Length;
sumsOfWeights[i] = sumOfWeights;
sumsOfWeightLogWeights[i] = sumOfWeightLogWeights;
entropies[i] = startingEntropy;
}
}
protected abstract bool OnBoundary(int x, int y);
public abstract UnityEngine.Texture2D Graphics();
protected static int[] DX = { -1, 0, 1, 0 };
protected static int[] DY = { 0, 1, 0, -1 };
static int[] opposite = { 2, 3, 0, 1 };//获取对立面
}
}
OverlappingModel.cs
sing System;
using System.Collections.Generic;
using UnityEngine;
namespace WFC
{
class OverlappingModel : Model
{
int N;
byte[][] patterns;
List<Color> colors;
int ground;
public OverlappingModel(string name, int N, int width, int height, bool periodicInput, bool periodicOutput, int symmetry, int ground)
: base(width, height)
{
this.N = N;
periodic = periodicOutput;
string resPath = $"samples/{name}";
Texture2D texture = Resources.Load<Texture2D>(resPath);
int SMX = texture.width;
int SMY = texture.height;
byte[,] sample = new byte[SMX, SMY];
colors = new List<Color>();
for (int y = 0; y < SMY; y++) for (int x = 0; x < SMX; x++)
{
Color color = texture.GetPixel(x, y);
int i = 0;
foreach (var c in colors)
{
if (c == color)//为减少colors长度的操作
{
break;
}
i++;
}
if (i == colors.Count)//i==colors.Count证明遍历完colors还没有color，所以add
{
colors.Add(color);
}
sample[x, y] = (byte)i;//此xy记录color在colors位置
}
int C = colors.Count;
long W = Stuff.Power(C, N * N);
/// <summary>
/// 根据遍历 byte[N*N] 提供的 x，y 参数代入 f 从中获取 byte 填充。
/// </summary>
/// <returns> N*N长度的byte[] </returns>
/// <param name="f"> byte取样函数 </param>
byte[] pattern(Func<int, int, byte> f)
{
byte[] result = new byte[N * N];
for (int y = 0; y < N; y++) for (int x = 0; x < N; x++)
{
result[x + y * N] = f(x, y);
}
return result;
};
/// <summary>
/// 以xy为起点取长宽为N*N的色块，以xy为起点，dx，dy为宽高。
/// </summary>
byte[] patternFromSample(int x, int y) => pattern((dx, dy) => sample[(x + dx) % SMX, (y + dy) % SMY]);
byte[] rotate(byte[] p) => pattern((x, y) => p[N - 1 - y + x * N]);//向右转
byte[] reflect(byte[] p) => pattern((x, y) => p[N - 1 - x + y * N]);//x左右翻转
long index(byte[] p)
{
long result = 0;
long power = 1;
for (int i = 0; i < p.Length; i++)
{
result += p[p.Length - 1 - i] * power;//乘以power次方，防止index有冲突。
power *= C;
}
return result;
};
byte[] patternFromIndex(long ind)
{
long residue = ind;
long power = W;
byte[] result = new byte[N * N];
for (int i = 0; i < result.Length; i++)
{
power /= C;
int count = 0;
while (residue >= power)
{
residue -= power;
count++;
}
result[i] = (byte)count;
}
return result;
};
Dictionary<long, int> weights = new Dictionary<long, int>();
List<long> ordering = new List<long>();
//periodicInput含义，如果periodicInput周期性输入为true，那么以xy为起点的N*N色块取值到xy最，到尽头可以从原料图片colors起始（0，0）取。
//反之，不是周期性，那么xy取最大值预留最大为max(xy)-N，因为非周期性N*N色块的xy>SMYSMX时不能从原料图片colors起始（0，0）取。
for (int y = 0; y < (periodicInput ? SMY : SMY - N + 1); y++) for (int x = 0; x < (periodicInput ? SMX : SMX - N + 1); x++)
{
//ps:8个N*N大小的索引自sample色块
byte[][] ps = new byte[8][];
//逐渐顺时针旋转90度的四个方向 0，2，4，6
//逐渐对应的反射四个方向 1，3，5，7
ps[0] = patternFromSample(x, y);
ps[1] = reflect(ps[0]);
ps[2] = rotate(ps[0]);
ps[3] = reflect(ps[2]);
ps[4] = rotate(ps[2]);
ps[5] = reflect(ps[4]);
ps[6] = rotate(ps[4]);
ps[7] = reflect(ps[6]);
//symmetry默认值8
for (int k = 0; k < symmetry; k++)//对称
{
long ind = index(ps[k]);
if (weights.ContainsKey(ind))
{
weights[ind]++;
}
else
{
weights.Add(ind, 1);
ordering.Add(ind);
}
}
}
T = weights.Count;
this.ground = (ground + T) % T;
patterns = new byte[T][];
base.weights = new double[T];
int counter = 0;
foreach (long w in ordering)
{
patterns[counter] = patternFromIndex(w);
base.weights[counter] = weights[w];
counter++;
}
/// <summary>
/// dx，dy当前p1周围其他色块坐标，判断p1和p2色块交界处像素是否一致
/// </summary>
bool agrees(byte[] p1, byte[] p2, int dx, int dy)
{
int xmin = dx < 0 ? 0 : dx;
int xmax = dx < 0 ? dx + N : N;
int ymin = dy < 0 ? 0 : dy;
int ymax = dy < 0 ? dy + N : N;
for (int y = ymin; y < ymax; y++) for (int x = xmin; x < xmax; x++)
{
if (p1[x + N * y] != p2[x - dx + N * (y - dy)])
{
return false;
}
}
return true;
};
propagator = new int[4][][];
for (int d = 0; d < 4; d++)
{
propagator[d] = new int[T][];
for (int t = 0; t < T; t++)
{
List<int> list = new List<int>();
for (int t2 = 0; t2 < T; t2++)
{
if (agrees(patterns[t], patterns[t2], DX[d], DY[d]))//对d(4)个方向进行匹配，如果相邻tile的边边color一(agrees)那么说明t2添加进可匹配集合。
{
list.Add(t2);
}
}
//propagator记录T的4个方向相邻匹配的tile色块集合。
propagator[d][t] = new int[list.Count];
for (int c = 0; c < list.Count; c++)
{
propagator[d][t][c] = list[c];
}
}
}
}
//periodic == periodicOuput
protected override bool OnBoundary(int x, int y) => !periodic && (x + N > FMX || y + N > FMY || x < 0 || y < 0);
public override Texture2D Graphics()
{
Texture2D result = new Texture2D(FMX, FMY);
int[] bitmapData = new int[result.height * result.width];
if (observed != null)//observed是坍塌运算的结果。
{
for (int y = 0; y < FMY; y++)
{
int dy = y < FMY - N + 1 ? 0 : N - 1;
for (int x = 0; x < FMX; x++)
{
int dx = x < FMX - N + 1 ? 0 : N - 1;
int obIndex = observed[x - dx + (y - dy) * FMX];
Color c = colors[patterns[obIndex][dx + dy * N]];
result.SetPixel(x, y, c);
}
}
}
else
{
for (int i = 0; i < wave.Length; i++)
{
float r = 0, g = 0, b = 0;
int x = i % FMX, y = i / FMX;
for (int dy = 0; dy < N; dy++) for (int dx = 0; dx < N; dx++)
{
int sx = x - dx;
if (sx < 0) sx += FMX;
int sy = y - dy;
if (sy < 0) sy += FMY;
int s = sx + sy * FMX;
if (OnBoundary(sx, sy)) continue;
for (int t = 0; t < T; t++) if (wave[s][t])
{
Color color = colors[patterns[t][dx + dy * N]];
r += color.r;
g += color.g;
b += color.b;
}
}
result.SetPixel(x, y, new Color(r, g, b));
}
}
result.Apply();
return result;
}
protected override void Clear()
{
base.Clear();
if (ground != 0)
{
for (int x = 0; x < FMX; x++)
{
for (int t = 0; t < T; t++)
{
if (t != ground)
{
Ban(x + (FMY - 1) * FMX, t);
}
}
for (int y = 0; y < FMY - 1; y++)
{
Ban(x + y * FMX, ground);
}
}
Propagate();
}
}
}
}
SimpleTiledModel.cs
using System;
using System.Linq;
using System.Xml.Linq;
using System.Collections.Generic;
using UnityEngine;
namespace WFC
{
class SimpleTiledModel : Model
{
List<Texture2D> tiles;
List<string> tilenames;
int tilesize;
bool black;
private string graphicsName = String.Empty;
public SimpleTiledModel(string name, string subsetName, int width, int height, bool periodic, bool black) : base(width, height)
{
this.graphicsName = $"{name} {subsetName}";
this.periodic = periodic;
this.black = black;
string dataXmlpath = $"{Application.dataPath}/Resources/samples/{name}/data.xml";
XElement xroot = XDocument.Load(dataXmlpath).Root;
tilesize = xroot.Get("size", 16);
bool unique = xroot.Get("unique", false);
List<string> subset = null;
if (subsetName != default(string))
{
XElement xsubset = xroot.Element("subsets").Elements("subset").FirstOrDefault(x => x.Get<string>("name") == subsetName);
if (xsubset == null){
Debug.LogError($"ERROR: subset {subsetName} is not found");
}else {
subset = xsubset.Elements("tile").Select(x => x.Get<string>("name")).ToList();
}
}
tiles = new List<Texture2D>();
tilenames = new List<string>();
var tempStationary = new List<double>();
List<int[]> action = new List<int[]>();//第一维记录xml 配置上的tilename(图片名称)顺时针旋转90度cardinality次后在变量tile(List<Texture2D>)上的索引位、第二维记录该旋转后的tile 8个方向后的索引。
Dictionary<string, int> firstOccurrence = new Dictionary<string, int>();
foreach (XElement xtile in xroot.Element("tiles").Elements("tile"))
{
string tilename = xtile.Get<string>("name");
if (subset != null && !subset.Contains(tilename)) continue;
Func<int, int> a, b;//对tile获取a正面，b反面
int cardinality;
char sym = xtile.Get("symmetry", 'X');
if (sym == 'L')
{
//a 0123 对应 b 1032
cardinality = 4;
a = i => (i + 1) % 4; //a正面，“L”形原材料图片经翻转后有4(cardinality=4)种不同情形图片，后面代码说明i是第cardinality次。
b = i => i % 2 == 0 ? i + 1 : i - 1;//b对称面，是相对a面的二次操作获取结果。
}
else if (sym == 'T')
{
//a 0123 对应 b 0321
cardinality = 4;
a = i => (i + 1) % 4;
b = i => i % 2 == 0 ? i : 4 - i;
}
else if (sym == 'I')
{
cardinality = 2;
a = i => 1 - i;//a正面，“I”形对称图左右或上下对称，可用同一张，所以有2(cardinality=2)种不同情形。
b = i => i;
}
else if (sym == '\\')
{
cardinality = 2;
a = i => 1 - i;
b = i => 1 - i;
}
else
{
cardinality = 1;
a = i => i;
b = i => i;
}
T = action.Count;//action依赖firstOccurrence用tilename为key记录tile在action中的起始第一个索引位置。
firstOccurrence.Add(tilename, T);//记录此tileName的起始index, kv(tilename, t)。
int[][] map = new int[cardinality][];
for (int t = 0; t < cardinality; t++)
{
map[t] = new int[8];//map记录每次翻转tile后的每个tile的八个方向所使用的tile在action中的索引。
map[t][0] = t;//map[t][0]是翻转后非对称的衍生tile
map[t][1] = a(t);//根据上个if代码块，对称性定义的a获取第t次翻转用的index。
map[t][2] = a(a(t));
map[t][3] = a(a(a(t)));
map[t][4] = b(t);
map[t][5] = b(a(t));
map[t][6] = b(a(a(t)));
map[t][7] = b(a(a(a(t))));
for (int s = 0; s < 8; s++)
{
map[t][s] += T;//索引递增叠加。
}
action.Add(map[t]);//所以action长度为 配置上的tiles的各自的tile的cardinality*8再累加个。
}
if (unique)
{
for (int t = 0; t < cardinality; t++)
{
string imagePath = $"samples/{name}/{tilename} {t}";
Texture2D tile = Resources.Load<Texture2D>(imagePath);
if(tile == null){
Debug.LogError($"load null {imagePath}");
}
tiles.Add(tile);
tilenames.Add($"{tilename} {t}");
}
}
else
{
string imagePath = $"samples/{name}/{tilename}";
Texture2D tile = Resources.Load<Texture2D>(imagePath);
tiles.Add(tile);
tilenames.Add($"{tilename} 0");
for (int t = 1; t < cardinality; t++)//根据cardinality次数将tile顺时针旋转。
{
tiles.Add(Rotate(tiles[T + t - 1]));
string newTilename = $"{tilename} {t}";
tilenames.Add(newTilename);
}
}
for (int t = 0; t < cardinality; t++) tempStationary.Add(xtile.Get("weight", 1.0f));
}
T = action.Count;
weights = tempStationary.ToArray();
//propagator，从tempPropagator中提取值为true的T*T，即相邻的tile
//propagator 记录每个 T 4个方向的可匹配相邻的 T 集合
propagator = new int[4][][];
var tempPropagator = new bool[4][][];//tempPropagator罗列出每个格子4个方向所能放的所有可(4*T*T)， 能够相邻匹配的action的index
for (int d = 0; d < 4; d++)
{
tempPropagator[d] = new bool[T][];
propagator[d] = new int[T][];
for (int t = 0; t < T; t++)
{
tempPropagator[d][t] = new bool[T];
}
}
foreach (XElement xneighbor in xroot.Element("neighbors").Elements("neighbor"))
{
string[] left = xneighbor.Get<string>("left").Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
string[] right = xneighbor.Get<string>("right").Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
if (subset != null && (!subset.Contains(left[0]) || !subset.Contains(right[0]))) continue;
//action的坐标索引依赖firstOccurrence
int firstLeft = firstOccurrence[left[0]];
int leftIndex = left.Length == 1 ? 0 : int.Parse(left[1]);
int firstRight = firstOccurrence[right[0]];
int rightIndex = right.Length == 1 ? 0 : int.Parse(right[1]);
//根据neighbors从tempPropagator中获取左右匹配的tile的配对，设置为true，以便传给propagator
int L = action[firstLeft][leftIndex];
int D = action[L][1];
int R = action[firstRight][rightIndex];
int U = action[R][1];
tempPropagator[0][R][L] = true;
tempPropagator[0][action[R][6]][action[L][6]] = true;//方向0对应了翻转后的方向6，下同理
tempPropagator[0][action[L][4]][action[R][4]] = true;
tempPropagator[0][action[L][2]][action[R][2]] = true;
tempPropagator[1][U][D] = true;
tempPropagator[1][action[D][6]][action[U][6]] = true;
tempPropagator[1][action[U][4]][action[D][4]] = true;
tempPropagator[1][action[D][2]][action[U][2]] = true;
}
//左右方向互换
for (int t2 = 0; t2 < T; t2++) for (int t1 = 0; t1 < T; t1++)
{
tempPropagator[2][t2][t1] = tempPropagator[0][t1][t2];
tempPropagator[3][t2][t1] = tempPropagator[1][t1][t2];
}
List<int>[][] sparsePropagator = new List<int>[4][];
for (int d = 0; d < 4; d++)
{
sparsePropagator[d] = new List<int>[T];
for (int t = 0; t < T; t++)
{
sparsePropagator[d][t] = new List<int>();
}
}
for (int d = 0; d < 4; d++) for (int t1 = 0; t1 < T; t1++)
{
List<int> sp = sparsePropagator[d][t1];
bool[] tp = tempPropagator[d][t1];
for (int t2 = 0; t2 < T; t2++)
{
if (tp[t2])
sp.Add(t2);
}
int ST = sp.Count;
propagator[d][t1] = new int[ST];
for (int st = 0; st < ST; st++) {
propagator[d][t1][st] = sp[st]; //propagator记录每个tile4个方向各自所适配的tile集合。
}
}
}
/// <summary>
/// 将 texture 复制一份，并向右旋转90度
/// </summary>
/// <returns>返回复制并旋转后texture</returns>
private Texture2D Rotate(Texture2D texture)
{
Texture2D result = new Texture2D(texture.width, texture.height);
for (int x = 0; x < texture.width; x++) for (int y = 0; y < texture.height; y++)
{
int rx = y;
int ry = texture.height - x - 1;
result.SetPixel(x, y, texture.GetPixel(rx, ry));
}
result.Apply();
return result;
}
protected override bool OnBoundary(int x, int y) => !periodic && (x < 0 || y < 0 || x >= FMX || y >= FMY);
public override Texture2D Graphics()
{
Texture2D result = new Texture2D(FMX * tilesize, FMY * tilesize);
if (observed != null)
{
//observed是已经完成坍塌，确定了绘图用的tile的集合。
for (int x = 0; x < FMX; x++) for (int y = 0; y < FMY; y++)
{
int index = observed[x + y * FMX];
Texture2D tile = tiles[index];
for (int x2 = 0; x2 < tile.width; x2++)
for (int y2 = 0; y2 < tile.height; y2++){
int px = x * tilesize + x2;
int py = (tilesize - 1 - y - tile.height) * tilesize + y2;
result.SetPixel(px, py, tile.GetPixel(x2, y2));
}
}
}
else
{
int tileheight = tiles[0].height;
//如果坍塌函数失败不能再进行下去，那么绘图单位tile的色值是对所有有可能的tile的颜色进行混合。
for (int x = 0; x < FMX; x++) for (int y = 0; y < FMY; y++)
{
bool[] a = wave[x + y * FMX];
int amount = (from b in a where b select 1).Sum();
double lambda = 1.0 / (from t in Enumerable.Range(0, T) where a[t] select weights[t]).Sum();
for (int yt = 0; yt < tilesize; yt++) for (int xt = 0; xt < tilesize; xt++)
{
int px = x * tilesize + xt;
int py = (tilesize - 1 - y - tileheight) * tilesize + yt;
if (black && amount == T) {
result.SetPixel(px, py, Color.clear);
}else{
double r = 0, g = 0, b = 0;
for (int t = 0; t < T; t++)
{
if (a[t])
{
Texture2D texture = tiles[t];
Color c = texture.GetPixel(xt, yt);
r += (double)c.r * weights[t] * lambda;
g += (double)c.g * weights[t] * lambda;
b += (double)c.b * weights[t] * lambda;
}
result.SetPixel(px, py, new Color((float)r, (float)g, (float)b));
}
}
}
}
}
result.Apply();
return result;
}
public string TextOutput()
{
var result = new System.Text.StringBuilder();
for (int y = 0; y < FMY; y++)
{
for (int x = 0; x < FMX; x++) result.Append($"{tilenames[observed[x + y * FMX]]}, ");
result.Append(Environment.NewLine);
}
return result.ToString();
}
}
}
Stuff.cs
using System.Linq;
using System.Xml.Linq;
using System.ComponentModel;
using System.Collections.Generic;
namespace WFC
{
static class Stuff
{
/// <summary>
/// 在集合a中，由随机数r根据a的每个元素的数值大小正比地获取a的某个元素索引
/// </summary>
/// <returns>集合a的某个元素索引值</returns>
public static int Random(this double[] a, double r)
{
double sum = a.Sum();
for (int j = 0; j < a.Length; j++)
{
a[j] /= sum;
}
int i = 0;
double x = 0;
while (i < a.Length)
{
x += a[i];
if (r <= x)
{
return i;
}
i++;
}
return 0;
}
/// <summary>
/// 求a的n次方
/// </summary>
public static long Power(int a, int n)
{
long product = 1;
for (int i = 0; i < n; i++) product *= a;
return product;
}
public static T Get<T>(this XElement xelem, string attribute, T defaultT = default(T))
{
XAttribute a = xelem.Attribute(attribute);
return a == null ? defaultT : (T)TypeDescriptor.GetConverter(typeof(T)).ConvertFromInvariantString(a.Value);
}
public static IEnumerable<XElement> Elements(this XElement x, params string[] names) => x.Elements().Where(xelem => names.Any(s => s == xelem.Name));
}
}