Game AI Blog Post: Climbing, Dropping and Jumping / by Thomas McGillicuddy

Overview.gif

Overview

For my final in Game AI, I focused on making a AI system that could traverse terrain easily in Unity. I ended up making a unit that can climb, drop and jump a basic obstacle course. The systems makes use of ray casting and a few box colliders to solve getting around obstacles in their way.  Units are destroyed when they cannot continue. 

The system that I created would be ideal for games with many AI characters that need to get around complex level geometry. This could be arena shooters, horde survival games or even as a simple system for a real time strategy game. 

Step 1 of each process is done on each unit every frame it is not preforming or calculating a solution. This mean that two short raycasts are done to check for wall obstacles and the existence of ground every frame.


2017-12-09 20-24-00_1.gif
Step 3, Illustrated in the Left 4 Dead documentation

Step 3, Illustrated in the Left 4 Dead documentation

Climbing

To start off, I made a basic climbing system based off of the Left 4 Dead AI system explained by Micheal Booth (link below). The process outlined in the document has 6 steps, but my system uses 5 because I don't need extra data to set information for an animation.

The entire climbing sequence is done in 5 steps.

Step 1. Approach

The unit sends a short raycast out checking for an obstacle that is directly in front of it. When an obstacle does appear, it triggers the sequence and sets the unit up to calculate the climb.

Step 2. Find Ceiling

Next, the unit sends a raycast out directly above itself. If it hits anything, it records the location of the ceiling as that is the the max height it can look until for a climbing solution.

Step 3. Find Ledge

Then, a series of raycasts are sent out in succession going up the obstacle. This continues until either a raycast doesn't return with a hit or the height limit is reach. The position of the successful raycast is recorded.

Step 4. Find Ledge Height

The previous raycast may not be the best height for the path, as it only takes into account the height of the upward movement interval. Thus, another raycast is done downwards to find the distance to the ledge of the obstacle. Half the height of the unit is then added to give the target location that the unit needs to move to.

Step 5. Preform Climb

With the calculations done and the target height established, the unit begins moving upwards until it reaches the target height. It then moves forward to put it on the actual ledge. From there is reverts back to its original movement vector. 


Dropping

I added a really basic dropping process so that units could get down from the great heights they had climbed to. This isn't based on a preexisting algorithm or process, but allow me to explain it.

The sequence is 3 really simple steps, the first of which is also used for jumping.

Step 1. Ground Check

As the unit moves forward it is raycasting slightly below and in front of it. When the raycast returns no collision, there is no ground in front of it. Another raycast directly downward is preformed to see if there is anything within a variable "safe drop" height.

Step 2. Find Ground

If an object is returned by the second raycast, the unit holds the location and adds half of its height to the Y position to find the proper target location to move to.

Step 3. Preform Drop

Now that the unit has the target it needs to move to, it move forward to match the X position of the drop. It then move downward until it reaches the proper Y position.

Dropping Only.gif

Jumping

This was probably the most complex component to the entire project in terms of math. The jumping process needs to interact with the physics system of Unity to really work correctly as it relies on a rigidbody component on the unit. To calculate the actual force needed to get to a target point, I found a thread where users Iron-Warrior and Zethros proposed a solution to the problem. I also referenced a Unity project made by Iron Warrior related to the topic. It has a cannon that launches cannon balls to target locations in the scene.

The jumping process is broken down into 5 steps, very similar to the climbing sequence.

Diagram drawn by Iron-Warrior in thread explination 

Diagram drawn by Iron-Warrior in thread explination 

Step 1. Ground Check

Just like checking for a safe drop, the unit knows when it needs to jump across a space when it doesn't detect ground in it's path. The difference between the two checks it that when the unit raycasts downward, it chooses to use a jump if it doesn't detect any objects within it's safe drop height.

Step 2. Jump Target Check

The unit uses a horizontal version of the Left 4 Dead check to determine if it can jump to a target in front of it. The max jump distance is determined by a variable that can be change in the code. The unit creates a box collier with a height of it's safe fall height and moves the box forward until an object is hit or the max jump distance is reached. We'll call this box the J-box.

Step 3. Target Correction

If an object is returned, the unit must find the top face of the object and the closest ledge as a jump target. This is done by taking the local scale of the object on it's Y axis and multiplying it by the size of it's box collier on it's Y axis to get the height of the object. The jump target is then X position of the J-box, the height of the object being jumped to, and the Z position of the J-box. A slight offset is added to the X position to take into account the width of the unit.

Step 4. Jump Calculation and Application

Now that the unit has a location to jump to, it's time to apply the force to get there. There's a good bit of math here, so I've added the code snippets to help.

We'll need some more data about the world and how the unit should get there. We need, the scene's gravity, the distance between the two points, the offset between the jump height and the current height, and the angle that the jump should be preformed at. We will also need to quickly calculate the planar positions of the target and the current position.

 
	float gravity = Physics.gravity.magnitude;
        Vector3 planarTarget = new Vector3(jumpTarget.x, 0, jumpTarget.z);
        Vector3 planarPostion = new Vector3(transform.position.x, 0, transform.position.z);
        float distance = Vector3.Distance(planarTarget, planarPostion);
        float yOffset = transform.position.y - jumpTarget.y;
        

The initial velocity is calculated by taking 1 over the cosine of the jump angle times the square root of (half gravity times distance squared) over (the distance times the tangent of the jump angle plus the Y offset)

 
       float initialVelocity = (1 / Mathf.Cos(jumpAngle)) * Mathf.Sqrt((0.5f * gravity * 
       			       Mathf.Pow(distance, 2)) / (distance * Mathf.Tan(jumpAngle) + yOffset));
    

The velocity that needs to be added to the rigidbody is calculated as:

  
Vector3 velocity = new Vector3(0, initialVelocity * Mathf.Sin(jumpAngle), initialVelocity *
     		   Mathf.Cos(jumpAngle));
    
Another great diagram by Iron-Warrior

Another great diagram by Iron-Warrior

The angle between the target location and the current location must be calculated to determine the correct vector to apply the velocity in. Zethos added in a check to make sure the velocity applied could work in a negative X direction.


float angleBetweenObjects = Vector3.Angle(Vector3.forward, planarTarget - planarPostion) * 
        		    (jumpTarget.x > transform.position.x ? 1 : -1);
                                    

The final vector takes into account the new angle between the target location and the current location and multiplies it by the velocity to get the final veclocity.


Vector3 finalVelocity = Quaternion.AngleAxis(angleBetweenObjects, Vector3.up) * velocity;

Finally, after all these calculations are complete, the velocity is applied to the rigidbody component.

Step 5. Landing Check

As the unit is flying through the air, it is doing a very short raycast right beneath it to determine whether it has landed or not. Once a raycast returns a hit, the unit set all the velocities on the rigidbody to zero. The unit can now return to it's original movement knowing it just crossed a fatal gorge sucessfully. 

Footage of Iron-Warrior's unity example in action

Footage of Iron-Warrior's unity example in action