I have recently been fiddling to try and fix problems I have encountered on this project which is now named Dynamaton. One issue I realized is that forces all take effect at the same magnitude at any particular distance. In reality, the electron shells of atoms repel each other strongly only in close proximity. To simulate this I included something that is very expensive: each force has a base "radius." Inside of this radius, particles do not interact using that particular force. Between that radius and the radius + 1, the force linearly increases to its maximum; then after radius + 1 it decreases with the inverse square law. This means that some forces will take effect in close proximity while some will take effect further away.

The biggest issue I had to deal with was making space toroidal. Since I implemented this by using the shorter radius, meaning that if on any particular axis the length was more than half of the space I would use the radius that wraps around, if two particles were precisely half of the width of the space in distance from each other they would toggle back and forth and achieve an equilibrium. This would always result in this pattern occurring in which every clump of particles spread into a cube matching the shape of the space like this.

I decided at this point that I would either leave space unbounded or bound it without making it toroidal. Unbounded space was not an option because then stuff would fly everywhere and it couldn't be seen. I tried bounding using a cube, which worked, but then everything went to the corners of the simulation. So now I am doing this.

I made it so that the velocity bounded off of the edge of the sphere where the hypothetical "new position" would be, not changing the position, when particles exceeded the bounds of the sphere.

Presently, this is single threaded and running on my CPU. I have plans to use OpenACC to easily make this run in parallel on my GPU, which should let me have many more particles than I presently do. Space segmentation optimizations will come later. The radius issue is particularly expensive because I must compute the square inverse of the adjusted radius for each force, which reduced the amount of particles I could spawn by a factor of 10, but it does make some significantly more interesting interactions, so I will continue to do this for now.

In addition, the meshes are set up. When particles enter a threshold and leave another, they mesh together and break apart. Before I had elasticity between meshed particles, but I might simply leave that functionality off. The last feature to implement is the reaction-diffusion system, so that will be coming up shortly. I also want to improve the graphics so that the particles look more like this shader toy shader and these spells from Skyrim (much more glowy). In addition to that, I will need to switch to the new shader pipeline, since I am sadly using OpenGL 1 features so far, since graphics performance isn't the limiting factor presently. OpenGL ES might be my target so that I can port this to Android fairly easily.

I have been working on my recent project quite a bit, though I've recently returned to college, thus I am spending a little less time on it. Particle physics and neural neural network systems are complete, though the reaction-diffusion system is partially in-place, since the chemicals are represented and interact in the particle physics simulation, which doesn't seem to be too expensive.

Over the last few days I have been learning about Radial Basis Function Networks (RBFNs). In my previous posts I only discussed the perceptron, however there is an alternative, and arguably better, function to compute the output of a node in a neural network. The perceptron multiplies its inputs by a weight and then sums them, producing output by passing this sum through a function that could be a sigmoid or a threshold with a binary output. In either case, the perceptron effectively creates a line, with one side of the line being 0 and the other being 1.

A single perceptron categorizing the input

Sometimes this splitting of space is behavior you want, but sometimes it isn't. One other way to divide space into 1 and 0 is using an oval. Now, to be clear, this is only what happens with two dimensions of input, each of which are the x and y on a graph; this method can be used for as many dimensions as you like, and an oval may become an ellipsoid in 3 dimensions. Whether oval or ellipsoid, a RBF is designed to encapsulate some area of space, indicating that this region is what we would like to include or dis-include. It seems obvious that in many situations, several regions might need to be specifically added into the data set; this is what the RBF is capable of doing.

An image of 2d space segmented with a RBFN

RBFNs do something very simple: they use the Cartesian equation for any n-dimensional ellipsoid (though technically "ellipsoid" refers to the 3-dimensional variant). The "threshold" that was used by the perceptron is a similar concept to the "radius" of the RBF. As is apparent from the image, an area is surrounded by this function, which allows the neural network to classify regions. If one did not square the distances in each dimension and used an absolute value function instead, it would create a cuboid or rectangle instead. One could make an argument for such a system, but the RBFN seems to be very popular and effective in the field. To simplify its definition: it creates a rounded space around a point and classifies inputs in that region. It gets more complicated with a whole network, rather than a single function, but the RBFN is obviously powerful.

The reason I am bringing this up is because I have decided that a RBFN will power my simulation instead of a perceptron network. As time goes on, I may consider a hybrid between the RBF and perceptron, but for now I will be making the switch, since I consider RBFs to be superior in most situations for classifying information. It is likely that I will also try the "cuboid" approach as well, but I assume that the differences will be insignificant, so the switch would be purely for efficiency reasons.

