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.