Friday, November 11, 2016

First Life

Here I'm gonna show you what I've made so far :).

This post contains a lot of long gifs so probably don't read this if you are using data. Most of them are also fairly low quality cause I'm still figuring out screen capturing.

Here is the very first one. Its goal is simply to keep its head up. It tried very hard but didn't have much to work with.



I made a slightly different design with the same goal, and this one did pretty much what was expected




This one later achieved a better score, it gets points for creativity




Next I wanted to give them control over rotation, not just contraction of muscles. With the same goal, this one learned to "shuffle". It had too much control that it could just stay upright even if that wasn't physically possible.



I went back to tweaking my physics engine because some behavior didn't look quite right. I finally got it working reasonably and gave one the goal of getting the highest average y. It is the first one to learn to "hop"



I thought this hopping was pretty cool so I arranged the spheres in a different position to see if they could hop better. Because they often moved around quite a bit while hopping I put it on a small platform so it had to jump fairly straight up. If they fell off the platform before 5 seconds was up they would immediately fail.

This one figured out that as long as you stay in the air long enough you're fine to go off the platform



Since they got pretty good at jumping, I figured I'd give them a more difficult goal: get as far as possible without falling off the platform. This was pretty easy to do, so I made it more difficult:



I was curious how well it would do with this setup, and the answer is surprisingly very well



So that's the current progress. It's pretty fun to set up strange goals for the creatures and see them manage to attain them. Most of these figured out their strategies in 2-5 minutes (from scratch) as well, since my physics engine can run many simulations very quickly, which makes this very fun to use in real time.

So yea, after these promising results I'm excited to see where things go from here :)

How to simulate bones and joints

My custom physics engine had collisions working great with velocities and gravities and such, however I needed a way to give "bones" and "joints" to creatures.

At the moment my creatures are composed of spheres. Here is an example of a "spider":

 

Each line you see is a bone, which you can think of as a rod between those two spheres. I can mark a bone as "usable" by the creature, which allows the creature to vary the length of that rod over time. Otherwise they are a fixed length.

I can also add a "joint" to any sphere, which restricts the ways in which two different bones attached to that sphere interact with each other. The intent here is to model simplified versions of joints that are occurring in real life biology: ball joints, hinge joints, saddle joints, etc.

Now, simulating bones and joints is hard, mostly because if you don't do it right they can explode under harsh conditions. Basically what happens is that if you run your simulation one step, then try and "correct" for where bones want their attached spheres' to be, if they are too far off the correction will be too harsh and the next frame more correction will be needed and this gets worse and worse until eventually your objects are accidentally at infinity. Sometimes it is not that severe, but you can still get "stuttering" if not programmed right which would be nice to avoid.

After about a week of trying various things, I found a simple method that works fairly well for simulating bones, collisions, and any kind of joints that I think is worth sharing here.

First, we need to talk about Vector Projections and Vector rejections. These are very general concepts that make a large amount of physics become very simple.

Graphic is from Wikipedia
In this picture, our two vectors are $a$ and $b$. The projection of $a$ onto $b$ is the part of $a$ that goes along $b$, which in this case is $a_1$. The rejection of $a$ from $b$ is the part of $a$ that is perpendicular to $b$ which is $a_2$.

Luckily, these are very easy to compute in any dimension. The projection is simply:

$$ a \text{ project onto } b = b (a \circ \frac{b}{\vert b \vert}) $$

Where $ \frac{b}{\vert b \vert}$ is simply the normalized vector in the direction of $b$ (with magnitude of 1), and $\circ$ is the dot product.

Because the projection plus the rejection is the original vector, to find the rejection we can simply do:

$$ a \text{ reject from } b = a - (a \text{ project onto } b)$$

To see an application of these, imagine that we have a ball that ran into the floor with a diagonal velocity:



The arrow pointing down is the velocity, the arrow pointing up is the normal. The normal is just a fancy word for the vector that is pointing away from the surface that you hit. One way to think of a normal is that if you accidentally went in the ground, that is the direction that you would have to be pushed in to get back out of the ground.