The next thing to add to my project is the coloring of the spheres based on chemicals. This is trivial, but complicated since I am not sure that a "bound" should be created for the maximum brightness of any particular color based on the input chemicals. My plan is simply to sum the chemicals multiplied by coefficients for each color, then bring e to the power of the negative result. This will give me a value starting at 1 and approaching 0 as the chemicals increase. Then I will subtract this from 1 to receive the intensity of the color. I don't particularly like this solution, but it seems the be the best way to do it; I may even apply this to the inputs for the neural network.

Since my previous (and first) post I began working on the actual simulation for the cells, but then soon ran into an obvious issue: the brains of the cells. For cellular automata it is sufficient to make a simple state machine in which cells make decisions using a sort of tiny program, but because I am using a reaction-diffusion simulation, this doesn't seem to be an ideal solution, because the output needs to be between 0 and 1, as I will explain later. My first assumption is that neural networks would be the ideal solution, since they work with non-binary results, though upon looking into the issue, it seemed that the ideal neuron was a perceptron, a simple neuron that sums weighted inputs and then runs a function on this value. Perceptrons originally were designed to output a 1 or 0 depending on if they exceed a threshold value, but they were modified to use sigmoid functions so that they can be trained using back-propagation (specifically the one 1/(1+e^-a)). In my situation, natural selection will train the creatures, since no "correct" output exists, thus I cannot use back-propogation. Another consideration would be recurrent neural networks, which are extremely difficult to train using back-propogatioin, yet they are widely used, so it seems that they would be very helpful to my situation, but they actually are complicated to process, and since I want to have lots of creatures at once, I believe that this is not the best option.

One thing I realized in my research is that a lot of effort was developed on algorithms that can be trained easily using back-propagation. One type of system that completely ignores that prospect is using, which I used with most of my older evolutionary celluar automata, is a genetic program. I believe that this is certainly a good option, so much that I wrote a whole blog post on them before I wrote this one, but as I was concluding the post I realized that this might not be a good option. After that, I did even more research into alternative algorithms, but I came up with very little that I hadn't already tried myself or read about online. I was going to use a genetic program, so I started writing the code, thinking of how I might just do it in the process. I needed to allocate space for so many small nodes that if I dynamically allocated memory from the heap for every node, I would end up wasting most of it in the overhead of allocation. It eventually forced me to accept that I would have to have some fixed maximum amount of inputs to a node. The main reason this was a problem was because I was still trying to incorporate perceptrons into my model. In addition, I would absolutely need to process the input, which in my case is all of the chemical concentrations, in a special way, since it was a scalar value that could be almost anywhere, while the output needed to be somewhere between 0 and 1, which works perfectly for a sigmoid function. Ultimately, I read up on the amazing things that deep neural networks were capable of, and then I was partially convinced, but not entirely.

One thing I felt was not considered in deep neural networks was the significance of multiplexers in logic. A multiplexer (MUX, for short) is normally used in digital logic to select from inputs using selector bits, and they can literally do everything. I really felt that I had to add these into the mix, though I can't put my finger exactly on what problem they would solve, but I just noticed that perceptrons would have a hard time selecting between two completely independent decisions, since all they can do is combine multiple decisions together depending on their weights, rather than choose one over the other. So I conceived of a hybrid model.

My model has three layers to it, which I will name according to convention. It has a fairly large input layer, which is designed to create multiple separable regions in the input space that can be used in subsequent calculations. The outputs of this layer are binary, so as to be computationally efficient, though I may switch later to sigmoid functions just to see how much better they are, but my understanding is that the purpose of the curve is just to help make back-propogation easier. The next layer is the hidden layer, which in my case is actually a series of layers each containing one muxeptron, which is a concept I imagined. Each one of these hidden layers can reach back to receive input from any previous layer, which I feel is very important to keep the input relevant even near the end of the calculation, but also so calculations can be reused. Muxeptrons are an invention I created for the purpose of adding MUXs into the mix. Each muxeptron contains three perceptrons; one perceptron will either fire or not fire; depending on whether the first perceptron fires or does not fire, one of the other two perceptrons will be chosen to be used as the output. Finally, the last layer is the output layer. Because my outputs need to be scalar values between 0 and 1, I figured this was a very good time to use a sigmoid function. The output layer can only access previous layers and uses normal perceptrons that use a sigmoid function, which is very basic and works properly to my needs. Since not all nodes will be used in the computation, I chose to compute from the output backwards. Computation begins at the output and as inputs are required, they are calculated accordingly.

