Ubisoft Entertainment: Using Algorithms to Create Riders Republic’s Trail Network

At the Ubisoft Developer Conference 2022, Senior Houdini Artist Igor Kharitonov spoke about creating procedurally generated tracks in Republic of Horsemen. To create the game’s vast network of interconnected trails, the team first used an orientation method to build a route between two points of interest on the landscape. The Pathfinder algorithm is seemingly simple: a designer assigns a point A and a point B on the map, and the algorithm creates the most optimal path possible, while taking into account the limits of the landscape, the curvature constraints of the path -even and obstacle avoidance. . The track generated would, in theory, take players from point A to point B without requiring them to drive straight up a mountain, take an incredibly tight turn, or crash into a tree or down a cliff. However, the trajectories generated were not suited to Riders Republic’s gameplay needs, as the path-finding algorithm made it difficult for the team to add track elements like ramps and bridges that make races difficult. funny bikes, so the team had to look for an alternative solution: genetic algorithms.

In Riders Republic, the genetic algorithm would take the generated trajectories – over hundreds of thousands of options – and sort each one by quality. It then randomly matches two best-performing routes (think of them as the parents), extrapolates the most ideal sections of each path, and then merges the two to create an improved trail (the child). This process would then repeat itself until the development team had a passable and fun course for players to enjoy. We spoke to Igor Kharitonov about the challenges of designing a landscape inspired by real national parks and how the team was able to shape the algorithms to best match the gameplay of Riders Republic.

When designing a racing/extreme sports game like Riders Republic, do you usually design the roads or the landscapes first? How was the process modified using real-world parameters?

Igor Kharitonov: In our approach, we were creating the landscape first, adding iconic trails from the national park to the world. Then the roads and tracks were carved over the existing terrain. The geology itself has been adopted to provide the amount of slope needed, which means that in Riders Republic the slopes are much steeper than in the real world.

However, when designing our race tracks, we realized that not only did they follow the underlying terrain, like regular roads, but they also had certain characteristics – like artificial bumps, for example – which made them more interesting to drive.

How did you determine the start and finish points for each course?

THIS : The global team has done a tremendous amount of work to design the full-scale road and trail network. Some points of interest have been chosen on the map and then linked to each other. Then each connection was processed by a route generator and replaced with real routes/tracks.

What data did you use to determine if a turn was too tight or a slope too steep? How did you calculate the best possible trail for the players?

THIS : Depending on the property, various mathematical equations can be used. To measure the sharpness of the turns, we calculated the curvature of the trajectory at each point and then inverted it to obtain the turn radius. The slope was calculated as a partial derivative over a terrain height field.

Early in development, there was no goal of finding the best possible course for players. We wanted to generate a course that meets the desired requirements, which ultimately results in good gameplay. To obtain these results, we used the genetic algorithm which borrows the notions of evolution from nature and operates on the concepts of population, selection, crossing and mutation. With this algorithm, we could start with trajectories, randomly generated between start and end points, and then evolve and converge towards something meaningful.

How did the genetic algorithm determine the best parts of the parents’ trajectories that should be passed on to the child?

THIS : There was no purpose to extract precisely the best parts of the parent tracks to promote them to the child. That’s not exactly how a genetic algorithm works. Instead, we perform an evaluation of all randomly generated trajectories and assign a corresponding score. The higher the score, the more elements we want a trajectory to contain. Then, this score is used to guide the selection process that defines crossover candidates. The higher the score, the more likely a trajectory is to be selected and crossed with another, so the more likely its parts are to be promoted to the next generation.

You mentioned that the genetic algorithm has been run hundreds of thousands of times. How do you know you’ve finally created the perfect course that will maximize player enjoyment?

THIS : The quality of the result of a genetic algorithm depends on a number of iterations, which can theoretically be infinite (with infinite computation time). Of course, with more and more iterations, the increase in quality begins to saturate and level off. This allows us to limit the number of iterations without sacrificing quality too much. The number of iterations was one of the hyperparameters of the system which was chosen by balancing between performance and quality of the solution.

How does the end result track affect the type of obstacles, such as ramps and bridges, that you can add?

THIS : Additional elements such as ramps and bridges were placed on the track according to certain rules, which required a specific slope, curvature and width of the track. These rules were part of the track description. Of course, it was essential to have track segments with the desired characteristics to be able to place the element. Therefore, it was important to ensure that the general parameters of the track responsible for its shape and the parameters of the artificial elements correspond to each other.

Riders Republic is available on Xbox Series X|S, Xbox One, PS5, PS4, Stadia, Amazon Luna and PC. If you want to know more about Riders Republic, read the exclusive gTV documentary or the recent Prada collaboration.

Sharon D. Cole