AI Jumping: Research Project

For my final research project for the class Artificial Intelligence for Games, I decided to look at how an AI would handle jumping, a subsection of steering behaviors. I created a tech demo for explanation purposes, with a video of it later in this post. If you would like to download and run the demo yourself, click here to download a zip folder and run the exe. Space is to toggle the AI.

What Is This Technique

So what is this AI technique? It’s fairly simple. When an AI is moving around a space, they might run into an obstacle where it would be more cost efficient to jump a gap than it is to go around. This can be seen in the below image. If I wanted to get around the gap, it would be much faster to jump. That being said, there are some limitations to jumping.

Unity’s Navigation and Pathfinding Image Example

One of my main references was Artificial Intelligence for Games: Second Edition by Ian Millington and John Funge. In this textbook, they discussed the technique in depth. One of the major downsides to allowing an AI to jump is the minimum required velocity. In general, there is a Jump Point and a Landing Point. For the AI to clear the gap, they would need to reach the required velocity by the time they get to the jump point. If the AI needs to be precise, they also need to approach the jump point at the angle needed to and at the landing point. Below are two figures that are used to help explain this.

This can get even more complicated depending on the physics and other variables that your AI needs to take into account. However, once the AI gets to the jump point, the calculations stop. The AI then flings themselves into the air and waits to land. Now, this doesn’t have to be set in stone of course. Depending on the type of character the AI is, you can add more to the complexity of the technique. A double jump, air control, temporary flight, drag or other forces, all of these can be added to the equation to tailor this to your needs.

Awesomenauts characters can move in many different ways

The Equation

Speaking of the equation, what is it? Well, at its core, it’s a simple trajectory calculation. Think of your AI as a projectile, and itself as the launcher. With that in mind, setting this up becomes very easy.

You already know:

  • The start point
  • The end point
  • Gravity
  • and Jump force

From there, we’re just looking to find the movement velocity needed. To do that, we’re going to first need to find how long it will take us to do this jump. That’s a fairly complex equation, but to quickly sum it up, you need to calculate the jump force against gravity and the distance between the vertical start and end values in order to give you the amount of time you’ll be in the air. After you find that, the movement velocity is simply a factor of the distance over air time.

While I hope that explained it, I’ll also put in the actual equations from the Artificial Intelligence for Games book, pasted as images for formatting.

What I Did

Going back to my tech demo, how does it compare to what the technique establishes? When I started making the demo, I knew I wanted it to be an endless runner where the AI would be jumping from platform the platform, loosely based on CANABALT. While making it I realized that, for my project, parts of the AI jumping technique weren’t needed. I didn’t need any jumping points since I was only moving in one direction. And due to the simple nature of the AI movement (a simple Seek steering), I didn’t need to worry about falling off the edge. So, I removed those parts of the technique to make it better for my purpose. And I think this a major strength of the technique. Due to it’s simplicity, it is very easy to add and remove various components from the calculation.

The AI itself only knows as much as it needs to. It can change its movement speed and jump force, but that’s it. When it figures out that it is in a good place to reach it’s target, it throws itself into the air. In the first half of the video I posted, I can taking manual control of the jump force and move speed. This was to show off the trajectory line and the limits that the AI had. But once Auto turned on, it was fully the computer. There were some issues with the AI jumping as soon as it could, which lead to it stumbling and bunny hopping on the edges, but it still made the jump every time.

Characters With Weird Movement

So let’s take this into a more complex setting. Awesomenauts is a 2D MOBA where characters and move, jump, and shoot. The thing that makes this even harder for an AI to accomplish is the various characters that it needs to control. As Joost Van Dongen of Ronimo Games says in his article, Teaching Awesomenaut’s AI Where to Jump, there are “jumps, double jumps, flying, hovering, hopping and air control. We also have moving platforms and the player can upgrade his jump height. How should an AI know which jumps it can make, how to time the jump, how much air control is needed?”

Nodes placed in a level to inform the behavior tree

The Awesomenaut’s team ended up solving this issue by combining the jumping technique with another AI technique, behavior trees. They filled their levels with nodes, both two way and one way, and then the AI used the information provided by the tree to decide if they should jump or not. It’s a really cool system and worth the read if you’re interested in how jumping can combine easily with other techniques.

Combining With Pathing

Another cool combination of jumping is found in Dot Star Money’s game, Nomera. Chris Brown made a very in depth write up titled Generalized Platformer AI Programming which shows off their implementation of jumping for their AI. Like the Awesomenauts post, it contains some really cool information that I won’t be able to completely summarize, so if this interests you I would suggest reading it yourself.

To put it simply, Nomera uses the level’s collision geometry to calculate areas that are safe to stand on. Next that area is processed and added to a list where the areas are split into sections. The two images below show this off:

gMek452.png
Collision Geometry
MGnhyFZ.png
Sections of walkable area

From there, the AI is able to calculate a path to their target. If they need to go up, the AI then follows the same technique that I implemented in my tech demo. It finds the right spot to jump from and then throws itself into the air. Combined, it all looks like this:

Ynhun7J.gif

Ending Thoughts

Jumping is a very simple technique compared to what some other AI’s can accomplish. However, thanks to it’s ease of use and multi purpose equation, I believe it’s incredibly important. If you are developing a game where the AI moves in real time, you’ll probably consider having the AI jump. This is extremely apparent in combat or puzzle type games where movement and position would be a crucial part of the AI’s purpose. And as seen in Awesomenauts and Nomera, they can be combined with existing systems very easily and in multiple smart ways.