Another thing I decided was that if a node was unconnected from the network, I would leave it unconnected. This seems strange, but my reasoning is that this will simulate junk DNA to some extent. In addition, if a new node is added to the network through a mutation, I will simply add it to the network unconnected; a future mutation may cause it to become connected to the network, which allows the network to gain complexity without significantly altering its function.

The purpose of this brain is to control the diffusion coefficients for each cell connection in the mesh. In each simulation step, the cells will run the "brain" algorithm to produce diffusion coefficients, which are intended to simulate active transport, though only for outgoing diffusion (I may change this in the future so that cells can transport chemicals inside of them). As in real biology, this active transport will require energy, which is also going to be a chemical (namely chemical 0, otherwise known as food) in the reaction-diffusion engine. When a cell produces a value of 0, it will force there to be no diffusion, while a value of 1 will force all chemicals to diffuse out of the cell in one cycle. However, a cell that actually managed to produce a 1 or 0 exactly (which should be impossible with the sigmoid function) would kill itself immediately because the food cost would be infinitely high. A natural rate of diffusion is established that is closer to 0 than 1 at the initialization of the simulation, and if a cell matches this rate of diffusion exactly, it will not have a food cost, thus cells should adapt to "understand" this value, possibly generating it and selecting it with their MUXs to avoid food costs when food is low.

The only things a cell can read from its environment are just the amount of chemicals inside of its own cell (including food, which IS a chemical). This means that a cell will have to use chemicals to send signals through the mesh.

Although this is unimplemented as of now, I want to share my thoughts on how the chemical reactions and physics calculations will occur. When the simulation is initialized, I will generate a series of random chemicals, then I will generate an arbitrary amount of chemical reactions that allow a few elements to combine in a 1:1 ratio into another element, so that there is conservation of chemicals. After the chemicals are all generated and organized in this fashion so that chemicals cannot be created or destroyed through chemical reactions, I will define a catalyst matrix so that each chemical acts to some degree as a catalyst for every available chemical reaction. This catalyst matrix will be multiplied by the vector of chemicals in every node, so that reaction rate constant can be determined. The reaction rate will still depend on the concentrations of the input chemicals to the reaction. I will probably bring these concentrations to the power of their ratio in the reaction, but I have a feeling that this will slow down my simulation substantially, so I might come up with an alternate solution later on after profiling.

As for the physics simulation, every chemical will interact with every other chemical. Two base force vectors will be computed: one "gravitational" force vector that makes both particles attract or repel and a "magnetic" force vector that is computed as the cross product of the velocities of the particles. Both forces will then be individually multiplied by the summation of the products of each of the two chemical concentrations multiplied by a constant coefficient for that particular force. Finally, the force vectors will be summed and then divided by the inverse of the distance squared so that they follow the inverse square law and have conservation of energy (to some extent). Opposite forces will be applied to each of the two nodes as particles. Also, forces will decrease linearly starting at some radius that I will define so that particle interactions do not get too strong and fling particles all over the place at high speed.

My main concern with the physics simulation is that multiplying all the chemicals together and by their physics coefficients might be very computationally expensive for large amounts of chemicals, so I might impose a limited set of physics interactions just like I did with the chemical reactions, but I will only do this if profiling shows this to be a significant burden, which it may not since it is only doing many multiplications, which aren't too difficult to compute, while the magnitude of the distance requires a square root to compute, which IS a requirement, because I have to divide the vector three times by this value to get from actual magnitude to inverse magnitude squared, thus I cannot just use it in its squared form. As things need to change in the simulation, I will update them and make them work a bit faster. This project will absolutely be using OpenCL eventually, but I will begin writing everything in C++ just to see how things turn out. I will also eventually optimize this by using a barnes-hut simulation so that the particle interactions don't get to expensive at large values.

As I said before, I will keep posting my ideas on this blog regarding this project. I have a feeling that very interesting things will result from the simulation. If I like it enough, maybe I will turn it into a game. Once the code is more fleshed-out, I will consider making it open-source, in which case I am likely to release it under the BSD license.

