You should include a "QWOP" mode where keys can control different limb/joint movements so you can attempt to walk and hilarity ensues.
I want to keep all control indirect for the actual game, but this is similar to my debug setup tbh!
I feel like there could be something lemmings-like here.
You could decide to add some type of constructions that the dogs need to transverse. It doesn't need to be your goal, but they try to do it, and you can decide on your own if you want to help them or not.
That'll give them something to do instead of standing around looking helpless waiting for you to toss them into the sky again.
I have a lot of thoughts about the actual gameplay, and I promise there'll be more to do than just tossing them around! That said, obstacle courses are something I've been seriously considering as a competition style element.
This is mesmerizing, I need to keep an eye on this fantastic thing you're making
Thank you so much! By the way, I've been seeing stuff from Jack the Reaper for a while now and it looks super good.
Ah god I love this.
Thanks!
If I'm understanding your techniques correctly, when you were originally coming up with a walk cycle, I'm guessing that you basically ran a ton of simulations, combining the most effective animations until you found one that basically met your specifications (based on what I know of evolution algorithms at least. If I'm already way off track, you might as well skip the rest of the question haha). At the same time though, you mention performing a lot of tweaks to the actual AI on top of adding entire new behaviors. The question I'm trying to arrive at here is basically, how much of the animation in this game is directly created by you versus created from evolution algorithms? For all of the new animations like the bucking and the bowing, are you manually creating these animations and then testing, tweaking, testing, tweaking, or are you basically generating a goal ("get this box off my back!") and then running a simulation until you find a behavior that does that? Or, are you doing a mix of both, creating an animation and then simulating small variations upon it until it's perfected?
This question got super convoluted really fast, so in summary, are you creating these animations or is the computer creating these animations? Or is it more complicated then that?
To that end, I'm wondering, have you ever considered naming these placeholder fellows? It's not hugely important but it's just something I've always found fun early on haha
Haha, glad you're into it! I'm not literally building dogs but I've been really liking the idea of just calling them "dogs" for good. There's something about using a familiar name for something unfamiliar that's really appealing to me.
Your questions about the genetics stuff are all great, and it's probably about time I do an info post on it, so here's an explanation that hopefully covers everything you're asking.
Learning to Walk
To start off with, let me just say that not all of my dogs' motions were created with genetics. In fact, as of right now, only their walk cycles are a result of the genetic algorithm. I do plan on using it for some more complex motions in the future, but it's not efficient for me to use for simpler motions like bucking, and this project is complex enough without me artificially making things harder for myself for programmer cred. Ultimately, my use of this genetics stuff is simpler than you might think. Hopefully this post doesn't take away too much of the magic.
Walking was the perfect use case for the genetic algorithm. It's a complex motion with lots of variables, and since my dogs have a limb setup that's not 100% the same as any real animal (it's similar to animals out there but all my proportions and angles are fudged), I don't even have a great reference to look at. Being able to walk requires not only moving forward, but also maintaining balance and keeping relatively straight. Manually setting up a physical walk cycle for a quadruped that works and looks relatively natural is not easy, and physically based movement is an active area of research that I am not at all up to date on or qualified to talk about. Basically, the genetic algorithm seemed like the perfect way for me to come up with a walk cycle because it seemed like it'd do most of the work for me. That didn't end up being exactly true, but I still stand by my use of it.
To start off with, let's talk about what the genetic algorithm is and how it works. Now full disclosure, I knew nothing about this stuff before starting this project, and I learned most of what I know about the algorithm from this webpage:
http://www.ai-junkie.com/ga/intro/gat2.html Anyone should feel free to correct me if I'm spreading misinformation.
As I understand it, the genetic algorithm is just a way of generating and optimizing potential solutions to a problem. Applications of the algorithm can range from ridiculously easy to incredibly complex depending on the problem, but the core ideas are pretty straightforward. In order to use it, there are two main things you need to think about. The first is that you need to be able to encode a potential solution as a series of 1s and 0s. This represents a single "gene" and its how solutions will be generated, mutated, and combined. The second thing is that you need to be able to define a fitness function. You need a way to determine how good any particular solution is.
Once you have that stuff down, the cycle is relatively straightforward:
- 1. A group of genes is selected for trial.
- 2. Trials are run and each gene is scored accordingly.
- 3. Genes "breed" with each other.
- 4. Genes "mutate".
Let's break this down using my walk cycle as an example.
1. Gene selection/generation
I mentioned above that you need to be able to encode a solution. In my case, the question becomes how to derive something like this:
From something like this:
11100000010100101110110101100111110001101111011011101111100100010101011101100000010000100000100011011110110010001101010000011100
All motion in the game is physical, I don't have any actual animations playing anywhere. Every single motion comes from the joint/rigidbody setup, and from torques applied to individual dog body parts.
I currently have a secondary physics animation system in progress, but most of my existing motions, walking included, work off of curves.
Without getting into implementation details, the walk cycle you see above is a series of curves defining the amount of torque to apply to a body part at any given time. Specifically, there are 3 curves for the legs (X, Y, and Z torque curves shared among all legs but evaluated with a time offset for each individual leg), and separate Z torque curves for both the front and back body segments.
The gene you see above decodes to a series of values for each keyframe on each curve, and is the literal current gene I'm using for walking.
Simple enough, but the devil is in the details. I never had any problem getting my dogs to move forward. From the very first test of walking, I was able to squeeze forward locomotion out of the algorithm. Generating natural walk cycles was a little harder.
When given too many variables to play with, the algorithm can take an incredibly long time to come up with anything usable. And given too few constraints, the algorithm has a nasty tendency of coming up with behaviors that, while totally efficient, are also totally goofy.
This is why my final strategy for walking genes involved a shared curve for all the legs, and why the offsets for each leg's evaluation of its curve was manually set. Yes, I could've allowed those offsets to be stumbled upon genetically, but giving the algorithm some constraints made things so much more efficient. In a sense, I'm using the algorithm to turn a frame into a topiary.
That being said, I can assure you that the algorithm is still pulling its weight. This is what generation 0 looks like for walk cycle evolution.
2. Genetic Trials
After constraints are defined and genes can be generated, it's time to run the trials. In my case, this involved spawning identical dog/platform setups, giving each a gene, and telling them all to walk forward. Fitness for walking is based off of distance walked in the time allotted for each round. There are some gotchas here as well.
A fitness function for walking that scores only off of distance traveled is a recipe for disaster. My earliest tests for this mostly all devolved into somersaulting, and I ended up with a few iterations where the dogs who made it the farthest would just recklessly fling themselves forward in a balled tangle of limbs.
As a rule, the genetic algorithm will take any exploit it can find and run with it, so fitness functions for more complex behaviors need to account for these things.
In addition to distance traveled, steadiness was important for a nice walk. Dogs that tip over or smash their faces into the ground immediately cut their scores in half and lose themselves the privilege of increasing their score in the future. Since I added a good deal of constraints to the walking genes, this was all I had to do to achieve good results, but if I had left things wide open, I would've had to be even stricter with how scoring worked.
3. Breeding
After the trials have been run and all the dogs have been scored, it's time to breed. The idea here is that the more "fit" a dog is, the higher chance they have at breeding. You need to generate the same number of genes you started with for the next round of trials, but there's no limit on how many times a dog can breed. My breeding selection is just using weighted randoms for each dog. A gene's score determines its relative chance of being chosen, and other than ensuring that a dog can't breed with itself, there's not too much to it.
When two dogs are chosen to breed, there's a chance of their genetic material combining. A crossover rate is defined (in my case, there's a 70% chance of genes combining during breeding), and if it's determined a crossover should occur, a random gene index is chosen. Everything before that index comes from dogA, and everything after it comes from dogB.
So, let's say you breed two genes:
0000and
1111It's determined that they should combine, so first a random index is chosen between 0 and 3. In this case, index 2 is chosen. That gets us a new gene where indices 0 and 1 come from the first gene and where indices 2 and 3 come from the second:
0011In this way, successful behaviors have a way of mingling and generating new behaviors that might have the best parts of each.
Because of the way this works, it's really important to take it into consideration when figuring out how you'll encode and decode your genes. For example, it's not great to separate dependent values too much. I have a few gene indices that act as negative multipliers, potentially reversing other values. I was careful to make sure all those multiplier indices are encoded directly next to the values they modify so that they generally stick together during breeding. If, for example, all your multipliers were grouped together at the very end of the gene, they would have a way higher chance of all changing at once when breeding occurred, resulting in a bred behavior that didn't actually resemble either of its parents too much.
4. Mutation
The final step is mutation, and it's the simplest of them all. Each new gene has a chance to mutate. This is a chance for completely new behaviors to crop up, even once things have started to even out.
The strategy here is to literally run through each index of each gene and give it a chance to flip itself. In my case, the mutation rate is very low, just 1%. The higher the mutation rate the less stable the results, so it's something to balance.
Final Thoughts
The last thing I have to say about walk cycles is the importance of leg structure and joint setup. I spent roughly 2 fulls weeks of dev time (probably over 100 hours of actual work) trying to get my dogs to walk in a reasonable way. In the end, the most important thing was structure. It sounds obvious, but the single biggest difference in how well my walk cycles came out was determined by the actual physical structure of the dogs themselves.
These are all the major dog iterations I've gone through on this project. Some involve huge overhauls, but most are just changes to leg and joint structure. One has its legs splayed outward, another has very straight front legs, another experiments with moving the legs super close together, one moves them far apart, etc, etc. Each dog in this picture was something I spent at least a full working day playing around with. Not included are the hundreds of tiny changes to joint values and limb rotations/positions not worth making entirely new dogs for. I even experimented with all that stuff coming from the genetic algorithm at one point.
The last piece of the locomotion puzzle for me was to give my dogs joint tension. Again, it seems obvious, but adding joint motors to the legs was what finally got me dogs stable enough to walk for a while without eventually turning into dead fish. Each joint has a motor with its own set of values and strengths attempting to drive the joint back to its default rotation. The motors aren't strong enough to stop movement, obviously, but they keep the limbs stable enough to deal with balance changes.
Anyways, that's it. Really hope this is interesting to someone, and that I explained things well. Happy to answer any additional questions.