Sunday, April 5, 2015

Getting Stuck in the Wall

Collision detection, if implemented properly, can take care of many collision issues; however, there are some cases where a collision doesn't happen as it should and an object is now stuck on the other side of the wall. This happens sometimes Eye of the Swarm. All levels are enclosed arenas where the borders are defined by an edge collider in Unity. There are cases when a swarm member gets stuck on the other side of the wall. The swarm member doesn't know that its on the other side of the wall and constantly pressing against the wall trying to get back to the player's position. This problem has plagued us for several months putting it on the back-burner thinking of a solution. There is a good solution to this problem, but the way Unity handles it makes the solution difficult to implement.

The arena border in the game is an organic blob that completely surrounds the area. Using linear algebra, there is an algorithm that is used to see if an object is inside an organic blob or outside. Starting from the position of the minion that is believed to be stuck, a ray will be cast from any direction and counts how many times it collides with the shape. If it intersects an even number of times, then it is outside; otherwise, it is inside. This algorithm works for any shaped blob no matter how concave or convex, so long as the shape is enclosed.

There are some problems with this algorithm depending on the direction the ray goes out. Since this can work with concave shapes as well, there is a chance that an intersection will also be a tangent on the intersecting point (floating point imprecision doesn't help as well). There are ways around this such as running the algorithm 3 times with 3 different directions and take the mode of the intersections. This should not be a problem with our game since there aren't that many points that could also act as a tangent. Also if such a tangent is found, then the next time the algorithm is run on the next frame, a different ray will be used and find the true number of intersections. 

There is also another case where this algorithm may run into problems. The arctic level has icebergs in which the swarm should not get trapped in (the iceberg also uses edge collider). Again this shouldn't be problem because if the swarm member is outside the iceberg, then it will add an even number to the total number intersections and won't affect the final calculation for the number of intersections with the border. If the swarm is stuck inside, then it will add an odd number to the total number of intersections and bring the number to an even number showing that it is stuck. 

This algorithm is all fine and good if the ray tracer is good. Unity has a ray caster which shows how many colliders it has gone through. The edge collider that constitutes the border is one collider. It doesn't matter how many times it has gone through the edge collider, it will only show that it went through the collider. The only object that shows how many times it did collide with a collider is Unity's Collision. This throws off the algorithm since it won't know how many collision point there are. We couldn't use this great solution unless we wanted to make our own ray tracer which we just didn't have the time to do, nor should we since that falls on Unity.

There are several other ways to detect if an object is outside the wall. We found a good way that wasn't fool proof, but ensured that no minion would ever get stuck in the wall. This solution is the bounce back algorithm. The swarm bounces off the wall using the collisions normal and reflection code. Using the normal of the collision, we move the swarm a little in that direction, giving them a bounce-back, that is ensured to keep the swarm on one side of the wall. The normal of the collision is always pointed towards the center of the collider so no matter what side of the wall a minion is on, it will still move in the same direction.

This works for the wall collider since the swarm is enclosed in it and the normal is always pointed towards the center of the arena area. This is not the case with icebergs in the arctic level. The center of the iceberg is not where the swarm should back back from. The code is the same, it's just in this context the trajectory of the bounce back will be inverted sending the swarm away from the iceberg. There is one special case with the arctic with a tight corner between an iceberg and the wall where both send the swarm into each other with the bounce back. A not so good fix for this is to artificially set the center of the collider further to its bottom and weighted towards the tight corner so that the normal is pointed away from the wall. This isn't a fix, but more a band-aid; however, it does relieve the problem so that it isn't so noticeable and even though the swarm still goes through the wall and iceberg, no swarm member will ever get stuck.

No comments:

Post a Comment