Elemental distribution part 1

We're examining a list of points in which we've accumulated celestial material. The next step is to examine each of the points in turn and determine what elements are going to appear there, and in what concentrations. The basic idea is to distribute the elements according to two parameters: the atomic "weight" of an element and the relative mass of the point we're examining.

The simplest example would be a distribution represented by a diagonal line on a graph where the lightest elements have the highest concentration and the heaviest elements have the least. Like this:

As the elements get heavier, their concentration drops. Easy. This is a line given by f(x) = -x + C (C being some useful offset > 0) and I could give my elements a concentration by simply assigning them a value from that formula with x being the element's number (an analogue for its weight).

But we want to add some more complexity. I'd like that line (without the C factor) to rotate around the origin if the structure were especially heavy, meaning that the concentration of elements in a high-density object would tend towards heavier elements (since more stuff = more pressure = heavier elements created), like this:

And that is just f(x) = x.

So I could say that the elemental concentrations in the least dense object in my galaxy would look like graph #1, and the densest object would look like graph #2. What about everything in between (ie, where most of my points will be)? For example, from these two graphs we would then expect the plot of an object in the exact middle of all densities to look like this:

With every element having a distribution equal to every other element.

Well, I could try performing a matrix rotation on my line based on a given point's density relative to the densest or sparsest points in the galaxy, and then take the integral of the resulting line under the area where the current element would lie, but that would leave me with the difficult problem of expressing the formula of the newly rotated line, and that's not a problem I really want to tackle. Instead, I'll simply use the density of the current point to determine the end-points of my line on the x-axis and then interpolate between those points for each element to get my density (y) values.

Okay, that works nicely, but now what I've got is a bunch of straight lines determining my distributions which is totally unrealistic, so the next step is to introduce some randomness into the concentrations. I will go into this next.

Points of light.

Here's a dump of the history info from my standardized test cell after a test run:

ME value increases for point: [512, 832]
3.6843689007676927E-4
2.716237547371342E-5
2.9090579695712552E-5
3.1144463596306965E-5
6.506629228372208E-5
7.405909856976646E-5
1.7063948094252874E-4
3.3792013449738514E-4
7.444779872999891E-4
0.002446036637268214
0.012186734948650564
0.2634531866962704
0.05472177183706822
----------
ME value increases for point: [512, 132]
3.7562109253996525E-4
2.867135985517093E-5
3.0778210777415476E-5
3.3027122124802656E-5
6.928975898518475E-5
7.921599901756085E-5
1.835023833388631E-4
3.6633310815393274E-4
8.139099483572199E-4
0.00268837270633909
0.01693013582993017
0.3543588907279924
0.04679710557484452
----------
ME value increases for point: [768, 640]
3.760923095653502E-4
2.915072708934144E-5
3.1326436311622165E-5
3.365123867539532E-5
7.064017770270657E-5
8.091135601364832E-5
1.8698489800672439E-4
3.7208456012115634E-4
8.258726661649197E-4
0.002729821637916935
0.01721015128808257
0.40555363904035674
0.09538530622543287
----------
ME value increases for point: [512, 768]
3.767499868527032E-4
2.8279704526428565E-5
3.032241944513951E-5
3.2500398334611576E-5
6.754609983521939E-5
7.69811061138045E-5
1.7632033895116132E-4
3.4639456486021885E-4
7.570867716124853E-4
0.0024541848351469445
0.011871005835509091
0.2395660995876462
0.01219728123002246
----------
ME value increases for point: [0, 640]
3.8561785862321E-4
1.2321449572353496E-5
1.26924945932426E-5
1.3073266099040977E-5
1.3463927338444061E-5
----------
ME value increases for point: [640, 0]
3.722880447846761E-4
9.88352883149037E-6
1.0129457676970466E-5
1.0380636692813959E-5
1.0637132442555548E-5
----------
ME value increases for point: [512, 144]
3.733165328463877E-4
2.750708483139135E-5
2.9457539037267986E-5
3.15347941568521E-5
6.524675689809289E-5
7.416671102236263E-5
1.693333998658301E-4
3.327206820422787E-4
7.26147700986548E-4
0.0023424264101682976
0.01045868543088396
0.02708073563331379
0.0015200371921317774
----------
ME value increases for point: [384, 384]
3.817576409065541E-4
2.9874999870465113E-5
3.212520064006556E-5
6.671118787423355E-5
7.64355917225563E-5
1.7542695358521127E-4
3.4845124474010053E-4
7.711369032722636E-4
0.0025399536635697523
0.0126289164665422
0.26379030752774035
7.561156233093637
158.16191766117714 <---- this point will be something big!
21.97533623061286
2.1882426816866567
1.1442409191569198
0.7480535613845003

I've run tests against my test cell (a cell which generates the same noise map every time) and random cells (random noise maps), and the interesting thing is that, very consistently, one point rises far above the others. This bodes well for the system I've set up, since while the majority of the cells in the galaxy will be "empty" space without significant structure, the ones that do have significant structure will tend to have one high-density point and some variable number of lower-but-variable-density points... just like a solar system. Neat.

Seeds of structure

Now that we've got a list of points that are "dense" enough to spawn structure and some information about how much matter and energy they contain as well as their history, how do we use that information to introduce structure into the local area? This will take me back to what I mentioned earlier about chemistry and fusion of elements. In essence what we have is a whole lot of Element 1 contained in a very small area. We need to take that homogenous soup and turn it into a physical object.

Broad plan:

Step 1: We have to determine, based upon the properties and history of that area, what new elements will form there and how much energy it will take to form them—the idea here being that eventually we will run out of energy to form new elements. The stage/rate at which this happens will produce certain attributes of the eventual structure. The initial density of the area will have a lot to say about that, since a higher density will form heavier elements with less wasted energy.

