How I Taught a Dinosaur to Row a Boat

Go Buddy go! Do what I programmed you to do!

Each project we do presents new challenges. In the case of Dinosaur Train's River Run the new challenge for me was creating an AI for an action/racing game opponent. If you haven't played the game already (which you should, it'll help all of this make more sense), the game has two characters rafting down a river trying to collect bugs that appear along the way. The character that collects the most bugs by the end of the river wins. In two-player both of the these characters are controlled by players, but in single-player the AI handles the extra player. The goal then for my AI was to create a life-like, fun opponent to fill in when a human opponent wasn't available. To do this I broke the problem down into two pieces: river navigation (getting the character from one end of the river to the other) and bug collection (finding and navigating to bugs).

River Navigation

The river in River Run has a few characteristics that played into the river navigation problem. First, the river is not the same every game. The river is composed of pieces that are swapped in and out randomly with each race. This means that a static 'best path' cannot be created for the AI player. The AI must chart its path dynamically.

Second, the river contains solid obstacles that must be traversed around to progress. The AI is expected to be able to reliably navigate around these obstacles and make it down river. Third, the camera dictates the pace at which players can progress down the river, so the rafter AI must maintain a pace that matches that of the camera.

We did not have a discrete solution for each of these problems, rather these problems were overcome by the combination of solutions which I'll outline below.

A couple examples of node placement in river sections.

The first step in creating the AI for navigating the river was to discern a means of expressing the shape of the river so the AI could navigate it. In this case the AI doesn't need to have a complete knowledge of the river since we don't need the AI to be able to navigate to any point in the river, only those points that are necessary to traverse it in a single direction (bottom to top in our case). We chose to represent the river as a series of nodes. These nodes would serve as locations along the river path which the rafter would traverse to. By representing the river as unconnected nodes, we can reorder our level pieces without concern for links between nodes.

The actual traversal AI for the character is relatively simple. Since we want the character to move naturally we restricted its movement method to using paddle strokes like the player. Internally it is 'pressing buttons' just like the player. The AI does a search every few ticks for a target (this scanning process we'll talk about in a second). When the AI finds a target it will begin to paddle straight toward it. To make the AI paddle toward the target it determines where the target is relative to the front of the raft (to the left or right) and paddles on the opposite side. This produces a natural looking motion with the AI alternating paddles to keep its nose pointed at the target when it's target is in front of it or paddling repeatedly on the same side to turn toward a target that is beside or behind it.

The valid nodes are those above the player (the orange line) and in the middle of the screen (between the black lines).

The traversal AI is simple but it is assisted by how the targets are chosen. To find a river node to paddle toward the AI searches the list of river nodes. This search is limited to nodes that have a y-position less than the character's y (meaning they are above it on the map) and nodes that are in the middle of the current game view. With these limitations in place, the search then chooses the closest node as it's new target. If it finds a target better than the current target it replaces it. Otherwise it continues pursuing the current target.

An example of 'most-likely' paths through river sections based on the node locations.

This method of selecting nodes does a few things for us. First, it makes sure the character is only traveling down river since they won't target nodes behind them. This means that our unconnected nodes now behave more like a directed graph with paths weighted based on how close they are to the previous node. Second, by only selecting nodes that are in the center of the screen we ensure that the AI keeps pace with the screen. Finally, because the AI continually pursues a target node even after it reaches it, the traversal AI causes the character to paddle in circles around its target node once it reaches it. This behavior was not intentionally created, but it gives the AI character a pleasant looking idle behavior and gives the player the feeling that the AI is actively searching for bugs.

An example of a level layout we'd avoid. Since the AI always wants to go up a u-shape like this will snare the AI.

Because there is no course correction in the traversal code, the river layout and node layout are both critical for the AI to make it down river. The river layout must be considerate of the abilities of the AI. A key terrain concern was avoiding creating concave terrain that the character can get caught in. Since the AI only attempts to move up, a concave shape that requires the AI to reverse direction to escape would trap the AI.

An example of ill-placed nodes. The left node is closer to the character, but the path to it is blocked by terrain.

Node placement can create similar problems for the AI. Since the AI tries to travel in a straight line between nodes and always chooses the closest valid node, placing nodes so that there is a clear path between close node pairs is necessary. Placing nodes such that the closest node is unreachable could trap the AI.

Bug Catching

Bug catching reuses much of the functionality of the river navigation system with small changes.

An illustration of bug scanning. Bugs inside the white ring are close enough to be considered.

The search for bugs occurs immediately before the search for river nodes. If a chasable bug is found, the AI will give chasing the bug precedence over traversing the river. Finding a chasable bug involves a distance search around the character. The selected bug will be the closest on-screen bug within a given range. If no bugs are found within the range, no bug is selected. When a bug is selected the traversal code used for node navigation is used to navigate the character to the bug. Thankfully this code works well with moving targets too. One change we made was increasing the paddling speed when chasing a bug. This has the benefit of decreasing the turning radius of the character so they are more likely to catch the bug and also gives the impression that the AI character is excited about catching the bug.

As the AI collides with terrain the scan ring shrinks until the problem bug lies outside the ring.

Because, unlike river nodes, bug locations are not static and the search for a chasable bug does not include a check for obstacles between the character and the bug, the situation in which the AI attempts to reach an inaccessible bug is likely. Solving this 'properly' would probably involve implementing a new mechanism for mapping the river and something akin to A*, but, well, we're game developers and sometimes the easy solution is good enough. So, our solution to this problem was to alter the search distance used when finding a 'chasable bug' when a search seems to be going wrong. Each time the character collides with the terrain the bug search distance decreases. If the character repeatedly collides against the terrain, the distance value will eventually shrink to the point that the sought bug will no longer be within chasable range and the AI will 'forget' about it and move on to navigating the river. Once the AI stops colliding with terrain the bug search range slowly grows back to its original size. While this 'bumping into terrain' behavior looks silly when it happens, it happens rarely enough that it isn't distracting and it's a graceful solution to a complex problem.

A Gentle Shove

The final system that assists our AI was actually originally created for human players. When testing the game with human players we found that players wandering off-screen was a significant problem, so we put into place a buffer on the top and bottom of the screen that would push players on-screen. This buffer pushed them vertically toward the center of the screen and horizontally toward the closest river node. This ensures that players pushed off-screen by a piece of terrain will be dislodged by a horizontal push and then pushed vertically back on screen. This ended up working out well for human players and also we discovered offered a fail-safe solution to when the AI got stuck too. While it rarely happens it's nice to have a little insurance in case everything else goes wrong.

Conclusion

This concludes this quick overview of how the rafting AI in River Run works. Hopefully you enjoyed it. If you want to see the AI in action to see the strengths and weaknesses of our solution, you can check it out here. If you have any questions, feel free to leave a comment we'll do our best to answer. Thanks for reading!