算法与计算机科学github.com
波函数坍缩算法
Show HN: Wave function collapse algorithm
2016 — 2021，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这个 GitHub 仓库展示并实现了 Wave Function Collapse（波函数坍缩）算法：从示例纹理或像素图学习局部相邻约束，再通过迭代坍缩生成风格一致、无缝且具有长程结构的图像。项目包含多种示例和扩展，后来常被用于游戏中的程序化纹理、关卡和体素场景生成。
为什么经久不衰：它把一个可直观可视化的约束求解过程变成生成复杂图案的工具，启发了大量程序化生成实践，今天看仍是理解 WFC 和关卡/纹理生成的好入口。
HN 评论精选
肯定长程有序与可视化，同时质疑它与早期基于块搜索的方法是否有本质区别，并建议测试噪声输入。
很棒的工作！它似乎完美地捕捉到了“长程有序”，这是此前很少有人能做到的！而且“坍缩”的可视化看起来非常有趣。但如果你仍然是在输入块分布上（均匀随机？）采样，你的算法在本质上真的与之前的搜索方法（例如 Efros 和 Leung）有质的不同吗？我还注意到你的输入纹理往往有清晰的边界（像素画中很常见）。如果输入含大量“噪声”，比如高清的岩石或云朵图像，结果会怎样会很有意思 ;) 虽然我仍然更喜欢搜索方法，因为它们容易实现（而且效果更好），但“深度”方法显然正在取得一些进展，比如 Deep Textures 以及结合 MRF 与 CNN 的图像合成工作。
fitzwatermellow查看英文原文
Great work! The fact that it captures "long-range order" seemingly perfectly is something not many have been able to do before! And the "collapse" visualization is great fun to watch. But is your algorithm really qualitatively all that different from previous search methods (e.g. Efros and Leung), if you are still (uniform random?) sampling over the input distribution of patches? I notice also your input textures tend to have sharp boundaries (as is common in pixel art). It would be interesting to see the results when the input has a lot of "noise", such as high def images of rocks or clouds ;) While I still prefer search methods because they are easy to implement (and give better results), "deep" methods are definitely gaining some ground: Deep Textures http://bethgelab.org/deeptextures/ Combining Markov Random Fields and Convolutional Neural Networks for Image Synthesis https://arxiv.org/abs/1601.04589
想反过来用算法从 3D 脑图像中分解和比较结构成分，用于病理研究。
太棒了，我很喜欢！和大多数机器学习/这些很酷的想法一样（我对它们的分类很模糊），我立刻想把它用于我们实验室的脑研究。我们有很多 3D 图像（很多 1028x1028 的 .tiff 拼接图，体素约 200nm×200nm×600nm），很想把这些图像反向喂进去。也就是说，我们有“远场”，想得到组成它的“元素”。比如有大量垂体数据，想比较垂体和海马体的“元素”。很多差异已知，但可能还有人类没看到的“其他东西”。这可能对疾病病理，比如路易体病前兆，很有用。
Balgair查看英文原文
Fantastic stuff. I love it! As with most meachine learning stuff and these very cool ideas (of which I am very hazy on, esp their categorizations) I immediately want to use it for our lab's brain work. We have a LOT of 3-D images (per voxel is ~200nmx200nmx~600nm for a lot of 1028x1028 .tiff images all stitched together) and would love to feed these images BACKWARDS into this. IE we have the 'far field', and we want the 'elements' that make it up. Say we have a large amount of data on the Pituitary gland, and we want to compare the 'elements' of the Pituitary to the 'elements' of the hippocampus. We know a lot of these differences, but there may be 'something else' in there that we humans are not seeing. This may be of great use to use for disease pathology like Lewy Body Disease precursors.
指出 WFC 本质是约束求解器，并分享用它生成迷你高尔夫关卡的经验。
我用这个算法生成迷你高尔夫球场。我用了这个仓库。这个算法实际上就是一个约束求解器。我很确定它和我大学时用 Prolog 写的数独求解器很像。它的名字和描述有点做作，可能因为学术上更流行。它就是个约束求解器。
nightowl_games查看英文原文
I used this algorithm to generate minigolf courses [1]. I used this repo [2]. The algorithm is literally just a constraint solver. I'm pretty sure it's pretty similar to the sudoku solver I wrote in prolog for a university course. It's kinda pretentiously named and described, probably because its more academic to do that. It's just a constraint solver. 1: https://twitter.com/00jknight/status/1249091532071645184 2: https://github.com/math-fehr/fast-wfc
实际关卡生成中难加约束且容易不可解，但 Bad North 证明特定游戏可用。
我玩过很多这个库 DeBroglie。很好玩，但我很难从中为关卡生成获得很多价值。你能得到很酷的图案，但关卡需要结构和意图才有意思。给算法加约束会变成大 O 噩梦，随着递归你经常得到不可解路径。Bad North 用得不错，所以取决于游戏，它可能是工具箱里很有用的工具。
hesdeadjim查看英文原文
I played around a lot with this library: https://github.com/BorisTheBrave/DeBroglie Fun stuff, but I struggled to get a lot of value out of using it for level gen. You get cool patterns, but levels need structure and intent to be interesting. Adding constraints to the algorithm becomes a big-oh nightmare and you end up with frequently unsolvable paths as the algorithm recurses. The game Bad North used it to good effect, so depending on the game it may be a very useful tool in the toolbelt. https://m.youtube.com/watch?v=0bcZb-SsnrA
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选