Step 2: Based upon the elements resulting from Step 1, we determine what sorts of chemical bonding will take place and in what amounts. This refers back to the simple chemistry developed earlier—certain elements will bond with others.

Step 3: The resulting substances from Step 2 will give us an idea of the nature of the structure in question, its chemical composition, size, etc.

One of the biggest kinks to work out here is in the chemistry. Likely I will need to go back and add some more sophistication to that system so that, while elements with the proper "numbers" will bond with certain others, there needs to be some preference in their bonding so that elements will bond in a path-of-least-resistance sort of way.

From clouds to rain

Now, finally, we're getting to the good parts. We have a map of a local area, or cell, with information regarding the amount of matter and energy available to do useful things... but getting from here to there is going to be a lot of work.

The first thing we need is a way to determine A) what elements are present in our cell, B) in what densities and C) at what locations. In order to determine that, we need to know how much energy is required to form elements, so it's back to chemistry.

In the real world, vast amounts of energy in the form of heat and pressure are required to fuse elements—14 million degrees Fahrenheit plus the gravity at the center of a star to fuse two hydrogen atoms together. We're not going to do anything like that here. Instead, we're going to simply use probability ranges to help determine distribution (with, of course, some randomness thrown in) and then the densities present in the local map we already have to determine how much fusion into larger elements will occur.

To simplify things, at least for now, we will first make the decision that we've already expended all the energy necessary to create a galaxy full of the simplest element in our periodic table, meaning that the global and local mass-energy values are what we have left over from that (implicit) process. So instead of just looking at the real universe's elemental abundance and dividing things up based on that, let's just say our entire local map is made up of Element 1. At first.

Now we need to examine the local map very carefully. We need to find concentrations of E1, their constituent values and their areas, which will help us start "fusing" them together into heavier elements. How do we find these concentrations?

To solve this problem, what I've done is created an "accretion algorithm." It's taken me about a month of weekend spare-time work to iterate, evolve and implement. Undoubtedly, I will go back and fine-tune it, but it seems to work well enough to move forward. The idea behind (astrophysical) accretion is the accumulation of celestial matter via the forces of gravity. As more material accumulates, it is able to attract more surrounding material, creating a feedback loop from which, eventually, enough material gathers to form planets, stars, etc. I can't directly simulate this process, not even in two dimensions and not even in a finite problem space—it would take trillions of floating point operations to even begin to see usable results. Instead, I take a few shortcuts using the information I already have in the local cell about where most of the material in the cell will most predictably wind up. After a successful run through (which typically takes a few seconds), roughly 97-99% of the existing material in the cell ends up in the brightest (densest) areas in differing concentrations. This material accumulation takes place in such a way that I record information about it, which will allow me to characterize the different accumulation points--the ones that gathered the most material the quickest could become stars or black holes, while the average areas could become planets, etc.

Sadly, there is nothing compelling, visually, to show for it yet: just a black image with a few white dots here and there. It's the information recorded from the process that will allow me to begin creating celestial bodies—bodies that will not simply be static fixtures, but bodies made of and born from material spawned from an internally-natural and consistent process and which are completely interactive. A gas giant will have harvestable gas. A world of hydrocarbons will have hydrocarbons—usable by anyone who can land there safely and extract it. These will not just be descriptions of static decorations and visual interest. Within the confines of Flat Galaxy, they will be real.

The material density map

Now we've got something (a fractal-noise image) that reasonably approximates, for our purposes, the elemental-matter-energy density of a galaxy. This would mean that a 1000x1000 pixel image represents an entire galaxy, so if we were making a galaxy the size of the Milky Way each pixel would represent roughly 600 trillion miles or 9.5×10^17 kilometers of space. That's a lot. This is only a proof-of-concept, and I'm not ready to start diving into that kind of scale. I'm going to reduce our galaxy size to something a little more manageable. Let's say about 1/1,000,000,000,000,000th of that size. This is a galaxy about 600 miles or 1000 kilometers across where each pixel represents about 0.6 miles squared (1 km squared). Everything in this galaxy will (probably) be scaled down appropriately: planets, stars, etc.