This is the first post of the blog, so I suppose some introduction might be necessary. The intention of this blog is to showcase the interesting projects I am working on for my friends and others. I work on a variety of interesting things and since some people might be interested in them, this will become the primary location for information on my personal projects and my thoughts regarding how people ought to be doing things.

In the past I have worked on a lot of cellular automatons in which each cell contained a genetic code that was designed to be mutated, mated, and tested against a variety of other randomly generated and mutated cells. Not long ago I had planned to work on a simple game, which I may still return to, that incorporated particle physics with "chemicals." The intention was that randomized creatures composed of particles would divide and consume the finite particle resources around them to fuel their growth, permitting competition among multiple species of such creatures. I have thought about this for a while and the idea has evolved, but it did not significantly change. I had tested whether it was feasible or not, and it seems to be a bit too computationally expensive regardless of how it is done.

However, I recently learned about reaction-diffusion simulations, which can be used to simulate real world chemical reactions and biological processes. These amazing things are generic and only have local interactions, making them amazingly easy to simulate massively in parallel. Here are some remarkable examples of emergent phenomena created by reaction-diffusion simulations:

The method by which these work is that a reaction occurs inside each cell every time there is a new cycle. One or more different "chemical" materials are each present in the cell, and each of these reacts each each other only within the same cell. In addition, some of the chemicals leave the cell and enter adjacent cells, which simulates the process of diffusion. Each chemical has its own "diffusion coefficient," which is used to determine what proportion of each chemical spills over into adjacent cells every cycle. Although the reaction can be made complicated to compute, this process is overall easy to compute in parallel, which makes it a prime candidate for optimization via OpenCL.

After learning how it worked, my initial thought was that a square grid is not a good way to carry out these simulations, since a square has eight neighbors: four neighbors in the cardinal directions with distance 1, and four neighbors in the diagonal directions with distance sqrt(2). Real simulation of 2d space would be better achieved by using hexagons, each with 6 equidistant neighbors. For a 3d simulation, I would personally use a rhombic-dodecahedral honeycomb to achieve the same effect. However, the trend in general is that adjacent cells diffuse with each other...but they don't have to be on a grid.

My primary intention is to somehow create an automaton with evolving creatures that uses reaction-diffusion equations to control the flow of chemicals, which could be used as food or other material, so I started by thinking of a few ways I could do this. I thought at first that I might try to create a separate "chemical" for each creature, but then I realized that this would become too computationally complex, and the chemicals would not be able to respond intelligently to their environment. The next thing I considered was to create a system that would have many emergent-phenomena, such that a replicating creature could develop with a genetic code very easily, much like Langston's Loops. This may be possible, and I may try this idea later, but I think that is something cellular automatons will do better at, and though I may be wrong, I believe it would be difficult to create such a rule-set.

I have decided that one possible way to achieve an interesting developing system is to make each simulated cell in the reaction-diffusion simulation have its own genetic code. Each one of these cells could identify its own species and act to its own benefit by attempting to divide and control the rate of diffusion via active transport all at the cost of food (pat of the reaction). Multiple chemicals could interact with each other in ways such that food may be destroyed and interesting things can be done to other cells, so that cells have a way to defend themselves and attack their neighbors. However, this model is not sufficient on its own because too many cells would need to be simulated and cells cant effectively interact with other cells to their own benefit, since I suspect that some equilibrium might be achieved in a finite space. Thus I plan to make the space effectively dimensionless from the perspective of cells. Each cell will connect in a mesh to a variable number of other cells. A new cell can appear anywhere when a cell divides, which will connect the two cells and split old connections between the two cells so that no new connections are made.

Now I could use this model simply by inserting random cells into the mesh and having them fight it out, trying to destroy cells by shorting out their food. However, I am going a step further. The plan is to generate random cells and place them in their own separate mesh, then place each of these cells as a particle into a 3d n-body particle simulation. Connections between cells will pull them together and chemicals will cause various forces to be applied between the cells. Now cells can effectively become colony-meshes and attack other colony-meshes using inter-particle forces, attaching to those colonies, then performing biological warfare by pumping food-depleting chemicals into the opponent or giving them chemicals that force them to repel and detach from each other. The possibilities for different adaptations in such a system is endless, and colonies could form complex structures and even neural-networks naturally as part of the chemical-diffusion system that worked along the meshes.

Hopefully anybody that has read this far is as excited as I am. I used this blog to flesh out my ideas and my thinking, but also to share the project. As the project develops, I will upload pictures, videos, and new information. All the while I will be learning this blog business as I go.