Percy's Alife Project

For Percy:I think you're really overreaching for your first alife alg., but I'll give you a couple tips anyway 1. Go with a sparse memory structure. Store coordinates for each particle in memory. Adjacency tests are easy, if you set up properly: Break a hash table of the world into octants, those octants into octants, etc, down to a specified depth. As an example, if your depth is only 1, you'd have 8 hash table entries (one for each octant of the 3d world), and each one would have a list of all elements that are inside it. When an element changes octants, you need to update the lists of course. At depth 2, you'd have 64 hash table entries, for comparison. You'll probably find it optimal to choose a depth where there's around 2-10 elements (depending on how you do your algorithms) per octant. It's roughly an O log N algorithm.2. Realistic temperature and fluid kinematics calculations can be very hard - do you really want to go there?3. If you do, I would recommend modelling them at a far, far lower precision grid than the locations of your "objects" can be at - perhaps 40x40x40. I wouldn't, however, recommend having them be at arbitrary locations, that will make it too complicated.4. If you want this to be a massive simulation, you're going to want to design it for grid computing.I hate to say it, but there is absolutely no simple solution for what you're talking about. Even a 3d Conway's Game of Life, using only 1 bit per cell, and then gzipped at 10x compression, on your million by million by million world, would take 12.5 exobytes of memory. You could never even dream of modelling realistic grid-based kinematics in such a world on a modern computer.I think as you try and think about it more, you'll probably decide on a simpler design. Remember: simpler designs run faster, too! ------------------
"Illuminant light,
illuminate me."

quote:

---

Regarding 2D versus 3D, 2D is just 3D with Z=1. We should be able to design the system so that it works for Z=n, including when n=1. This allows us to debug in the simpler 2D environment and then move to 3D to add greater variability and complexity - or not if we find that 2D is sufficient for our needs.

---

I... wouldn't recommend that. Virtually everything will be a special case for z=1 (actually, typical worlds are either zero-indexed, or indexed over a wide numeric range in both directions. For non-floating point worlds, I prefer zero-indexed, as you can use inherent wraparound of your variables).

quote:

---

An object's type is the sum of its mutational history. For example, if an object's type is "a", then if one of them mutates during fission then the new type would be "a.a". If "a" mutates again during a subsequent fission then the new type would be "a.b". If "a.b" mutates during fission then the new type would be "a.b.a".

---

Are you proposing to have it remember every evolutionary pathway of every object in the already memory-intensive universe? Also, I hope that you're not proposing that you do that through C++ inheritance - if so, you're talking about recompilation of the code in real-time - incredibly, incredibly slow, and not really accomplishing much of a purpose.

quote:

---

This approach permits an efficiency. Since all objects of the same type are identical with respect to algorithms and properties, each object type's algorithms and properties can be represented centrally and therefore never need be represented more than once, not only saving space but reducing the possibility of cache misses and going virtual. Naturally each individual object possesses unique parameters, such as available energy, temperature, mass, etc

---

Just use a hash table.

quote:

---

if (ContainsFood(xLoc+2, yLoc, zLoc)) {
if (Unoccupied(xLoc+1, yLoc, zLoc)) {
MovXPos;
} else if (Unoccupied(xLoc+1, yLoc+1, zLoc)) {
MovXPos; MovYPos;
} else if (Unoccupied(xLoc+1, yLoc-1, zLoc)) {
MovXPos; MovYNeg;
} else if (Unoccupied(xLoc+1, yLoc, zLoc+1)) {
MovXPos; MovZPos;
} else if (Unoccupied(xLoc+1, yLoc, zLoc-1)) {
MovXPos; MovZNeg;
} else if (Unoccupied(xLoc+1, yLoc+1, zLoc+1)) {
MovXPos; MovYPos; MovZPos;
} else if (Unoccupied(xLoc+1, yLoc+1, zLoc-1)) {
MovXPos; MovYPos; MovZNeg;
} else if (Unoccupied(xLoc+1, yLoc-1, zLoc+1)) {
MovXPos; MovYNeg; MovZPos;
} else if (Unoccupied(xLoc+1, yLoc-1, zLoc-1)) {
MovXPos; MovYNet; MovZNeg;
}
}

