Efficient Ground Vehicle
Path Following in Game AI

An important component of game AI is driving vehicles along predefined paths in an effective and efficient manner. The task of computing control actions that keep a vehicle along a path while tracking a target speed is referred to as the path following problem. This problem has been extensively explored in robotics and control literature, particularly for applications in unmanned ground and aerial vehicles [1, 2]. In the context of game AI, path following presents particular challenges, including navigation in a wide range of environments, adhering to limited computational requirements, and achieving good performance across a range of vehicles for games that contain a wide selection of vehicle types.

While many of the works from robotics and control literature can be applied to game AI, few papers discuss the various adaptations necessary to make use of these established techniques. Most of the works that consider path following for AI controlled vehicles are for car racing games [3, 4, 5]. Onieva et al. [3] offer a comprehensive overview of their 7-part driving architecture, which utilizes several vehicle sensors to gather information about the vehicle’s position relative to the track. The sensor readings along with a learned module determine the optimal parameter values in the different modules. Another notable related work is the fuzzy logic based self-driving racing car control system by Etlik et al. [4]. The authors use a vision based lane detection system for online lane detection and fuzzy logic for generating position and velocity references. The work by Melder and Tomlinson [5] provide an introduction to Proportional-Integral-Derivative (PID) controllers for game AI, as well as brief descriptions of some of the PID variants.

In this work, we consider the path following problem for controlling ground vehicles in game AI. We propose a general framework which may serve as a benchmark solution offering reasonable path following accuracy and efficiency for a wide range of vehicles and environments. We leverage established, effective, and computationally cheap techniques for speed and steering control and use an analytical result for computing the maximum curvature of a quadratic Bézier curve in a novel algorithm for computing the target speed. The performance of our approach is evaluated by running experiments in a first-person shooter game containing a suite of different vehicles.

We denote vehicle speed along the axis of the vehicle’s forward vector as $v\in\mathbb{R}$. The sign of $v$ denotes the direction of the vehicle’s motion, i.e., $v<0$ indicates the vehicle is going in reverse and vice versa. We assume there are two inputs to the game for changing the vehicle’s motion: steering and throttle for lateral and longitudinal motion, respectively.

The speed controller leverages a Proportional-Integral (PI) controller which regulates vehicle speed via throttle commands using the difference between the target speed and the vehicle’s current speed, referred to as the error signal [6]. The PI controller uses both the proportional and integral terms of the error signal to generate a vehicle command. However, certain strategies must be implemented to mitigate common issues associated with the integral term including integral windup [6]. To generate a steering command, our first step is to compute a target position on the path some lookahead distance in front of the vehicle. From here, we use the geometric steering controller pure pursuit [7] which is based on a steering angle control law that minimizes the cross track error characterized by the target position. This algorithm effectively computes a gain at each time step for a proportional feedback controller using geometric properties of the path tracking problem in the case of a bicycle kinematic model. In case of a stuck event being triggered, which we define as a situation where the vehicle fails to make sufficient progress along the path within a certain time frame, the commands outputted from the speed and steering controllers are overridden by the stuck manager module. For instance, we invert the sign of the throttle input during several frames in the hopes that we recover to a position where the vehicle is no longer stuck. Another potential strategy is to simply teleport the vehicle to a new position. For further strategies, we refer readers to existing works [3].

A commonly used method for computing a target speed is to determine the optimal speed for a vehicle to travel through a turn of a given radius while maintaining tire traction. Often referred as critical speed, the following equation relates a vehicle’s safe turning speed to the balance between centripetal force and maximum lateral force that the tires can handle [8]:

where $a_{\text{lat}}>0$ is a tuning parameter, $g$ is gravitational acceleration, and $\kappa$ is curvature. The parameter $a_{\text{lat}}$ allows us to effectively tune vehicle speed around corners based on the handling of a particular vehicle. As a point of reference, the maximum lateral acceleration found in human normal driving is $0.4g$ [9]. Once a suitable value has been specified for $a_{\text{lat}}$, the problem of computing target speed reduces to finding curvature $\kappa$. In a typical path following setting, this refers to the curvature at a particular point in the path. However, this assumes that curvature information of the path is readily available, e.g. the case of a path described by a function that is twice differentiable. If the path is defined by a list of waypoints, then the approach used here is to use curve-fitting functions to estimate the path curvature, which provides a candidate representation of the path curvature profile.

In our approach, we use a series of quadratic Bézier curves to efficiently capture an estimated curvature profile of the path $P$. The following is the parametric equation $\textbf{B}(t)$ which defines a quadratic Bézier curve with control points $\textbf{p}_{1},\textbf{p}_{2},\textbf{p}_{3}$:

The first and third control points $\textbf{p}_{1},\textbf{p}_{3}$ are the endpoints (at $t=0$ and $t=1$, respectively) while $\textbf{p}_{2}$ generally does not lie on the curve. To compute curvature along the curve, we may use the standard curvature equation $\kappa(t)=\lvert\textbf{B}(t)^{\prime}\times\textbf{B}(t)^{\prime\prime}\rvert\lVert\textbf{B}(t)^{\prime}\rVert^{-3}$, and a sampling strategy to sample curvature of points along the curve. However, a more efficient approach is to leverage the particular geometric constraints of quadratic Bézier curves. Specifically, the maximum curvature can be computed analytically, allowing us to determine an upper bound for the curvature profile without the need for sampling. This is the core motivation for employing quadratic Bézier curves over higher order curves which may provide better estimates of the curvature profile though at a much higher computation cost.

Figure 3(a) shows a sample quadratic Bézier curve and we highlight the two equally sized spheres drawn along the segment $\textbf{p}_{1}\textbf{p}_{3}$ which meet at the midpoint m. The radius of these spheres is equal to half the euclidean distance between the endpoint and the midpoint m, i.e. $r=\frac{1}{2}\lVert\textbf{p}_{1}-\textbf{m}\rVert$. There are two possible cases that characterize the curvature profile of $\textbf{B}(t)$ based on where the control point $\textbf{p}_{2}$ lies in relation to these two spheres. If $\textbf{p}_{2}$ lies outside of the two spheres, i.e. $\lVert\textbf{p}_{2}-\frac{1}{2}(\textbf{p}_{1}+\textbf{m})\rVert>r$ and $\lVert\textbf{p}_{2}-\frac{1}{2}(\textbf{p}_{3}+\textbf{m})\rVert>r$, then from the work by Deddi et al. [10] the maximum curvature of $\textbf{B}(t)$ is given by the expression:

Note, the denominator is the squared area $A$ of the triangle characterized by the three control points. In the second case, $\textbf{p}_{2}$ lies inside one of the two spheres which means the curvature of $\textbf{B}(t)$ is monotone [11]. This implies the maximum curvature occurs at either of the two endpoints $\textbf{B}(0)=\textbf{p}_{1}$, $\textbf{B}(1)=\textbf{p}_{3}$ and therefore maximum curvature is the expression [10]:

With these two results, we can efficiently compute the maximum curvature of an arbitrary quadratic Bézier curve without having to sample points along the curve like in the case of more complex parametric curves.

Algorithm 1 summarizes our approach to computing a target speed $v_{\text{target}}$ given inputs vehicle position r, the path to be followed $P$, and parameters maximum lateral acceleration $a_{\text{lat}}$, waypoint spacing $\Delta h$, waypoint count $N$, and speed limits $v_{\min}$, $v_{\max}$. The first major step involves constructing a new path $\tilde{P}$ by sampling points from the original path $P$ at regular intervals of size $\Delta h$ (Lines 1-4). By capturing the salient features of the original path structure up to a lookahead distance $\Delta h\cdot N$ from the vehicle’s current position r, we are able to determine appropriate target speeds in advance. This is particularly useful in areas where the vehicle needs to slow down, such as sharp corners. The purpose of initializing $\tilde{P}$ with r (Line 1) is made more clear in the steps to follow. In the next step, we iterate through the waypoints of our new path $\tilde{P}$, and calculate the maximum curvature $\kappa_{\max}$ among all the quadratic Bézier curves that can be created from three sequential waypoints in $\tilde{P}$ (Lines 5-9). We use Equation (3) and (4) to compute the maximum curvature of each curve. Since the first Bézier curve is always defined by the vehicle position and two points on the path $P$, we ensure the target speed is decreased whenever the vehicle is too far away from the path. In the final step of our algorithm, we use Equation (1) to compute target speed given $\kappa_{\max}$ and $a_{\text{lat}}$ followed by clamping on $v_{\text{target}}$ given limits $v_{\min}$, $v_{\max}$.