(Note: I can generate density maps larger than 1000x1000, which would give us much more fine-grained detail about the galaxy, but this is just a starting point. Plus, increasing the size of the image causes pattern generation to take exponentially longer amounts of time and currently results in images that are usually too dim to be very usable. This is something I'll come back to address later.)

Next we need a starting number. This number will be a reference point to the amount of energy and mass that exists in this galaxy (remember they're the same thing both in reality and, very transparently, in our model). We can produce this matter-energy (ME) number by simply totaling the values of each point in our density map. Here's an example number: 32329096.

Now we need to take our density map and divide it up. Each pixel is 1 sq. km, which we need to divide into a bunch of more fine-grained units--basically what will become tiles on a local area map, or cell. A square meter is obviously a good first choice. This means that each pixel on our density map represents a cell of 1 sq. km. * 1000 meters/km = 1,000,000 meters squared. This is a little more than 1/100th of the size of the entire Manhattan area--per pixel, one million times, which means our galaxy is about 1/10th the size of the entire US.

So, say we're examining a pixel in the dead-center of the density map. We can estimate its individual ME value at about 32329096 / (1000*1000) = ~32.33. This small number is the amount of matter and energy we have available to distribute around the cell the pixel on the density map represents. For the time being, we're not going to allow values to distribute across boundaries, so each cell will be in a sense self-contained.

Now the noise functions mentioned in the previous post become really useful. We can generate a 1000x1000 pixel (these represent meters, now) noise map and scale it to our cell's ME value as it relates to the maximum (and minimum) ME values of the entire galaxy, giving us a proportionate and appropriately random (or determined, if we want to direct it a bit) distribution of matter and energy in the cell.

What we need is a noise map that, when we total all its values, equals the local ME value. If our local ME value is 32.33, then we want to produce a noise map where each point's value is, on average, equal to 32.33 / (1000*1000) = 0.00003233. We can do this by producing a random noise map with random values and using a little math to map the values to our desired range. This gives us a noise map with a total ME value equaling its corresponding ME value in the density map. And, if we produce an images from this by normalizing each point in the resulting noise map by the scaled maximum of any point (the density map point with the highest ME value), we can see that each cell has a "brightness" to match:

A cell with 10% of the highest cell's ME value

25%

50%

75%

But herein lies the rub. We can't do this ahead of time, because while each noise map only takes about half a second to produce (that's even using a fast cosine function during interpolation--using the standard Java one takes a second), we're producing one for each pixel on a density map of 1000x1000 pixels. Even if we filter out the pixels with zero values, at least ~50% of the pixels still have a value and it would take about 65 hours to produce every noise map (half that if we use less-pretty linear interpolation--and still far too long). That's apart from the fact that we certainly couldn't hold them all in memory, and they'd eat up about 2 terabytes of HD space. Nope. We need to produce them only as needed. I will begin to address this next.

Blending

I wasn't totally satisfied with the layered fractals being the stepping-off point for a true material density map, so I made some revisions to the code. I spent several days delving into various noise functions and eventually came up with a fairly fast and simple method of blending the disparate-looking fractals using a sort of hybrid Perlin-noise-with-cosine-interpolation function. These are a few of the results:

A lot closer to what I'm looking for. The blending functions aren't perfect and still leave some of the undesired "webbing" between less dense parts of the image, but I can start from here. After basically spending the entire week playing around and with and digging into various noise-generation methods (Perlin, Simplex, midpoint-displacement), I've got a handle on to how to use them going forward for a lot of procedural stuff. Time well spent.

Layered fractals

Per the previous post, here are a few images of layered fractals. Unfortunately, they're not as impressive as I'd hoped as it seems like when one fractal is bright, the other is dim. Rarely if ever are they both bright at the same time. The other problem is that they aren't as organic as I wanted them to be, since using different formulas for each results in images that don't line up nicely and using the same formula for each results in images that look too similar, enough that you often can't tell where one is vs. the other. Nevertheless, they're still pretty cool.

I also made a few more improvements to the fractal generation itself, most notably introducing multi-threading logic to the (embarrassingly parallel) pattern generation so that generating ten two-fractal images went from taking about 50 seconds on average to taking just 20 seconds on average. I'll take a 60% speed improvement anytime.

(Edit: I forgot to apply my previous optimization for those numbers. With both of my optimizations, the multi-threaded version takes 10 seconds to generate 10 two-fractal images while the one-thread version takes 30 seconds. With none of my optimizations, that same set took about 50 seconds to generate, a total improvement of about 80%).

And here's a couple single-fractal images I just thought were really awesome.

Galaxies and fractals

Now we have a basic chemistry. What do we do with it? Well, we want to distribute atomic particles throughout our model. According to what criteria? We certainly wouldn't want to distribute it evenly, or our little universe would look the same everywhere. We don't want it to be completely random, since the whole idea of Flat Galaxy is to seed our models with order over a large scale. One thing that fulfills this criteria very nicely: fractals.

A fractal is a pattern that is a pattern that exhibits self-similarity. They're seen everywhere in nature, and there's even a competing theory to the Big Bang that matter distribution throughout the universe is based on a fractal pattern. Which means that our own Milky Way galaxy is in some sense a model of the pattern of the entire universe. Fractal patterns are generated by recursively (self-referentially) iterating over complex polynomial functions, taking the output of the previous iteration of the function as input for the next iteration of the function. The classic Julia set function is f(z) = z^2 + c where, basically, z represents a point on the complex plane (which is mapped to the image plane) and c represents a complex number that largely determines the behavior of the fractal. We simply iterate through the function for each point on the screen and if after X number of iterations the output has not diverged (based on some threshold value) to infinity, we draw it on the screen.

Another bonus to fractals is that for now, at least, there is no physics model in Flat Galaxy. Implementing physics would complicate things immensely, even in 2d, and would force me to spend large amounts of time writing collision detection code on a fairly immense scale. Most problematic is that it would eat up processing cycles I would prefer to be dedicated to more important things. We can gloss over the lack of physics in various other ways. Fractals are one of them. We don't have to simulate accretion disks or orbits or anything else. Instead, we can just use a probability map based on a fractal and the amount of energy required to form any given element to determine concentrations of elements. From there, we can narrow our focus to the elements themselves, allowing them to bond depending on their individual properties and proximity.

I grabbed a simple fractal generation algorithm off the internet and made a bunch of modifications. The first modification was to the output functionality so that the images produced would color-code based on the density of the points. The images look best in grayscale, since they look how you'd expect a top down image of a galaxy to look. Unfortunately, the images also take some time to generate (around 2 seconds each on a fairly new computer), so I made a small, simple optimization that gave a 40-50% speed improvement without any degradation of the fractal, provided the threshold value for the fractal in question is of a certain value (the lower the threshold value--which also has a proportional relationship to the "brightness" of the image--the less optimization can be done).

I also added functionality to superimpose two fractals, one on top of another, randomize the complex function used to generate the fractal(s), and to randomize the complex values that represent c.

Here are a few of the images generated by the program (I think these are all one-fractal images. I'll have to generate some decent two-fractal images, since I think I deleted most of them):

You might notice that the "orientation" of these patterns is somewhat similar. This is because the same function was used to generate most of them.

I'm still working on the generation process for the superimposed fractal set, since those ones tend to be far more hit or miss. Randomizing the functions and the c-value also generate a lot of useless images (which are usually automatically filtered out based on a couple threshold values), and my plan is to generate these images continuously on a web server and send them to the client, which can then pick and choose which images to use without having to generate them itself. I also may put some work into smoothing the "webbing" you can see around the areas in between the lighter areas.

Next is taking these images and creating a material density map.

A procedurally generated chemistry

We can appropriately characterize chemistry as the interactions between basic elements. In the real world, elements are atoms. In Flat Galaxy, basic elements will be somewhat different. We're going to come up with a chemistry-creation scheme that contains enough randomness to give us something different every time but with enough structure that we can expect to be able to use some of the results.

Let's start by generating around 100 random numbers from 1-100:

89 31 64 4 60 ... 71 75 7 48 53

These are our elements. Think of them as atomic numbers (not atomic weights). We would expect to get each number about once on average, but in one trial we won't, and we're going to cut out duplicates. This leaves us with slightly fewer than our expected number (exactly how many is, I believe, a probabilistic "expected" function).

Now let's generate a semi-random "fixing" number in the lower half of our number range:

20

What is the point of this fixing number? It's entirely arbitrary, but it gives us a reference point from which we can tease out relationships between our elements. Why in the lower half of our number range? No reason, other than it'll give us interesting values. I actually picked 20 in this case because it's close to the number we would expect to get consistently with enough trials (remember, random number in the lower half of a range of numbers from 1 to slightly less than 100).

Now what? Well, from here we start examining similarities in the numbers based on breaking their values up into discrete chunks, kind of like how electrons in atoms are broken up into electron shells. The amount of "electrons" each shell can fit is determined by a function loosely based on the general 2n^2 value in real-life chemistry, where n is the shell number, but which also incorporates our fixing number from earlier. This gives us some interesting values for shell capacities, and I've even had it exactly mimic real life electron shell capacities on occasion.

Once our "elements" are given shells with capacities, we divide their "electrons" up into these shells and whatever is left over in the final shell is what that element has to make bonds with other elements. For example, if Element 30 has 12 electrons in its outermost shell which has a capacity of 20, we know that Element 30 will readily bond with any element looking to either give up 8 electrons (ie has 8 electrons in its outer shell) or any element looking to gain 12 electrons. From here, we can group our elements with similar bonding properties together, and even construct a "periodic table." Due to the randomness I've introduced into the system, this table ranges from narrow and deep to wide and shallow (based largely on the fixing number--larger fixing number means a wider, shallower table). It doesn't quite measure up to the real life periodic table, but there's a lot of subtlety it's still missing. Here are a couple examples, with similar elements in the same columns:

Number of elements targeted: 118
Number of elements actually generated: 101
Generated fix: 5
[ 1 ][ 3 ][ 4 ][ 5 ][ 10][ 11][ 12][ 13][ 14][ 15]
[ 2 ][ 7 ][ 8 ][ 9 ][ 25][ 26][ 27][ 38][ 39][ 30]
[ 16][ 17][ 18][ 19][ 35][ 36][ 47][ 48][ 49][ 40]
[ 20][ 22][ 33][ 24][ 45][ 46][ 57][ 58][ 59][ 50]
[ 31][ 32][ 43][ 34][ 55][ 56][ 67][ 68][ 69][ 60]
[ 41][ 42][ 53][ 44][ 65][ 66][ 77][ 78][ 99][ 80]
[ 51][ 52][ 73][ 54][ 75][ 76][ 87][108][109][ 90]
[ 61][ 72][ 83][ 64][ 85][ 86][ 97][118][   ][100]
[ 71][ 82][103][ 74][ 95][ 96][107][   ][   ][   ]
[ 81][ 92][113][ 84][105][106][117][   ][   ][   ]
[ 91][102][   ][ 94][115][116][   ][   ][   ][   ]
[101][112][   ][114][   ][   ][   ][   ][   ][   ]

Sorry about the font size and spacing here. It was necessary to make it fit.

Number of elements targeted: 118
Number of elements actually generated: 121
Generated fix: 12

[ 2 ][ 9 ][ 4 ][ 5 ][ 6 ][ 7 ][ 14][ 15][ 16][ 56][ 18][ 19][ 20][ 21][ 22][ 39][ 38][ 41][ 40][ 43][ 42][ 45][ 90][ 46]
[ 23][ 24][ 10][ 11][ 12][ 28][ 29][ 54][ 31][ 78][ 33][ 34][ 35][ 36][ 37][ 85][108][ 87][ 86][ 89][ 88][ 91][114][ 92]
[ 47][ 48][ 25][ 26][ 27][ 52][ 53][ 76][ 55][102][ 57][ 58][ 59][ 82][ 61][109][132][111][110][113][112][115][   ][116]
[ 62][ 63][ 49][ 50][ 51][ 67][ 75][100][ 77][126][ 79][ 80][ 81][130][ 83][133][   ][135][134][   ][   ][   ][   ][   ]
[ 68][ 70][ 64][ 65][ 66][ 74][   ][124][101][   ][103][104][105][   ][107][   ][   ][   ][   ][   ][   ][   ][   ][   ]
[ 69][ 94][ 71][ 72][ 73][ 98][   ][   ][125][   ][127][128][   ][   ][131][   ][   ][   ][   ][   ][   ][   ][   ][   ]
[ 93][118][ 95][ 96][ 97][122][   ][   ][   ][   ][   ][   ][   ][   ][   ][   ][   ][   ][   ][   ][   ][   ][   ][   ]
[117][   ][119][120][121][   ][   ][   ][   ][   ][   ][   ][   ][   ][   ][   ][   ][   ][   ][   ][   ][   ][   ][   ]

You can definitely see some patterns in the numbers which I'd like to mix up a bit, and it's not exactly scientific, but it's a start.

On materials

It looks like a basic chemistry may come along sooner than I thought.

In order to give the environments in Flat Galaxy an origin (and thus a way of creating themselves), I have to come up with a logical way of building their foundations. When we look at the real world, we see natural environments that have arisen all because of the interactions of basic elements--chemistry. I could build this naively and simply say things like "there are these basic elements and these particular combinations of the elements give rise to these materials and these materials make up these environments." This would be pretty simple, but it's also more arbitrary than I want. Of course, at their most basic, the laws of physics and thus chemistry are arbitrary. We just ascribe value to them because they allow our universe to exist. So far no one has discovered any fundamental reason for, say, universal gravitation to exist (and I'll go out on a limb and suggest no one ever will).

Anyway, to avoid gratuitously arbitrary rules, we'll attempt to model the underlying composition of Flat Galaxy after our own universe, but we'll avoid simulation by establishing some rules and guidelines about the basic structure.

Since we've decided that "fuel" (which represents both energy and matter, since they are the same thing anyway) should remain constant, we'll establish a starting value for that at the outset. Doesn't really matter what this number is. Everything will be scaled to it. That's the total amount of energy + mass in this universe. Now we break that number up into something. This is the starting point of the chemistry. We need rules about interactions to seed our universe with useful material. It is generally thought that the amounts of matter and anti-matter spewed out by the Big Bang should have been equal, and it's only by some crazy random stroke of luck that a fraction of a tiny fraction of imbalance between the two resulted in every bit of matter in the physical universe around us. If "random" is good enough for the real universe, it's good enough for us.

In fact, we can use randomness to our advantage all over the place.

See, instead of feeding a bunch of carefully calculated numbers into a box in order to ensure a desired outcome, why don't we just throw whatever numbers we want into the box until we get something interesting?

And how do we get something interesting? We start by presuming the existence of material (rather than throw numbers into the box until this happens), and then work towards interesting interactions between basic elements. And therein lies the rub. What are our interactions, and how do they work? We'll need a very clever solution for this.

On coding specifics, part 2

I've now invested three major design decisions into open source Java libraries. Despite what I said before, I may not get around to porting the project to C++ or C#. The strengths of those languages are speed and well-established, powerful graphics libraries. The strengths of Java are ease of maintenance, great base libraries, fantastic community support, and portability.

I found an open source 2D graphics library built on LWJGL called Slick that so far appears to do everything I need it to do, and has extensibility options for things I might need that it doesn't do.

I'm currently trying to figure out how I can distribute as much of the program's load as evenly as possible. I would like to set up a series of interdependent web services using various AWS services for the processing and exposing of data. This would make everything scalable on a finer level via loosely coupled components, rather than bogging down one machine which handles every task atomically. The issue there is, of course, timing/blocking and latency, but if I labor with that design pattern in mind, doing the actual uncoupling later will be much simpler.

Still working on the basic ecosystem model. Lots of boilerplate that, once set up, will allow much faster iteration through design ideas. Dynamically modifiable fuel system (nearly) in place with a persistent backing that can be exposed to the program from anywhere (local file or web service) and processed as a simple object with list of objects (ie, all fuel objects contain a list of children fuel objects). I've spent a bit of time on this part because it's the backbone of the entire model. I'd like to get it right the first time and not be forced into a rewrite in three months that sets me back a month.

On coding specifics

I'm going to start writing my models in Java because I have a high level of comfort with it and at this stage I have zero interest in wrestling with syntax in languages I haven't used in over two years (C# and C++). I plan to rewrite the systems in C# or C++ when I'm ready to start looking at graphics, but that is a long way off yet. I plan to do the graphics in XNA so I can focus on the stuff I care about and not spend an eternity mucking around with graphics horribleness since A) I'm bad at it and B) it's not as important to me.

The systems code will probably be in C# as well, provided the performance impact compared to C++ is acceptable. If it's not, I'll have to migrate it.

In order for performance to be acceptable as the model grows in scale, I'll probably have to multithread parts of the application, but I'll deal with that when the time comes. In the meantime, I will try to write my code with multithreading in the back of my mind so the transition is as smooth as possible.

On the fuel tree

As I sat down to write some my prototypes, I immediately ran into a problem, which was that I hadn't yet figured out a way for fuel types to be dynamic. There's really no way I could hard code each type as a separate class and have it derive from a parent type at compile-time. I needed to have a hierarchical tree of fuel types, but I needed one that could be expanded as needed at run time. The easiest way of doing this is just to have a base Fuel class which holds a list or a set of Fuels (ie, a list of objects of its same type) representing its children, and a parent Fuel.

This works just fine, but I was concerned it wouldn't be very flexible or efficient (not to mention not very elegant or pretty), so I wrote an algorithm which traverses an existing fuel tree and assigns a value to each node which encodes information about that node's parent and children, all the way to the root node of the tree. I'm sure this has been done a thousand times, but a quick googling didn't turn up anything obvious, so I just did it.

This would be a really fast way of checking the tree for parents and children--it's basically just a simple index. Rather than hike the tree up or down each time you want to check if a given fuel is the parent or child of another fuel, you just do a (constant time) comparison of each fuel's indexed value and you have your answer.

Of course, the main drawback is that each time you add anything to the tree, the entire thing must be re-indexed. Another drawback is that the amount of bits needed to index the tree is n/2, where n is the number of nodes. This is because any node with children doesn't need any extra bits above what its children need (ie if a node has four children, then all five nodes--parent and four children--can be represented by four bits), but any node without children requires an entire bit for itself. Since we could reasonably expect half of all nodes to not have children (since you can only ever add a leaf or a parent), we'd have to be careful about managing our data types to make sure we didn't run out of room to store our index total.

So the process would be first building a tree using some syntactic notation like the one in the previous post, and from there maintaining a big tree of our fuels and re-indexing it each time a new fuel is added (or removed), the advantage being only the index would be used for the frequent fuel-type checks. I wouldn't anticipate new fuels being added (and forcing a re-index) nearly often enough to compare to the cost of hiking the tree for each check.

Then again, the tree will probably remain small. Under a thousand items for the forseeable future. Hiking through a tree of that size, even a thousand times a second, is easy-mode for modern processors, especially since we'd expect most queries against the tree from a given node to be made relatively close to the target node. I'll have to decide if it's worth implementing once I see what kind of performance problems I have from all the other systems running at the same time.

On fuels

I've prototyped blocks and connections (inputs and outputs). Now I need a structure for fuels. My aim is to have fuels work hierarchically, so that using a more general type of fuel in an input that requires a more specific type of fuel is possible, but at a reduced effectiveness. This much is easy--it follows the basic polymorphic OOP model of any major programming language.

Here's a starting blueprint for a fuel:

• A type
• An ID (this may be used for bit masking for more dynamic fuel identification)
• A concrete flag (whether this fuel is a physical substance or denotes a class of fuels)
• A parent fuel type (implicit)

There will likely be major additions to this, but it's a start. Here's an example of a fuel tree:

• Fuel
• Organic
• Blood
• Animal blood
• Human blood
• Elephant blood
• Sugar
• Animal sugar
• Plant sugar
• Inorganic
• Oil
• Natural oil
• Fossil oil
• Corn oil
• Synthetic oil
• Robot oil
• Robot A oil
• Robot B oil
• Car oil
• Water

Every fuel type derives from the most general Fuel type. In order for this to make sense, we should allow for fuels to have restrictions on whether or not we can use fuels of a more general type in their place. We can do this by simply setting a flag on the fuel blueprint (or class).

• Allow more general fuel type flag

What we do with this is when a block goes to make a connection, the input of the connection is checked for which type of fuel it accepts. If this fuel type doesn't match the type coming from the ouput, the fuel is checked for this flag and if the flag is "true," then we check if the output's fuel matches the fuel type of the current fuel's parent. And so on until we encounter a "false," or exhaust the fuel tree, or we find a match.

My goal is to allow new fuel types to be developed or defined without having to code them explicitly. This is pretty ambitious, as it would require developing a basic chemistry system to govern the interaction between connections--instead of just fuel types, you could compose a fuel of "elements," some of which could interact and some of which could not. For now, though, this is only a goal.

With these basic building blocks I am going to attempt to create a simple ecosystem which can sustain basic "life" systems on other organic and inorganic systems.

A step back

I've been delving into basic systems a lot lately, trying to work out how they will interact and behave on a massive scale. This has made me lose some of my focus on the overall vision of what I want to accomplish. In trying to meticulously design the building blocks of Flat Galaxy and apply them to a hypothetical, fully-realized model, I have stepped toward the dangerous world of simulation, a world which will force me to develop something that will take far more time and resources than I can dedicate.

I need to take a breath and reiterate (to myself) what I'm attempting to do. My ultimate goal is to have a set of hierarchical, layered systems-within-systems. I want one level to have an effect on the next level up, and so on. I want to create as little "special" programming as possible. Instead, I want to create a set of rules and objects governed by those rules which together can develop more complicated systems on their own, and even new rules, without "designer oversight." In short, I want to create a procedural natural ecosystem which can tend towards order in the short term. This means both the agents and their environment are linked at a very basic level. Everything should be interactive, from plants to planets. In order to build this type of system, there are basic rules that must be established between these two classes of interactivity.

Regarding agents:

1. Biological systems will strive to keep their health at an optimal level.
2. Biological systems will strive to make their functions as efficient as possible.
3. Biological systems will attempt to reproduce.

Regarding the environment:

1. Non-biological systems can be created randomly or by biological systems.
2. Non-biological systems should arise naturally via the interaction of other non-biological systems.

In taking a step back, I am setting some guidelines for myself. My original intention was not to write any code for at least a month or two, but I am finding that more and more difficult as I cannot keep track of every potentially viable scenario without doing some code testing, and writing out pseudo code tests in a notebook is really tedious and frustrating. So I will allow myself to write code, but I will only do so when I have to and I will limit the scope of my tests as much as I can, for now. 

Which leads me to my second guideline, which is that I'm going to start by attempting to develop a very simple model on which I can build, but a model which attempts to incorporate in one fashion or another every important mechanic. I've spent far too much brain energy visualizing scenarios involving actual users and their myriad interactions with themselves and the model, and it's just overwhelming. I'm going to zoom up and focus on a simple AI-driven model which will give me an indication of what direction to go in as I develop more complicated systems.

On inputs and outputs

Inputs and outputs are the glue of all blocks and thus all systems. They are what allow the infinite reconfigurability of the various interacting ecosystems of Flat Galaxy. I have drafted a few simple rules for inputs and outputs which will govern their behavior. These rules are not set in stone. Actually, they very likely will change a great deal as I go along, since everything hinges upon the behavior of inputs and outputs making sense and most importantly, not causing Flat Galaxy to come to a screeching halt.

I have given a description of inputs and outputs in a previous post, but I will repeat my definitions here, as they currently stand:

Each input and output (abstract "put") will have:

• A name
• A fuel type
• An external and/or internal type value
• A modifying factor
• An amount (or capacity or bandwidth)

And each input will have:

• A queue
• An accept/refuse insufficient fuel switch
• A wait/discard fuel switch

Draft #1 of Rules for Outputs:

1. An output will always try to send as much of its block's remaining fuel as possible, up to a max of the output's Amount*Factor.
2. Output capacities are determined by the quality and type of the output (not the type of fuel it can output).
3. Output factors start at x1 and remain so unless a skill increases or decreases that factor.

Draft #1 of Rules for Inputs:

1. An input's capacity does not guarantee it will receive that amount of fuel. That depends on the output to which it is connected.
2. Input capacities are determined by the quality and type of the input (not the type of fuel it can receive).
3. Input factors start at x1* and remain so unless a skill decreases** that factor.

These rules allow for fuel conversion without producing more total fuel than a block started with (at best, equal amounts). By utilizing the ranked output list in conjunction with outputs as described above, a block can convert smaller amounts of various fuels into a large amount of a desired fuel or vice versa. Note: There is not a guarantee of a one-to-one correspondence between an input and output of the same fuel type in a block. That is, you are not guaranteed that gaining X amount of Fuel A via your input will allow you to send off X amount of Fuel A via your output. Your block must be configured correctly and the proper amounts of total fuel must reach your block in order for this to occur.

There are some major gotchas here, like what happens when an output and input's capacities and factors disagree, but I haven't yet worked those details out. Likely they will tie into how skills modify the input/output factors vs. how much of a given skill exists in the world at the time. It will probably get a little complicated, but such complication will be necessary for balance, and will be presented as simply as possible to the end user.

* This will almost certainly change to model natural energy loss in energy exchange, but I haven't yet figured out what the formula will be, so for now it's x1.

** Meaning input factors can only reach a maximum of x1. If the input factor were x0.5, a skill could modify it to increase towards x1.

On closed and open systems

Another foundation of this process is understanding how systems work. In Flat Galaxy, there are two types of systems: open and closed. The body from the "blocks and boxes" post is an example of a closed system. There are no inputs from outside of the system to inside the system as it has no outside-facing connections. As a result, it is impossible for anything to interact with this system and for the system to interact with anything else. Only the body's component blocks interact with each other, and that's it. Well, that's not very interesting.

To open the system to the world, we must either create a new block with an "external" input (or output) or give one of our existing blocks an "external" input (or output). The system has now gone from closed to open. Much more interesting. Now outside influences can modify the status and behavior of our body system. Of course, the connection into the body will be of a certain type of fuel, but now the possibilities of connections are virtually limitless.

An important note here about "fuel cycle." A fuel cycle is the name I've given to the processing of the effects of input and output. A fuel cycle occurs when fuel leaves or enters a system via an outside-facing input or output. In our closed body system, only one fuel cycle occurs: the initial fuel cycle after the creation of the system*. If the system is still functional after that cycle (i.e. its overall health does not fall below the critical threshold), then it is in a closed equilibrium. Once we open it up, anytime fuel enters the system, we calculate a cycle. This is like the clock cycle in a processor. On the rising clock, we send fuel out of the block into waiting input queues. On the falling clock, we accumulate all existing inputs from input queues into blocks.

There are several important details still to be worked out here, but this is the basic idea.

* This is not a final design decision. I may decide to continually process inputs and outputs in all systems, open or closed and whether or not they have received or lost fuel from an external source.

On blocks

It has come time to lay out an initial description of a block. This will directly correlate to the object code design of blocks.

Each block will have:

• A name
• An ID
• A value that determines whether the block has an inherent initial base score or its initial base score is determined by the definition of the system in which the block is contained
• A score (the source of which is determined by the above)
• A set of inputs
• A (ranked) list of outputs

Each input and output (abstract "put") will have:

• A name
• A fuel type
• An external and/or internal type value
• A modifying factor
• An amount (or capacity or bandwidth)

And each input will have:

• A queue
• An accept/refuse insufficient fuel switch
• A wait/discard fuel switch

Now some explanation of functionality. Each block will receive, via its inputs, a currency or "fuel." This fuel will be of differing types, depending on the type of input, and the amount of fuel received is determined by whatever block is sending the fuel via its corresponding output as well as the associated input factor. The output has no obligation to send the amount of fuel "requested" in the receiving block's input, but if the amount is insufficient, the receiving block's input can choose to refuse to process the incoming fuel entirely, or until enough fuel is present in its queue. When fuel is sent out via a block's outputs, the amount of fuel to send is checked as well as the associated output factor, which modifies the amount value.

Each block simply pools all the fuel it receives from its inputs on each cycle, and then sends fuel out, starting at the top of its output list*. Within the block, fuel types are ignored, but the types of inputs and outputs a block can contain can be determined by its owning system's definition. For example, a body system could disallow any connection to or from a "heart" block which is not of "blood" type fuel.

The goal should be that the total input and output amounts are equal (or in favor of the input), which would mean that the block is at equilibrium. The reason for this is because the overall health of the system the blocks belong to is determined by some function (determined by the system's definition) of all the scores of all the blocks after their outputs have been sent out--midpoint of the fuel cycle. The lower a block's score, the lower the overall health of the system. If the overall health of the system reaches a critical level (determined by its definition), the system is broken or unusable until it is fixed or whatever.

Now, just because a block is at equilibrium does not mean that the entire system is at equilibrium. Care must be taken to ensure that the system is configured in such a way that no block's score quickly reaches zero. This could result in a cascade failure of blocks and thus, the system.

*Update: This is the reverse of what I intend to actually happen (which is: ouput first, then input).

On unbreakable rules

The idea of creating a model of interacting, free-form systems is ambitious. In order to keep it from being too ambitious and in order to introduce a rewarding, meaningful experience, there needs to be some written-in-stone rules that govern the systems I am creating. Here are the first few I have come up with:

1. A block cannot (directly) affect a block it is not (directly) connected to.
2. A block cannot (directly) affect or (directly) connect to itself.
3. Connections are governed by two things: definitions and proximity. Conditions set by both must be met for a connection between blocks to work.
4. System definitions are canon. If a definition of a system is not met, the system is broken and unusable.

On blocks and boxes

At its most basic, Flat Galaxy will consist of blocks with inputs and outputs. These blocks or "affectors," are the most fundamental system in the model. They will be the pieces that larger systems are made up of. To continue the body model from the last post, the affectors in the body will be the major physical systems, as well as the organs. The body itself will not be an affector since you don't affect anything with your "body." You can touch something with your hand, in which case the affector was your muscles which controlled your hand.

The idea is not to make everything an affector--just the things that make sense. In the example above, your brain-block affector would have an output to your musculoskeletal system-block, which would have an output to your arm-block, then hand-block. We could become more fine-grained later and have finger-blocks. The nice thing about the "block" system is that we can create new ones very easily. All we have to do is define its inputs, its outputs and the way in which its inputs and outputs are affected within the block.

Confusing? Another example:

We want a body made up of organs and systems. We have a definition of this body: it must have one heart, one brain, one head, one nervous system. That's it. That's our body. (Let's not discuss where the heart goes.) Once we plug the necessary affector blocks into the body-box we will have a working body. The health of our body is determined by a combination of the health of the blocks within. If all four blocks are perfectly healthy, our body is at its maximum health. Now let's say we want a stronger heart to raise our overall health, so we take out the old heart and find a stronger heart--let's say 2x stronger--laying around our lab somewhere and drop it in, and now our overall health has increased. The difference between the two hearts was that the stronger one contributes more to the overall health of the body.

Our body blocks aren't currently connected to each other (normally, though, certain connections would be required in the body definition), which means each block simply contributes some value to the body's health and that's it. In this type of body, if one block "dies," the body dies because it no longer meets the body's required definition. If we connect our body parts together what happens? We'll connect the brain to the heart and the nervous system, the heart to the brain and the nervous system to the head. Now what? Well, either in the block's definition or the body's definition (haven't decided yet), each block can contribute to the health of anything it has an output connected to, meaning that our overall health can increase with our connections (but so does the potential for failure).

To avoid having to write code to detect cycles or feedback loops, such as where our brain is connected to our heart and our heart to our brain, we only process each block once when a change is detected in any block, and a change in a block resulting from this processing can't trigger another go-round.

Things I haven't decided yet:

1. Body box definition determines A) the value each block gets (and therefore contributes) and/or B) the factor by which each block contributes (e.g., heart contributes 2x its value) to overall health.

or

2. Affector blocks determine A) their own inherent value and/or B) the factor by which they contribute to overall health.

