CAM6
WaveFunctionCollapse
CAM6 | WaveFunctionCollapse | |
---|---|---|
6 | 99 | |
32 | 22,745 | |
- | - | |
2.1 | 4.8 | |
9 months ago | 5 days ago | |
JavaScript | C# | |
Apache License 2.0 | GNU General Public License v3.0 or later |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
CAM6
-
Programming the CAM-6 Cellular Automata Machine Hardware in Forth (CAM6 Simulator demo)
Github Repo: https://github.com/SimHacker/CAM6/
-
Ask HN: What weird technical scene are you fond/part of?
https://www.youtube.com
I hate it when a program I wrote mocks me. In Lex Fridman's interview of Steven Wolfram, he demonstrates the machine learning functions in Mathematica by taking a photo of himself, which identifies him as a .... (I won't give it away):
https://www.youtube.com/watch?v=ez773teNFYA&t=2h20m05s
Here's a video I recently recorded of the CAM-6 simulator I implemented decades ago, and rewrote in JavaScript a few years ago.
https://www.youtube.com/watch?v=LyLMHxRNuck
I recorded that demo to show to Norman Margolus, who co-wrote the book and wrote the CAM6 PC Forth code and many rules, so it's pretty long and technical and starts out showing lots of code, but I'm sure you'll totally get and appreciate it. I linked to a pdf copy of the book in the comments, as well as the source code and playable app.
Demo of Don Hopkins' CAM6 Cellular Automata Machine simulator.
Live App: https://donhopkins.com/home/CAM6
Github Repo: https://github.com/SimHacker/CAM6/
Javacript Source Code: https://github.com/SimHacker/CAM6/blob/master/javascript/CAM...
PDF of CAM6 Book: https://donhopkins.com/home/cam-book.pdf
Comments from the code:
// This code originally started life as a CAM6 simulator written in C
-
Theory of Self Reproducing Automata [pdf]
https://news.ycombinator.com/item?id=22738268
DonHopkins on March 31, 2020 | parent | context | favorite | on: Von Neumann Universal Constructor
Here's some stuff about that I posted in an earlier discussion, and transcribed from his book, "Theory of Self-Reproducing Automata".
His concept of self-reproducing mutating probabilistic quantum mechanical machine evolution is quite fascinating and terrifying at the same time (or outside of time), potentially much more powerful and dangerous than mere physical nanotechnology "gray goo" and universe-infesting self replicating von Neumann probes:
Can Programming Be Liberated from the von Neumann Style? (1977) [pdf] (thocp.net)
https://news.ycombinator.com/item?id=21855249
https://news.ycombinator.com/item?id=21858465
John von Neuman's 29 state cellular automata machine is (ironically) a classical decidedly "non von Neumann architecture".
https://en.wikipedia.org/wiki/Von_Neumann_cellular_automaton
He wrote the book on "Theory of Self-Reproducing Automata":
https://archive.org/details/theoryofselfrepr00vonn_0
He designed a 29 state cellular automata architecture to implement a universal constructor that could reproduce itself (which he worked out on paper, amazingly):
https://en.wikipedia.org/wiki/Von_Neumann_universal_construc...
He actually philosophized about three different kinds of universal constructors at different levels of reality:
First, the purely deterministic and relatively harmless mathematical kind referenced above, an idealized abstract 29 state cellular automata, which could reproduce itself with a Universal Constructor, but was quite brittle, synchronous, and intolerant of errors. These have been digitally implemented in the real world on modern computing machinery, and they make great virtual pets, kind of like digital tribbles, but not as cute and fuzzy.
https://github.com/SimHacker/CAM6/blob/master/javascript/CAM...
Second, the physical mechanical and potentially dangerous kind, which is robust and error tolerant enough to work in the real world (given enough resources), and is now a popular theme in sci-fi: the self reproducing robot swarms called "Von Neumann Probes" on the astronomical scale, or "Gray Goo" on the nanotech scale.
https://en.wikipedia.org/wiki/Self-replicating_spacecraft#Vo...
https://grey-goo.fandom.com/wiki/Von_Neumann_probe
>The von Neumann probe, nicknamed the Goo, was a self-replicating nanomass capable of traversing through keyholes, which are wormholes in space. The probe was named after Hungarian-American scientist John von Neumann, who popularized the idea of self-replicating machines.
Third, the probabilistic quantum mechanical kind, which could mutate and model evolutionary processes, and rip holes in the space-time continuum, which he unfortunately (or fortunately, the the sake of humanity) didn't have time to fully explore before his tragic death.
p. 99 of "Theory of Self-Reproducing Automata":
>Von Neumann had been interested in the applications of probability theory throughout his career; his work on the foundations of quantum mechanics and his theory of games are examples. When he became interested in automata, it was natural for him to apply probability theory here also. The Third Lecture of Part I of the present work is devoted to this subject. His "Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components" is the first work on probabilistic automata, that is, automata in which the transitions between states are probabilistic rather than deterministic. Whenever he discussed self-reproduction, he mentioned mutations, which are random changes of elements (cf. p. 86 above and Sec. 1.7.4.2 below). In Section 1.1.2.1 above and Section 1.8 below he posed the problems of modeling evolutionary processes in the framework of automata theory, of quantizing natural selection, and of explaining how highly efficient, complex, powerful automata can evolve from inefficient, simple, weak automata. A complete solution to these problems would give us a probabilistic model of self-reproduction and evolution. [9]
[9] For some related work, see J. H. Holland, "Outline for a Logical Theory of Adaptive Systems", and "Concerning Efficient Adaptive Systems".
https://www.deepdyve.com/lp/association-for-computing-machin...
https://deepblue.lib.umich.edu/bitstream/handle/2027.42/5578...
https://www.worldscientific.com/worldscibooks/10.1142/10841
Ericson2314 3 months ago [-]
> Although I refer to conventional languages as "von Neumann languages" to take note of their origin and style, I do not, of course, blame the great mathematician for their complexity. In fact, some might say that I bear some responsibility for that problem.
From the paper. Whew.
-
Show HN: Making a Falling Sand Simulator
Typically a cellular automata simulation will have some edge condition like wrapping or mirroring an adjacent cell.
A nice optimization trick is to make the cell buffers 2 cells wider and taller (or two times whatever the neighborhood radius is), and then before each generation you update the "gutter" by copying just the wrapped (or mirrored) pixels. Then your run the rule on the inset rectangle, and the code (in the inner loop) doesn't have to do bounds checking, and can assume there's a valid cell to read in all directions. That saves a hell of a lot of tests and branches in the inner loop.
Also, the Margolus neighborhood can be defined in terms of the Moore neighborhood + vertical phase (even/odd row) + horizontal phase (even/odd column) + time phase (even/odd time). Then you can tell if you're at an even or odd step, and which of the four squares of the grid you're in, to know what to do.
That's how the CAM6 worked in hardware: it used the x/y/time phases as additional bits of the index table lookup.
https://github.com/SimHacker/CAM6/blob/master/javascript/CAM...
Here's how my CAM6 emulator computes the Margolus lookup table index, based on the 9 Moore neighbors + phaseTime, phaseX, and phaseY:
function getTableIndexUnrotated(
- Ask HN: What book changed your life?
-
It's always been you, Canvas2D
Oh, nicely done! Trying to code up cellular automata simulations are pretty much guaranteed to push my brains through my nostrils - I've never progressed far beyond classic Conway. Your CAM6 library[1] may be about to steal my weekend from me!
[1] - https://github.com/SimHacker/CAM6
WaveFunctionCollapse
- I use Wave Function Collapse to create levels for my game (2022) [video]
-
It's Okay to Make Something Nobody Wants
Thank you! And yes, I agree. I was looking at uh https://github.com/mxgmn/WaveFunctionCollapse and wondering if that were applicable here :)
Have a good day!
- The Wavefunction Collapse Algorithm
-
Kullback–Leibler Divergence
Intuitively, it measures the difference between two probability distributions. It's not symmetric, so it's not quite that, but in my opinion, it's good intuition.
As motivation, say you're an internet provider, providing internet service to a business. You naturally want to save money, so you perhaps want to compress packets before they go over the wire. Let's say the business you're providing service to also compresses their data, but they've made a mistake and do it inefficiently.
Let's say the business has, incorrectly, determined the probability distribution for their data to be $q(x)$. That is, they assign probability of seeing symbol $x$ to be $q(x)$. Let's say you've determined the "true" distribution to be $p(x)$. The entropy, or number of bits, they expect to transmit per packet/symbol will be $-\sum p(x) lg(q(x))$. Meaning, they'll compress their stream under the assumption that the distribution is $q(x)$ but the actually probability of seeing a packet, $x$, is $p(x)$, which is why the term $p(x) lg(q(x))$ shows up.
The number of bits you're transmitting is just $-\sum p(x) lg(p(x))$. Now we ask, how many bits, per packet, is the savings of your method over the businesses? This is $-\sum p(x) lg(q(x)/p(x))$, which is exactly the Kullback-Leibler divergence (maybe up to a sign difference).
In other words, given a "guess" at a distribution and the "true" distribution, how bad is it between them? This is the Kullback-Leibler distribution and why it shows up (I believe) in machine learning and fitness functions.
As a more concrete example, I just ran across a paper talking [0] about using WFC [1] to asses how well it, and other algorithms, do when trying to create generative "super mario brothers" like levels. Take a 2x2 or 3x3 grid, make a library of tiles, use that to generate a random level, then use the K-L divergence to determine how well your generative algorithm has done compared to the observed distribution from an example image.
[0] https://arxiv.org/pdf/1905.05077.pdf
[1] https://github.com/mxgmn/WaveFunctionCollapse
-
All of it under the most poorly designed and maintained village
Reminds me of wave function collapse - a programmatic way to generate mazes.
-
How to detect and fix isolated terrain (islands or lakes) in a tile-based terrain?
I am using WFC to generate the terrain, with pretty much a copy-paste implementation of the original WFC implemented into Unity.
-
How to make wfc or post-gen script in blender?
If you still want to go the WFC route, the original WFC repository is a great place to start. There's also a (relatively barebones looking) Godot plugin you could take a look at.
- Wave Function Collapse
-
collapsed
wave function collapse studies - this is done with the https://github.com/mxgmn/WaveFunctionCollapse algorithm after I saw https://github.com/CodingTrain/Wave-Function-Collapse mention it. done in P5! IG https://www.instagram.com/ronivonu/
-
Room Generation Using Constraint Satisfaction
There’s an interesting approach similar to this called [Wave Function Collapse](https://github.com/mxgmn/WaveFunctionCollapse) (no relation to wfc in physics idea besides inspiration). It can infer the probabilistic constraints from one input example, and it seems to generalize quite well. Here’s a [little demo](https://oskarstalberg.com/game/wave/wave.html)
What are some alternatives?
BezierInfo-2 - The development repo for the Primer on Bézier curves, https://pomax.github.io/bezierinfo
Raylib-cs - C# bindings for raylib, a simple and easy-to-use library to learn videogames programming
SVM-Face-and-Object-Detection-Shader - SVM using HOG descriptors implemented in fragment shaders
eShopOnContainers - Cross-platform .NET sample microservices and container based application that runs on Linux Windows and macOS. Powered by .NET 7, Docker Containers and Azure Kubernetes Services. Supports Visual Studio, VS for Mac and CLI based environments with Docker CLI, dotnet CLI, VS Code or any other code editor. Moved to https://github.com/dotnet/eShop.
GoJS, a JavaScript Library for HTML Diagrams - JavaScript diagramming library for interactive flowcharts, org charts, design tools, planning tools, visual languages.
OpenFK - An open source replacement for the U.B. Funkeys executable.
uBlock - uBlock Origin - An efficient blocker for Chromium and Firefox. Fast and lean.
DeBroglie - DeBroglie is a C# library implementing the Wave Function Collapse algorithm with support for additional non-local constraints, and other useful features.
new-wave - Stack Computer Bytecode Interpreters: The New Wave
dnSpy-Unity-mono - Fork of Unity mono that's used to compile mono.dll with debugging support enabled
virtualagc - Virtual Apollo Guidance Computer (AGC) software
texture-synthesis - 🎨 Example-based texture synthesis written in Rust 🦀