In this section, we describe the experimental setup used for collecting results for validating our proposed path follower. We used a first-person shooter game (Battlefield 2042) as the platform for running experiments and used a machine with an NVIDIA Tesla T4 GPU with a 16-core CPU and 110 GB of RAM. The game contains a wide selection of ground vehicles with varying driving characteristics. We integrated the proposed path follower with the test automation system which deploys AI bots for testing large multiplayer games, referred to as AutoPlayers [12]. To compare our approach, we used as a baseline the original path following logic present in AutoPlayers. Briefly, the path following logic leverages a series of heuristics that fail to generalize well across certain vehicles and environments. For instance, the target speed module computes a target inversely proportional to the largest angle between the vehicle forward vector and a segment on the path in front of the vehicle up until a lookahead distance. Such an approach can lead to noisy target speed outputs when the path is complex or contains sharp turns. In addition, the speed controller employs the simpler P-controller (i.e. no integral term) meaning no history of previous errors is kept to influence the throttle command.

Several metrics were used to assess the performance of the proposed path following solutions. During each frame, we recorded the cross track error, and indicators whether the vehicle is inside the path corridor and whether the vehicle is stuck. We consider the total number of stuck events to be the core metric of interest since its result has the widest set of implications. In the context of bots for testing, we would like to minimize the number of times vehicles get stuck to ensure good quality performance tests and effective soak tests. If vehicles get stuck too often, then the resulting test data may provide a poor representation of real gameplay and may not reflect realistic game scenarios. We note that it is very difficult to completely avoid vehicles getting stuck since the generated paths do not account for the vehicle kinematics and dynamics.

The following parameters were set for the target speed generation module: $a_{\text{lat}}=0.4$, $\Delta h=6\ m$, $N=5$, $v_{\min}=1\ m/s$, $v_{\max}=10\ m/s$. For the parameters that are the same across the two approaches (e.g. min/max target speed), the same values were set to ensure fair comparisons.

In our first set of experiments, we assessed the ability of different vehicles to follow a set of predefined test paths. For each test path, a particular vehicle is spawned at the first waypoint and then commanded to follow the path until the final waypoint. We generated 10 test paths capturing a wide range of challenging environments such as steep hills, narrow corridors, and sharp turns. Further, six different vehicles, each with a distinct set of driving characteristics, were considered for evaluation. These vehicles include Storm, Bolte, Panhard Crab, Zaha, Armata, and Hovercraft. The first three vehicles were deemed easily maneuverable, while the latter three presented greater challenges due to slower turning rate, larger turning radius, poor traction, etc. We performed a total of $60$ tests, $10$ for each one of the $6$ vehicles.

Table I summarizes the performance of three path followers: the baseline, our proposed solution with parameters from Section III, and our proposed solution with per-vehicle-tuned parameters including maximum lateral acceleration parameter $a_{\text{lat}}$ from the target speed generation module. The reported metrics include the number of trials with at least one stuck event, the total number of stuck events as well as a breakdown per vehicle, mean cross track error, percentage of time spent inside the path corridor, total time taken to complete the path, and mean vehicle speed. The first major result is the $70\%$ decrease in the total number of stucks events when comparing our approach to the baseline. In the case of the hovercraft, the addition of the integral term in the speed controller helped resolve the issue of getting stuck while driving up steep hills. We see similar path following improvements across the other vehicles and the smaller range of stuck events suggests our proposed solution generalizes better to different vehicle types. Our approach with fixed parameters maintained similar performance as the baseline for tracking error and inside corridor percentage while driving vehicles at faster speeds. We improve in these two metrics when we use our approach with per-vehicle tuned parameters. With faster average vehicle speeds and a further decrease in number of stuck events, we achieved a $39\%$ decrease in mean total time when comparing with the baseline.

To assess the performance of our proposed method in a more realistic game scenario, we performed soak tests. These tests consisted of 5-minute game sessions in conquest mode and a specific map with 64 AI-controlled bots divided into two teams. A total of 5 randomized trials were ran for both the baseline and proposed path follower. We normalized the number of stuck events by the total number of seconds spent driving a ground vehicle across all 64 players. For the proposed approach, a ground vehicle was stuck on average every $131\text{s}$ ($\sigma=36$) of driving time and every $60\text{s}$ ($\sigma=7$) with the baseline. This means, we were more than twice as likely to get stuck with the baseline path follower compared to our proposed solution.

In this short paper we tackled the path following problem in the context of game AI. Our focus was on developing a simple and efficient framework that achieves reasonable performance across ground vehicles and game environments. Such a framework is particularly beneficial for bots that test games in development or for developing a benchmark solution. The main contribution of this work is the novel target speed generation algorithm which uses quadratic Bézier curves to efficiently estimate the curvature profile of a path. In future work, we plan to expand our framework to include aerial vehicles and to test the performance of our approach with a larger collection of ground vehicle types and game environments. Additionally, we intend to explore the use of automatic tuning methods such as black box optimization which may significantly increase path following performance and eliminate manual parameter tuning.