On a model

My interest here is in creating a model of the world. Well, not the world, but a world. I don't have the time, talent or ambition to create a rigorous simulation, and that's not what this will be. I want to make a fine distinction between a true simulation, which attempts to approximate a system by creating and changing as many variables as are necessary (or as are possible) with respect to time, and a model, which attempts to approximate a system by valuing the inputs and outputs of the system's constituent parts.

Let me give an example.

Let's say I wanted to simulate the human heart and its operation. In order to do this, I would create a system which approximated the heart by creating variables and objects based around the physical components and function of the heart. I would have an object based on a carotid artery, and within that object I would have variables which governed its operation, such as its hardness and softness, as well as how blocked it is, and so on. This kind of system is difficult to scale and is extremely error prone.

I want to avoid this as much as possible.

So let's say I want to instead create a simple model of the heart. Instead of creating variables, I create one object: the heart. Instead of worrying about what's going on inside of the heart, I worry about what goes into it and what comes out of it. Blood, yes, but more importantly, what effect it has on the other organs in the body and what effect the other organs have on the heart.

But wait! All I've done is simply increased the scale of my variables and I'm just creating a simulation all over again!

Well, not quite. See, the critical difference is that I'm not trying to simulate anything. I'm just interested in heuristics. I'm concerned with a set of inputs and a set of outputs which give us a sample of true, real-life interaction at a given state. I'm interested in the sum effect of those inputs and outputs on our well-being at some point in time. I don't care that my aorta is blocked, I don't necessarily know that my heart isn't working right, which is causing the other organs to fail, all I know for sure is that the overall effect of this is a decrease in my physical well-being.