---

If you do things this way, do you realize how much code you're going to be accumulating, and having to process each cycle? You can't spell things out so flatly - you need fuzziness, such as "direction vector" and "velocity vector". Unless you want some sort of cellular automata, in which case, you're thinking on *far* too high of a level.

quote:

---

This is a big algorithm, and this is only for food two locations away on the X-axis. We need to check for food at all 56 cubes adjacent to the outside of our 3x3x3 cube, so we have to repeat this 55 more times.

---

Do you realize how much CPU you're talking about here? With fast functions calls, the above algorithm may take, say, 20 cpu cycles. That's 1120 cycles just for food detection per organism. What happens when there's nothing in neighboring cells? Because, with the size of the world you proposed, unless you have terabytes worth of ram to use for storing organisms in, virtually always the neighboring cells will be empty. And have you thought about how you would make such an algorithm mutable (important if you want interesting behavior)? Do you recompile (incredibly slow time to create), or is it a virtual machine (a lot of work, and slow processing time)?

quote:

---

foodAdj = 10; // Add 10 to "goodness" of each cube adjacent to food
energyAdj = 20; // Add 20 to "goodness" of each cube adjacent to energy
cellwallAdj = 10; // Add 10 to "goodness" of cubes adjacent to cell wall object

---

Are you proposing arbitrary metadata, or a preset list of possibilities? How many bits are you thinking about for each? Are they dynamically stored, or statically? Your proposal is going to gobble up memory like crazy, so everything you add to every object makes it a lot much more of a memory eater.Why use this grid of cells at all? Unless you're storing your data as a fixed point simulation of floating point arithmetic (in which case, you want to process at a much higher level - dividing the universe into quadrants), what is the purpose? So you can basically make a really slow version of a cellular automata? Complex behavior comes from simple rules, too, you don't need all of this stuff. Why do your actions at the level of components of organisms when your sample functions are organism-level? Are you going to program in physics, so that when one part of an organism moves, the others move with it (so that your cell wall doesn't take off and ditch the rest of your cell), or is each part of each organism going to have to have the same code in it (running many, many times for the identical effect)? What about resistance? Reactions inducing opposite reactions? "Spring" effects versus rigid bodies? Breaking points?Again, I think you're really overreaching for a first attempt here. I would recommend that you start with something easy - a custom cellular automata or simple particle sim or something. If you want a "virtual zoo" type alife sim, I recommend that you have the organisms exist in spatial coordinates, instead of a grid through cells. I would recommend that you not try to model components of cells like this, just model the whole thing. If you want a component sim, don't set the actions that they can take as being things at the cellular level, like "moving". And I would recommend that you have behavior work through a neural net - or even something that just acts like a neural net: Stimulation of some kind of sensor -> Check for activation level of neuron -> if greater than activation level, fire neuron -> neuron stimulates other neurons, either ones that cause activity, other sensory neurons, or neurons that aren't either for senses or action. Repeat. You don't have to have it be able to learn - no backtracing or anything of the sort - you can simply develop them through natural selection. They would effectively be taking the place of the complex chemical interactions that exist in a cell.------------------
"Illuminant light,
illuminate me."

quote:

---

Ok, just real quick, in regards to computing time could we follow SETIs lead, and divide the computing power up between many different computers?

---

No, you can't. SETI processes packets of data - small amounts of data transfer with large computing time in between. Processing a 3d world virtually always requires very large bandwidth for sharing what is going on in the "border regions". Unless you want bandwidth to be a very serious bottleneck, you're going to need a grid computing system with at least gigabit ethernet.As computers get more powerful overall, this problem does decrease - the larger the world you can process and the faster you can go through it, the less the ratio of surface area to volume (and consequently, the ratio of border regions to transfer versus data to computer). However, due to latency, you're never going to be able to process something like this at a reasonable speed over the internet, unless we can get around that pesky speed of light.

quote:

---

Heres an algorithm that is more efficient than an Object checking all 26 spaces around itself. Order all the Objects in the world from smallest to largest in a pointer list according to their X value.

---

Size is not the key. Geography is. You need a geographic hash table. It's not that hard, really. You can get, depending on how you decide to compute, between O N and O log N. What you advocated sounds like a bubble sort, O N^2. You could do 3 merge sorts or qsorts instead, but why?------------------
"Illuminant light,
illuminate me."

quote:

---

quote:

---

I... wouldn't recommend that. Virtually everything will be a special case for z=1 (actually, typical worlds are either zero-indexed, or indexed over a wide numeric range in both directions. For non-floating point worlds, I prefer zero-indexed, as you can use inherent wraparound of your variables).

---

​

Not sure what you mean by zero-indexed in the context of sparse arrays - I'm probably being dense. As described in earlier posts, I'm planning to use a sparse array,

---

My apologies, I don't think I was very clear. You said for z=1. In general, a 3d universe either runs from z=0 to z=some positive value, or from z=some negative value to z=some positive value. If you're storing your coordinates in fixed-point format (instead of floating point format), there are often cases where you can simply let your variables wrap around on their own, saving you precious CPU cycles. But I think this is a bit of a sidetrack - whatever coordinate system you use to store your data in will be fine - the key is that starting a universe in 2d and expanding to 3d often works out harder than starting in 3d to begin with, because in 2d, most things work out to special cases in a 3d world - for an example, you'd never notice Gimbal locking in a 2d world.

quote:

---

Someone mentioned octants - I haven't investigated this yet, but just guessing at what it means the concept seems good.

---

That was me. It's a pretty effective method. In the simplest model, you can picture the world evenly bisected along each axis, thus leaving 8 octants. Each octant is a hash table entry - each has a list of all organisms (or organism components) that are inside of them. If you take a step further, you can subdivide each of those octants into 8 octants, and have each of those store a much smaller list. You can keep doing this until you only have a organisms per octant. You can then compare with everything within a certain number of octants away.

quote:

---

What I'd like to do is represent every unique evolutionary pathway. Oftentimes many objects would have the same pathway, and all such objects would include a pointer to a class holding both the pathway name and the functions and parameters representing that object type. I'm not planning to have any compilation step as part of the simulation.

---

Ok, so you're just going to store it in a string then (i.e., not class inheritance) - that's reasonable, so long as you're going to truncate its length. Picture it this way: evolution occurs on the order of tens of thousands, hundreds of thousands, millions, billions of generations. There's no way you could dream of holding a very long evolutionary pathway string for each organism.

quote:

---

My experience has been that careful design allows you to move more efficient implementations beneath well designed interfaces. I work in an industry whose products tend to have hundreds of thousands of lines of code, and which are used on machines with gigabytes of RAM and terabytes of disk, and which nonetheless oftentimes take a week to run. Adding efficiency and performance to a new feature after initial introduction is something we often do. I share the memory and performance concerns, but would prefer not to let such considerations overly influence the initial specification.

---

And my experience from alife sims is that they tend to gobble up memory I'd just try to make sure that this isn't an afterthought.

quote:

---

It's interesting that simple rules can replicate some things about real life, but that doesn't mean that real life is following anything like the same rules.

---

Please keep in mind that the amout of evolution you will see is relative to the speed that the application runs. Thus, speed is utterly, completely critical to a good sim. So, even if the rules are simpler, if they run faster, you may well see more complex behavior.

quote:

---

I personally don't believe that the immense variety and sheer richness of real life cell behavior emerges from cellular automata.

---

I don't know... even Conway's Game of Life is turing-complete. Conway's biggest problem is that it suffers from a lack of entropy, but that doesn't mean that all cellular automata must.

quote:

---

So by the same token, while I would like to have *a* physics, it wouldn't be *the* physics

---

A perfectly reasonable notion. But I would recomend that "a" physics that you chose include the ability for one part of an organism to drag others with it. By the way, I really don't mean to sound overly critical here. It's always great to see more people work on different ideas for alife and genetic algorithms. I started work on one a week ago based on primitive bases that act roughly like amino acids, to see what we can get to link up, starting with a random arrangement and different kinds of energy input. I'll post it on here when I get it done.------------------
"Illuminant light,
illuminate me."[This message has been edited by Rei, 10-19-2003]