Sunday, January 29, 2012

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.

Saturday, January 28, 2012

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.

Thursday, January 26, 2012

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.

Wednesday, January 25, 2012

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.

Tuesday, January 24, 2012

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.


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."