So if we know our ball is about to hit the ground, we don't want its velocity to keep pushing it into the ground. Instead, we have two choices: bounce, in which case the y component of the velocity is flipped, or don't bounce: in which case the y component of the velocity is removed and the ball rolls to the side.

With a surface that is flat this is easy to do. However lets say you hit a floor that is tilted. How do you find the new velocity?

The answer is very simple: use the vector rejection. Specifically, given a normal $n$ (we assume is normalized) and a velocity $v$, we first compute $n \circ v$. If this value is negative, $v$ isn't even going towards the surface so we can just return $v$. If this value is positive, we can simply return 

$$ v \text{ reject from } n$$

if we don't want to bounce, or

$$ v \text{ reject from } n - v \text{ project to } n$$

if we do want to bounce.

The reason this works is because the vector rejection gives us the component of our velocity that is not along the normal, which is the only part that is left if we don't bounce. If we do bounce, we want to add the negated component of the velocity that is going along the normal (the projection).

So that's pretty great that you have such a clean formula for any collision.

Now we want to simulate a bone. To do this, I first run my physics simulation for one tick assuming the bone doesn't exist, then for every bone (and joint - this technique is very general) I do the following four steps:

*Edit: Turns out this doesn't quite work as intended - it is not energy conserving, and as a result things are able to "fly" by manipulating the added energy. While cool, this isn't what I intended and removes quite a bit of cool behavior cause the strategy is usually "fly to the goal".

Because that didn't work, this is a new method that is working great for simulating bones. I haven't been able to figure out joints yet, but this is a start and you can still do quite a bit with bones.

1. Each bone has a "desired distance". If the bones are close enough to that desired distance apart (I use 0.05 or less), do nothing. Otherwise, if the actual distance between the two spheres connected by the bone is too big, pretend that they hit a surface outside the rod that is pushing them in. If it is too small, pretend that they hit a surface inside the rod that is pushing them out.

















2. Use the non bouncing collision algorithm above with those normals.

3. The non bouncing collision algorithm might have caused some velocity to be lost. Compute the lost velocity of each sphere (simply by taking original velocity - new velocity), then average these lost velocities together. Now each sphere's actual resulting velocity is new velocity + average of lost velocities.

This works great with fixed bone sizes, assuming the spheres start at the desired distance apart. However, we would like the creature to be able to change a few bone's sizes to act as muscles instead of bones. The problem is that 1-3 doesn't add velocity to correct for this changed size. For example, if both spheres are sitting on the ground, they don't have any velocity so the collision algorithm doesn't do anything to pull them together. To fix this, we can do:

4. Use a variable named "prevDistance". Initially this is set to the desired distance. Now, if the desired distance is changed, prevDistance no longer equals the desired distance. If they aren't equal, add a velocity of desired distance - prevDistance to each sphere, pointed towards away from each other (if desired distance - prevDistance is negative this will add a velocity that is pointing towards each other). Now, set prevDistance to the current distance between spheres.

What this does is continue to add velocity until the spheres reach their new desired position. Once that happens they run as normal, using only steps 1-3, because prevDistance is approximately equal to desired distance.

