This post is a little different than the others. As you can tell from the title, instead of covering a single week, I'll be talking about two weeks of changes and stuff I've done.
Last week I completed the Octree and improved character movement by adding steps to the walk animation. Right now I'm very happy with how the animation looks and work. I'm sure there are some small improvements I could make, but I'm pretty satisfied with the outcome of this project so far. It does have the issue, however, of the limbs clipping through objects in the environment. That's what I'll be tackling in these two weeks.
Unfortunately for me, this topic isn't easy to research. Everything I have found has the obstacle avoidance be heavily integrated with the IK system and not added on afterwards, so I can't adopt their algorithms without drastically editing my previous work. In other words, I'm on my own for this task, but it'll be an interesting challenge.
As I see it there are a few ways to avoid an obstacle that in the way of the limb's end effector and it's target. I could perform some sort of pathfinding algorithm and have the limb follow that exact path. This is a promising choice because I already have a feature detection mesh showing the locations of obstacles. However this isn't the best choice because its just too expensive to calculate a path each frame. More importantly it would require me to edit the feature detection mesh to get collisions of all surfaces. This isn't worth it. It would add a crazy amount of extra nodes in the environment. In the end this method would potentially work, but would cause more problems than it fixes. Secondly, a greedier algorithm in which the limb reacts to detecting a collision would work. With this idea, the limb tries to reach for its target and when it detects an incoming collision it handles it by moving away and towards the base of the limb. With this method, we are assuming that there's a path towards the base that is unobstructed, which is potentially problematic, but I think it's a fairly safe assumption.
The second option is the one that I'm going to be implementing. Since, this algorithm is reactionary, the first step is to know when a collision is about to occur so that we can avoid it. This is a pretty simple act of ray casting from the end effector towards the target and detecting any collisions up to a certain distance.
Now that we know if we have a collision and that collision data we can start messing with the math to actively avoid the obstacle. My first instinct is to push the end effector away from the collision towards the base and then have it try and approach its target again. This process is repeated until hopefully we get around the obstacle, although that's not always possible. Actually, I need to make a quick sidebar about how we move the end effector. I can't directly change its location because it would ruin the orientation of all the joints, however instead I can set a temporary target for the limb to reach. This way, the limb hits an obstacle, the IK system moves it to its new temporary location and then it resumes its trajectory to its normal target.
Now let's finally talk about the math of where to move the temporary target to avoid the obstacle. The main thought is that I need to move the temporary target away from the impact point and towards the base of the limb. That's a fairly simple operation. By adding the normal of the impact point and the vector pointing from the impact to the base we get the half angle between the two. So we push it out in that direction and BAMM we're done. Just kidding doing this mostly works but I'm noticing some weirdness. So there's the situation of when the half angle we generate is basically the negative of the line from the impact point to the target. When this happens, the limb avoids the wall and then immediately runs into it again at the exact same location. So we're caught in a bad loop. I could try getting different angle of approach. By that I mean instead of getting the half angle, I lean more towards moving to the base, but we get the same issue. Whenever the vector of avoidance is parallel to the vector to the point we end up stalling.
So this is a weird issue. Unfortunately this isn't an issue I can exactly fix, but I think I've come up with a method that lessens the issue. So instead of moving the end effector away based solely on an angle, we instead calculate what a slide would be along the surface that it's stuck on and then offset it away from the surface so that we don't immediately collide with it. The math to do this is pretty cool. So we know the normal of the impact point and the vector to the base from there. If we use the normal we can deduce the plane that represents the surface that we collided with. Then by projecting the vector to the base onto that plane, we have a vector that slides along it going towards the plane. So we scale that normalized vector with the scaled normalized normal vector and we get a very direct path to the base. This doesn't actually solve the issue, but ensures that we're moving in the most meaningful way possible over time.
1 - Limb avoiding an obstacle in its way
2 - Limb getting stuck in a loop because the vector to the target and to the base are parallel
Now that we steer the end effector to avoid collision we need a way to stop the body of the limb from just clipping with obstacles. Seeing as this is going to be attached to a moving monster and the IK can't avoid collisions if it doesn't also control the total movement of the character we can get away with some stuff. For example, to stop the limb from causing collisions while reaching, it's easiest to just stop the IK system to work when it's colliding with an obstacle. So if a middle segment is touching a wall, it and everything down to the base won't move to prevent the limb from going deeper into the wall. However, any joints above it are free to explore and get as close as possible.
3 - Limb stopping it's body from continuing due to collision, but the edges keep going
When implementing this I ran into the simple issue of both system fighting each other. The end effector tries to steer away from obstacles while the whole joint just freezes if a collision is found. My simple solution to just have the segment attached to the end effector check for collisions a little differently. Typically i check along the whole segment, I only do collision checks from the previous node to about 80% of the length of the segment, this allows for some wiggle room and prevents the systems from even occurring at the same time.
4 - Previous walk example
5 - Character walking around with the added collisions avoidance. As you can tell it doesn't really look any different. Note the X shows the ideal resting limb locations for each of the limbs
So it turns out that because the character moves around so much, the collision avoidance sorta doesn't become apparent. It's also not reasonable to avoid collisions when the model moves itself into the wall, so rip. But I guess it's a good sign that thing's don't look weird. So there's that.
As a quick pet project I also wanted to change how the monster works to make it look smoother. The main idea is to decouple the direction of movement with the direction the monster is facing. I feel like it'll look cooler and more robotic by doing it this way and removes some of the awkwardness of the movement when rotating around. To do that I need to edit some of the movement code, since it assumes that the forward input is actually the forward of the model. So I instead need to base the forward input on the forward of the camera alone the horizontal plane. See above for the changes to that too.