In this model, the heart wouldn't be inherently more important than any other organ. The only difference would be what its inputs were (i.e., what other objects can affect its operation) and the fact that its outputs are everywhere in the body, meaning its operation has an effect everywhere in the body.

The beauty of a system like this is twofold. First, it greatly simplifies the amount of "special interaction" design that must be done (because the heart isn't "special"), and it allows us to reconfigure our model anytime we want. We've created a modular body which, in conjunction with other modular systems, lends us all the flexibility we need to define "what" we're made of.

On a Flat Galaxy

I'm Adam. This is my blog about a personal design/code project I am working on. And go.

For a long time I have maintained that two concepts are central to the evolutionary future of interactive entertainment:

1. That other people are the source of our entertainment and
2. That the interactions between basic systems and ecosystems give rise to emergent properties which provide endless possibilities

The first concept has been capitalized on in the MMORPG video game genre to varying degrees over the past twenty years or so. It is important, but not what I'm specifically interested in right now (I will come back to it much later).

I can think of about a dozen instances over the past few years in which I have lamented or commented on the lack of emergent properties in video games. Game designers seem content, if not eager, to define everything for us. They strictly define the boundaries of the world and the ways in which we can interact with that world. They do this ostensibly to protect us from ourselves, because doing it any other way requires insane amounts of testing, debugging and balancing. When half or more of your budget goes towards your graphics alone, precious little time and money are left to dedicate to difficult and "unnecessary" features such as, for example, good AI. The real reason game designers are so eager to define our worlds for us is because that's just The Way Things Are Done.

A few designers have attempted to break from this, to the point where now it is becoming somewhat of a cult trend. Minecraft and Dwarf Fortress are notable examples of attempts to allow players to define their worlds. Dwarf Fortress is, I think, the best current example of a game attempting to allow the interactions of various systems to provide a player with entertainment. Dwarf Fortress, unfortunately, suffers from an obtuse interface, limited scope and difficult, often-opaque gameplay mechanics, a result of the designer rebelling against the status quo just a bit too hard.

After years of wishing and wanting, I have decided to put my money where my mouth is and my skills to use in designing and creating a proof-of-concept model of emergent ecosystems interacting to furnish a user with an inexhaustible set of opportunities for creating his own funny, bitter, sad, happy and epic stories and adventures. In homage to Carl Sagan, I'm calling it "Flat Galaxy."