In code (C#) we have:
public static Vector3 VectorProjection(Vector3 a, Vector3 b)
{
    return b*Vector3.Dot(a, b.normalized);
}

public static Vector3 VectorRejection(Vector3 a, Vector3 b)
{
    return a - VectorProjection(a, b);
}

public static Vector3 VectorAfterNormalForce(Vector3 force, Vector3 normal)
{
    Vector3 rejection = VectorRejection(force, normal);
    Vector3 projection = VectorProjection(force, normal);
    float pointingInSameDirection = Vector3.Dot(normal, force);
    // Not pointing in same direction
    if (pointingInSameDirection <= 0.0f)
    {
        return rejection;
    }
    // Pointing in same direction
    else
    {
        return rejection + projection;
    }
}

public static void ApplyBone(Bone bone)
{
    float curDist = Vector3.Distance(bone.me.pos, bone.other.pos);

    if (Math.Abs(bone.desiredDist - curDist) >= 0.05f)
    {
        Vector3 collisionNormal = ((curDist - bone.desiredDist) / Math.Abs(bone.desiredDist - curDist)) * (bone.me.pos - bone.other.pos).normalized;

        Vector3 myNotAlongNormal = VectorAfterNormalForce(bone.me.velocity, -collisionNormal);
        Vector3 otherNotAlongNormal = VectorAfterNormalForce(bone.other.velocity, collisionNormal);

        Vector3 myAlongNormal = bone.me.velocity - myNotAlongNormal;
        Vector3 otherAlongNormal = bone.other.velocity - otherNotAlongNormal;

        Vector3 averageAlongNormal = (myAlongNormal + otherAlongNormal) / 2.0f;

        bone.me.velocity = myNotAlongNormal + averageAlongNormal;
        bone.other.velocity = otherNotAlongNormal + averageAlongNormal;

        Vector3 normalPointingAway = -(bone.other.pos - bone.me.pos).normalized;

        if (bone.prevDistance != bone.desiredDist )
        {
            bone.other.velocity += -normalPointingAway* (bone.desiredDist - bone.prevDistance);
            bone.me.velocity += normalPointingAway* (bone.desiredDist - bone.prevDistance);
        }
        bone.prevDistance = curDist;
    }
}

Sunday, October 30, 2016

Introduction

My end goal is to make full procedural 3D creatures. The (vague) goals I have are:
  • Animation - Creatures move in believable ways. Ideally, given any layout of a creature, this should be able to help it figure out how it can best move, stand, run, etc.
  • Evolution - Various creatures can develop through based on what works best in their given environment. Physical traits such as size, size and position of various limbs, muscle strengths, etc. can develop overtime, and in this way "species" can arise..
  • Communication - Creatures don't exist in isolation: communication of some kind is used to send signals to other creatures to inform them of various things. I would like to have multiple different kinds of creatures living together with shared resources in some equilibrium (such as Predator-Prey dynamics). Simple communication could be mating calls, ownership of territory, being the "alpha", more advanced ones would be ant-like colony behavior or Bee Dancing.
  • Open source: I would like to create open, free tools that allow others to use these creatures in whatever projects they have and expand upon my work here if desired
I don't actually care if they look realistic in the sense of modeling and texturing and such because the behavior is more of what I am interested in.

Where I'm at so far is:

I can simulate the Hill-Type Muscle to impose biological constraints to help creatures learn to move in believable ways, as they did here. This was horribly gross but, assuming my simulation is correct, I think I did it :)

I would like to use Unity because it is a very easy to use program that many people are already familiar with, and so I am not reinventing the wheel. However I also need joints that don't randomly explode like Unity joints, and I need to be able to Simulate 5-10 seconds of movement in a few milliseconds so I can evaluate the performance of creatures quickly.

To do this, in the last week I wrote my own physics engine underneath Unity. It has rigidbodies with velocities and collisions, joints that work extremely reliably, is deterministic so you can run an evaluation and then later replicate the results, and is compatible with typical Unity physics so an actual Unity rigidbody can interact with my custom rigidbodies. It is able to simulate about 100 creatures a second, each of which has been run for 500 "steps" which is equivalent to 5 seconds. I'd like to speed this up but it's not bad for now. I'm then running a Genetic algorithm on some arbitrary metric I pick (say, trying to get the creatures to keep the average position of their head as high as possible to encourage "standing up" or even "jumping") and seeing what creatures run the best. Once I find ones that work well, I can view them in "real time" and simulate a step every frame and still see the exact behavior that it was evaluated on which can be pretty fun.

Right now I'm playing with various basic types of creatures with very basic distance joints (you can think of them as simply spheres with a rod attached between them that contracts or expands based on the creature's internal logic), but I'm going to next look into making more detailed joints with some kinds of limits - eventually using the Hill Type Muscle Model - and potentially creating various different kinds of internal logic.

That's where I'm at :) I'll be making posts as this progresses, and hopefully I'll be able to achieve something that is decently cool.